Как точно рассчитывается центроид многоугольников?

10

Я хотел бы знать, как именно инструменты QGIS Geometry -> многоугольник центроид вычисляют координаты точки. Например, разделяет ли он границу многоугольника на маленькие точки, берет две пары из двух точек (длина и ширина) с максимальным расстоянием и принимает пересечение этих двух линий в качестве центроида?

Хаусладен Карина
источник

Ответы:

13

Если QGIS вычисляет центроид с помощью GEOS, который является портом JTS, то алгоритм выглядит следующим образом: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/algorithm/CentroidArea.html . О теории есть ссылка в javadoc на http://www.faqs.org/faqs/graphics/algorithms-faq/ , см. Раздел 2.02: Как можно вычислить центроид многоугольника?

Центроид (он же центр масс или центр тяжести) многоугольника может быть вычислен как взвешенная сумма центроидов разбиения многоугольника на треугольники. Центроид треугольника - это просто среднее значение его трех вершин, т. Е. Он имеет координаты (x1 + x2 + x3) / 3 и (y1 + y2 + y3) / 3. Это предполагает сначала триангуляцию многоугольника, а затем формирование суммы центроидов каждого треугольника, взвешенной по площади каждого треугольника, всю сумму, нормированную по общей площади многоугольника. Это действительно работает, но есть более простой метод: триангуляция не обязательно должна быть разбиением, а скорее может использовать положительно и отрицательно ориентированные треугольники (с положительными и отрицательными областями), как это используется при вычислении площади многоугольника. Это приводит к очень простому алгоритму для вычисления центроида, основанному на сумме центроидов треугольника, взвешенных с их подписанной областью. Треугольниками можно считать те, которые образованы любой фиксированной точкой, например, вершиной v0 многоугольника и двумя конечными точками последовательных ребер многоугольника: (v1, v2), (v2, v3) и т. Д. Площадь треугольника с вершинами a, b, c - половина этого выражения: (b [X] - a [X]) * (c [Y] - a [Y]) - (c [X] - a [X] ) * (b [Y] - a [Y]);

Code available at ftp://cs.smith.edu/pub/code/centroid.c (3K).
Reference: [Gems IV] pp.3-6; also includes code.

Мне кажется, что метод точный. Если вы хотите проверить, как используются значения координат, возможны ли ошибки округления и т. Д., Вы можете взглянуть на исходный код JTS или GEOS.

user30184
источник
1
Еще несколько ссылок: gdal.org/python/osgeo.ogr.Geometry-class.html#Centroid отмечает, что GDAL использует метод GEOS, описанный в geos.osgeo.org/doxygen/classgeos_1_1algorithm_1_1Centroid.html . QGIS использует функциональность GDAL в фоновом режиме.
AndreJ
2
Метод точен только для очень маленьких полигонов. Для больших вы сталкиваетесь с проблемой, что шар не плоский.
Питер Тейлор,