Existe-t-il des versions numériquement stables de l'algorithme de recherche du centroïde pour les polygones?

Question

Dire que j'ai un polygone 2-D presque dégénéré tels que:

[[40.802,9.289],[40.875,9.394],[40.910000000000004,9.445],[40.911,9.446],[40.802,9.289]]

Pour référence, cela ressemble:

Si j'utilise l'algorithme standard de barycentre comme indiqué on Wikipedia, par exemple ce code python:

pts = [[40.802,9.289],[40.875,9.394],[40.910000000000004,9.445], [40.911,9.446],[40.802,9.289]] 
a = 0.0 
c = [0.0, 0.0] 
for i in range(0,4): 
    k = pts[i][0] * pts[i + 1][1] - pts[i + 1][0] * pts[i][1] 
    a += k 
    c = [c[0] + k * (pts[i][0] + pts[i + 1][0]), c[1] + k * (pts[i][1] + pts[i + 1][1])] 
c = [c[0]/(3 * a), c[1]/(3 * a)] 

Je reçois c = [-10133071.666666666, -14636692.583333334]. Dans d'autres cas où a == 0.0 je pourrais également obtenir une division par zéro. Ce que j'aimerais idéalement, c'est que dans le pire des cas, le centroïde soit égal à l'un des sommets ou quelque part dans le polygone, et qu'aucune tolérance arbitraire ne soit utilisée pour éviter cette situation. Y a-t-il une manière intelligente de réécrire l'équation pour la rendre plus stable numériquement?

Answer 1

Lorsque la zone est nulle (ou très proche de zéro, si vous ne pouvez pas vous permettre de faire l'arithmétique exacte), la meilleure option est probablement de prendre le centroïde de périmètre de l'ensemble des points.

Le centroïde de périmètre est donné par le rapport entre la somme pondérée des points médians de chaque côté du polygone (le poids est la longueur du côté correspondant) et le périmètre du polygone. En utilisant l'arithmétique exacte, il est possible de calculer le centroïde dans ce cas. point rouge est le barycentre du périmètre et le vert est le vrai barycentre

je sage pour calculer le centre de gravité exactement https://cloud.sagemath.com/projects/f3149cab-2b4b-494a-b795-06d62ae133dd/files/2016-08-17-102024.sagews.

Les gens ont cherché un moyen de relier ces points les uns par rapport aux autres - https://math.stackexchange.com/questions/1173903/centroids-of-a-polygon.

Answer 2

Je ne pense pas que cette formule peut être facilement rendue plus stable vers des polygones 2D presque dégénérés. Le problème est que le calcul de la surface (A) repose sur la soustraction des formes trapézoïdales (voir Paul Bourke). Pour les très petites zones, vous tombez inévitablement sur la précision numérique.

Je vois deux solutions possibles:

1.) Vous pouvez vérifier la zone et si elle passe en dessous d'un seuil est le polygone assumeront dégénérés et prendre juste la moyenne de x minimale et maximale et les valeurs y (le milieu de la ligne)

2.). Utilisez arithmétique à virgule flottante avec une plus grande précision, peut-être quelque chose comme mpmath.

Btw. vous avez une erreur dans votre code. Il devrait être:

c = [c[0] + k * (pts[i][0] + pts[i + 1][0]), c[1] + k * (pts[i][1] + pts[i + 1][1])] 

Cependant cela ne fait pas de différence.