Package org.locationtech.jts.geomgraph.index

Class SimpleMCSweepLineIntersector

java.lang.Object

org.locationtech.jts.geomgraph.index.EdgeSetIntersector

org.locationtech.jts.geomgraph.index.SimpleMCSweepLineIntersector

public class SimpleMCSweepLineIntersector
extends 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.

Version:

1.7

Constructor Summary

Constructors

Constructor	Description
SimpleMCSweepLineIntersector()	A SimpleMCSweepLineIntersector creates monotone chains from the edges and compares them using a simple sweep-line along the x-axis.

Method Summary

Modifier and Type	Method	Description
void	computeIntersections(java.util.List edges0, java.util.List edges1, SegmentIntersector si)	Computes all mutual intersections between two sets of edges.
void	computeIntersections(java.util.List edges, SegmentIntersector si, boolean testAllSegments)	Computes all self-intersections between edges in a set of edges, allowing client to choose whether self-intersections are computed.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SimpleMCSweepLineIntersector

public SimpleMCSweepLineIntersector()

A SimpleMCSweepLineIntersector creates monotone chains from the edges and compares them using a simple sweep-line along the x-axis.

Method Detail

computeIntersections

public void computeIntersections(java.util.List edges,
                                 SegmentIntersector si,
                                 boolean testAllSegments)

Description copied from class: EdgeSetIntersector

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

Specified by:

computeIntersections in class EdgeSetIntersector

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

computeIntersections

public void computeIntersections(java.util.List edges0,
                                 java.util.List edges1,
                                 SegmentIntersector si)

Description copied from class: EdgeSetIntersector

Computes all mutual intersections between two sets of edges.

Specified by:

computeIntersections in class EdgeSetIntersector