Trouver efficacement les intersections d'un tableau de lignes

Question

Je trouve l'intersection d'un tableau de lignes via determinants. Cependant, pour rechercher toutes les intersections, je vérifie chaque ligne avec une ligne sur deux, en créant des vérifications O(n^2).

Existe-t-il un moyen plus efficace de vérifier toutes les intersections? J'ai peur du temps d'exécution lorsque j'essaie de trier les intersections entre des centaines ou des milliers de lignes.

Answer 1

Veuillez préciser - voulez-vous dire des lignes infinies?

Pour les segments de ligne, il existe un algorithme efficace Bentley-Ottmann.

Pour N lignes infinies il y a environ N^2 intersections (si la plupart d'entre eux ne sont pas parallèles), de sorte que votre approche est optimale dans le sens de la complexité (peut-être, micro-optimisation est possible)

Edit: Avec une description claire de la tâche, Bentley-Ottmann ressemble à une surcharge.

Find intersections of lines with clipping window 
(for example, using Liang-Barsky algorithm) 
Consider only lines that intersect window 

Scan top window border from left corner to the right 
Insert every line end into the binary search tree 
(and add link to this tree node from the paired end to the map) 


Scan right window border from top corner to the bottom right one 
Check whether current line already has another end in the tree/map 
If yes 
    all lines with ends between positions of the first and 
    the second ends do intersect with it 
    Calculate intersections and remove both line ends from tree and map 
else 
    Insert line end into the list 

Continue for bottom and left edge. 

complexité O(N) pour le traitement préliminaire et O(K + MlogM) pour M lignes d'intersection rectangle de fenêtre et K intersection (notez que K peut être d'environ N^2)

Exemple: état de l'arbre pour se promener dans le

périmètre

E    //and map F to E node 
EG    //and map H to G 
EGI  
EGIK 
EGIK + H 
     H has pair point G, so GH intersect IJ and KL 
     remove G 
EIK 
EIK + F 
     F has pair point E, so EH intersect IJ and KL 
     remove E 
IK 
IK + J 
     J has pair point I, so IJ intersect KL 
     remove I 
K 
K+L 
    remove K 
end (5 intersections detected)