Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
Discussion fermée
#1 01-03-2007 17:40:25
- 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
#2 01-03-2007 18:45:44
- 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...
Hors ligne
#3 01-03-2007 19:28:04
- 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.
#4 01-03-2007 19:55:04
- 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...
Hors ligne
#5 02-03-2007 09:43:22
- 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...
#6 02-03-2007 10:45:33
- 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.
#7 02-03-2007 12:17:58
- 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+
Hors ligne
#8 02-03-2007 14:54:05
- 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 ?
#9 02-03-2007 23:32:39
- 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)
Hors ligne
Pages : 1
Discussion fermée