Как я вычисляю область 2-го полигона?
9 ответов
Вот стандартный метод , 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]])
комментарии David Lehavi: стоит упомянуть, почему этот алгоритм работает: Это - приложение теорема Green за в€ функций ’y и x; точно в пути планиметр работы. Более конкретно:
Формула выше =
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area
Мой наклон состоял бы в том, чтобы просто начать отрезать треугольники. Я не вижу, как что-либо еще могло постараться не быть ужасно волосатым.
Берут три последовательных точки, которые включают полигон. Удостоверьтесь, что угол - меньше чем 180. У Вас теперь есть новый треугольник, который не должен быть никакой проблемой вычислить, удалить срединную точку из списка полигона точек. Повторитесь, пока Вы не будете иметь только три точки в запасе.
- Набор базисная точка (самая выпуклая точка). Это будет Вашей точкой опоры треугольников.
- Вычисляют (произвольную) больше-всего-левую-точку, кроме Вашей базисной точки.
- Вычисляют, 2nd-most-left указывают для завершения треугольника.
- Сохраняют эту триангулированную область.
- Сдвиг по одной точке направо каждое повторение.
- Сумма триангулированные области
Лучше, чем подведение итогов треугольников суммирует трапецоиды в Декартовом пространстве:
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;
}
Или сделайте криволинейный интеграл. Теорема Stokes позволяет Вам выражать интеграл области как криволинейный интеграл. Немного квадратуры Гаусса и Вашего дяди Bob's.
Чтобы подробно остановиться на треугольном и суммировать треугольные области, те работают, если у Вас, оказывается, есть выпуклый полигон, ИЛИ Вы, оказывается, выбираете точку, которая не генерирует строки к любой точке, которые пересекают полигон.
Для общего полигона непересечения, необходимо суммировать векторное произведение векторов (контрольная точка, указать на a), (контрольная точка, укажите на b), где a и b являются "следующими" друг за другом.
Принятие у Вас есть список точек, которые определяют полигон в порядке (порядок, являющийся точками i, и i+1 формируют строку полигона):
Сумма (векторное произведение ((указывают 0, указывают i), (указывают 0, указывают i + 1)), поскольку я = 1 к n - 1.
Берут величину того векторного произведения, и у Вас есть площадь поверхности.
Это обработает вогнутые полигоны, не имея необходимость волноваться о выборе хорошей контрольной точки; любые три точки, которые генерируют треугольник, который не является в полигоне, будут иметь векторное произведение, которое указывает в противоположном направлении любого треугольника, который является в полигоне, таким образом, области суммированы правильно.
Ряд точек без любых других ограничений не обязательно исключительно определяет полигон.
Так, сначала необходимо ли решить что полигон создать из этих точек - возможно, выпуклая оболочка? http://en.wikipedia.org/wiki/Convex_hull
Тогда треугольный и вычисляют область. http://www.mathopenref.com/polygonirregulararea.html
Один способ сделать это был бы к , разлагают полигон на треугольники , вычисляют область треугольников и берут сумму в качестве области полигона.
Векторное произведение является классиком.
Если у Вас есть огромное количество такого вычисления, чтобы сделать, попробуйте следующую оптимизированную версию, которая требует половина меньшего количества умножения:
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 это может иметь значительное значение.
Править: "Область Треугольников и Полигонов, 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;