Suite

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

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


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


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. A propos de la théorie, il y a un lien dans la javadoc vers http://www.faqs.org/faqs/graphics/algorithms-faq/, voir la section 2.02 : Comment peut-on 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 pour 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 aires 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ée par leur aire signée. Les triangles peuvent être considérés comme ceux formés par n'importe quel point fixe, par exemple, le sommet v0 du polygone, et les deux extrémités des arêtes consécutives du polygone : (v1,v2), (v2,v3), etc. d'un triangle de 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 disponible sur ftp://cs.smith.edu/pub/code/centroid.c (3K). Référence : [Gems IV] pp.3-6 ; comprend également le 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.


Voir la vidéo: Polygones réguliers