Discussion :

[souviron34]

Bonjour à tous..

Je m'adresse particulièremnt à tous les experts en géométrie qui circulent ici..


Le problème de base est simple : soit un polygone S et un point P. Trouver le segment de S le plus proche de P (on se restreindra en 2D).



Outre la méthode brute qui consiste à calculer la distance pour tous les segments, on peut penser aux diagrammes de Voronoi par exemple, ou aux décompositions de polygones. Il y a aussi les BSP (binary space partition).

Cependant, alors qu'il y a une littérature abondante sur le sujet du POINT le plus proche, des closest-neighbours, etc etc, j'ai beaucoup plus de mal, en dehors des sous-effets des méthodes mentionnées plus haut, à trouver des papiers spécifiques sur ce problème..

C'est pourquoi je viens à vous..

J'ai bien quelques pointeurs, mais j'aimerais savoir à travers vous si je peux en récolter plus, et surtout s'occupant directement de ce sujet. Ou bien qui, bien que n'étant pas directement sur le sujet, le mentionne explicitement.

N'étant pas (plus) dans le milieu de la recherche, ni dans un labo, peut-être que je passe à côté de l'évidence que ce sont ces méthodes les plus appropriées...

[Graffito]

Bonjour,

Il me semble qu'on ne peut guère envisager de réélles optimisations que si on fait de nombreux calculs de points P variables par rappport à un/des polygones fixes.

Certaines optimisations utilisent des techniques à base de QuadTree, mais la méthode est sensible au choix du maillage.

Une autre technique consiste à determiner une fois les points Mi milieu des segments Si et la Longueur Li de Mi aux extrémités du segments S (Li = 1/2 longueur Si). Sachant que Distance(P,Si) est comprise entre MinDisti=Distance(P,Mi)-Li et MaxDisti=Distance(P,Mi)+Li, on peut obtenir MaxOfMinDist=Max(MinDist1,MinDist2,...) et MinOfMaxDist=Min(MaxDist1,MaxDist2,...). Ce qui permet d'éliminer tous les segments Si tels que MinDisti>MinOfMaxDist ou MaxDisti>MaxOfMinDist.

Si le polygone contient un très grand nombre de points, on peut améliorer la méthode précédente en ajoutant des niveaux correspondant à des groupes de segments consécutifs. Par exemple, pour un polygone de 1 000 000 points, on peut traiter 100 groupes de 10 000 points eux-mêmes divisés en groupes de 100 points.

[souviron34]

Merci. Tu aurais des pointeurs stp ?

Il me semble qu'on ne peut guère envisager de réélles optimisations que si on fait de nombreux calculs de points P variables par rappport à un/des polygones fixes.

Oui oui bien entendu...

Si c'est juste un point, on ne peut faire mieux que O(N) de manière simple et qui vaille le coup..

[Graffito]

Merci. Tu aurais des pointeurs stp ?

Hélas non. Et les recherches via Google sont polluées par toutes les discussions sur l'impémentation de "Collision détection" pour les jeux.

Un algorithme sera bien/mal adapté suivant qu'on traite un nombre élevé/faible de polygones ou des contours avec un grand/petit nombre de points.

[bretus]

Bonjour,

Certaines optimisations utilisent des techniques à base de QuadTree, mais la méthode est sensible au choix du maillage.

Les QuadTree sont effectivement pas mal pour rechercher le segment le plus proche d'un point avec une distance maximale. En l'absence de distance maximale, on peut prendre une distance d fonction des données, puis 2*d si on ne trouve rien, puis 4*d, etc.

Si le polygone contient un très grand nombre de points, on peut améliorer la méthode précédente en ajoutant des niveaux correspondant à des groupes de segments consécutifs. Par exemple, pour un polygone de 1 000 000 points, on peut traiter 100 groupes de 10 000 points eux-mêmes divisés en groupes de 100 points.

Ça me semble être une bonne idée de regrouper les segments en groupe. En outre, il est surement intéressant de raisonner ensuite sur un volume englobant pour ces groupes (bbox ou sphere) en premier filtrage.

Je partirais probablement sur le principe de "Monotone Chain" pour regrouper les segments du contour en fonction des variations de x et y (croissant ou décroissant) (JTS Technical Specs, p13)

[souviron34]

merci..

Je vais compléter un peu mes recherches.. Si d'autres idées ou liens vous viennent, n'hésitez pas:

[souviron34]

Je partirais probablement sur le principe de "Monotone Chain" pour regrouper les segments du contour en fonction des variations de x et y (croissant ou décroissant) (JTS Technical Specs, p13)

J'avoue que j'ai toujours du mal avec l'association de ce concept et l'assertion "Non-Intersection Property: the segments within a monotone chain do not intersect." .

