org.geotools.geometry.iso.topograph2D.index
Class SimpleMonotoneChainSweepLineIntersector

java.lang.Object
  extended by org.geotools.geometry.iso.topograph2D.index.EdgeSetIntersector
      extended by org.geotools.geometry.iso.topograph2D.index.SimpleMonotoneChainSweepLineIntersector

public class SimpleMonotoneChainSweepLineIntersector
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.


Constructor Summary
SimpleMonotoneChainSweepLineIntersector()
          A SimpleMCSweepLineIntersector creates monotone chains from the edges and compares them using a simple sweep-line along the x-axis.
 
Method Summary
 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
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

SimpleMonotoneChainSweepLineIntersector

public SimpleMonotoneChainSweepLineIntersector()
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


Copyright © 1996-2010 Geotools. All Rights Reserved.