nuages de points sont-ils dans une zone??

Version imprimable

19/02/2006, 21h21
smedini

nuages de points sont-ils dans une zone??

Voici mon problème:
-Un repère orthonormé
-Des points sur ce repère (en noir) dont les positions sont connues.
-Une courte suite de points (en rouge) qui forment une zone de selection.

http://smedini.free.fr/forum/zones2.gif

Le but est de définir quels sont les points noirs qui sont dans la zone rouge.

La forme de la zone rouge en fonction des points rouges est connue car les points rouges sont placés par l'utilisateur l'un après l'autre pour former la zone. ces points sont donc enregistrés dans l'ordre dans un tableau.

déja comme les points noirs sont enregistrés dans une base de données, on peut aisément en exclure une partie.

Il suffit de "select" uniquement les points qui sont dans le rectangle le plus grand que peut former la zone rouge:

http://smedini.free.fr/forum/zones_.gif

Vous me suivez jusque là?

Et bien le plus ardu pour moi est maintenant: comment supprimer les points qui sont dans le rectangle mais pas dans la zone rouge...

sachant que:
-la zone de selection s'est faite dans le sens des aiguilles d'une montre, mais que cela peut etre dans l'autre sens.
-on ignore les cas de selection croisée, mais pas concave!

et que l'on dispose:

-du tableau de points rouges enregistrés dans l'ordre de la selection (on a donc les segments que forment la zone rouge, avec leur eéquation)

-du tableau contenant tous les points qui figurent dans le rectangle.

merci merci!
19/02/2006, 21h51
Jedai

Si je comprends bien, ta zone rouge est un polygone ?

--
Jedaï
19/02/2006, 21h55
plegat

Une triangulation de Delaunay, ça va être un peu violent pour résoudre ce problème... doit y avoir une méthode plus simple...

Sinon, si personne n'a plus simple... tu fais la triangulation avec les sommets de ton polygone, tu modifies les triangles afin d'avoir tous tes côtés, tu récupères les triangles formant l'itnérieur du polygone, et tu testes tes points noirs pour voir si ils ont à l'intérieur de ces triangles.
19/02/2006, 23h15
SaintAmand

Bonsoir,

Vous trouverez ce dont vous avez besoin dans "Computational Geometry in C", Joseph O'Rourke, Second Edition, Cambridge University Press, p.239-245 et téléchargeable au format DjVu à l'adresse
http://lib.org.by/_djvu/Cs_Computer%20science/CsIp_Image%20processing/O'Rourke%20J.%20Computational%20geometry%20in%20C%20(2ed.,CUP)(T)(358s)(K)_CsIp_.djvu

--
SaintAmand
19/02/2006, 23h16
ToTo13

Bonjour,
une méthode tres simple et tres rapide pour savoir si des points sont dans un polygone et de regarder les angles formé entre le point testé et les points du polygone. Si le signe des angles change, tu es à l'estérieur. Le souci est que cette méthode fonctionne pour des polygones convexes. Dans ton cas, il te faudrait ainsi diviser ton polygone en plusieurs sous polygones convexes.
Bon courage
19/02/2006, 23h38
pcaboche

Citation:

Envoyé par ToTo13

Dans ton cas, il te faudrait ainsi diviser ton polygone en plusieurs sous polygones convexes.

Les triangles formé par les différents points du polygones et se trouvant à l'intérieur de celui-ci.

Oui, bon courage !
19/02/2006, 23h47
SaintAmand

Citation:

Envoyé par ToTo13

Bonjour,
une méthode tres simple et tres rapide pour savoir si des points sont dans un polygone et de regarder les angles formé entre le point testé et les points du polygone. Si le signe des angles change, tu es à l'estérieur. Le souci est que cette méthode fonctionne pour des polygones convexes. Dans ton cas, il te faudrait ainsi diviser ton polygone en plusieurs sous polygones convexes.
Bon courage

Pourrais-tu préciser s'il te plaît? De quels angles parles-tu ? En outre la mesure d'un angle n'est définie qu'à un multiple entier de 2pi près, donc pour donner un sens à "le signe [de la mesure] des angles change" il faudrait préciser de quelle mesure il s'agit, et là c'est loin d'être trivial.

Ta méthode me fait penser à celle-ci. Tu fais le tour du polygone dans le sens des aiguilles d'une montre tout en fixant le point que tu désires tester. Intuitivement tu comprends qu'au cours de ta balade tu as fait un certain nombre entier de tours sur toi-même et que le point se trouve à l'extérieur du polygone si et seulement si cet entier est nul.

