Jak dokładnie obliczany jest środek ciężkości wielokątów?

10

Chciałbym wiedzieć, jak dokładnie narzędzia QGIS Geometry -> centroid wielokąta obliczają współrzędne punktu. Na przykład, czy dzieli granicę wielokąta na małe punkty, bierze dwie pary dwóch punktów (długość i szerokość) z maksymalną odległością i przyjmuje przecięcie tych dwóch linii jako środek ciężkości?

Hausladen Carina
źródło

Odpowiedzi:

13

Jeśli QGIS oblicza centroid z GEOS, który jest portem JTS, algorytmem jest http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/algorithm/CentroidArea.html . O teorii znajduje się link w javadoc do http://www.faqs.org/faqs/graphics/algorithms-faq/ , patrz sekcja 2.02: Jak można obliczyć centroid wielokąta ?.

Środek ciężkości (inaczej środek ciężkości lub środek ciężkości) wielokąta można obliczyć jako ważoną sumę centroidów podziału wieloboku na trójkąty. Środek ciężkości trójkąta jest po prostu średnią jego trzech wierzchołków, tj. Ma współrzędne (x1 + x2 + x3) / 3 i (y1 + y2 + y3) / 3. Sugeruje to najpierw triangulację wielokąta, a następnie utworzenie sumy centroidów każdego trójkąta, ważonej przez powierzchnię każdego trójkąta, a cała suma znormalizowana przez całkowity obszar wielokąta. To rzeczywiście działa, ale istnieje prostsza metoda: triangulacja nie musi być partycją, ale raczej może wykorzystywać trójkąty dodatnio i ujemnie zorientowane (z dodatnimi i ujemnymi obszarami), jak ma to miejsce przy obliczaniu powierzchni wielokąta. Prowadzi to do bardzo prostego algorytmu obliczania centroidu, opartego na sumie trójkątów centroidów ważonych ich podpisanym obszarem. Trójkąty mogą być te utworzone przez dowolny stały punkt, np. Wierzchołek v0 wielokąta i dwa punkty końcowe kolejnych krawędzi wielokąta: (v1, v2), (v2, v3) itp. Obszar trójkąta z wierzchołkami a, b, c stanowi połowę tego wyrażenia: (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.

Wydaje mi się, że metoda jest dokładna. Jeśli chcesz sprawdzić, w jaki sposób używane są wartości współrzędnych i czy mogą wystąpić błędy zaokrąglania itp., Możesz zajrzeć do kodu źródłowego JTS lub GEOS.

użytkownik30184
źródło
1
Jeszcze tylko kilka linków: gdal.org/python/osgeo.ogr.Geometry-class.html#Centroid zauważa, że ​​GDAL używa metody GEOS opisanej na geos.osgeo.org/doxygen/classgeos_1_1alameterm_1_1Centroid.html . QGIS korzysta z funkcji GDAL w tle.
AndreJ
2
Metoda jest dokładna tylko dla bardzo małych wielokątów. W przypadku dużych masz problem z tym, że kula ziemska nie jest płaska.
Peter Taylor,