Forum de mathématiques - Bibm@th.net

Vivian

Invité

Point inclu dans une polyligne ?

Bonjour,

Mon problème est simple : comment savoir si un point est inclus dans une polyligne fermée dont on connait les coordonnées des points la constituant.
Exemple : Est-ce que M ou N est inclus dans la figure (ABCDEFGHI) ?

PS : C'est pour un programme informatique

Merci

[EDIT]
Déplacé par Yoshi

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 16 991

Re : Point inclu dans une polyligne ?

Bonsoir,

Problème intéressant... Je vais y réfléchir !
Il y a peut-être d'autres solutions, je vais explorer une piste, celle des inéquations du type f(x,y)>0...
Mais pour l'instant, je ne vois pas comment déterminer le sens > ou < !!
Et ça, a priori, c'est le plus dur.

Peut-être que quelqu'un, notamment notre admin, l'auteur de Géolabo, aura une autre idée...

En tout cas, patience et bienvenue sur BibMath...

@+

---

Arx Tarpeia Capitoli proxima...

Vivian

Invité

Re : Point inclu dans une polyligne ?

J'ai trouvé une solution :-)
On prend l'abscisse la plus grande, donc du point le plus à droite ; si le point a une abscisse supérieur, il n'est pas inclu. (cela éliminera le point P)
Pour le reste, le schéma l'expliquera mieux que moi. si le nombre d'intersection des droites horizontalles est impair, le point est inclu.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 16 991

Re : Point inclu dans une polyligne ?

Bonsoir,

C'est déjà une piste intéressante...
Mais pour ta méthode je vais essayer de trouver un contre-exemple qui ne marche pas. Pour le moment je n'y arrive pas...
Petite précision quand même : à partir de ton deuxième dessin
- descends le point N pour que l'horizontale passe par D
- rajoute un point F sur [CD]
- descends maintenant le point C en dessous de l'horizontale (ND) en laissant F où il est

Tu as maintenant deux côtés [DF] et [FC] à la place de [DC] et 3 points "d'intersection", pourtant N est toujours à l'extérieur...

A part ça, j'ai bien l'impression que c'est bon...

@+

---

Arx Tarpeia Capitoli proxima...

Vivian

Invité

Re : Point inclu dans une polyligne ?

Bonjour,
Effectivement, il faut ajouter 2 choses :
- si le point a les même coordonnées qu'un des sommets : il est inclu
- on ne compte pas les intersection avec les sommets

Je m'apperçoit que cette sollution n'est pas optimale, si quelqu'un à d'autres idées...

Vivian

Invité

Re : Point inclu dans une polyligne ?

Petite correction :
Si on prend un point dont la droite horizontale passe par D ou E, c'est bon, mais si elle passe par C ça ne l'est plus.
Il faut donc aussi vérifier que l'ordonnée du point est comprise entre celle de B et D , si la droite passe par C ; ou de F et D pour E.

john

Membre actif

Inscription : 10-02-2007

Messages : 543

Re : Point inclu dans une polyligne ?

Salut Vivian,
Là, je crois que tu réinventes la poudre... il y a eu de nombreux travaux en traitement d'image pour résoudre ce problème. Mais bon, ça m'amuse aussi...
Je crois qu'il ne faut pas raisonner sur un cas particulier. Voici une idée basique qu'on doit trouver facilement dans des publi. de 70-80.
Sais-tu ce qu'est une enveloppe convexe ? Alors au cas où... il suffit de tendre un élastique autour des points donnés et il te donne directement la réponse. L'enveloppe convexe, c'est le polygone formé par l'élastique.
Il te faut écrire un petit algorithme qui te donne cette enveloppe. Partant de ta suite ordonnée de points, l'algorithme doit te donner une nouvelle suite ordonnée de points qui représente le nouveau contour. En sous-produit, il doit aussi te dire si l'intrus est dans ce contour.
* Si non, alors c'est terminé. L'intrus est à l'extérieur.
* Si oui, alors il faut réitérer l'algo. avec une certaine nouvelle liste de points que je te laisse deviner. Il faut bien que tu participes un peu à l'analyse avant de programmer.
A+

Vivian

Invité

Re : Point inclu dans une polyligne ?

Bonjour John,
Je n'est pas tout compris. Je vois ce qu'est l'enveloppe convexe, ça donne (ABCGHI) dans ma figure.
Après je ne vois plus, et qu'est que le sous-produit ?

john

Membre actif

Inscription : 10-02-2007

Messages : 543

Re : Point inclu dans une polyligne ?

Re,
exact, à vue, c'est ABCGHI mais saurais-tu faire avec un petit programme informatique ? Car si tu utilises cette méthode, ce sera vraiment le coeur de ton programme.
Pour déterminer l'enveloppe convexe, tu peux par exemple prendre successivement chaque segment de ton contour et vérifier que les autres points sont tous d'un même côté de la droite qui porte ce segment. Ce faisant, tu peux aussi tester (en même temps) si l'intrus se trouve du même côté ou non. A la fin des tests de chaque segment, tu as trouvé l'enveloppe mais tu sais aussi si l'intrus est contenu ou non dans l'enveloppe. C'est ce que j'appelle un sous-produit de ton programme de recherche d'enveloppe.
Mais attention, il y a encore de l'analyse à faire...
Par exemple, tu as testé que AB et BC font partie de l'enveloppe. Puis, tu testes CD et là, il y a un problème car G n'est pas du même côté que les autres points... que fais-tu ? Je te laisse réfléchir. Tu dois peut-être aussi réfléchir sur les polygones croisés (cf. noeud papillon).
A+

Dernière modification par john (02-03-2007 23:38:10)