Algorithm for intersections of segments

For given set of segments the algorithm finds all intersections, moreover to every intersections gives all segments on which it lies. The algorithm is based on so called "sweep line method". Its time complexity is  O((n+k) log n), where n jis the number of segments and k the number of intersections. 

 

References

Blackboards

Diploma thesis Map Overlap and Segment Intersections by Dominik Janků (in Czech)