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.locate; 13 14 import java.util.Iterator; 15 16 import org.locationtech.jts.algorithm.PointLocation; 17 import org.locationtech.jts.geom.Coordinate; 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.LinearRing; 22 import org.locationtech.jts.geom.Location; 23 import org.locationtech.jts.geom.Polygon; 24 import org.locationtech.jts.geom.Polygonal; 25 26 27 /** 28 * Computes the location of points 29 * relative to a {@link Polygonal} {@link Geometry}, 30 * using a simple <tt>O(n)</tt> algorithm. 31 * <p> 32 * The algorithm used reports 33 * if a point lies in the interior, exterior, 34 * or exactly on the boundary of the Geometry. 35 * <p> 36 * Instance methods are provided to implement 37 * the interface {@link PointInAreaLocator}. 38 * However, they provide no performance 39 * advantage over the class methods. 40 * <p> 41 * This algorithm is suitable for use in cases where 42 * only a few points will be tested. 43 * If many points will be tested, 44 * {@link IndexedPointInAreaLocator} may provide better performance. 45 * 46 * @version 1.7 47 */ 48 public class SimplePointInAreaLocator 49 implements PointOnGeometryLocator 50 { 51 52 /** 53 * Determines the {@link Location} of a point in an areal {@link Geometry}. 54 * The return value is one of: 55 * <ul> 56 * <li>{@link Location.INTERIOR} if the point is in the geometry interior 57 * <li>{@link Location.BOUNDARY} if the point lies exactly on the boundary 58 * <li>{@link Location.EXTERIOR} if the point is outside the geometry 59 * </ul> 60 * 61 * @param p the point to test 62 * @param geom the areal geometry to test 63 * @return the Location of the point in the geometry 64 */ locate(Coordinate p, Geometry geom)65 public static int locate(Coordinate p, Geometry geom) 66 { 67 if (geom.isEmpty()) return Location.EXTERIOR; 68 /** 69 * Do a fast check against the geometry envelope first 70 */ 71 if (! geom.getEnvelopeInternal().intersects(p)) 72 return Location.EXTERIOR; 73 74 return locateInGeometry(p, geom); 75 } 76 77 /** 78 * Determines whether a point is contained in a {@link Geometry}, 79 * or lies on its boundary. 80 * This is a convenience method for 81 * <pre> 82 * Location.EXTERIOR != locate(p, geom) 83 * </pre> 84 * 85 * @param p the point to test 86 * @param geom the geometry to test 87 * @return true if the point lies in or on the geometry 88 */ isContained(Coordinate p, Geometry geom)89 public static boolean isContained(Coordinate p, Geometry geom) { 90 return Location.EXTERIOR != locate(p, geom); 91 } 92 locateInGeometry(Coordinate p, Geometry geom)93 private static int locateInGeometry(Coordinate p, Geometry geom) 94 { 95 if (geom instanceof Polygon) { 96 return locatePointInPolygon(p, (Polygon) geom); 97 } 98 99 if (geom instanceof GeometryCollection) { 100 Iterator geomi = new GeometryCollectionIterator((GeometryCollection) geom); 101 while (geomi.hasNext()) { 102 Geometry g2 = (Geometry) geomi.next(); 103 if (g2 != geom) { 104 int loc = locateInGeometry(p, g2); 105 if (loc != Location.EXTERIOR) return loc; 106 } 107 } 108 } 109 return Location.EXTERIOR; 110 } 111 112 /** 113 * Determines the {@link Location} of a point in a {@link Polygon}. 114 * The return value is one of: 115 * <ul> 116 * <li>{@link Location.INTERIOR} if the point is in the geometry interior 117 * <li>{@link Location.BOUNDARY} if the point lies exactly on the boundary 118 * <li>{@link Location.EXTERIOR} if the point is outside the geometry 119 * </ul> 120 * 121 * This method is provided for backwards compatibility only. 122 * Use {@link #locate(Coordinate, Geometry)} instead. 123 * 124 * @param p the point to test 125 * @param poly the geometry to test 126 * @return the Location of the point in the polygon 127 * 128 */ locatePointInPolygon(Coordinate p, Polygon poly)129 public static int locatePointInPolygon(Coordinate p, Polygon poly) 130 { 131 if (poly.isEmpty()) return Location.EXTERIOR; 132 LinearRing shell = poly.getExteriorRing(); 133 int shellLoc = locatePointInRing(p, shell); 134 if (shellLoc != Location.INTERIOR) return shellLoc; 135 136 // now test if the point lies in or on the holes 137 for (int i = 0; i < poly.getNumInteriorRing(); i++) { 138 LinearRing hole = poly.getInteriorRingN(i); 139 int holeLoc = locatePointInRing(p, hole); 140 if (holeLoc == Location.BOUNDARY) return Location.BOUNDARY; 141 if (holeLoc == Location.INTERIOR) return Location.EXTERIOR; 142 // if in EXTERIOR of this hole keep checking the other ones 143 } 144 // If not in any hole must be inside polygon 145 return Location.INTERIOR; 146 } 147 148 /** 149 * Determines whether a point lies in a {@link Polygon}. 150 * If the point lies on the polygon boundary it is 151 * considered to be inside. 152 * 153 * @param p the point to test 154 * @param poly the geometry to test 155 * @return true if the point lies in or on the polygon 156 */ containsPointInPolygon(Coordinate p, Polygon poly)157 public static boolean containsPointInPolygon(Coordinate p, Polygon poly) { 158 return Location.EXTERIOR != locatePointInPolygon(p, poly); 159 } 160 161 /** 162 * Determines whether a point lies in a LinearRing, 163 * using the ring envelope to short-circuit if possible. 164 * 165 * @param p the point to test 166 * @param ring a linear ring 167 * @return true if the point lies inside the ring 168 */ locatePointInRing(Coordinate p, LinearRing ring)169 private static int locatePointInRing(Coordinate p, LinearRing ring) 170 { 171 // short-circuit if point is not in ring envelope 172 if (! ring.getEnvelopeInternal().intersects(p)) 173 return Location.EXTERIOR; 174 return PointLocation.locateInRing(p, ring.getCoordinates()); 175 } 176 177 private Geometry geom; 178 179 /** 180 * Create an instance of a point-in-area locator, 181 * using the provided areal geometry. 182 * 183 * @param geom the areal geometry to locate in 184 */ SimplePointInAreaLocator(Geometry geom)185 public SimplePointInAreaLocator(Geometry geom) { 186 this.geom = geom; 187 } 188 189 /** 190 * Determines the {@link Location} of a point in an areal {@link Geometry}. 191 * The return value is one of: 192 * <ul> 193 * <li>{@link Location.INTERIOR} if the point is in the geometry interior 194 * <li>{@link Location.BOUNDARY} if the point lies exactly on the boundary 195 * <li>{@link Location.EXTERIOR} if the point is outside the geometry 196 * </ul> 197 * 198 * @param p the point to test 199 * @return the Location of the point in the geometry 200 */ locate(Coordinate p)201 public int locate(Coordinate p) { 202 return SimplePointInAreaLocator.locate(p, geom); 203 } 204 205 } 206