Площадь неправильной формы

Question

У меня есть множество точек, которые лежат на изображении. Эти множества точек образуют неправильную замкнутую форму. Мне нужно найти область этой формы. Есть ли какое-нибудь тело, которое является нормальным алгоритмом, используемым для расчета площади? Или какая-либо поддержка доступна в библиотеках, таких как boost? Я использую C ++.

Answer 1

Если вы многоугольник простой (у него нет общей точки, за исключением пар последовательных сегментов), тогда вам поможет Википедия:

Формула для области:

(предполагается, что последняя точка совпадает с первой)

Вы можете легко реализовать это как

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;

Конечно, вершины должны быть упорядочены в соответствии с их естественным следованием в многоугольнике.

Answer 2

Для этого есть формула суммирования .

Answer 3

Возможно, вы захотите быть более точным, возможно, даже предоставив графический пример.

Например, если у вас есть только пиксели, то количество пикселей равно площади.Но если точки являются углами многоугольника, то площадь многоугольника определить не так просто.Вы должны использовать полигональную триангуляцию и суммировать площади полученных треугольников.

Answer 4

Простейший способ сделать это, вероятно, состоит в том, чтобы триангулировать вашу форму и вычислить площадь треугольников. У Дэйва Эберли есть библиотека (Boost license), которая может помочь с триангуляцией; здесь больше информации здесь . Посмотрите на TriangulateEC, например.

Answer 5

Без скромности я отсылаю вас к моему ответу на другой вопрос Объединенная область перекрывающихся кругов . Монте-Карло является надежным, легко распараллеливающимся и, в конечном итоге, даст вам ответ с требуемой точностью.

Answer 6

В Boost.Geometry есть поддержка для вычисления площади полигонов (которая еще не принята для повышения и которая очень запутана в использовании) В противном случае вам придется сначала определить полигон, который определяется вашими точками. Судя по всему, все ваши точки являются вершинами многоугольника, так что это просто вопрос правильного расположения наборов точек. Другая возможность состоит в том, что вы ищете выпуклую оболочку вашего набора точек (см. http://en.wikipedia.org/wiki/Convex_hull_algorithms).

Answer 7

Примечание. Если вы не знаете порядок точек и не можете гарантировать, что ваш многоугольник выпуклый, определить порядок фигуры невозможно, так как может быть более одного возможного порядка точек, который создаетполигонЕсли вы знаете, что многоугольник является выпуклым, определить порядок точек легко.Просто отсортируйте точки по углу от одной конкретной точки, причем первая точка является той, которая образует линию между собой и начальной точкой, так что все остальные точки находятся на одной стороне линии.Треугольники, образованные этим процессом, также можно использовать для расчета площади.