Doc Classic

Class PointLocator

  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.algorithm;
 13  
 14 import java.util.Iterator;
 15  
 16 import org.locationtech.jts.geom.Coordinate;
 17 import org.locationtech.jts.geom.CoordinateSequence;
 18 import org.locationtech.jts.geom.Geometry;
 19 import org.locationtech.jts.geom.GeometryCollection;
 20 import org.locationtech.jts.geom.GeometryCollectionIterator;
 21 import org.locationtech.jts.geom.LineString;
 22 import org.locationtech.jts.geom.LinearRing;
 23 import org.locationtech.jts.geom.Location;
 24 import org.locationtech.jts.geom.MultiLineString;
 25 import org.locationtech.jts.geom.MultiPolygon;
 26 import org.locationtech.jts.geom.Point;
 27 import org.locationtech.jts.geom.Polygon;
 28  
 29 /**
 30  * Computes the topological ({@link Location})
 31  * of a single point to a {@link Geometry}.
 32  * A {@link BoundaryNodeRule} may be specified 
 33  * to control the evaluation of whether the point lies on the boundary or not
 34  * The default rule is to use the the <i>SFS Boundary Determination Rule</i>
 35  * <p>
 36  * Notes:
 37  * <ul>
 38  * <li>{@link LinearRing}s do not enclose any area - points inside the ring are still in the EXTERIOR of the ring.
 39  * </ul>
 40  * Instances of this class are not reentrant.
 41  *
 42  * @version 1.7
 43  */
 44 public class PointLocator
 45 {
 46   // default is to use OGC SFS rule
 47   private BoundaryNodeRule boundaryRule = 
 48       //BoundaryNodeRule.ENDPOINT_BOUNDARY_RULE; 
 49       BoundaryNodeRule.OGC_SFS_BOUNDARY_RULE;
 50  
 51   private boolean isIn;         // true if the point lies in or on any Geometry element
 52   private int numBoundaries;    // the number of sub-elements whose boundaries the point lies in
 53  
 54   public PointLocator() {
 55   }
 56  
 57   public PointLocator(BoundaryNodeRule boundaryRule)
 58   {
 59     if (boundaryRule == null)
 60       throw new IllegalArgumentException("Rule must be non-null");
 61     this.boundaryRule = boundaryRule;
 62   }
 63  
 64   /**
 65    * Convenience method to test a point for intersection with
 66    * a Geometry
 67    * @param p the coordinate to test
 68    * @param geom the Geometry to test
 69    * @return <code>true</code> if the point is in the interior or boundary of the Geometry
 70    */
 71   public boolean intersects(Coordinate p, Geometry geom)
 72   {
 73     return locate(p, geom) != Location.EXTERIOR;
 74   }
 75  
 76   /**
 77    * Computes the topological relationship ({@link Location}) of a single point
 78    * to a Geometry.
 79    * It handles both single-element
 80    * and multi-element Geometries.
 81    * The algorithm for multi-part Geometries
 82    * takes into account the SFS Boundary Determination Rule.
 83    *
 84    * @return the {@link Location} of the point relative to the input Geometry
 85    */
 86   public int locate(Coordinate p, Geometry geom)
 87   {
 88     if (geom.isEmpty()) return Location.EXTERIOR;
 89  
 90     if (geom instanceof LineString) {
 91       return locateOnLineString(p, (LineString) geom);
 92     }
 93     else if (geom instanceof Polygon) {
 94       return locateInPolygon(p, (Polygon) geom);
 95     }
 96  
 97     isIn = false;
 98     numBoundaries = 0;
 99     computeLocation(p, geom);
100     if (boundaryRule.isInBoundary(numBoundaries))
101       return Location.BOUNDARY;
102     if (numBoundaries > 0 || isIn)
103       return Location.INTERIOR;
104  
105     return Location.EXTERIOR;
106   }
107  
108   private void computeLocation(Coordinate p, Geometry geom)
109   {
110     if (geom instanceof Point) {
111       updateLocationInfo(locateOnPoint(p, (Point) geom));
112     }
113     if (geom instanceof LineString) {
114       updateLocationInfo(locateOnLineString(p, (LineString) geom));
115     }
116     else if (geom instanceof Polygon) {
117       updateLocationInfo(locateInPolygon(p, (Polygon) geom));
118     }
119     else if (geom instanceof MultiLineString) {
120       MultiLineString ml = (MultiLineString) geom;
121       for (int i = 0; i < ml.getNumGeometries(); i++) {
122         LineString l = (LineString) ml.getGeometryN(i);
123         updateLocationInfo(locateOnLineString(p, l));
124       }
125     }
126     else if (geom instanceof MultiPolygon) {
127       MultiPolygon mpoly = (MultiPolygon) geom;
128       for (int i = 0; i < mpoly.getNumGeometries(); i++) {
129         Polygon poly = (Polygon) mpoly.getGeometryN(i);
130         updateLocationInfo(locateInPolygon(p, poly));
131       }
132     }
133     else if (geom instanceof GeometryCollection) {
134       Iterator geomi = new GeometryCollectionIterator((GeometryCollection) geom);
135       while (geomi.hasNext()) {
136         Geometry g2 = (Geometry) geomi.next();
137         if (g2 != geom)
138           computeLocation(p, g2);
139       }
140     }
141   }
142  
143   private void updateLocationInfo(int loc)
144   {
145     if (loc == Location.INTERIOR) isIn = true;
146     if (loc == Location.BOUNDARY) numBoundaries++;
147   }
148  
149   private int locateOnPoint(Coordinate p, Point pt)
150   {
151       // no point in doing envelope test, since equality test is just as fast
152       
153     Coordinate ptCoord = pt.getCoordinate();
154     if (ptCoord.equals2D(p))
155       return Location.INTERIOR;
156     return Location.EXTERIOR;
157   }
158  
159   private int locateOnLineString(Coordinate p, LineString l)
160   {
161     // bounding-box check
162     if (! l.getEnvelopeInternal().intersects(p)) return Location.EXTERIOR;
163     
164     CoordinateSequence seq = l.getCoordinateSequence();
165     if (! l.isClosed()) {
166           if (p.equals(seq.getCoordinate(0))
167           || p.equals(seq.getCoordinate(seq.size() - 1)) ) {
168         return Location.BOUNDARY;
169       }
170     }
171     if (PointLocation.isOnLine(p, seq)) {
172       return Location.INTERIOR;
173     }
174     return Location.EXTERIOR;
175   }
176  
177   private int locateInPolygonRing(Coordinate p, LinearRing ring)
178   {
179       // bounding-box check
180       if (! ring.getEnvelopeInternal().intersects(p)) return Location.EXTERIOR;
181  
182       return PointLocation.locateInRing(p, ring.getCoordinates());
183   }
184  
185   private int locateInPolygon(Coordinate p, Polygon poly)
186   {
187     if (poly.isEmpty()) return Location.EXTERIOR;
188  
189     LinearRing shell = poly.getExteriorRing();
190  
191     int shellLoc = locateInPolygonRing(p, shell);
192     if (shellLoc == Location.EXTERIOR) return Location.EXTERIOR;
193     if (shellLoc == Location.BOUNDARY) return Location.BOUNDARY;
194     // now test if the point lies in or on the holes
195     for (int i = 0; i < poly.getNumInteriorRing(); i++) {
196       LinearRing hole = poly.getInteriorRingN(i);
197       int holeLoc = locateInPolygonRing(p, hole);
198       if (holeLoc == Location.INTERIOR) return Location.EXTERIOR;
199       if (holeLoc == Location.BOUNDARY) return Location.BOUNDARY;
200     }
201     return Location.INTERIOR;
202   }
203  
204  
205  
206 }
207