高效地找到線陣列的交點

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)