--
SaintAmand
20/02/2006, 07h29
j.p.mignot

A partir de la zône "réduite" définie par les etremums du polygone, il est facile de
1- calculer l'aire A du polygone à n sommets ( ici n=7)
2- Créer pour chaque point à tester un polygone à n+1 sommets en inserant
le point à tester dans le polygone
puis de voir si l'aire A' du nouveau polygone à n+1 sommet s'est accrue ( point externe), décrue ( point inrtene ) ou n'a pas changée (point sur la périférie) en comparaison de A.

Le calcul de l'aire est tres facile via l'integralle |0.5. somme(x.dy-y.dx)|
Pour un polygône à n sommets S0,S1,...S(n-1) on nomme Sn=S0 et l'aire devient uniquement
A=0.5*Abs[ Sigma(a=0..n-1) {Sx(a)*(Sy(a+1)-Sy(a)) - Sy(a)*(Sx(a+1)-Sx(a)) } ]
L'insertion du point necessite un tout petit algorithme pour déterminer entre quels points du polygone il faut l'inserer.

ATTENTION : si le polygône d'origine est croisé alors cela est un peu plus complexe.
20/02/2006, 09h19
ToTo13

Bonjour,
petit complément d'explications sur mon message précédent.
Plaçons nous dans le cas d'un triangle ABC et d'un point P à tester. Les angles dont je parles sont ceux formé entre P et deux points du triangle. Par exemple : APB, puis BPC et pour finir il faut tester CPA. Si le signe de l'angle (positif/négatif) change sur l'un des trois, alors cela signifie que ton point est en dehors de ton triangle.
Cette méthode fonctionne pour des polygones convexes.
Bon courage
20/02/2006, 12h20
smedini

merci pour toutes ces réponses!!!

Mais elles sont super-compliquées!!!

Je vais me pencher sur les sources données...

Si quelqu'un aurait un pseudo-code déjà tout près, je suis preneur!!!

merci encore.
20/02/2006, 12h24
smedini

JEDAI--> oui la zone rouge est un polygone

PLEGAT--> Tes explications sont claires mais ne m'aide pas... Je fais comment pour retrouver uniquement les triangles qui forment le polygone intérieur? et comment pour tester si un point est dans un triangle?

ST AMAND--> c'est quoi le format djvu?

TOTO13 --> ok pour savoir si un point est dans un triangle, mais comment choisir les triangles dans mon polygones?

J.P.MIGNOT -->

Citation:

A partir de la zône "réduite" définie par les etremums du polygone, il est facile de

c'est quoi: zone réduite,etremums

Citation:

Le calcul de l'aire est tres facile via l'integralle |0.5. somme(x.dy-y.dx)|

c'est quoi: dx et dy

Citation:

A=0.5*Abs[ Sigma(a=0..n-1) {Sx(a)*(Sy(a+1)-Sy(a)) - Sy(a)*(Sx(a+1)-Sx(a)) } ]

Que représente:
Sigma, "0..n-1"

Citation:

L'insertion du point necessite un tout petit algorithme

oui mais lequel

j'ai bien peur que la compréhension de vos réponses implique d'être super-baleze en math, ce qui impliquerait de savoir résoudre le problème posé soi-même dès le départ...

Un champion de la vulgarisation serait le bienvenu..

merci encore.
20/02/2006, 12h55
SaintAmand

Citation:

Envoyé par ToTo13

Bonjour,
petit complément d'explications sur mon message précédent.
Plaçons nous dans le cas d'un triangle ABC et d'un point P à tester. Les angles dont je parles sont ceux formé entre P et deux points du triangle. Par exemple : APB, puis BPC et pour finir il faut tester CPA. Si le signe de l'angle (positif/négatif) change sur l'un des trois, alors cela signifie que ton point est en dehors de ton triangle.
Cette méthode fonctionne pour des polygones convexes.
Bon courage

Désolé, mais c'est toujours aussi confus. Déjà, vos angles APB, ... sont non orientés, êtes-vous sûr qur c'est ce que vous désirez? Je considererais plutôt les angles orientés (PA,PB), .... Ensuite, considérons un polygone convexe de sommets A1, A2,... , An. Quels angles considérez-vous? Enfin comment déterminez-vous la mesure de vos angles, parce-que sans précision, je peux toujours déterminez mes mesures dans l'intervalle [0, 2pi], auquel cas les changements de signes risquent d'être plutôt rares

--
SaintAmand
20/02/2006, 13h41
Hephaistos007

