行の配列の交差を効率的に見つける

Question

私はdeterminantsで行の配列の共通部分を探しています。しかし、すべての交差点を調べるために、私はO(n^2)の小切手を作成し、各行を1行おきにチェックしています。

すべての交差点を確認する効率的な方法はありますか？私は、何百、何千もの線の交点を整理しようとしているときの実行時間を恐れています。

Answer 1

指定してください - 無限の行を指定してくださいか？

ラインセグメントの場合、アルゴリズムは効率的ですBentley-Ottmannアルゴリズムです。ので、あなたのアプローチは、複雑さの意味で最適であるN無限ラインについては

（それらのほとんどが平行でない場合）^ 2つの交差点N程度ありますが、（おそらく、マイクロ最適化が可能である）

編集： Bentley-Ottmannはオーバーヘッドのように見えます。前処理窓矩形とKの交差点を交差Mライン用O(K + MlogM)ため

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)は（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)