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

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

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

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

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

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

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

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

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

Код Python, заданный многоугольником, представленным в виде списка координат вершин (x, y), неявно переходящий от последней вершины к первой:

def area(p):
    return 0.5 * abs(sum(x0*y1 - x1*y0
                         for ((x0, y0), (x1, y1)) in segments(p)))

def segments(p):
    return zip(p, p[1:] + [p[0]])

Комментарий Дэвида Лехави: Стоит упомянуть, почему этот алгоритм работает: это приложение Теорема Грина для функций -y и x; точно так же, как работает планиметр. Более конкретно:

Формула выше =
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area

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

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

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

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

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

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

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

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

Перекрестное произведение - это классика.

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

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 не четное.

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

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

Обновлено: «Площадь треугольников и многоугольников 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;

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

ДАННЫЙ: многоугольник ВСЕГДА может быть составлен из n-2 треугольников, которые не перекрываются (n = количество точек ИЛИ сторон). 1 треугольник = 3-сторонний многоугольник = 1 треугольник; 1 квадрат = 4-сторонний многоугольник = 2 треугольника; и т. д. до тошноты QED

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

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

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

нас интересуют только случаи, которые относятся к первому варианту (полностью ограничены).

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

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

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

Кроме того, если вы хотите интегрироваться с картографированием и начинаете с геопозиций, вы должны ПЕРВОЕ преобразовать геоточки в точки экрана. это требует решения модели и формулы для формы Земли (хотя мы склонны думать о Земле как о сфере, на самом деле это неправильный яйцевидный (яйцевидный), с вмятинами). есть много моделей, для получения дополнительной информации вики. Важный вопрос заключается в том, будете ли вы рассматривать эту область как плоскость или как кривую. в общем, "небольшие" области, где точки находятся на расстоянии до нескольких километров друг от друга, не будут генерировать значительную ошибку, если рассматривать их как плоские, а не выпуклые.

Чтобы вычислить площадь многоугольника

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

Эта страница показывает, что формула

можно упростить до:

Если вы выпишете несколько терминов и сгруппируете их в соответствии с общими факторами xi, равенство нетрудно увидеть.

Окончательное суммирование более эффективно, поскольку требует умножения только n вместо 2n.

def area(x, y):
    return abs(sum(x[i] * (y[i + 1] - y[i - 1]) for i in xrange(-1, len(x) - 1))) / 2.0

Я узнал об этом упрощении от Джо Кингтона, здесь.

Если у вас есть NumPy, эта версия работает быстрее (для всех массивов, кроме очень маленьких):

def area_np(x, y):        
    x = np.asanyarray(x)
    y = np.asanyarray(y)
    n = len(x)
    shift_up = np.arange(-n+1, 1)
    shift_down = np.arange(-1, n-1)    
    return (x * (y.take(shift_up) - y.take(shift_down))).sum() / 2.0

Реализация Формула шнурков может быть выполнена в 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

Избежание цикла делает эту функцию примерно в 50 раз быстрее, чем 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

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

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

I'm going to give a few simple functions for calculating area of 2d polygon. This works for both convex and concave polygons. we simply divide the polygon into many sub-triangles.

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

Код 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