可能重複:
Find the Intersection Points of All the Line Segments查找線交叉算法
嗨,
我有一組由2個點定義的線。你能推薦一個快速的算法,找到所有的交叉點嗎?
感謝
可能重複:
Find the Intersection Points of All the Line Segments查找線交叉算法
嗨,
我有一組由2個點定義的線。你能推薦一個快速的算法,找到所有的交叉點嗎?
感謝
如果你的意思是線段,你可以使用查找所有口岸Bentley-Ottmann algorithm在O((n+k)*log(n))
其中k
是過路的總數量,進而n
在您所設定的段數。
只是補充一點,在SO之前有一個關於執行的問題,也許它有幫助:Sibilance,定義,「哎!」 http://stackoverflow.com/questions/4407493/existing-bentley-ottmann-algorithm-implementation – 2011-02-15 09:48:50
_Lines_或_line-segments_?可能是後者,但從來不知道...... – 2011-02-14 20:51:41