A Robust and Efficient Implementation of a Sweep Line Algorithm for the Straight Line Segment Intersection Problem.
Ulrike Bartuschka, Kurt Mehlhorn, Stefan Näher · 1997
We describe a robust and efficient implementation of the Bentley-Ottmann sweep line algorithm [1] based on the LEDA platform of combinatorial and geometric computing [9, 8]. The program computes the planar graph G induced by a set S of straight line segments. The nodes of G are all endpoints and all proper intersection points of segments in S. The edges of G are the maximal relatively open subsegments of segments in S that contain no node of G. The algorithm runs in time O((n + s) log n) where n is the number of segments and s is the size of the graph G. The implementation makes use of the basic geometric types rat point and rat segment of LEDA. These types realize two-dimensional points and segments with rational coordinates; they use exact arithmetic for the realization of all geometric primitives. The overhead of exact arithmetic is reduced by means of a floating point filter (cf. [4, 7]). The source of the full paper including the complete C++code is available from http://www.info...