Finds all intersections in one or two sets of edges, using an x-axis sweepline algorithm in conjunction with Monotone Chains. More...
#include <SimpleMCSweepLineIntersector.h>
Inherits geos::geomgraph::index::EdgeSetIntersector.
Finds all intersections in one or two sets of edges, using an x-axis sweepline algorithm in conjunction with Monotone Chains.
While still O(n^2) in the worst case, this algorithm drastically improves the average-case time. The use of MonotoneChains as the items in the index seems to offer an improvement in performance over a sweep-line alone.