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

Question

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

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

Answer 1

Вот стандартный метод , 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

Answer 2

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

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

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;

Answer 3

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

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

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

Answer 4

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

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

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

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

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

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

Answer 5

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

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

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

Answer 6

Для расчета площади многоугольника

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

Answer 7

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

Answer 8

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

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

Answer 9

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

ДАНО: многоугольник ВСЕГДА может быть составлен из 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 в массиве.

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

Answer 10

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

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