Как рассчитать площадь 2-го многоугольника?

Question

Предполагая ряд точек в 2-мерном пространстве, которые не пересекаются самостоятельно, каков эффективный метод определения площади результирующего многоугольника?

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

Answer 1

1. Установите базовую точку (наиболее выпуклая точка). Это будет вашей точкой поворота треугольников.
2. Рассчитайте самую левую точку (произвольную), отличную от вашей базовой точки.
3. Рассчитайте 2-ую самую левую точку, чтобы завершить ваш треугольник.
4. Сохраните эту триангулированную область.
5. Сдвиг на одну точку вправо на каждой итерации.
6. Сумма триангулированных областей

Answer 2

Один из способов сделать это - разложить многоугольник на треугольники , вычислить площадь треугольников и взять сумму как площадь многоугольника.

Answer 3

код Python

Как описано здесь: http://www.wikihow.com/Calculate-the-Area-of-a-Polygon

С пандами

import pandas as pd

df = pd.DataFrame({'x': [10, 20, 20, 30, 20, 10, 0], 'y': [-10, -10, -10, 0, 10, 30, 20]})
df = df.append(df.loc[0])

first_product = (df['x'].shift(1) * df['y']).fillna(0).sum()
second_product = (df['y'].shift(1) * df['x']).fillna(0).sum()

(first_product - second_product) / 2
600

Answer 4

Я собираюсь дать несколько простых функций для вычисления площади 2-го многоугольника. Это работает как для выпуклых, так и для вогнутых многоугольников. мы просто делим многоугольник на множество под-треугольников.

//don't forget to include cmath for abs function
struct Point{
  double x;
  double y;
}
// cross_product
double cp(Point a, Point b){ //returns cross product
  return a.x*b.y-a.y*b.x;
}

double area(Point * vertices, int n){  //n is number of sides
  double sum=0.0;
  for(i=0; i<n; i++){
    sum+=cp(vertices[i], vertices[(i+1)%n]); //%n is for last triangle
  }
  return abs(sum)/2.0;
}

Answer 5

C способ сделать это:

float areaForPoly(const int numVerts, const Point *verts)
{
    Point v2;
    float area = 0.0f;

    for (int i = 0; i<numVerts; i++){
        v2 = verts[(i + 1) % numVerts];
        area += verts[i].x*v2.y - verts[i].y*v2.x;
    }

    return area / 2.0f;
}

Answer 6

Я бы хотел просто начать отрезать треугольники. Я не понимаю, как что-то еще могло избежать ужасно волосатых волос.

Возьмите три последовательные точки, которые составляют многоугольник. Убедитесь, что угол меньше 180. Теперь у вас есть новый треугольник, который не составит труда вычислить, удалите среднюю точку из списка точек многоугольника. Повторяйте, пока у вас не останется только три очка.