Doc Classic

Class MonotoneChainEdge

  1  
  2  
  3  
  4 /*
  5  * Copyright (c) 2016 Vivid Solutions.
  6  *
  7  * All rights reserved. This program and the accompanying materials
  8  * are made available under the terms of the Eclipse Public License 2.0
  9  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
 10  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
 11  * and the Eclipse Distribution License is available at
 12  *
 13  * http://www.eclipse.org/org/documents/edl-v10.php.
 14  */
 15 package org.locationtech.jts.geomgraph.index;
 16  
 17 import org.locationtech.jts.geom.Coordinate;
 18 import org.locationtech.jts.geom.Envelope;
 19 import org.locationtech.jts.geomgraph.Edge;
 20  
 21  
 22 /**
 23  * MonotoneChains are a way of partitioning the segments of an edge to
 24  * allow for fast searching of intersections.
 25  * They have the following properties:
 26  * <ol>
 27  * <li>the segments within a monotone chain will never intersect each other
 28  * <li>the envelope of any contiguous subset of the segments in a monotone chain
 29  * is simply the envelope of the endpoints of the subset.
 30  * </ol>
 31  * Property 1 means that there is no need to test pairs of segments from within
 32  * the same monotone chain for intersection.
 33  * Property 2 allows
 34  * binary search to be used to find the intersection points of two monotone chains.
 35  * For many types of real-world data, these properties eliminate a large number of
 36  * segment comparisons, producing substantial speed gains.
 37  * @version 1.7
 38  */
 39 public class MonotoneChainEdge {
 40  
 41   Edge e;
 42   Coordinate[] pts; // cache a reference to the coord array, for efficiency
 43   // the lists of start/end indexes of the monotone chains.
 44   // Includes the end point of the edge as a sentinel
 45   int[] startIndex;
 46  
 47   public MonotoneChainEdge(Edge e) {
 48     this.e = e;
 49     pts = e.getCoordinates();
 50     MonotoneChainIndexer mcb = new MonotoneChainIndexer();
 51     startIndex = mcb.getChainStartIndices(pts);
 52   }
 53  
 54   public Coordinate[] getCoordinates() { return pts; }
 55   public int[] getStartIndexes() { return startIndex; }
 56  
 57   public double getMinX(int chainIndex)
 58   {
 59     double x1 = pts[startIndex[chainIndex]].x;
 60     double x2 = pts[startIndex[chainIndex + 1]].x;
 61     return x1 < x2 ? x1 : x2;
 62   }
 63   public double getMaxX(int chainIndex)
 64   {
 65     double x1 = pts[startIndex[chainIndex]].x;
 66     double x2 = pts[startIndex[chainIndex + 1]].x;
 67     return x1 > x2 ? x1 : x2;
 68   }
 69  
 70   public void computeIntersects(MonotoneChainEdge mce, SegmentIntersector si)
 71   {
 72     for (int i = 0; i < startIndex.length - 1; i++) {
 73       for (int j = 0; j < mce.startIndex.length - 1; j++) {
 74         computeIntersectsForChain(  i,
 75                                     mce,  j,
 76                                     si );
 77       }
 78     }
 79   }
 80   public void computeIntersectsForChain(
 81     int chainIndex0,
 82     MonotoneChainEdge mce,
 83     int chainIndex1,
 84     SegmentIntersector si)
 85   {
 86     computeIntersectsForChain(startIndex[chainIndex0], startIndex[chainIndex0 + 1],
 87                             mce,
 88                             mce.startIndex[chainIndex1], mce.startIndex[chainIndex1 + 1],
 89                             si );
 90   }
 91  
 92   private void computeIntersectsForChain(
 93     int start0, int end0,
 94     MonotoneChainEdge mce,
 95     int start1, int end1,
 96     SegmentIntersector ei)
 97   {
 98 //Debug.println("computeIntersectsForChain:" + p00 + p01 + p10 + p11);
 99  
100     // terminating condition for the recursion
101     if (end0 - start0 == 1 && end1 - start1 == 1) {
102       ei.addIntersections(e, start0, mce.e, start1);
103       return;
104     }
105     // nothing to do if the envelopes of these chains don't overlap
106     if (! overlaps(start0, end0, mce, start1, end1)) return;
107  
108     // the chains overlap, so split each in half and iterate  (binary search)
109     int mid0 = (start0 + end0) / 2;
110     int mid1 = (start1 + end1) / 2;
111  
112     // Assert: mid != start or end (since we checked above for end - start <= 1)
113     // check terminating conditions before recursing
114     if (start0 < mid0) {
115       if (start1 < mid1) computeIntersectsForChain(start0, mid0, mce, start1,  mid1, ei);
116       if (mid1 < end1)   computeIntersectsForChain(start0, mid0, mce, mid1,    end1, ei);
117     }
118     if (mid0 < end0) {
119       if (start1 < mid1) computeIntersectsForChain(mid0,   end0, mce, start1,  mid1, ei);
120       if (mid1 < end1)   computeIntersectsForChain(mid0,   end0, mce, mid1,    end1, ei);
121     }
122   }
123   
124   /**
125    * Tests whether the envelopes of two chain sections overlap (intersect).
126    *
127    * @param start0
128    * @param end0
129    * @param mce
130    * @param start1
131    * @param end1
132    * @return true if the section envelopes overlap
133    */
134   private boolean overlaps(
135       int start0, int end0,
136       MonotoneChainEdge mce,
137       int start1, int end1)
138   {
139     return Envelope.intersects(pts[start0], pts[end0], mce.pts[start1], mce.pts[end1]);
140   }
141  
142 }
143