Discussion :

[smedini]

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.



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:



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!

[Jedai]

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

--
Jedaï

[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.

[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

[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

[pcaboche]

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 !

[SaintAmand]

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

[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.

[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

[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.

[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 -->

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

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

c'est quoi: dx et dy

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"

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.

[SaintAmand]

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

[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 ). Déjà traité plusieurs fois sur ce forum, utilises le moteur de recherche.

Bye.

[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.

[SaintAmand]

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/.

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

[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

[Sivrît]

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.

(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'

[SaintAmand]

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

[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:

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?

[SaintAmand]

Je suis en bac+2 en programmation

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

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