У меня есть многоугольник, точнее координаты его вершин, я его как будто накладываю
на клетчатую бумагу, так, что он делиться на клеточки. Поскольку он у меня не ложиться
точь-в-точь по клеточкам, то он будет их пересекать. Я ищу площадь каждой клетки, лежащей,
хотя бы частично, в многоугольнике. Итогом программы должна быть матрица, элементами
которой будут площади каждой клетки. Скажу на всякий случай, все клетки одного размера,
а площадь клетки - это площадь той части клетки, которая находится внутри многоугольника.
#include "pch.h"
#include
#include
#include
#include
#include
#include
using namespace std;
struct flat_vector
{
double x;
double y;
};
double angle(flat_vector xy1, flat_vector xy2) {
return xy1.x * xy2.y - xy2.x*xy1.y;
}
flat_vector max(flat_vector& pxy1, flat_vector& pxy2) {
if (pxy1.x >= pxy2.x && pxy1.y >= pxy2.y) {
return flat_vector{
pxy1.x, pxy1.y
};
}
else if (pxy1.x >= pxy2.x && pxy1.y <= pxy2.y) {
return flat_vector{
pxy1.x,pxy2.y
};
}
else if (pxy1.x <= pxy2.x && pxy1.y <= pxy2.y) {
return flat_vector{
pxy2.x, pxy2.y
};
}
else {
return flat_vector{
pxy2.x, pxy1.y
};
}
}
flat_vector min(flat_vector& pxy1, flat_vector& pxy2) {
if (pxy1.x >= pxy2.x && pxy1.y >= pxy2.y) {
return flat_vector{
pxy2.x, pxy2.y
};
}
else if (pxy1.x >= pxy2.x && pxy1.y <= pxy2.y) {
return flat_vector{
pxy2.x,pxy1.y
};
}
else if (pxy1.x <= pxy2.x && pxy1.y <= pxy2.y) {
return flat_vector{
pxy1.x, pxy1.y
};
}
else {
return flat_vector{
pxy1.x, pxy2.y
};
}
}
flat_vector pere(flat_vector& xyp1, flat_vector& xyp2, flat_vector& pxy1, flat_vector&
pxy2) {
double eps = 0.001;
double z = ((xyp1.x - xyp2.x)*(pxy1.y - pxy2.y) - (xyp1.y - xyp2.y)*(pxy1.x -
pxy2.x));
double q = ((xyp1.x*xyp2.y - xyp1.y * xyp2.x)*(pxy1.x - pxy2.x) - (xyp1.x - xyp2.x)*(pxy1.x*pxy2.y
- pxy1.y * pxy2.x)) / z;
double e = ((xyp1.x*xyp2.y - xyp1.y * xyp2.x)*(pxy1.y - pxy2.y) - (xyp1.y - xyp2.y)*(pxy1.x*pxy2.y
- pxy1.y * pxy2.x)) / z;
if (abs(z) >= eps) {
return flat_vector{
q,
e
};
}
else {
return flat_vector{
NULL,NULL
};
}
}
double are(vector& xyp, vector& pxy) {
//vector xyp{ {0,0},{2,0},{5,1}, {4,4},{2,4} };// координаты многоугольника
double n = xyp.size();
//vector pxy{ {4,0.5},{5,0.5},{5,1.5},{4,1.5} };//координаты клетки
double b = pxy.size();
xyp.push_back(xyp[0]);
pxy.push_back(pxy[0]);
flat_vector nu{ NULL,NULL };
vector xxyy;
vector lxy;
int k = 0;
int m = 0;
for (int i = 0; i < n; i++) {
//cout << "Точки пересечения " << i + 1 << "-й вершины многоугольника с пикселем"
<< endl;
//cout << "----------------------------------------------------------" << endl;
for (int j = 0; j < b; j++) {
xxyy.push_back(pere(xyp[i], xyp[i + 1], pxy[j], pxy[j + 1]));
if (xxyy[k] != nu) {
if (xxyy[k] < max(pxy[j], pxy[j + 1]) && xxyy[k] > min(pxy[j], pxy[j
+ 1])) {
lxy.push_back(xxyy[k]);
//cout << lxy[m] << endl;
m++;
}
}
k++;
}
}
vector xxy;
vector x_y;
double *ug;
int s = 0;
int l = 0;
int full = 0;
ug = new double[n];
for (int j = 0; j < b; j++) { //определяю какие точки клетки лежат в многоугольнике
for (int i = 0; i < n; i++) {
xxy.push_back(pxy[j] - xyp[i]);
x_y.push_back(xyp[i + 1] - pxy[j]);
}
for (int i = 0; i < n; i++) {
ug[i] = angle(xxy[l], x_y[l]);
l++;
if (ug[i] > 0) {
s = 1;
}
}
//cout << "Точка " << pxy[j];
if (s == 0) {
lxy.push_back(pxy[j]);
//cout << " внутри" << endl;
full++;
m++;
}
else
{
//cout << ") снаружи" << endl;
}
s = 0;
}
foo(lxy);
sort(lxy);
//lxy.push_back(lxy[0]);
m = lxy.size();
double *ar;
ar = new double[m];
double area = 0;
for (int i = 0; i < m; i++) {
//cout << lxy[i] << endl;
}
for (int i = 0; i < m - 1; i++) {
ar[i] = angle(lxy[i], lxy[i + 1]);
area += ar[i];
}
area /= 2;
if (full == 4) {//если все 4 вершины пикселя лежат в мн-ке, то площадь клетки
автоматически равна 1
area = 1;
}
else {
area = abs(area);
}
//cout << area << endl;
return area;
}
double Max(double& x, double& y) {
if (x >= y) {
return x;
}
else {
return y;
}
}
double Min(double& x, double& y) {
if (x >= y) {
return y;
}
else {
return x;
}
}
int main()
{
//double x_data[4] = { 3.6,5.4,1.9,0.1 };//координаты многоугольника
//double y_data[4] = { 0.2,1.2,7.3,6.3 };
vector xy_data = { {3.6,0.2},{5.4,1.2},{1.9,7.3},{0.1,6.3} };
//int shear_vector_x=6; //вектор сдвига
//int shear_vector_y=1;
flat_vector shear_vector = { 6,1 };
int num_steps = 20;//количество шагов
flat_vector D_shear_vector = shear_vector / num_steps;
int numel = 4;//количество вершин многоугольника
double x_max = 5.4;//крайние точки
double y_max = 7.3;
double x_min = 0.1;
double y_min = 0.2;
x_max = x_max - x_min;
y_max = y_max - y_min;
double nx = ceil(x_max);//количество столбцов матрицы
double my = ceil(y_max);//количество строк
double nu = 0;//это нужно, чтобы лишний раз Max и Min не переделывать с типами
double pix_matr[6][8];//матрица в которую записывается площадь клетки, принадлежащей
многоугольнику, то бишь от 0 до 1
pix_matr[0][0] = 0;
double area;
double background = 0.01;
double contrast = 0.7;
double target = background * (1 + contrast) / (1 - contrast);
for (int t = 0; t < +num_steps; t++) {
for (int p = 0; p < numel; p++) {
x_max += shear_vector.x; //сдвигаем по х
x_min = floor(x_min);
x_min = Max(nu, x_min);
x_max = ceil(x_max);
nu = nx - 1;
x_max = Min(x_max, nu);
y_max += shear_vector.y;//сдвигаем по у
y_min = floor(y_min);
nu = 0;
y_min = Max(nu, y_min);
for (int iy = 0; iy < my; iy++) {
cout << endl;
for (int jx = 0; jx < nx; jx++) {
// (iy, jx) = координаты ЛЕВОГО НИЖНЕГО угла ЯЧЕЙКИ с
//клеткой, соответствующие индексам массива(iy + 1, jx + 1)
if (y_min <= iy && iy <= y_max && x_min <= jx && jx <= x_max)
{//проверяем, проецируется ли многоугольник на клетку хотя бы частично
double jjx = jx;
double iiy = iy;
vector pxy = { {jjx,iiy},{jjx + 1,iiy}, {jjx
+ 1,iiy + 1}, {jjx,iiy + 1} };
area = are(xy_data, pxy);
pix_matr[iy + 1][jx + 1] = pix_matr[iy + 1][jx + 1] + area
* target + (1 - area)*background;
}
else {
pix_matr[iy + 1][jx + 1] = pix_matr[iy + 1][jx + 1] + background;
}
cout << pix_matr[iy + 1][jx + 1] << " ";
}
}
}
move(xy_data, D_shear_vector);
}
return 0;
}
Я не прошу смотреть весь код полностью, скажу, что ошибка у меня в 362 строке area
= are(xy_data, pxy);
Я совместила 2 кода в один, и функция are, которая ищет площадь, была mainом в другом
коде. Я пока новичок и не придумала ничего умнее. Можно ли так создавать функции и
как поступить?
UPD: Поправила код, теперь выводит матрицу с площадями, только часть из них не верные
#include "pch.h"
#include
#include
#include
#include
#include
using namespace std;
struct flat_vector
{
double x;
double y;
};
....
int main()
{
locale::global(locale(""));
vector xyp{ {0,0},{2,0},{5,1}, {4,4},{2,4} };// координаты многоугольника
int n = xyp.size();
vector pxy{ {0,0},{1,0},{1,1},{0,1} };//координаты пикселя
double b = pxy.size();
xyp.push_back(xyp[0]);
pxy.push_back(pxy[0]);
flat_vector nu{ std::nan(""),std::nan("") };
vector xxyy;
int m = 0;
int s = 0;
int l = 0;
int k = 0;
double are[5][4];
double area;
for (int q = 0; q < 4; q++) {//столбцы
for (int a = 0; a < 5; a++) {//строки
vector lxy;//сюда записываем вершины клетки и точки пересечения
клетки и многоугольника
for (int i = 0; i < n; i++) {//программа поиска точек пересечения, работает
правильно
for (int j = 0; j < b; j++) {
xxyy.push_back(pere(xyp[i], xyp[i + 1], pxy[j], pxy[j + 1]));
if (xxyy[k] != nu) {
if (xxyy[k] < max(pxy[j], pxy[j + 1]) && xxyy[k] > min(pxy[j],
pxy[j + 1])) {
lxy.push_back(xxyy[k]);
//cout << lxy[m] << endl;
//m++;
}
}
k++;
}
}
double *ug;//с помощью данного элемента будем проверять положительность угла
ug = new double[n];
int full = 0; //переменная, если будет равняться 4 (т.е. все вершины
клетки принадлежат мн-ку), то площадь равна 1
l = 0;//счётчик отрезков, которые представлены ниже
//Данные 2 вектора предназначены для того, чтобы проверять углы между
отрезками от точки (вершины клетки) до двух соседних сторон
//Не буду много тут объяснять, потому что циклы ниже работают правильно
vector xxy;//отрезок от
vector x_y;
for (int j = 0; j < b; j++) { //определяю какие точки пикселя лежат в
многоугольнике
for (int i = 0; i < n; i++) {
xxy.push_back(pxy[j] - xyp[i]);
x_y.push_back(xyp[i + 1] - pxy[j]);
}
for (int i = 0; i < n; i++) {
ug[i] = angle(xxy[l], x_y[l]);
l++;
if (ug[i] > 0) {
s = 1;
}
}
//cout << "Точка " << pxy[j];
if (s == 0) {
lxy.push_back(pxy[j]);
//cout << " внутри" << endl;
full++;
}
//else
//{
//cout << ") снаружи" << endl;
//}
s = 0;
}
foo(lxy);//удаляем повторяющиеся координаты
sort(lxy);//выстраиваем оставшиеся координаты последовательно
lxy.push_back(lxy[0]);
m = lxy.size();
double *ar;//вспомогательный массив для нахождения площади
ar = new double[m];
area = 0;
//for (int i = 0; i < m; i++) {
// cout << lxy[i] << endl;//этот цикл производит все точки клетки,
которые принадлежат многоугольнику
//}
for (int i = 0; i < m - 1; i++) {
ar[i] = angle(lxy[i], lxy[i + 1]);
area += ar[i];
}
area /= 2;//площадь
if (full == 4) {//если все 4 вершины пикселя лежат в мн-ке, то площадь
пикселя автоматически равна 1
area = 1;
}
else {
area = abs(area);
}
are[a][q] = area;//записываем площадь всех клеток в матрицу
cout << are[a][q] << " ";
move(pxy, { 1,0 });//сдвигаем, чтобы перейти к следующей клетки справа
}
cout << endl;
move(pxy, { -5,1 });//поскольку ряд проработан, переходим на строчку выше
}
return 0;
}
UPD2: проблема была в этой строке
if (xxyy[k] < max(pxy[j], pxy[j + 1]) && xxyy[k] > min(pxy[j], pxy[j + 1])){
Проверялось лежит ли точка пересечения на стороне клетки, но не проверялось, лежит
ли точка пересечения ещё и на стороне многоугольника. Когда заменяю эту строку на следующую
if (xxyy[k] < max(pxy[j], pxy[j + 1]) && xxyy[k] > min(pxy[j], pxy[j + 1]) &&
xxyy[k] < max(xyp[i], xyp[i + 1]) && xxyy[k] > min(xyp[i], xyp[i + 1])) {
то ошибку "Необработанное исключение по адресу 0x0FC5E906 (ucrtbased.dll) в ConsoleApplication3.exe:
Недопустимый параметр был передан функции, для которой недопустимые параметры вызывают
неустранимую ошибку., произошло" выдаёт почему-то в 246 строке
lxy.push_back(lxy[0]);
До этого тут ошибки не было, просто не все значения были правильно и всё.
http://cpp.sh/65v7n
UPD3: Исправила ошибку, чтобы после последней элемента строки не сдвигалось
было
move(pxy, { 1,0 });
стало
if(a<4){
move(pxy, {1,0});
}else
{
move(pxy, { -4,1 });
cout << endl;
}
Теперь выводит правильно, но только 3 строки из 4, на 4 он останавливается (опять
тут lxy.push_back(lxy[0]);). Есть предположение, что выдаёт ошибку, потому что ни одна
вершина первой клетки 4 строки не лежит в многоугольнике.
http://cpp.sh/6jpul
UPD4:
ошибка вот в чём, когда у нас ни одна точка клетки не принадлежит многоугольнику,
то массив lxy будет пустой, это значит, что я не могу записать первый элемент в конец
lxy.push_back(lxy[0]), поэтому мы должны проверить, не пустой ли массив.
if(lxy.size()>0){
Программа почти завершена.
Ответы
Ответ 1
Вот вам алгоритм подсчёта площадей.
Перебираете все клетки, которые потенциально могут попасть в многоугольник. Для этого
можно, например, описать вокруг него прямоугольник, взяв максимум/минимум абсциссы/ординаты
вершин многоугольника, и все клетки в этом прямоугольнике и перебирать (кстати, такой
прямоугольник называется "описывающий прямоугольник" или "bounding box").
Теперь анализируем каждую клетку. Анализ довольно прост.
Если все 4 вершины клетки лежат в многоульнике - ответ 1.
Если 3 вершины внутри, то из площади клетки (1) нужно вычесть площадь треугольника,
который отрезается многоугольником. Для этого перебором всех рёбер многоугольника находим
их пересечения с границами клетки, находим 2 точки пересечения, и после этого найти
площадь отрезаемого треугольника не составит труда.
Если только 2 вершины внутри, то действуем аналогично пункту 2, также находим 2 точки
пересечения рёбер многоугольника с границами клетки, и отрезаем трапецию (или считаем
площадь оставшейся трапеции).
Если только 1 вершина внутри, то пересечения клетки с многоугольником является треугольником,
аналогично пункту (1) ищется его площадь, которая и даст ответ.
