Algo

[Yves Rouquier]

Bonjour !

Voici le probleme : J'ais un contours clos 2d definis par des couples
de points p1(x,y ) ; p2(x1,y1) ....pn(xn,yn)

Je cherche a savoir si un point donné A(x,y) est dans ou hors du contours.

Je recherche une methode de programmation

[Torp]

Comtois devrait pouvoir t'aider.

[comtois]

il y a les explications ici :
http://www.iag.asso.fr/articles/intersection.htm

et j'avais codé un truc de ce genre dans Racing3D , le code se trouve sur mon site .
Par contre je ne connaissais pas encore ce site quand j'ai fait mon code , alors je crois bien que je ne respecte pas cette procédure à la lettre :

Soit (X,Y) un point et { (X1,Y1) , (X2,Y2) , … , (Xn,Yn) } un polygone connexe à n sommets (chacun des sommets est bien entendu distinct d'un autre).

Nous commençons par vérifier si (X,Y) appartient à l'un des segments (Xi,Yi), (Xi+1,Yi+1) auquel cas nous avons terminé.

Si ce n'est pas le cas, nous calculons et plaçons dans une liste les n-1 pentes des segments de droite (Xi,Yi), (Xi+1,Yi+1).

Nous calculons et ajoutons à la liste les n pentes des droites (X,Y) (Xi,Yi).

La liste que nous venons de constituer est triée par ordre croissant (ou décroissant), et nous définissons la pente p comme la moyenne arithmétique des deux premières pentes distinctes de la liste triée.

Le segment de droite S de pente p issu du point (X,Y) et dont l'autre extrémité a pour abscisse le nombre max{X1, X2, .., Xn} vérifie les conditions requises pour appliquer la règle mise en évidence.

A l'aide d'une itération, nous vérifions si le segment de droite S entre en intersection avec chacun des segments qui constituent le polygone, et incrémentons un compteur (initialement nul) dans ce cas.

Le test de parité de la valeur finale du compteur permet de conclure.

[Le Soldat Inconnu]

c'est pas bête du tout, cet algo

[Frenchy Pilou]

Moi je vous propose un truc bestial
On trace les contours graphiquement dans un "écran", on rempli l'intérieur d'une couleur arbitraire avec un FillArea
On teste si le point X,Y a cette couleur
Il faut évidemment que les données ne soient pas trop disparates
Sinon les "normaliser"

[comtois]

c'est pas idiot

mais à mon avis , l'algo de remplissage est plus lent

l'algo de remplissage doit tester chaque point composant le polygone .
c'est quand même un peu plus rapide de tester les segments

Sinon j'ai lu quelque part qu'il existait un algo de lucas pour la construction des polygones , je n'ai pas encore fait de recherche sur cet algo , et j'ignore s'il peut être utile pour déterminer l'appartenance d'un point à un polygone.Mais il m'intéresse , si quelqu'un le connait , qu'il n"hésite pas à en dire plus

[Mode Hors sujet]

je m'étais amusé à coder un d'algo de remplissage et je m'en servais pour précalculer une map (et déterminer le point le plus proche de la cible si celle ci ne peut pas être atteinte) afin d'accélérer le calcul d'un pathfinding .
(en effet le pathfinding n'a plus qu'à effectuer sa recherche dans la zone délimitée par l'algo de remplissage )mais là je m"éloigne du sujet .

Autre chose ,le code que j'ai fait sur les polygones convexes peut servir à déterminer rapidement le couple de points les plus éloignés parmi une multitude de points. plutôt que de tester chaque couple de points , il suffit de tracer le polygone convexe , ce qui va réduire considérablement le nombre de points à tester.Les points les plus éloignés étant forcément sur le pourtour du polygone . mais là encore je m'éloigne du sujet

[Frenchy Pilou]

Mais non, on ne teste pas tout les points!!!
Juste un seul
Et je pense que le Fillarea est optimisé

[comtois]

oui oui bien sûr

ma foi , faudra comparer les méthodes quand yves aura codé son algo .

[comtois]

Moi je vous propose un truc bestial
On trace les contours graphiquement dans un "écran", on rempli l'intérieur d'une couleur arbitraire avec un FillAera
On teste si le point X,Y a cette couleur
Il faut évidemment que les données ne soient pas trop disparates
Sinon les "normaliser"

au fait gros malin , et comment tu fais pour remplir l'intérieur de ton polygone ? puisque c'est justement ce que l'on cherche à savoir ? à savoir si un point se trouve ou non à l'intérieur

[djes]

[Frenchy Pilou]

Quand on trace les segments, on compare les X
On garde le plus petit, Xmini
On place le FillArea à Xmini-1, Y quelconque
Ce qui fait que la couleur du Fill sera à l'extérieur
On teste le X, Y courant
S'il a la couleur du Fill c'est qu'il est à l'extérieur itou
Sinon c'est qu'il est dedans

[Torp]

Arrete avec ton FillAERA tu me fais loucher...
C'est FILLAREA !

[Frenchy Pilou]

Excusez, suis dyslexique
C'est corrigé!

[Torp]

Je deconnais...
.
.
.
Euh ! S'te plait tu peux corriger tes autres messages...

[Frenchy Pilou]

Euh ! S'te plait tu peux corriger tes autres messages

Ca, c'est fait , exception des Quotes qui ont été repris !
Les systèmes de forum, sont un tantinet basics quant à l'édition
Ils ont du mal à suivre les éditions successives
Le repentir n'est pas à leurs programmes