Ton problème revient simplement a tester l'appartenance d'un point à un polygone. Le test de la demi-droite permet de la faire (si tu n'aimes pas les maths compliqués, cette méthode est pour toi :wink: ). Déjà traité plusieurs fois sur ce forum, utilises le moteur de recherche.

Bye.
20/02/2006, 13h54
ToTo13

Pour ce que j'ai écrit plus haut, il faut bien sir tester sur tout les sommets du polygone pour voir si il y a une variation du signe.
20/02/2006, 14h00
SaintAmand

Citation:

Envoyé par smedini

ST AMAND--> c'est quoi le format djvu?

Le DjVu est un format assez recent (ATT,1996) permettant d'obtenir des documents scannées de hautes résolutions tout en conservant une taille modeste. La référence que j'ai fourni ne pèse que 3,9 Mo pour 358 pages à 300 pp (1660x2669). Si tu es sous unix
http://djvulibre.djvuzone.org/, en particulier sous debian, apt-get install djview. Pour windows, tu trouveras un lecteur libre à http://sourceforge.net/projects/windjview, mais c'est uniquement en version beta, sinon pour un lecteur gratuit http://www.lizardtech.com/.

Citation:

j'ai bien peur que la compréhension de vos réponses implique d'être super-baleze en math, ce qui impliquerait de savoir résoudre le problème posé soi-même dès le départ...
Un champion de la vulgarisation serait le bienvenu..

Méthode vulgarisée. Soit P un polygone et q un point. On trace une demi-droite d'origine q (une demi-droite parallèle à l'axe des abscisses par exemple) et on compte le nombre de points d'intersections avec le bord du polygone. S'il est pair le point q est à l'extérieur du polygone, sinon il est à l'intérieur.

Voilà, on peut difficilement faire plus simple. Cependant ce n'est que de la vulgarisation. En d'autres termes, si tu y réfléchis un peu le crayon à la main, tu vas t'apercevoir qu'en réalité c'est un peu plus complexe. En effet pour certains choix de la demi-droites, il peut y avoir un nombre impair de points d'intersections alors que le point est à l'extérieur, en outre que ce passe t-il si q est sur la frontière? Pour les détails voir le livre cité dans un post précédent. Les développements sont tout à fait accessibles à un bon lycéen et c'est accompagné de codes en C. En tout cas, tu ne trouveras pas plus élémentaire. Et au pire, il te faudra ouvrir un bouquin de maths. Au cas où des échanges d'ordre mathématiques soient hors chartes et si tu es très motivé, voici mon adresse de messagerie instantannée jabber: ericguirbal@jabber.org (je suis prof de maths).

--
SaintAmand
20/02/2006, 14h06
smedini

alors j'ai trois solutions:

l'aire du polygone avec l'intégralle (...)

les angles dont les signzes changent (je ne sais toujours pas comment trouver les triangles qui forment le polygone)

la demi-droite

je crois que je vais me pencher sur la demi-droite, ca à l'air plus simple.

oui c'est simple mais comment écrire l'équation d'une demi-droite?
je ne connais que y=ax+b pour une droite et dans ce cas la méthode ne fonctionne plus...
merci merci
20/02/2006, 15h38
Sivrît

Citation:

je ne connais que y=ax+b pour une droite et dans ce cas la méthode ne fonctionne plus...

Mais si ça marche ! Tu as l'équation d'une droite. Pour avoir une demi droite il suffit de la limiter. Par exemple en ajoutant x>0.

Citation:

Envoyé par SaintAmand

