Comment le centroïde des polygones est-il calculé exactement?

10

Je voudrais savoir exactement comment les outils de géométrie QGIS -> polygone centroïde calculent les coordonnées du point. Par exemple, divise-t-il la frontière du polygone en petits points, prend deux paires de deux points (longueur et largeur) avec une distance maximale et prend le croisement de ces deux lignes comme centre de gravité?

Hausladen Carina
la source

Réponses:

13

Si QGIS calcule le centroïde avec GEOS qui est un port JTS, l'algorithme est celui-ci http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/algorithm/CentroidArea.html . À propos de la théorie, il existe un lien dans le javadoc vers http://www.faqs.org/faqs/graphics/algorithms-faq/ , voir la section 2.02: Comment calculer le centroïde d'un polygone?.

Le centroïde (alias le centre de masse ou centre de gravité) d'un polygone peut être calculé comme la somme pondérée des centroïdes d'une partition du polygone en triangles. Le centre de gravité d'un triangle est simplement la moyenne de ses trois sommets, c'est-à-dire qu'il a les coordonnées (x1 + x2 + x3) / 3 et (y1 + y2 + y3) / 3. Cela suggère d'abord de trianguler le polygone, puis de former une somme des centroïdes de chaque triangle, pondérée par l'aire de chaque triangle, la somme entière normalisée par l'aire totale du polygone. Cela fonctionne en effet, mais il existe une méthode plus simple: la triangulation n'a pas besoin d'être une partition, mais peut plutôt utiliser des triangles orientés positivement et négativement (avec des zones positives et négatives), comme cela est utilisé lors du calcul de l'aire d'un polygone. Cela conduit à un algorithme très simple de calcul du centroïde, basé sur une somme de centroïdes triangulaires pondérés par leur aire signée. Les triangles peuvent être considérés comme étant ceux formés par n'importe quel point fixe, par exemple le sommet v0 du polygone et les deux extrémités de bords consécutifs du polygone: (v1, v2), (v2, v3), etc. d'un triangle avec les sommets a, b, c est la moitié de cette expression: (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.

Il me semble que la méthode est exacte. Si vous souhaitez vérifier comment les valeurs de coordonnées sont utilisées et s'il peut y avoir des erreurs d'arrondi, etc., vous pouvez consulter le code source de JTS ou GEOS.

user30184
la source
1
Juste quelques autres liens: gdal.org/python/osgeo.ogr.Geometry-class.html#Centroid note que GDAL utilise la méthode GEOS décrite sur geos.osgeo.org/doxygen/classgeos_1_1algorithm_1_1Centroid.html . QGIS utilise la fonctionnalité GDAL en arrière-plan.
AndreJ
2
La méthode n'est précise que pour les très petits polygones. Pour les grands, vous rencontrez le problème que le globe n'est pas plat.
Peter Taylor