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

//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;
}

Перекрестный продукт является классическим.

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

area = 0;
for( i = 0; i < N; i += 2 )
   area += x[i+1]*(y[i+2]-y[i]) + y[i+1]*(x[i]-x[i+2]);
area /= 2;

Я использую индекс массива для ясности. Эффективно использовать указатели. Хотя хорошие компиляторы сделают это за вас.

Полигон считается «закрытым», что означает, что вы копируете первую точку как точку с индексом N. Также предполагается, что многоугольник имеет четное число точек. Добавим дополнительную копию первой точки, если N не равно.

Алгоритм получается путем разворачивания и объединения двух последовательных итераций классического алгоритма кросс-произведения.

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

EDIT: «Площадь треугольников и многоугольников 2D и 3D» описывает еще более эффективный метод

// "close" polygon
x[N] = x[0];
x[N+1] = x[1];
y[N] = y[0];
y[N+1] = y[1];

// compute area
area = 0;
for( size_t i = 1; i <= N; ++i )
  area += x[i]*( y[i+1] - y[i-1] );
area /= 2;

Реализация формулы Shoelace может быть выполнена в Numpy. Предполагая эти вершины:

import numpy as np
x = np.arange(0,1,0.001)
y = np.sqrt(1-x**2)

Мы можем определить следующую функцию для поиска области:

def PolyArea(x,y):
    return 0.5*np.abs(np.dot(x,np.roll(y,1))-np.dot(y,np.roll(x,1)))

И получение результатов:

print PolyArea(x,y)
# 0.26353377782163534

Избегать цикла делает эту функцию ~ 50X быстрее, чем PolygonArea:

%timeit PolyArea(x,y)
# 10000 loops, best of 3: 42 µs per loop
%timeit PolygonArea(zip(x,y))
# 100 loops, best of 3: 2.09 ms per loop

Примечание: я написал этот ответ для другого вопроса , я просто упомянул об этом здесь, чтобы иметь полный список решения.

Лучше суммирования треугольников суммирует трапеции в декартовом пространстве:

area = 0;
for (i = 0; i < n; i++) {
  i1 = (i + 1) % n;
  area += (vertex[i].y + vertex[i1].y) * (vertex[i1].x - vertex[i].x) / 2.0;
}

Или сделать контурный интеграл. Теорема Стокса позволяет выразить интеграл области как контурный интеграл. Маленькая квадратура Гаусса и ваш дядя Боб.

Код Python

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

] С pandas

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

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

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;
}

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

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

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

Набор точек без каких-либо других ограничений не обязательно однозначно определяет многоугольник.

Итак, сначала вам нужно решить, какой полигон построить из этих точек - возможно, выпуклый корпус? http://en.wikipedia.org/wiki/Convex_hull

Затем триангулируем и вычисляем область. http://www.mathopenref.com/polygonirregulararea.html

Вычислить область многоугольника

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1# polygon_area

int cross(vct a,vct b,vct c)
{
    vct ab,bc;
    ab=b-a;
    bc=c-b;
    return ab.x*bc.y-ab.y*bc.x;
}    
double area(vct p[],int n)
{ 
    int ar=0;
    for(i=1;i+1<n;i++)
    {
        vct a=p[i]-p[0];
        vct b=p[i+1]-p[0];
        area+=cross(a,b);
    }
    return abs(area/2.0);
}    

Чтобы расширить области триангуляции и суммы треугольников, они работают, если у вас есть выпуклый многоугольник ИЛИ вы случайно выбрали точку, которая не генерирует линии для каждой другой точки, пересекающей многоугольник.

. Для общего непересекающегося многоугольника вам нужно суммировать произведение произведения (опорная точка, точка a) (контрольная точка, точка b), где a и b являются «рядом» друг с другом.

Предполагая, что у вас есть список точек, которые определяют многоугольник в порядке (порядок, когда точки i и i + 1 образуют линию многоугольника):

Сумма (кросс-произведение ((точка 0, точка i), (точка 0, точка i + 1)) для i = 1 до n - 1.

Возьмите величину этого поперечного произведения и у вас есть площадь поверхности.

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

независимое от языка решение:

GIVEN: многоугольник может ВСЕГДА состоять из n-2 треугольников, которые не перекрываются (n = количество точек OR сторон). 1 треугольник = трехгранный многоугольник = 1 треугольник; 1 квадрат = 4-сторонний многоугольник = 2 треугольника; и т. д. ad nauseam QED

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

, если вы возьмете любые 3 последовательные точки в пути многоугольников и создаете треугольник с этими точками, вы будете имеют один и только один из трех возможных сценариев:

1. полученный треугольник полностью находится внутри исходного многоугольника
2. , в результате треугольник полностью выходит за пределы оригинального многоугольника
3. , что приводит к треугольнику частично содержится в исходном многоугольнике

, нас интересуют только случаи, которые попадают в первый вариант (полностью содержащийся).

каждый раз, когда мы находим один из них, мы прерываем его, вычисляем его площадь (легко peasy, не будем объяснять формулу здесь) и создаем новый многоугольник с одной меньшей стороной (эквивалентный полигону с этим треугольником, отрубленным ). пока мы не оставим только один треугольник.

как реализовать это программно:

создать массив (последовательных) точек, которые представляют путь ВОКРУГ многоугольника. начните в точке 0. запустите массив, создавая треугольники (по одному за раз) из точек x, x + 1 и x + 2. преобразуйте каждый треугольник из формы в область и пересечь его с областью, созданной из многоугольника. Если полученное пересечение идентично исходному треугольнику, то указанный треугольник полностью содержится в многоугольнике и может быть отрублен. удалите x + 1 из массива и начните снова с x = 0. в противном случае (если треугольник находится вне [частично или полностью] многоугольника), переходите к следующей точке x + 1 в массиве.

дополнительно, если вы хотите интегрироваться с отображением и начинать с геоинтеграции, вы должны преобразовать из геоинформации на экранные точки FIRST. это требует решения моделирования и формулы для формы земли (хотя мы склонны думать о Земле как о шаре, это на самом деле нерегулярная яйцевидная (яйцо) с вмятинами). существует много моделей, для получения дополнительной информации wiki. важная проблема заключается в том, считаете ли вы район плоской или изогнутой. в общем, «маленькие» области, где точки до нескольких километров друг от друга, не будут вызывать значительную ошибку, если рассматривать плоские и не выпуклые.