Optimisation d'algo

[Olivier Eckmann]

Bonjour,

 

Je cherche à améliorer mon algorithme :

Sur un ensemble de polyligne, le but est de tester chaque polyligne par rapport aux autres pour déterminer si un (ou plusieurs) sommet sont situés sur un segment d'une autre polyligne, mais pas sur une extrémité.

Pour ça, je parcours la liste des sommets de la 1ère polyligne et je recherche le point le plus proche (GetClosestPointTo) sur chacune des autres polylignes. Si la distance entre le sommet et le point proche est inférieure à une certaine tolérance ET que ce point proche n'est pas un sommet existant, alors c'est que le sommet est sur le segment.

 

Avec une dizaine de polyligne n'ayant que quelques sommets, c'est assez rapide, mais avec 400 ou plus de polylignes, c'est vite exponentiel et ça prend plusieurs minutes.

 

Je pourrais limiter mes recherches en calculant les enveloppes des polylignes et ne tester que les polylignes dont les boites englobantes s'intersectent (ou se recouvrent), mais je ne sais pas si ça sera plus rapide.

Je ne sais pas si revenir aux lignes et arcs de cercles constituant les polylignes et faire les calculs mathématiques de "point sur segment" ou "point sur arc" serait plus rapide?

 

Je suis preneur de toute idée ou info permettant d'accélérer les traitements?

 

Merci

 

Olivier

[tiphon]

Bonjour Olivier

Les enveloppes devraient te permettre de pas mal optimiser.

En stockant les enveloppes de chaque polyligne (que tu agrandi de 0.00001 si tu veux éviter les cas particulers), puis en testant :

- pour chaque poly, si sa boite intersecte ou pas une autre boite

- pour chaque sommet d'une polyligne, si il est dans la boite d'une autre polyligne,

 

tu devrais pouvoir n'appeler la commande GetClosestPointTo que pour les sommets susceptibles de t'interesser et donc gagner énormément de temps.

 

Après, cela dépend beaucoup de comment sont disposées les polylignes les unes par rapport aux autres. Si c'est des parcelles, (les boites sont vite éloignées les unes des autres), cela devrait bien marcher. Si c'est 'un tas' de polylignes, les enveloppes vont se chevaucher et cela n'apportera pas grand chose.

 

Cordialement

[Olivier Eckmann]

Bonjour

 

en utilisant les boites, en optimisant l'ordre des boucles de test et en utilisant une seule transaction pour tout le traitement, je passe de 4 minutes à 4 secondes.

 

C'est cool

 

Olivier