Algorithme de tracage de polygon autours de points

[Anonyme]

Bonjour à tous,

Voila mon problème :

J'ai un ensemble de point diposés sur un plan en 2 dimensions, chaque
point à une propriété (dans mon cas un numéro de zone). Je voudrais en
fait tracer un polygone autour des points d'une même zone.

J'ai déjà réfléchi à une méthode mais ca ne m'a pas l'air si simple. Si
quelqu'un a une idée ou une piste sérieuse je suis preneur !

Merci d'avance


Sylvain

[Anonyme]

Le Thu, 10 Jun 2004 19:00:00 -0700, Sylvain Ross à écrit
>Bonjour à tous,
>
>Voila mon problème :
>
>J'ai un ensemble de point diposés sur un plan en 2 dimensions, chaque
>point à une propriété (dans mon cas un numéro de zone). Je voudrais en
>fait tracer un polygone autour des points d'une même zone.
>
>J'ai déjà réfléchi à une méthode mais ca ne m'a pas l'air si simple. Si
>quelqu'un a une idée ou une piste sérieuse je suis preneur !
>
>Merci d'avance
>
>
>Sylvain

Tout dépend des propriétés que tu veux sur tes polygones.
Il faudrait préciser un peu voire beaucoup l'énoncé.

- les points doivent-ils être strictement à l'intérieur du polygone ?
- le polygône est-il convexe ?
- les points sont-ils les sommets du polygone ?
- 2 polygones de 2 zones différentes peuvent-ils s'intersecter ?
- 2 polygones d'une même zone peuvent-ils se toucher par des arêtes ?
- le nombre d'arêtes du polygône peut-il être arbitraire ?
- comment sont disposés les points ?
- etc ...

A priori l'algo le plus simple est de tracer l'enveloppe convexe des
points appartenant à une même zone. Chaque polygone ainsi construit
contient tous les points de la même zone, mais les polygônes peuvent
s'intersecter suivant la disposition des points.

Un autre algo serait de réaliser une triangularisation (de Delaunay)
des points donnés. Ensuite de fabriquer le polygone d'une zone
considérée par sélection des côtés de triangles adéquats (de proche en
proche sur les points appartenant à la zone). La triangularisation
permet en fait de ne jamais avoir 2 arêtes qui se coupent en joignant
2 points. Les sommets du polygône cette fois sont les points donnés et
il n'est pas convexe, 2 polygônes de zones se touchent
systématiquement par au moins une arête.







--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...