#cpp
У меня есть многоугольник, точнее координаты его вершин, я его как будто накладываю на клетчатую бумагу, так, что он делиться на клеточки. Поскольку он у меня не ложиться точь-в-точь по клеточкам, то он будет их пересекать. Я ищу площадь каждой клетки, лежащей, хотя бы частично, в многоугольнике. Итогом программы должна быть матрица, элементами которой будут площади каждой клетки. Скажу на всякий случай, все клетки одного размера, а площадь клетки - это площадь той части клетки, которая находится внутри многоугольника. #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) ищется его площадь, которая и даст ответ.
Комментариев нет:
Отправить комментарий