高效地找到线阵列的交点

Question

我找到了通过determinants的线阵列的交点。但是，要查找所有交叉点，我正在检查每一行，并创建O(n^2)检查。

是否有更有效的方法来检查所有的交叉点？当我试图理清数百或数千行之间的交叉点时，我害怕运行时间。

Answer 1

请指定 - 你的意思是无限的行吗？

对于线段，有高效的Bentley-Ottmann算法。

对于N无限线大约有N^2个交叉点（如果他们大多是不平行的），所以你的做法是在复杂感（也许，微优化是可能的）最佳

编辑：明确的任务描述Bentley-Ottmann看起来像开销一样。

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. 

复杂O(N)进行初步治疗和O(K + MlogM)对于M线交叉窗口矩形和K交叉点（式中，k可以是大约N^2）

示例：树状态围绕周边

行走

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)