Площадь неправильной формы
У меня есть множество точек, которые лежат на изображении. Эти множества точек образуют неправильную замкнутую форму. Мне нужно найти область этой формы. Есть ли какое-нибудь тело, которое является нормальным алгоритмом, используемым для расчета площади? Или какая-либо поддержка доступна в библиотеках, таких как boost? Я использую C ++.
7 ответов
Если ваш многоугольник простой (у него нет никаких общих точек, кроме пар последовательных сегментов), тогда вам на помощь придет Википедия:
Формула для площади
(предполагается, что последняя точка такая же, как и первая)
Вы можете легко реализовать это как
float area = 0.0f;
for (int i = 0; i < numVertices - 1; ++i)
area += point[i].x * point[i+1].y - point[i+1].x * point[i].y;
area += point[numVertices-1].x * point[0].y - point[0].x * point[numVertices-1].y;
area = abs(area) / 2.0f;
Конечно, вершины должны быть упорядочены в соответствии с их естественным расположением в многоугольнике ..
Возможно, вы захотите быть более точным, возможно, даже предоставив графический пример.
Например, если у вас есть точки, просто пиксели, то количество пикселей равно площади. Но если точки являются углами многоугольника, то площадь многоугольника определить не так просто. Вы должны использовать триангуляцию многоугольника и просуммировать площади полученных треугольников.
Без скромности отсылаю вас к моему ответу на другой вопрос Комбинированная область перекрывающихся кругов. Монте-Карло надежен, прост в распараллелировке и, в конечном итоге, даст вам ответ на требуемую точность.
Самый простой способ сделать это - триангулировать фигуру и вычислить площадь треугольников. У Дэйва Эберли есть библиотека (лицензия Boost), которая может помочь с триангуляцией; больше информации здесь. Ищите, например, TriangulateEC.
Примечание. Если вы не знаете порядок точек и не можете гарантировать, что ваш многоугольник выпуклый, невозможно определить порядок фигур, поскольку может быть более одного возможного порядка расположения точек. точки, образующие многоугольник. Если вы знаете, что многоугольник выпуклый, определить порядок точек несложно. Просто отсортируйте точки по углу от одной конкретной точки, причем первая точка будет той, которая образует линию между собой и начальной точкой, так что все другие точки находятся на одной стороне от линии. Треугольники, образованные в результате этого процесса, также можно использовать для расчета площади.
В Boost.Geometry есть поддержка вычисления площади полигонов (что еще не принято в ускорение и что очень запутанно в использовании). В противном случае вам придется сначала определить многоугольник, который определяется вашими точками. Судя по всему, все ваши точки являются вершинами многоугольника, так что это просто вопрос правильного упорядочивания наборов точек. Другая возможность состоит в том, что вы ищете выпуклую оболочку вашего набора точек (см. http://en.wikipedia.org/wiki/Convex_hull_algorithms ).