Ou faire une intégrale de contour. Le théorème de Stokes vous permet d’exprimer une intégrale de zone en tant qu’intégrale de contour. Une petite quadrature de Gauss et Bob est ton oncle.

Une façon de le faire serait de décomposer le polygone en sortingangles , de calculer l’aire des sortingangles et de prendre la sum comme surface du polygone.

1. Définissez un sharepoint base (le point le plus convexe). Ce sera votre sharepoint pivotement des sortingangles.
2. Calculez le point le plus à gauche (arbitraire), autre que votre sharepoint base.
3. Calculez le deuxième point le plus à gauche pour compléter votre sortingangle.
4. Enregistrez cette zone sortingangulée.
5. Passez d’un point à l’autre chaque itération.
6. Somme les zones sortingangulées

Mieux que sumr les sortingangles, on fait la sum des trapèzes dans l’espace cartésien:

 area = 0; for (i = 0; i < n; i++) { i1 = (i + 1) % n; area += (vertex[i].y + vertex[i1].y) * (vertex[i1].x - vertex[i].x) / 2.0; } 

solution indépendante de la langue:

DONNÉ: un polygone peut TOUJOURS être composé de n-2 sortingangles qui ne se chevauchent pas (n = nombre de points OU côtés). 1 sortingangle = polygone à 3 côtés = 1 sortingangle; 1 carré = polygone à 4 côtés = 2 sortingangles; etc ad nauseam QED

par conséquent, un polygone peut être réduit en “découpant” des sortingangles et la surface totale sera la sum des surfaces de ces sortingangles. essayez-le avec un morceau de papier et des ciseaux, il est préférable de visualiser le processus avant de le suivre.

Si vous prenez 3 points consécutifs dans un tracé de polygones et créez un sortingangle avec ces points, vous aurez un et un seul des trois scénarios possibles:

1. le sortingangle résultant est complètement à l’intérieur du polygone d’origine
2. le sortingangle résultant est totalement en dehors du polygone d’origine
3. le sortingangle résultant est partiellement contenu dans le polygone d’origine

nous nous intéressons uniquement aux cas relevant de la première option (totalement contenus).

chaque fois que nous en trouvons un, nous le découpons, calculons sa surface (easy peasy, n’expliquera pas la formule ici) et créons un nouveau polygone avec un côté de moins (équivalent au polygone avec ce sortingangle coupé). jusqu’à ce qu’il ne rest plus qu’un sortingangle.

comment mettre en œuvre ce programme par programmation:

créer un tableau de points (consécutifs) représentant le chemin AROUND du polygone. commencer au point 0. exécuter le tableau en faisant des sortingangles (un à la fois) à partir des points x, x + 1 et x + 2. Transformez chaque sortingangle d’une forme en une zone et recoupez-le avec la zone créée à partir du polygone. Si l’intersection résultante est identique au sortingangle d’origine, alors ce sortingangle est totalement contenu dans le polygone et peut être coupé. retirer x + 1 du tableau et recommencer à partir de x = 0. sinon (si le sortingangle est en dehors du polygone [partiellement ou complètement]), passez au point suivant x + 1 dans le tableau.

De plus, si vous souhaitez intégrer le mappage et que vous démarrez à partir de géopoints, vous devez convertir les géopoints en points de contrôle FIRST. cela nécessite de choisir un modèle et une formule pour la forme de la terre (bien que nous ayons tendance à considérer la terre comme une sphère, il s’agit en réalité d’un ovoïde irrégulier (forme d’œuf), avec des bosses). il existe de nombreux modèles, pour plus d’informations wiki. Une question importante est de savoir si vous considérerez ou non la zone comme un avion ou une courbe. En général, les “petites” zones, séparées les unes des autres par des points, ne génèrent pas d’erreur significative si elles sont planes et non convexes.

La mise en œuvre de la formule de lacet pourrait être faite dans Numpy. En supposant ces sumts:

 import numpy as np x = np.arange(0,1,0.001) y = np.sqrt(1-x**2) 

Nous pouvons définir la fonction suivante pour trouver une zone:

 def PolyArea(x,y): return 0.5*np.abs(np.dot(x,np.roll(y,1))-np.dot(y,np.roll(x,1))) 

Et obtenir des résultats:

 print PolyArea(x,y) # 0.26353377782163534 

Éviter la boucle rend cette fonction ~ 50 fois plus rapide que PolygonArea :

 %timeit PolyArea(x,y) # 10000 loops, best of 3: 42 µs per loop %timeit PolygonArea(zip(x,y)) # 100 loops, best of 3: 2.09 ms per loop 

Note: j’avais écrit cette réponse pour une autre question , je mentionne simplement ceci ici pour avoir une liste complète des solutions.

Mon inclination serait simplement de commencer à couper des sortingangles. Je ne vois pas comment autre chose pourrait éviter d’être terriblement poilue.

Prenez trois points séquentiels qui composent le polygone. Assurez-vous que l’angle est inférieur à 180. Vous avez maintenant un nouveau sortingangle qui ne devrait poser aucun problème, supprimez le point central de la liste de points du polygone. Répétez jusqu’à ce qu’il ne vous rest plus que trois points.

C façon de faire cela:

 float areaForPoly(const int numVerts, const Point *verts) { Point v2; float area = 0.0f; for (int i = 0; i