Doc Classic

Class MCIndexSegmentSetMutualIntersector

  1 /*
  2  * Copyright (c) 2016 Vivid Solutions.
  3  *
  4  * All rights reserved. This program and the accompanying materials
  5  * are made available under the terms of the Eclipse Public License 2.0
  6  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
  7  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
  8  * and the Eclipse Distribution License is available at
  9  *
 10  * http://www.eclipse.org/org/documents/edl-v10.php.
 11  */
 12 package org.locationtech.jts.noding;
 13  
 14 import java.util.ArrayList;
 15 import java.util.Collection;
 16 import java.util.Iterator;
 17 import java.util.List;
 18  
 19 import org.locationtech.jts.index.SpatialIndex;
 20 import org.locationtech.jts.index.chain.MonotoneChain;
 21 import org.locationtech.jts.index.chain.MonotoneChainBuilder;
 22 import org.locationtech.jts.index.chain.MonotoneChainOverlapAction;
 23 import org.locationtech.jts.index.strtree.STRtree;
 24  
 25  
 26 /**
 27  * Intersects two sets of {@link SegmentString}s using a index based
 28  * on {@link MonotoneChain}s and a {@link SpatialIndex}.
 29  *
 30  * Thread-safe and immutable.
 31  * 
 32  * @version 1.7
 33  */
 34 public class MCIndexSegmentSetMutualIntersector implements SegmentSetMutualIntersector
 35 {
 36   /**
 37   * The {@link SpatialIndex} used should be something that supports
 38   * envelope (range) queries efficiently (such as a 
 39   * {@link org.locationtech.jts.index.quadtree.Quadtree}
 40   * or {@link STRtree}.
 41   */
 42   private STRtree index = new STRtree();
 43  
 44   /**
 45    * Constructs a new intersector for a given set of {@link SegmentString}s.
 46    * 
 47    * @param baseSegStrings the base segment strings to intersect
 48    */
 49   public MCIndexSegmentSetMutualIntersector(Collection baseSegStrings)
 50   {
 51       initBaseSegments(baseSegStrings);
 52   }
 53  
 54   /** 
 55    * Gets the index constructed over the base segment strings.
 56    * 
 57    * NOTE: To retain thread-safety, treat returned value as immutable!
 58    * 
 59    * @return the constructed index
 60    */
 61   public SpatialIndex getIndex() { return index; }
 62  
 63   private void initBaseSegments(Collection segStrings)
 64   {
 65     for (Iterator i = segStrings.iterator(); i.hasNext(); ) {
 66       addToIndex((SegmentString) i.next());
 67     }
 68     // build index to ensure thread-safety
 69     index.build();
 70   }
 71   
 72   private void addToIndex(SegmentString segStr)
 73   {
 74     List segChains = MonotoneChainBuilder.getChains(segStr.getCoordinates(), segStr);
 75     for (Iterator i = segChains.iterator(); i.hasNext(); ) {
 76       MonotoneChain mc = (MonotoneChain) i.next();
 77       index.insert(mc.getEnvelope(), mc);
 78     }
 79   }
 80  
 81   /**
 82    * Calls {@link SegmentIntersector#processIntersections(SegmentString, int, SegmentString, int)} 
 83    * for all <i>candidate</i> intersections between
 84    * the given collection of SegmentStrings and the set of indexed segments. 
 85    * 
 86    * @param a set of segments to intersect
 87    * @param the segment intersector to use
 88    */
 89   public void process(Collection segStrings, SegmentIntersector segInt)
 90   {
 91       List monoChains = new ArrayList();
 92     for (Iterator i = segStrings.iterator(); i.hasNext(); ) {
 93       addToMonoChains((SegmentString) i.next(), monoChains);
 94     }
 95     intersectChains(monoChains, segInt);
 96 //    System.out.println("MCIndexBichromaticIntersector: # chain overlaps = " + nOverlaps);
 97 //    System.out.println("MCIndexBichromaticIntersector: # oct chain overlaps = " + nOctOverlaps);
 98   }
 99  
100   private void addToMonoChains(SegmentString segStr, List monoChains)
101   {
102     List segChains = MonotoneChainBuilder.getChains(segStr.getCoordinates(), segStr);
103     for (Iterator i = segChains.iterator(); i.hasNext(); ) {
104       MonotoneChain mc = (MonotoneChain) i.next();
105       monoChains.add(mc);
106     }
107   }
108  
109   private void intersectChains(List monoChains, SegmentIntersector segInt)
110   {
111     MonotoneChainOverlapAction overlapAction = new SegmentOverlapAction(segInt);
112  
113     for (Iterator i = monoChains.iterator(); i.hasNext(); ) {
114       MonotoneChain queryChain = (MonotoneChain) i.next();
115       List overlapChains = index.query(queryChain.getEnvelope());
116       for (Iterator j = overlapChains.iterator(); j.hasNext(); ) {
117         MonotoneChain testChain = (MonotoneChain) j.next();
118         queryChain.computeOverlaps(testChain, overlapAction);
119         if (segInt.isDone()) return;
120       }
121     }
122   }
123  
124   public static class SegmentOverlapAction
125       extends MonotoneChainOverlapAction
126   {
127     private SegmentIntersector si = null;
128  
129     public SegmentOverlapAction(SegmentIntersector si)
130     {
131       this.si = si;
132     }
133  
134     public void overlap(MonotoneChain mc1, int start1, MonotoneChain mc2, int start2)
135     {
136       SegmentString ss1 = (SegmentString) mc1.getContext();
137       SegmentString ss2 = (SegmentString) mc2.getContext();
138       si.processIntersections(ss1, start1, ss2, start2);
139     }
140  
141   }
142 }
143