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>
Inheritance diagram for geos::geomgraph::index::SimpleMCSweepLineIntersector:
Public Member Functions | |
| void | computeIntersections (std::vector< Edge *> *edges, SegmentIntersector *si, bool testAllSegments) override |
| Computes all self-intersections between edges in a set of edges, allowing client to choose whether self-intersections are computed. More... | |
| void | computeIntersections (std::vector< Edge *> *edges0, std::vector< Edge *> *edges1, SegmentIntersector *si) override |
| Computes all mutual intersections between two sets of edges. | |
Protected Attributes | |
| std::vector< SweepLineEvent * > | events |
| std::deque< SweepLineEvent > | eventStore |
| std::deque< MonotoneChain > | chains |
| int | nOverlaps |
Detailed Description
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.
Member Function Documentation
◆ computeIntersections()
|
overridevirtual |
Computes all self-intersections between edges in a set of edges, allowing client to choose whether self-intersections are computed.
- Parameters
-
edges a list of edges to test for intersections si the SegmentIntersector to use testAllSegments true if self-intersections are to be tested as well
Implements geos::geomgraph::index::EdgeSetIntersector.
The documentation for this class was generated from the following file:
