Doc Classic

Class IndexedNestedRingTester

  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.operation.valid;
 13  
 14 import java.util.ArrayList;
 15 import java.util.List;
 16  
 17 import org.locationtech.jts.algorithm.PointLocation;
 18 import org.locationtech.jts.algorithm.locate.IndexedPointInAreaLocator;
 19 import org.locationtech.jts.geom.Coordinate;
 20 import org.locationtech.jts.geom.Envelope;
 21 import org.locationtech.jts.geom.LinearRing;
 22 import org.locationtech.jts.geom.Location;
 23 import org.locationtech.jts.geomgraph.GeometryGraph;
 24 import org.locationtech.jts.index.SpatialIndex;
 25 import org.locationtech.jts.index.strtree.STRtree;
 26  
 27 /**
 28  * Tests whether any of a set of {@link LinearRing}s are
 29  * nested inside another ring in the set, using a spatial
 30  * index to speed up the comparisons.
 31  *
 32  * @version 1.7
 33  */
 34 public class IndexedNestedRingTester
 35 {
 36   private GeometryGraph graph;  // used to find non-node vertices
 37   private List rings = new ArrayList();
 38   private Envelope totalEnv = new Envelope();
 39   private SpatialIndex index;
 40   private Coordinate nestedPt;
 41  
 42   public IndexedNestedRingTester(GeometryGraph graph)
 43   {
 44     this.graph = graph;
 45   }
 46  
 47   public Coordinate getNestedPoint() { return nestedPt; }
 48  
 49   public void add(LinearRing ring)
 50   {
 51     rings.add(ring);
 52     totalEnv.expandToInclude(ring.getEnvelopeInternal());
 53   }
 54  
 55   public boolean isNonNested()
 56   {
 57     buildIndex();
 58  
 59     for (int i = 0; i < rings.size(); i++) {
 60       LinearRing innerRing = (LinearRing) rings.get(i);
 61       Coordinate[] innerRingPts = innerRing.getCoordinates();
 62  
 63       List results = index.query(innerRing.getEnvelopeInternal());
 64 //System.out.println(results.size());
 65       for (int j = 0; j < results.size(); j++) {
 66         LinearRing searchRing = (LinearRing) results.get(j);
 67         Coordinate[] searchRingPts = searchRing.getCoordinates();
 68  
 69         if (innerRing == searchRing)
 70           continue;
 71  
 72         if (! innerRing.getEnvelopeInternal().intersects(searchRing.getEnvelopeInternal()))
 73           continue;
 74  
 75         Coordinate innerRingPt = IsValidOp.findPtNotNode(innerRingPts, searchRing, graph);
 76         
 77         /**
 78          * If no non-node pts can be found, this means
 79          * that the searchRing touches ALL of the innerRing vertices.
 80          * This indicates an invalid polygon, since either
 81          * the two holes create a disconnected interior, 
 82          * or they touch in an infinite number of points 
 83          * (i.e. along a line segment).
 84          * Both of these cases are caught by other tests,
 85          * so it is safe to simply skip this situation here.
 86          */
 87         if (innerRingPt == null)
 88           continue;
 89  
 90         boolean isInside = PointLocation.isInRing(innerRingPt, searchRingPts);
 91         if (isInside) {
 92           nestedPt = innerRingPt;
 93           return false;
 94         }
 95       }
 96     }
 97     return true;
 98   }
 99  
100   /**
101    * An implementation of an optimization introduced in GEOS
102    * https://github.com/libgeos/geos/pull/255/commits/1bf16cdf5a4827b483a1f712e0597ccb243f58cb
103    * 
104    * Not used for now, since improvement is small and very data-dependent.
105    * 
106    * @return
107    */
108   /*
109   private boolean isNonNestedWithIndex()
110   {
111     buildIndex();
112
113     for (int i = 0; i < rings.size(); i++) {
114       LinearRing outerRing = (LinearRing) rings.get(i);
115       Coordinate[] outerRingPts = outerRing.getCoordinates();
116
117       IndexedPointInAreaLocator ptLocator = new IndexedPointInAreaLocator(outerRing);
118       List results = index.query(outerRing.getEnvelopeInternal());
119 //System.out.println(results.size());
120       for (int j = 0; j < results.size(); j++) {
121         LinearRing searchRing = (LinearRing) results.get(j);
122         if (outerRing == searchRing)
123           continue;
124         
125         if (! outerRing.getEnvelopeInternal().intersects(searchRing.getEnvelopeInternal()))
126           continue;
127
128         Coordinate[] searchRingPts = searchRing.getCoordinates();
129         Coordinate innerRingPt = IsValidOp.findPtNotNode(searchRingPts, outerRing, graph);
130         
131         if (innerRingPt == null)
132           continue;
133
134         boolean isInside = Location.EXTERIOR != ptLocator.locate(innerRingPt);
135         //boolean isInside = PointLocation.isInRing(innerRingPt, outerRingPts);
136         
137         if (isInside) {
138           nestedPt = innerRingPt;
139           return false;
140         }
141       }
142     }
143     return true;
144   }
145   */
146  
147   private void buildIndex()
148   {
149     index = new STRtree();
150  
151     for (int i = 0; i < rings.size(); i++) {
152       LinearRing ring = (LinearRing) rings.get(i);
153       Envelope env = ring.getEnvelopeInternal();
154       index.insert(env, ring);
155     }
156   }
157 }
158