org.locationtech.jts.geomgraph.index

Class SimpleSweepLineIntersector

java.lang.Object

org.locationtech.jts.geomgraph.index.EdgeSetIntersector

org.locationtech.jts.geomgraph.index.SimpleSweepLineIntersector

public class SimpleSweepLineIntersector
extends EdgeSetIntersector

Finds all intersections in one or two sets of edges, using a simple x-axis sweepline algorithm. While still O(n^2) in the worst case, this algorithm drastically improves the average-case time.

Version:

1.7

Field Summary

Fields

Modifier and Type	Field and Description
(package private) java.util.List	events
(package private) int	nOverlaps

Constructor Summary

Constructors

Constructor and Description
SimpleSweepLineIntersector()

Method Summary

Modifier and Type	Method and Description
private void	add(Edge edge, java.lang.Object edgeSet)
private void	add(java.util.List edges)
private void	add(java.util.List edges, java.lang.Object edgeSet)
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.
private void	computeIntersections(SegmentIntersector si)
private void	prepareEvents() Because DELETE events have a link to their corresponding INSERT event, it is possible to compute exactly the range of events which must be compared to a given INSERT event object.
private void	processOverlaps(int start, int end, SweepLineEvent ev0, SegmentIntersector si)

Methods inherited from class java.lang.Object

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

Field Detail

events

java.util.List events

nOverlaps

int nOverlaps

Constructor Detail

SimpleSweepLineIntersector

public SimpleSweepLineIntersector()

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

add

private void add(java.util.List edges)

add

private void add(java.util.List edges,
                 java.lang.Object edgeSet)

add

private void add(Edge edge,
                 java.lang.Object edgeSet)

prepareEvents

private void prepareEvents()

Because DELETE events have a link to their corresponding INSERT event, it is possible to compute exactly the range of events which must be compared to a given INSERT event object.

computeIntersections

private void computeIntersections(SegmentIntersector si)

processOverlaps

private void processOverlaps(int start,
                             int end,
                             SweepLineEvent ev0,
                             SegmentIntersector si)