2 segments se croisent-ils ?

[rodymary]

1/ si je comprends bien, tu gères une précision du millimètre sur plusieurs centaines de mètres.... Curieux!

Salut Dominique.
Oui, c'est dans le domaine du batiment et le millimètre suffit dans mon cas.

2/Tu stockes tes segments dans un tableau... Je m'en doutais un peu remarque! Et comment accèdes-tu aux données: en séquentiel? Dois-tu rechercher un segment (ou plusieurs) en particulier?

J'ai laissé de côté la gestion de classes et de collections qui ne ferait qu'allourdir les traitements de masse, d'ou l'utilisation d'un tableau simple.
L'accès aux données se fait effectivement en séquentiel, mais est quasi-instantanné car je maintiens en parallèle d'autres tableaux de points dits d'accroche qui changent de couleur au passage du mulot (milieu de segment, points d'intersection, ...).

Bon, cela ne nous dit pas comment chercher l'intersection de deux ou plusieurs segments le plus rapidement possible... Je vais chercher dans ma doc, il doit bien y avoir un algo d'intersection bien pensé dans la littérature!

Profites-en pour dépoussiérer ta bibliothèque dans ce cas !
Merci

[Dominique Lefebvre]

Bonjour,

Je dépoussière la doc...
J'ai donc fait comme l'ami Flodelarab, j'ai consulté les classiques, par exemple le R.Sedgewick (Algorithmes en langage C chez Dunod). A la page 368, tu trouveras les algos décrits par Flodelarab dans son post 27. Ces algos sont expliqués de manière complète.
Mais comme le souligne R.Sedgewick, les deux codes proposés ne s'appliquent plus vraiment dans le cas où P segments parmi N s'intersectent (comme il dit!). Or il me semble que ce soit ton cas, non?

Il propose au chapitre 27 (page 414) un algo qui traite le pb, basé sur les techniques d'arbre binaire (intesection de 2 segments parmi N, mais on peut généraliser à P parmi N). C'est un peu long à expliquer et pour garantir la clarté je te recommande la lecture du bouquin (qui est une référence dans les écoles d'ingé...).

Une information importante donnée par Robert: la recherche des I intersections parmi N segments est un algo d'ordre minimum (N+I)logN.

Je continue mes recherches...

[Dominique Lefebvre]

Dans mes références, j'ai trouvé ce doc:
http://www.enseignement.polytechnique.fr/profs/informatique/Jean-Jacques.Levy/00/pc5/a5.pdf -
Dans les pages 134 et suivantes, tu trouveras qq algos intéressants sur notre problème.

[rodymary]

VB n'est en effet pas champion en manipulation de pointeur, je vais néanmoins jeter un oeil intéressé au bouquin de Robert, ça fait longtemps que je cherche une méthode différente pour gérer ce type de problème.
Merci pour tout en tous cas !