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



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

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

290   16  

16 ответов:

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

код 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]])

David Lehavi комментарии: стоит упомянуть, почему этот алгоритм работает: это приложение теорема Грина для функций-y и x; точно в пути a планиметра строительство. Более конкретно:

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

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

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

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 не является четным.

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

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

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;

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

enter image description here

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

enter image description here

если вы выпишете несколько терминов и сгруппируете их в соответствии с общими факторами 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

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

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

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

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

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

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

сумма (перекрестное произведение ((точка 0, точка i), (точка 0, точка i + 1)) для i = 1 - n-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);
}    

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

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

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

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

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

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

дано: многоугольник всегда может состоять из n-2 треугольников, которые не перекрываются (n = количество точек или сторон). 1 треугольник = 3 угольник = 1 треугольник, 1 квадрат = 4 угольник = 2 треугольники; и т. д. до тошноты КЭД

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

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

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

нас интересуют только случаи это падение в первом варианте (полностью содержится).

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

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

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

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

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

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

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

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

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

код

как описано здесь: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

Я собираюсь дать несколько простых функций для вычисления площади 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;
}
    Ничего не найдено.

Добавить ответ:
Отменить.