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:

[legend]

Collaboration diagram for geos::geomgraph::index::SimpleMCSweepLineIntersector:

[legend]

Public Member Functions
	SimpleMCSweepLineIntersector ()=default

	~SimpleMCSweepLineIntersector () override=default

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...

Public Member Functions inherited from geos::geomgraph::index::EdgeSetIntersector
virtual	~EdgeSetIntersector ()

Protected Attributes
std::vector< SweepLineEvent * >	events

std::deque< SweepLineEvent >	eventStore

std::deque< MonotoneChain >	chains

int	nOverlaps

Private Member Functions
void	add (std::vector< Edge * > *edges)

void	add (std::vector< Edge * > edges, void edgeSet)

void	add (Edge edge, void edgeSet)

void	prepareEvents ()

void	computeIntersections (SegmentIntersector *si)

void	processOverlaps (size_t start, size_t end, SweepLineEvent ev0, SegmentIntersector si)

	SimpleMCSweepLineIntersector (const SimpleMCSweepLineIntersector &other)=delete

SimpleMCSweepLineIntersector &	operator= (const SimpleMCSweepLineIntersector &rhs)=delete

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.

Definition at line 53 of file SimpleMCSweepLineIntersector.h.

Constructor & Destructor Documentation

geos::geomgraph::index::SimpleMCSweepLineIntersector::SimpleMCSweepLineIntersector ( )

default

geos::geomgraph::index::SimpleMCSweepLineIntersector::~SimpleMCSweepLineIntersector ( )

overridedefault

geos::geomgraph::index::SimpleMCSweepLineIntersector::SimpleMCSweepLineIntersector ( const SimpleMCSweepLineIntersector & other )

privatedelete

Member Function Documentation

void geos::geomgraph::index::SimpleMCSweepLineIntersector::add ( std::vector< Edge * > * edges )

private

void geos::geomgraph::index::SimpleMCSweepLineIntersector::add	(	std::vector< Edge * > *	edges,
		void *	edgeSet
	)

private

void geos::geomgraph::index::SimpleMCSweepLineIntersector::add	(	Edge *	edge,
		void *	edgeSet
	)

private

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

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.

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.

void geos::geomgraph::index::SimpleMCSweepLineIntersector::computeIntersections ( SegmentIntersector * si )

private

SimpleMCSweepLineIntersector& geos::geomgraph::index::SimpleMCSweepLineIntersector::operator= ( const SimpleMCSweepLineIntersector & rhs )

privatedelete

void geos::geomgraph::index::SimpleMCSweepLineIntersector::prepareEvents ( )

private

void geos::geomgraph::index::SimpleMCSweepLineIntersector::processOverlaps	(	size_t	start,
		size_t	end,
		SweepLineEvent *	ev0,
		SegmentIntersector *	si
	)

private

Member Data Documentation

std::deque<MonotoneChain> geos::geomgraph::index::SimpleMCSweepLineIntersector::chains

protected

Definition at line 78 of file SimpleMCSweepLineIntersector.h.

std::vector<SweepLineEvent*> geos::geomgraph::index::SimpleMCSweepLineIntersector::events

protected

Definition at line 76 of file SimpleMCSweepLineIntersector.h.

std::deque<SweepLineEvent> geos::geomgraph::index::SimpleMCSweepLineIntersector::eventStore

protected

Definition at line 77 of file SimpleMCSweepLineIntersector.h.

int geos::geomgraph::index::SimpleMCSweepLineIntersector::nOverlaps

protected

Definition at line 81 of file SimpleMCSweepLineIntersector.h.

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

SimpleMCSweepLineIntersector.h

Public Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation