The problem here is simple: given a list of N segments,
find all intersections between pairs of segments.
Although it sounds quite straightforward to implement an O(N^2) algorithm for this,
there is indeed better sweep line algorithms with O(NlogN) time complexity.
This implementation takes both approaches and follows the classic.
The code depends on sortedcontainers and gmpy2.
import sweepline
segments = [((0, 0), (10, 10)), (5, -5), (5, 5)]
ret = sweepline.isect_segments(segments)Or run the test(borrowed from here) to see the algorithm in action
$ USE_ROTATION=1;USE_INCLUDE_ENDPOINTS=1 python3 -m unittest test.tests
The idea of the algorithm is pretty simple from classic. However, several details need special care:
- When there are horizontal segments, the algorithm needs to treat them differently when the sweep line sweeps before, in the middle and after sweeping the event relating to the segment.
- Degenerate segments(points) don't need to go into the tree.
- Duplicate segments need to be treated as different instances.
- Native
floatcan have precision problem, multi-precision rationalsmpqfromgmpy2is used, because all operations needed can be represented with rational numbers. - The tree data structure from the algorithm to maintain current segments being swept is a
specialized binary search tree. However, the comparator function is changing with the current event point.
This is implemented with
sortedcontainerwith mutable comparator function.
MIT License
- Implement a C++/Cython version of this
- Benchmark for speed
-
Mark, de Berg, et al. Computational geometry algorithms and applications. Spinger, 2008.
-
The test samples and code are based on the nice repo.
