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.operation;
035:
036: import java.util.*;
037: import com.vividsolutions.jts.geom.*;
038: import com.vividsolutions.jts.geomgraph.*;
039: import com.vividsolutions.jts.algorithm.*;
040: import com.vividsolutions.jts.geomgraph.index.SegmentIntersector;
041:
042: /**
043: * Tests whether a <code>Geometry</code> is simple.
044: * In general, the SFS specification of simplicity
045: * follows the rule:
046: * <ul>
047: * <li> A Geometry is simple if and only if the only self-intersections are at
048: * boundary points.
049: * </ul>
050: * This definition relies on the definition of boundary points.
051: * The SFS uses the Mod-2 rule to determine which points are on the boundary of
052: * lineal geometries, but this class supports
053: * using other {@link BoundaryNodeRule}s as well.
054: * <p>
055: * Simplicity is defined for each {@link Geometry} subclass as follows:
056: * <ul>
057: * <li>Valid polygonal geometries are simple by definition, so
058: * <code>isSimple</code> trivially returns true.
059: * (Hint: in order to check if a polygonal geometry has self-intersections,
060: * use {@link Geometry#isValid}).
061: * <li>Linear geometries are simple iff they do not self-intersect at points
062: * other than boundary points.
063: * (Using the Mod-2 rule, this means that closed linestrings
064: * cannot be touched at their endpoints, since these are
065: * interior points, not boundary points).
066: * <li>Zero-dimensional geometries (points) are simple iff they have no
067: * repeated points.
068: * <li>Empty <code>Geometry</code>s are always simple
069: * </ul>
070: *
071: * @see BoundaryNodeRule
072: *
073: * @version 1.7
074: */
075: public class IsSimpleOp {
076: private Geometry geom;
077: private boolean isClosedEndpointsInInterior = true;
078: private Coordinate nonSimpleLocation = null;
079:
080: /**
081: * Creates a simplicity checker using the default SFS Mod-2 Boundary Node Rule
082: *
083: * @deprecated use IsSimpleOp(Geometry)
084: */
085: public IsSimpleOp() {
086: }
087:
088: /**
089: * Creates a simplicity checker using the default SFS Mod-2 Boundary Node Rule
090: *
091: * @param geom the geometry to test
092: */
093: public IsSimpleOp(Geometry geom) {
094: this .geom = geom;
095: }
096:
097: /**
098: * Creates a simplicity checker using a given {@link BoundaryNodeRule}
099: *
100: * @param geom the geometry to test
101: * @param boundaryNodeRule the rule to use.
102: */
103: public IsSimpleOp(Geometry geom, BoundaryNodeRule boundaryNodeRule) {
104: this .geom = geom;
105: isClosedEndpointsInInterior = !boundaryNodeRule.isInBoundary(2);
106: }
107:
108: /**
109: * Tests whether the geometry is simple.
110: *
111: * @return true if the geometry is simple
112: */
113: public boolean isSimple() {
114: nonSimpleLocation = null;
115: if (geom instanceof LineString)
116: return isSimpleLinearGeometry(geom);
117: if (geom instanceof MultiLineString)
118: return isSimpleLinearGeometry(geom);
119: if (geom instanceof MultiPoint)
120: return isSimpleMultiPoint((MultiPoint) geom);
121: // all other geometry types are simple by definition
122: return true;
123: }
124:
125: /**
126: * Gets a coordinate for the location where the geometry
127: * fails to be simple.
128: * (i.e. where it has a non-boundary self-intersection).
129: * {@link #isSimple} must be called before this method is called.
130: *
131: * @return a coordinate for the location of the non-boundary self-intersection
132: * @return null if the geometry is simple
133: */
134: public Coordinate getNonSimpleLocation() {
135: return nonSimpleLocation;
136: }
137:
138: /**
139: * Reports whether a {@link LineString} is simple.
140: *
141: * @param geom the lineal geometry to test
142: * @return true if the geometry is simple
143: * @deprecated use isSimple()
144: */
145: public boolean isSimple(LineString geom) {
146: return isSimpleLinearGeometry(geom);
147: }
148:
149: /**
150: * Reports whether a {@link MultiLineString} geometry is simple.
151: *
152: * @param geom the lineal geometry to test
153: * @return true if the geometry is simple
154: * @deprecated use isSimple()
155: */
156: public boolean isSimple(MultiLineString geom) {
157: return isSimpleLinearGeometry(geom);
158: }
159:
160: /**
161: * A MultiPoint is simple iff it has no repeated points
162: * @deprecated use isSimple()
163: */
164: public boolean isSimple(MultiPoint mp) {
165: return isSimpleMultiPoint(mp);
166: }
167:
168: private boolean isSimpleMultiPoint(MultiPoint mp) {
169: if (mp.isEmpty())
170: return true;
171: Set points = new TreeSet();
172: for (int i = 0; i < mp.getNumGeometries(); i++) {
173: Point pt = (Point) mp.getGeometryN(i);
174: Coordinate p = pt.getCoordinate();
175: if (points.contains(p)) {
176: nonSimpleLocation = p;
177: return false;
178: }
179: points.add(p);
180: }
181: return true;
182: }
183:
184: private boolean isSimpleLinearGeometry(Geometry geom) {
185: if (geom.isEmpty())
186: return true;
187: GeometryGraph graph = new GeometryGraph(0, geom);
188: LineIntersector li = new RobustLineIntersector();
189: SegmentIntersector si = graph.computeSelfNodes(li, true);
190: // if no self-intersection, must be simple
191: if (!si.hasIntersection())
192: return true;
193: if (si.hasProperIntersection()) {
194: nonSimpleLocation = si.getProperIntersectionPoint();
195: return false;
196: }
197: if (hasNonEndpointIntersection(graph))
198: return false;
199: if (isClosedEndpointsInInterior) {
200: if (hasClosedEndpointIntersection(graph))
201: return false;
202: }
203: return true;
204: }
205:
206: /**
207: * For all edges, check if there are any intersections which are NOT at an endpoint.
208: * The Geometry is not simple if there are intersections not at endpoints.
209: */
210: private boolean hasNonEndpointIntersection(GeometryGraph graph) {
211: for (Iterator i = graph.getEdgeIterator(); i.hasNext();) {
212: Edge e = (Edge) i.next();
213: int maxSegmentIndex = e.getMaximumSegmentIndex();
214: for (Iterator eiIt = e.getEdgeIntersectionList().iterator(); eiIt
215: .hasNext();) {
216: EdgeIntersection ei = (EdgeIntersection) eiIt.next();
217: if (!ei.isEndPoint(maxSegmentIndex)) {
218: nonSimpleLocation = ei.getCoordinate();
219: return true;
220: }
221: }
222: }
223: return false;
224: }
225:
226: private static class EndpointInfo {
227: Coordinate pt;
228: boolean isClosed;
229: int degree;
230:
231: public EndpointInfo(Coordinate pt) {
232: this .pt = pt;
233: isClosed = false;
234: degree = 0;
235: }
236:
237: public Coordinate getCoordinate() {
238: return pt;
239: }
240:
241: public void addEndpoint(boolean isClosed) {
242: degree++;
243: this .isClosed |= isClosed;
244: }
245: }
246:
247: /**
248: * Tests that no edge intersection is the endpoint of a closed line.
249: * This ensures that closed lines are not touched at their endpoint,
250: * which is an interior point according to the Mod-2 rule
251: * To check this we compute the degree of each endpoint.
252: * The degree of endpoints of closed lines
253: * must be exactly 2.
254: */
255: private boolean hasClosedEndpointIntersection(GeometryGraph graph) {
256: Map endPoints = new TreeMap();
257: for (Iterator i = graph.getEdgeIterator(); i.hasNext();) {
258: Edge e = (Edge) i.next();
259: int maxSegmentIndex = e.getMaximumSegmentIndex();
260: boolean isClosed = e.isClosed();
261: Coordinate p0 = e.getCoordinate(0);
262: addEndpoint(endPoints, p0, isClosed);
263: Coordinate p1 = e.getCoordinate(e.getNumPoints() - 1);
264: addEndpoint(endPoints, p1, isClosed);
265: }
266:
267: for (Iterator i = endPoints.values().iterator(); i.hasNext();) {
268: EndpointInfo eiInfo = (EndpointInfo) i.next();
269: if (eiInfo.isClosed && eiInfo.degree != 2) {
270: nonSimpleLocation = eiInfo.getCoordinate();
271: return true;
272: }
273: }
274: return false;
275: }
276:
277: /**
278: * Add an endpoint to the map, creating an entry for it if none exists
279: */
280: private void addEndpoint(Map endPoints, Coordinate p,
281: boolean isClosed) {
282: EndpointInfo eiInfo = (EndpointInfo) endPoints.get(p);
283: if (eiInfo == null) {
284: eiInfo = new EndpointInfo(p);
285: endPoints.put(p, eiInfo);
286: }
287: eiInfo.addEndpoint(isClosed);
288: }
289:
290: }
|