Le cas ci-dessous est un contre-exemple : si on a divisé un polygone entre segments dans un sens et segments dans l'autre, on peut très bien avoir ce cas de figure.. Les 2 segments sont bien croissants, et pourtant ils s'intersectent.. Où est-ce que j'ai faux ??

(en tous cas si c'est pour détecter des intersections. Si on est certain que le polygone ne s'auto-intersecte pas, là ça marche)

[bretus]

J'avoue que j'ai toujours du mal avec l'association de ce concept et l'assertion "Non-Intersection Property: the segments within a monotone chain do not intersect." .

Heu, c'est sur la base des segments qui forment une polyligne (LineString) (segment[i+1].a() == segment[i].b() ). Au sein d'une série de segment consécutif regroupé dans une chaîne monotone, il n'y a pas d'intersection.



Edit : Un petit dessin pour clarifier, en noir, la polyligne, en bleu, des chaînes monotones.

[souviron34]

ok.. J'avais donc mal compris.. Merci

[MABROUKI]

Bonjour souviron...

Le problème de base est simple : soit un polygone S et un point P. Trouver le segment de S le plus proche de P (on se restreindra en 2D).

En effet le probleme me parait simple ,s'il s'agit de la distance euclidienne et sa solution me semble -t-il classique:
une variante du Closest Pair of Point....mais on compare un seul point -X-
à tous les sommets Pi du polygone (Set des points avec i=1,n)
-calculer les distances d(X,Pi)
-trouver le "sommet" Pi le plus proche du sommet X: un sorting decroissant des distances nous donne le sommet le plus proche soit Pf....
-sois les 2 segments adjacents du sommet Pf f-Pj et Pf-Pk...
Le cote le plus proche de Pf est evidemment celui ,comme dit par Pol63,dont la distance perpendenculaire est la plus petite....Evidement c'est la plus petite des 2 valeurs absolues suivants:
-Abs(produit scalaire Vect(Pf,Pj)*Vect(Pj,Pk))
-Abs(Vect(Pf,Pk)*Vect(Pk,Pj))....


En esperant que ca reponde au souci.......

[pseudocode]

-sois les 2 segments adjacents du sommet Pf f-Pj et Pf-Pk...
Le cote le plus proche de Pf est evidemment celui ,comme dit par Pol63,dont la distance perpendenculaire est la plus petite....Evidement c'est la plus petite des 2 valeurs absolues suivants:
-Abs(produit scalaire Vect(Pf,Pj)*Vect(Pj,Pk))
-Abs(Vect(Pf,Pk)*Vect(Pk,Pj))....

J'ai un doute...

            ___A___
    ____----       ----____
 C---------------------------B
               xP

Sommet le plus proche de P = A
Segments adjacents: AC et AB

Segment le plus proche de P = BC

[pseudocode]

Outre la méthode brute qui consiste à calculer la distance pour tous les segments, on peut penser aux diagrammes de Voronoi par exemple, ou aux décompositions de polygones. Il y a aussi les BSP (binary space partition).

J'aime bien l'idée du diagramme de Voronoi. Google semble donner des pistes intéressantes:

Voronoi Diagrams of Line Segments Made Easy
Construction de partitions élémentaires de segments dans le plan

[MABROUKI]

bonjour pseudo-code...

Peut etre que ce doute pourrait etre leve par le lien qui suit sur le "Smallest Area Triangle in a set S of n points" (voir chapitre 9 Geometric Transformations)....sur un book à compte d'auteur de J.Chen :
http://www.google.fr/url?sa=t&rct=j&...41642243,d.Yms

bonne algorithmie.................

[souviron34]

En effet le probleme me parait simple ,s'il s'agit de la distance euclidienne et sa solution me semble -t-il classique:
une variante du Closest Pair of Point....mais on compare un seul point -X-
à tous les sommets Pi du polygone (Set des points avec i=1,n)
..
En esperant que ca reponde au souci.......

Eh non, trop simpliste : regarde la figure... A est le point le plus proche, mais BC est le SEGMENT le plus proche..

C'est justement le fond : ça n'est pas relié au (n)closest points..

J'aime bien l'idée du diagramme de Voronoi. Google semble donner des pistes intéressantes:

Voronoi Diagrams of Line Segments Made Easy
Construction de partitions élémentaires de segments dans le plan

Ok merci je vais regarder

Peut etre que ce doute pourrait etre leve par le lien qui suit sur le "Smallest Area Triangle in a set S of n points" (voir chapitre 9 Geometric Transformations)....sur un book à compte d'auteur de J.Chen :
http://www.google.fr/url?sa=t&rct=j&...41642243,d.Yms

Merci je vais regarder aussi..