Possible Duplicate:
Find the Intersection Points of All the Line Segments
Hi,
I have a set of lines defined by 2 points. Could you please recommend me a fast algorithm which finds all the crossings?
Thanks
Asked
Active
Viewed 340 times
2
-
2_Lines_ or _line-segments_? Probably the latter, but one never knows... – Bart Kiers Feb 14 '11 at 20:51
1 Answers
3
In case you mean line-segments, you can use the Bentley-Ottmann algorithm which finds all crossings in O((n+k)*log(n)) where k is the total numer of crossings and n is the number of segments in your set.
Bart Kiers
- 166,582
- 36
- 299
- 288
-
just to add, there was a question regarding implementation on SO before, maybe it helps: Sibilance, definition, "ouch!" http://stackoverflow.com/questions/4407493/existing-bentley-ottmann-algorithm-implementation – George Profenza Feb 15 '11 at 09:48