геометрия — Как найти площадь сложного многоугольника
Для несложных полигонов это довольно просто:
A = 1/2 * (x1*y2 - x2*y1 + x2*y3 - x3*y2 + ... + x(n-1)*yn - xn*y(n-1) + xn*y1 - x1*yn)
Вот моя реализация в C ++:
struct Point {
double x, y;
} point[210];
double area(int n) {
double a=0, b=0;
for(int i=0; i<n-1; ++i) {
a += point[i].x * point[i+1].y;
b += point[i].y * point[i+1].x;
}
return (a - b)/2;
}
Но что, если многоугольник сложный? Есть ли подобный способ найти его область?
Замечания: Я пытался использовать ту же технику, но она не работала. Для многоугольника
(0,0) , (0,7) , (4,3) , (0,3) , (2,4) , (2,1) , (0, 0)
формула выше дает мне 28.000, что должно быть 26.000. Единственное объяснение, которое я мог дать, состояло в том, что треугольник (0,3), (2,4), (2,3) отсчитывается дважды (точка (2,3) — это пересечение отрезков (0,3), (4,3) и (2,4), (2,1)).
Решение
В соответствии с эта ссылка формула, которую вы проиллюстрировали, для выпуклых многоугольников, но пример, который вы даете не кажется один.
постскриптум Вместо двумерного массива рассмотрите использование ниже для лучшей читаемости.
struct Point{
double x,y;
};
Point point[210];
...
a += point[i].x * point[i+1].y;
Другие решения
Эта формула работает для просто полигоны (те, кто не самопересекающийся), выпуклый или нет. Обратите внимание, что он вычисляет подписанный Площадь многоугольника. Если (простой) многоугольник по часовой стрелке, площадь, вычисленная по этой формуле, будет отрицательной.
Для непростого многоугольника формула вычисляет сумму подписанной площади всех простых компонентов многоугольника. Ваш примерный компонент имеет самопересечения, и один из его компонентов, треугольник, вносит двойной вклад в площадь.