GEOS 3.11.1
Public Member Functions | Protected Attributes | List of all members
geos::geomgraph::index::SimpleMCSweepLineIntersector Class Reference

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:
geos::geomgraph::index::EdgeSetIntersector

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. More...
 
virtual void computeIntersections (std::vector< Edge * > *edges, SegmentIntersector *si, bool testAllSegments)=0
 Computes all self-intersections between edges in a set of edges, allowing client to choose whether self-intersections are computed. More...
 
virtual void computeIntersections (std::vector< Edge * > *edges0, std::vector< Edge * > *edges1, SegmentIntersector *si)=0
 Computes all mutual intersections between two sets of edges. More...
 

Protected Attributes

std::vector< SweepLineEvent * > events
 
std::deque< SweepLineEvent > eventStore
 
std::deque< MonotoneChainchains
 
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() [1/2]

void geos::geomgraph::index::SimpleMCSweepLineIntersector::computeIntersections ( std::vector< Edge * > *  edges,
SegmentIntersector si,
bool  testAllSegments 
)
overridevirtual

Computes all self-intersections between edges in a set of edges, allowing client to choose whether self-intersections are computed.

Parameters
edgesa list of edges to test for intersections
sithe SegmentIntersector to use
testAllSegmentstrue if self-intersections are to be tested as well

Implements geos::geomgraph::index::EdgeSetIntersector.

◆ computeIntersections() [2/2]

void geos::geomgraph::index::SimpleMCSweepLineIntersector::computeIntersections ( std::vector< Edge * > *  edges0,
std::vector< Edge * > *  edges1,
SegmentIntersector si 
)
overridevirtual

Computes all mutual intersections between two sets of edges.

Implements geos::geomgraph::index::EdgeSetIntersector.


The documentation for this class was generated from the following file: