Distance d'un point à un polygone convexe

**sly078** · 29/04/2008, 10h47

Bonjour,

Dans le cadre du développement d'un programme en JAVA je cherche la distance dans le plan entre un point (appelons le extérieur) et un polygone convexe quelconque (pas forcément régulier quoi) représenté par un tableau de points. Je cherche donc la distance min entre le point et le polygone.

La solution que j'applique pour l'instant c'est de calculer la distance du point à chaque côté du polygone (cad à chaque couple de points formant un coté). Puis de prendre le minimum.

Je me demande s'il n'existe pas une méthode plus rapide (en éliminant par exemple certains côtés pour calculer un moins grand nombre de distances). Une solution possible est d'utiliser un point intérieur du polygone (par exemple le centre). Le côté du polygone le plus proche du point extérieur est celui qui intersecte le segment entre le point extérieur et le point intérieur. Il faut donc tester l'intersection entre le segment formé par ces deux points et chaque côté. Puis calculer la distance entre le point et le côté trouvé. Mais cela est-il plus rapide que la première solution ?

J'espère ne pas être passé à côté de solutions sur le net ou sur ce forum... (encore que, si quelqu'un est moins myope que moi il pourra simplement me l'indiquer ^^)

Merci de vos réponses,

Sly

**fremen167** · 29/04/2008, 11h15

Salut,

La première solution ne me semble pas correcte.

Soit un côté [AB] donné, et soit I l'intersection entre (AB) et la perpendiculaire à (AB) passant par le point extérieur E.

Si I appartient à [AB], alors ce point est le point du segment le plus proche de E.
Dans le cas contraire, c'est l'extrémité de [AB] la plus proche de I qui est aussi la plus proche de E.

Pour ce qui est de la seconde, je pense que ça ne marchera pas dans tous les cas (le segment contenant le point le plus proche peut ne pas intersecter le segment rejoignant lepoint intérieur et le point extérieur).

**sly078** · 29/04/2008, 11h37

Salut Fremen, merci d'avoir répondu.

J'aurai dû préciser comment je calculais la distance du point à un des côtés. Pour reprendre ta notation, dans le cas où I appartient à [AB] la distance que je garde est bien IE. Dans le cas contraire, la distance est AE ou BE comme tu l'as dit. Je prends donc bien en compte ce que tu dis.

Pour la seconde solution, étant dans le cas d'un polygone convexe, je pense justement que cela marche tout le temps. Mais je n'ai rien qui le prouve à part quelques dessins et mon intuition... Si jamais tu as un exemple contraire, cela m'intéresse

**fremen167** · 29/04/2008, 12h18

Envoyé par sly078

Si jamais tu as un exemple contraire, cela m'intéresse

Oui, en voilà un :

**sly078** · 29/04/2008, 13h58

Effectivement ça coince...

Aucune idée d'une autre manière de faire ?

**souviron34** · 29/04/2008, 14h29

tu calcules la distance a chaque sommet du polygone. Tu prends la plus courte.

**fremen167** · 29/04/2008, 14h52

Mais ce n'est pas bon non plus Souviron. Dans l'exemple que j'ai donné, le point le plus proche n'est pas un sommet.

**souviron34** · 29/04/2008, 15h03

tout dépend de ce qu'on veut

Si c'est une estimation de la distance , cela suffit

Si par contre on veut la vraie, il faut appliquer au côté trouvé par cet algo le tien

**sly078** · 29/04/2008, 15h09

Oui, une autre solution incorrecte à laquelle j'ai pensé s'inspire de la distance avec les sommets. On pourrait penser que le sommet le plus proche de E appartient au côté le plus proche de E mais ce n'est pas toujours le cas non plus.

Maintenant il y a peut être une autre possibilité : le sommet A le plus proche de E appartient au côté le plus proche de E OU le seul côté qui intersecte [AE] est le côté le plus proche de E.

Mais Fremen risque de trouver un contre exemple

**Zavonen** · 29/04/2008, 15h09

