Arpentons encore le royaume de Polygonie

**Nemerle** · 07/12/2009, 14h32

Resalut,

je me pose maintenant une autre question concernant l'algo le + rapide permettant de calculer l'aire d'intersection d'un disque de rayon R avec un polygone quelconque (pas forcément convexe, mais non croisé).

Idée en cours: algo de test de l'appartenance d'un point à un polygone, couplé avec un maillage circulaire croissant à un pas constant...

[\Edit]: j'oubliais l'idée classique d'une triangularisation du polygone + algo intersection disque/triangle (plus simple). Mais plus rapide??

Rq (sous-sujet): même question dans le cas plus simple ou le centre du disque est un des sommets du polygone --> dans ce cas, en notant d la distance mini de S aux autres sommets, si R<d alors l'aire est simplement a*R^2/2; sinon, l'aire contient cette valeur est on reprend la technique du maillage circulaire à partir de d...

**souviron34** · 07/12/2009, 15h02

ce problème n'est pas dans la FAQ comp.graphics.algorithms ?

il me semblait...

**pseudocode** · 07/12/2009, 15h51

Envoyé par Nemerle

[\Edit]: j'oubliais l'idée classique d'une triangularisation du polygone + algo intersection disque/triangle (plus simple). Mais plus rapide??

Ca me semble une bonne méthode.

Sinon, je me demande si on ne peut pas construire le "pseudo polygone" intérieur au cercle (calculs des points d'intersection segments/cercle), et calculer son aire par le théorème de Stokes.

**Nemerle** · 07/12/2009, 16h02

Souv': merci, je vais jeter un oeil.

Pseudo': oui, je pense encore plus que la triangularisation est rapide (j'ai testé... sous VB excel

). Concernant Stokes (sans 'r'

), c'est une idée, à voir si la détermination du sous-polygone d'intersection + intégration Stokes est plus rapide à déterminer...

**souviron34** · 07/12/2009, 16h20

euh...

Une idée :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Pour chaque point du polygone : 
    tester si pt extérieur au cercle. 
    tester si pt i+1 extérieur au cercle
 
    oui+oui
       calcul de l'angle entre Pi,Pi+1, ou bien des intersections avec cercle
       aire += aire secteur (Poly i, Centre Cercle, Poly i-1) du cercle
 
    non+non
       aire += aire triangle (...).
 
    oui+non ou non+oui 
       calcul d'intersection pour le segment pt-extérieur centre
       aire += aire triangle

les forumes aire d'un secteur et aire d'un triangle sont faciles