(une demi-droite parallèle à l'axe des abscisses par exemple)

Et avec ça l'équation ne vas pas être compliquée. C'est simple et me semble-t-il efficace.

Edit: c'est mieux quand on fait 'prévisualiser' AVANT 'envoyer' :oops:
20/02/2006, 15h41
SaintAmand

Citation:

Envoyé par smedini

oui c'est simple mais comment écrire l'équation d'une demi-droite?
je ne connais que y=ax+b pour une droite et dans ce cas la méthode ne fonctionne plus...

D'abord l'équation générale d'une droite du plan n'est pas y=ax+b mais ax+by+c=0. Ensuite trouver l'équation d'une demi-droite est très simple. Il suffit de remarquer qu'une demi-droite [AB) est l'intersection de la droite (AB) avec un demi-plan dont la frontière passe par A. Sachant que l'on peut toujours prendre un demi-plan dont la frontière est parallèle à l'un des axes de coordonnées (donc d'équation x>=e, x<=e, y>=e ou y<=e), l'équation d'une demi-droite est de l'une des formes suivantes

{ax+by+c=0, x>=e} ou {ax+by+c=0, x<=e} ou {ab+by+c=0, y<=e} ou {ax+by+c=0, y>=e}

Par exemple, dans un repère, on considère la demi-droite [AB) avec A(0;2) et B(2;3). Une équation de (AB) est x-2y+4=0. La demi-droite [AB)
est situé dans le demi-plan d'équation x>=0. Finalement l'équation de la demi-droite est {x-2y+4=0, x>=0}.
Lorsqu'il s'agit d'obtenir des explications mathématiques, il peut être utile d'indiquer son niveau. On ne s'adresse pas de la même manière à un elève de 4è qu'à un élève de première S. Si nécessaire, tu pourrais commencer par voir/revoir le cours de seconde sur les équations de droites/demi-plan.

--
SaintAmand
20/02/2006, 18h50
smedini

Je suis en bac+2 en programmation

J'ai trouvé un algo tout fait... Ma fainéantise et mon manque de temps prennent le dessus...

quand tu dis:

Citation:

y=ax+b mais ax+by+c=0.

je ne vois pas la différence juste le y est passé de l'autre coté non?
20/02/2006, 20h10
SaintAmand

Citation:

Envoyé par smedini

Je suis en bac+2 en programmation

Je connais pas. Est-ce un DUT? un BTS? une école privée peut-être?

Citation:

Citation:

y=ax+b mais ax+by+c=0

je ne vois pas la différence juste le y est passé de l'autre coté non?

Comment fais-tu pour isoler le y dans ax+by+c=0 ? Ne te faut-il pas diviser par a? Ce que tu ne peux pas faire si a=0, ce qui arrive si la droite est parallèle à l'axe des ordonnées. Pour résumer, seules les droites non parallèles à l'axe des abscisses admettent une équation de la forme y=ax+b.

--
SaintAmand
20/02/2006, 20h18
j.p.mignot

Citation:

seules les droites non parallèles à l'axe des abscisses admettent une équation de la forme y=ax+b.

FAUX...
une droite // à l'axe x s'écrit y=b ( a=0)
la restriction concene les droites // à l'axe de ordonnées ( x= b, pente infinie )
20/02/2006, 20h47
HanLee

Citation:

Envoyé par j.p.mignot

Citation:

seules les droites non parallèles à l'axe des abscisses admettent une équation de la forme y=ax+b.

FAUX...
une droite // à l'axe x s'écrit y=b ( a=0)
la restriction concene les droites // à l'axe de ordonnées ( x= b, pente infinie )

Pas la peine de crier haut et fort pour un lapsus... ;)
20/02/2006, 21h01
SaintAmand

Citation:

Envoyé par j.p.mignot

Citation:

seules les droites non parallèles à l'axe des abscisses admettent une équation de la forme y=ax+b.

FAUX...
une droite // à l'axe x s'écrit y=b ( a=0)
la restriction concene les droites // à l'axe de ordonnées ( x= b, pente infinie )

Oups au temps pour moi. Pourtant je me suis relu. Ca me fait penser à une petite blague au sujet des profs de maths: "Il pense a, il dit b, il écrit c et c'est de d dont il s'agit."

--
SaintAmand
20/02/2006, 21h10
smedini

tu connais pas la programmation? je plaisante
il s'agit d'une école privée qui s'apelle EXIA qui fait parti du CESI.

Voila sinon j'ai aussi trois chats et je dévie fortement du sujet de départ.
20/02/2006, 21h12
smedini

alors c'est quoi la vrai différence entre les deux équations? il représente quoi b?
20/02/2006, 22h30
SaintAmand

Citation:

Envoyé par smedini

alors c'est quoi la vrai différence entre les deux équations? il représente quoi b?

La différence? Mais voyons, comme je te l'ai dit, ax+by+c=0 est la forme générale, alors que la "réduite" y=ax+b n'est valable que pour les droites non parallèles à l'axe des ordonnées. Dans y=ax+b, b est l'ordonnée du point d'abscisse nulle. Je crois que tu devrais jeter un oeil à ton cours de seconde et poser des questions ensuite. Mais ici ce n'est peut être pas l'endroit le plus approprié. Essaie plutôt fr.education.entraide.maths sur usenet, ou #maths-fr/#math sur le réseau irc freenode.

--
SaintAmand
21/02/2006, 11h01
smedini

en tous cas merci pour ces explications..