001:
002: /*
003: * The JTS Topology Suite is a collection of Java classes that
004: * implement the fundamental operations required to validate a given
005: * geo-spatial data set to a known topological specification.
006: *
007: * Copyright (C) 2001 Vivid Solutions
008: *
009: * This library is free software; you can redistribute it and/or
010: * modify it under the terms of the GNU Lesser General Public
011: * License as published by the Free Software Foundation; either
012: * version 2.1 of the License, or (at your option) any later version.
013: *
014: * This library is distributed in the hope that it will be useful,
015: * but WITHOUT ANY WARRANTY; without even the implied warranty of
016: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
017: * Lesser General Public License for more details.
018: *
019: * You should have received a copy of the GNU Lesser General Public
020: * License along with this library; if not, write to the Free Software
021: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
022: *
023: * For more information, contact:
024: *
025: * Vivid Solutions
026: * Suite #1A
027: * 2328 Government Street
028: * Victoria BC V8T 5G5
029: * Canada
030: *
031: * (250)385-6040
032: * www.vividsolutions.com
033: */
034: package com.vividsolutions.jts.algorithm;
035:
036: import java.util.Iterator;
037: import com.vividsolutions.jts.geom.*;
038: import com.vividsolutions.jts.geomgraph.GeometryGraph;
039:
040: /**
041: * Computes the topological relationship ({@link Location})
042: * of a single point to a {@link Geometry}.
043: * The algorithm obeys the <i>SFS Boundary Determination Rule</i>
044: * to determine whether the point lies on the boundary or not.
045: * <p>
046: * Notes:
047: * <ul>
048: * <li>{@link LinearRing}s do not enclose any area - points inside the ring are still in the EXTERIOR of the ring.
049: * </ul>
050: * Instances of this class are not reentrant.
051: *
052: * @version 1.7
053: */
054: public class PointLocator {
055: // default is to use OGC SFS rule
056: private BoundaryNodeRule boundaryRule = BoundaryNodeRule.ENDPOINT_BOUNDARY_RULE; //OGC_SFS_BOUNDARY_RULE;
057:
058: private boolean isIn; // true if the point lies in or on any Geometry element
059: private int numBoundaries; // the number of sub-elements whose boundaries the point lies in
060:
061: public PointLocator() {
062: }
063:
064: public PointLocator(BoundaryNodeRule boundaryRule) {
065: if (boundaryRule == null)
066: throw new IllegalArgumentException("Rule must be non-null");
067: this .boundaryRule = boundaryRule;
068: }
069:
070: /**
071: * Convenience method to test a point for intersection with
072: * a Geometry
073: * @param p the coordinate to test
074: * @param geom the Geometry to test
075: * @return <code>true</code> if the point is in the interior or boundary of the Geometry
076: */
077: public boolean intersects(Coordinate p, Geometry geom) {
078: return locate(p, geom) != Location.EXTERIOR;
079: }
080:
081: /**
082: * Computes the topological relationship ({@link Location}) of a single point
083: * to a Geometry.
084: * It handles both single-element
085: * and multi-element Geometries.
086: * The algorithm for multi-part Geometries
087: * takes into account the SFS Boundary Determination Rule.
088: *
089: * @return the {@link Location} of the point relative to the input Geometry
090: */
091: public int locate(Coordinate p, Geometry geom) {
092: if (geom.isEmpty())
093: return Location.EXTERIOR;
094:
095: if (geom instanceof LineString) {
096: return locate(p, (LineString) geom);
097: } else if (geom instanceof Polygon) {
098: return locate(p, (Polygon) geom);
099: }
100:
101: isIn = false;
102: numBoundaries = 0;
103: computeLocation(p, geom);
104: if (boundaryRule.isInBoundary(numBoundaries))
105: return Location.BOUNDARY;
106: if (numBoundaries > 0 || isIn)
107: return Location.INTERIOR;
108:
109: return Location.EXTERIOR;
110: }
111:
112: private void computeLocation(Coordinate p, Geometry geom) {
113: if (geom instanceof LineString) {
114: updateLocationInfo(locate(p, (LineString) geom));
115: } else if (geom instanceof Polygon) {
116: updateLocationInfo(locate(p, (Polygon) geom));
117: } else if (geom instanceof MultiLineString) {
118: MultiLineString ml = (MultiLineString) geom;
119: for (int i = 0; i < ml.getNumGeometries(); i++) {
120: LineString l = (LineString) ml.getGeometryN(i);
121: updateLocationInfo(locate(p, l));
122: }
123: } else if (geom instanceof MultiPolygon) {
124: MultiPolygon mpoly = (MultiPolygon) geom;
125: for (int i = 0; i < mpoly.getNumGeometries(); i++) {
126: Polygon poly = (Polygon) mpoly.getGeometryN(i);
127: updateLocationInfo(locate(p, poly));
128: }
129: } else if (geom instanceof GeometryCollection) {
130: Iterator geomi = new GeometryCollectionIterator(
131: (GeometryCollection) geom);
132: while (geomi.hasNext()) {
133: Geometry g2 = (Geometry) geomi.next();
134: if (g2 != geom)
135: computeLocation(p, g2);
136: }
137: }
138: }
139:
140: private void updateLocationInfo(int loc) {
141: if (loc == Location.INTERIOR)
142: isIn = true;
143: if (loc == Location.BOUNDARY)
144: numBoundaries++;
145: }
146:
147: private int locate(Coordinate p, LineString l) {
148: Coordinate[] pt = l.getCoordinates();
149: if (!l.isClosed()) {
150: if (p.equals(pt[0]) || p.equals(pt[pt.length - 1])) {
151: return Location.BOUNDARY;
152: }
153: }
154: if (CGAlgorithms.isOnLine(p, pt))
155: return Location.INTERIOR;
156: return Location.EXTERIOR;
157: }
158:
159: private int locateInPolygonRing(Coordinate p, LinearRing ring) {
160: // can this test be folded into isPointInRing ?
161: if (CGAlgorithms.isOnLine(p, ring.getCoordinates())) {
162: return Location.BOUNDARY;
163: }
164: if (CGAlgorithms.isPointInRing(p, ring.getCoordinates()))
165: return Location.INTERIOR;
166: return Location.EXTERIOR;
167: }
168:
169: private int locate(Coordinate p, Polygon poly) {
170: if (poly.isEmpty())
171: return Location.EXTERIOR;
172: LinearRing shell = (LinearRing) poly.getExteriorRing();
173:
174: int shellLoc = locateInPolygonRing(p, shell);
175: if (shellLoc == Location.EXTERIOR)
176: return Location.EXTERIOR;
177: if (shellLoc == Location.BOUNDARY)
178: return Location.BOUNDARY;
179: // now test if the point lies in or on the holes
180: for (int i = 0; i < poly.getNumInteriorRing(); i++) {
181: LinearRing hole = (LinearRing) poly.getInteriorRingN(i);
182: int holeLoc = locateInPolygonRing(p, hole);
183: if (holeLoc == Location.INTERIOR)
184: return Location.EXTERIOR;
185: if (holeLoc == Location.BOUNDARY)
186: return Location.BOUNDARY;
187: }
188: return Location.INTERIOR;
189: }
190:
191: }
|