Comment calculer la surface d'un polygone à deux dimensions ?

Question

Si l'on suppose une série de points dans l'espace 2D qui ne se coupent pas eux-mêmes, quelle est une méthode efficace pour déterminer la surface du polygone résultant ?

À titre d'information, il ne s'agit pas d'un devoir et je ne cherche pas de code. Je cherche une description que je peux utiliser pour mettre en œuvre ma propre méthode. J'ai mon idée sur l'extraction d'une séquence de triangles à partir de la liste de points, mais je sais qu'il y a un tas de cas limites concernant les polygones convexes et concaves que je n'arriverai probablement pas à saisir.

Answer 1

Voici la méthode standard AFAIK. En gros, il faut additionner les produits croisés autour de chaque sommet. Beaucoup plus simple que la triangulation.

Code Python, étant donné un polygone représenté comme une liste de coordonnées de sommet (x,y), enveloppant implicitement du dernier sommet au premier :

def area(p):
    return 0.5 * abs(sum(x0*y1 - x1*y0
                         for ((x0, y0), (x1, y1)) in segments(p)))

def segments(p):
    return zip(p, p[1:] + [p[0]])

David Lehavi commente : Il convient de préciser pourquoi cet algorithme fonctionne : C'est une application de Le théorème de Green pour les fonctions -y et x ; exactement de la manière dont fonctionne un planimètre. Plus précisément :

Formule ci-dessus =
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area

Answer 2

Le produit croisé est un classique.

Si vous avez des millions de calculs de ce type à faire, essayez la version optimisée suivante qui nécessite moitié moins de multiplications :

area = 0;
for( i = 0; i < N; i += 2 )
   area += x[i+1]*(y[i+2]-y[i]) + y[i+1]*(x[i]-x[i+2]);
area /= 2;

J'utilise l'indice de tableau pour plus de clarté. Il est plus efficace d'utiliser des pointeurs. Bien que les bons compilateurs le fassent pour vous.

On suppose que le polygone est "fermé", ce qui signifie que vous copiez le premier point comme point avec l'indice N. On suppose également que le polygone a un nombre pair de points. Ajoutez une copie supplémentaire du premier point si N n'est pas pair.

L'algorithme est obtenu en déroulant et en combinant deux itérations successives de l'algorithme classique du produit en croix.

Je ne suis pas sûr de la comparaison entre les deux algorithmes en ce qui concerne la précision numérique. Mon impression est que l'algorithme ci-dessus est meilleur que l'algorithme classique car la multiplication tend à restaurer la perte de précision de la soustraction. Lorsque l'on est contraint d'utiliser des flottants, comme dans le cas du GPU, cela peut faire une différence significative.

EDIT : "Aire des triangles et polygones 2D & 3D" décrit une méthode encore plus efficace

// "close" polygon
x[N] = x[0];
x[N+1] = x[1];
y[N] = y[0];
y[N+1] = y[1];

// compute area
area = 0;
for( size_t i = 1; i <= N; ++i )
  area += x[i]*( y[i+1] - y[i-1] );
area /= 2;

Answer 3

Cette page montre que la formule

peut être simplifié à :

Si vous écrivez quelques termes et les regroupez selon les facteurs communs de xi l'égalité n'est pas difficile à voir.

La sommation finale est plus efficace puisqu'elle ne requiert que n multiplications au lieu de 2n .

def area(x, y):
    return abs(sum(x[i] * (y[i + 1] - y[i - 1]) for i in xrange(-1, len(x) - 1))) / 2.0

J'ai appris cette simplification auprès de Joe Kington, ici .

---

Si vous avez NumPy, cette version est plus rapide (pour tous les tableaux sauf les très petits) :

def area_np(x, y):        
    x = np.asanyarray(x)
    y = np.asanyarray(y)
    n = len(x)
    shift_up = np.arange(-n+1, 1)
    shift_down = np.arange(-1, n-1)    
    return (x * (y.take(shift_up) - y.take(shift_down))).sum() / 2.0

Answer 4

Étape 1 = trianguler le polygone.

Étape 2 = trouver l'aire de chaque triangle.

Étape 3 = additionnez les surfaces de l'étape 2.

L'étape 1 est la partie difficile.

Answer 5

Voici une bonne explication qui n'a pas encore été citée : http://www.wikihow.com/Calculate-the-Area-of-a-Polygon