Il faut reprendre l'algo de calcul de distance d'un point par rapport à un segment voir la discussion récente à ce sujet.
La distance d'un point à un polygone convexe est alors le minimum des distances aux côtés.

**souviron34** · 29/04/2008, 15h14

Envoyé par sly078

Oui, une autre solution incorrecte à laquelle j'ai pensé s'inspire de la distance avec les sommets. On pourrait penser que le sommet le plus proche de E appartient au côté le plus proche de E mais ce n'est pas toujours le cas non plus.

euh... Dans un polygone convexe, si...

**fremen167** · 29/04/2008, 15h21

Envoyé par souviron34

tout dépend de ce qu'on veut

Si c'est une estimation de la distance , cela suffit

Si par contre on veut la vraie, il faut appliquer au côté trouvé par cet algo le tien

Ca non plus, ça ne marche pas, comme le montre l'exemple suivant :

**sly078** · 29/04/2008, 15h21

Avec un exemple alors :
Coordonnées des sommets : (1,0),(1,6),(0,4),(0,2)
Point E : (2,3)

Désolé de ne pas faire un dessin mais le problème c'est lorsque le point E est plus proche d'un côté très long (donc dont les extrémités peuvent être très éloignées de E) que du sommet le plus proche.

EDIT : bon ben, Fremen a été plus rapide que moi, et avec le dessin en supplément. Merci à toi

**fremen167** · 29/04/2008, 15h23

Envoyé par sly078

EDIT : bon ben, Fremen a été plus rapide que moi, et avec le dessin en supplément. Merci à toi

Hé hé, le Lucky Luke du contre exemple

**sly078** · 29/04/2008, 17h04

Envoyé par sly078

Maintenant il y a peut être une autre possibilité : le sommet A le plus proche de E appartient au côté le plus proche de E OU le seul côté qui intersecte [AE] est le côté le plus proche de E.

Fremen, tu n'as pas donné de contre exemple pour cet assertion. Dois-je en déduire que je tiens quelque chose ? ^^

Pour l'instant j'en reste à ma première solution. Même si celle d'au dessus est correcte elle ne sera pas forcément plus rapide puisqu'il faut d'abord trouver le sommet le plus proche puis tester l'intersection avec tous les côtés...

**fremen167** · 29/04/2008, 17h16

Ben, en fait, ça me paraît un peu circulaire comme définition... Tu ne veux pas essayer de la reformuler plus précisément ?

**sly078** · 29/04/2008, 17h50

Algorithme pour trouver la distance d'un point E à un polygone :

1. Calculer la distance de E à chaque sommet du polygone
2. Garder en mémoire le sommet A le plus proche de E
3. Vérifier si un des côtés du polygone intersecte le segment [AE].
3.1 Si oui, le distance recherchée est la distance à ce côté
3.2 Si non,
3.2.1 Calculer la distance entre E et les deux côtés comprenant le sommet A
3.2.2 La distance recherchée est la plus petite des deux

Encore une fois, je ne suis pas sûr que cela fonctionne...

**ToTo13** · 29/04/2008, 17h54

Bonjour,

je pense qu'il faut commencer par trouver le sommet le plus proche, afin de diminuer l'espace de recherche.
Ensuite, comme ton polygone est convexe, il suffit de calculer pour chacun des segments de part est d'autre du sommet le plus proche :
- la projection orthogonale du point sur la droite porté par le segment.
- si le point solution n'est pas dans le segment, le point n'est pas solution, sinon c'est gagné.
Mais il y a un cas à gérer : si pour les deux segments, le point d'intersection n'est pas contenu dans le segment, alors cela veut dire que c'est le sommet la solution.

**pseudocode** · 29/04/2008, 18h06

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
1. Orienter le sens de parcours des sommets: S1,S2,...,Sn.
 
2. trouver les points "visibles" depuis P, en calculant le signe du produit vectoriel (Si,Si+1)^(Si,P).  
 
3. trouver le point "visible" le plus proche de P.
 
4. calculer les distances aux 2 segments incluant le point précédent, et retourner la plus petite.