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.valid;
035:
036: import java.util.*;
037: import com.vividsolutions.jts.algorithm.*;
038: import com.vividsolutions.jts.geomgraph.*;
039: import com.vividsolutions.jts.geom.*;
040: import com.vividsolutions.jts.util.*;
041:
042: /**
043: * Implements the algorithsm required to compute the <code>isValid()</code> method
044: * for {@link Geometry}s.
045: * See the documentation for the various geometry types for a specification of validity.
046: *
047: * @version 1.7
048: */
049: public class IsValidOp {
050:
051: /**
052: * Checks whether a coordinate is valid for processing.
053: * Coordinates are valid iff their x and y ordinates are in the
054: * range of the floating point representation.
055: *
056: * @param coord the coordinate to validate
057: * @return <code>true</code> if the coordinate is valid
058: */
059: public static boolean isValid(Coordinate coord) {
060: if (Double.isNaN(coord.x))
061: return false;
062: if (Double.isInfinite(coord.x))
063: return false;
064: if (Double.isNaN(coord.y))
065: return false;
066: if (Double.isInfinite(coord.y))
067: return false;
068: return true;
069: }
070:
071: /**
072: * Find a point from the list of testCoords
073: * that is NOT a node in the edge for the list of searchCoords
074: *
075: * @return the point found, or <code>null</code> if none found
076: */
077: public static Coordinate findPtNotNode(Coordinate[] testCoords,
078: LinearRing searchRing, GeometryGraph graph) {
079: // find edge corresponding to searchRing.
080: Edge searchEdge = graph.findEdge(searchRing);
081: // find a point in the testCoords which is not a node of the searchRing
082: EdgeIntersectionList eiList = searchEdge
083: .getEdgeIntersectionList();
084: // somewhat inefficient - is there a better way? (Use a node map, for instance?)
085: for (int i = 0; i < testCoords.length; i++) {
086: Coordinate pt = testCoords[i];
087: if (!eiList.isIntersection(pt))
088: return pt;
089: }
090: return null;
091: }
092:
093: private Geometry parentGeometry; // the base Geometry to be validated
094: /**
095: * If the following condition is TRUE JTS will validate inverted shells and exverted holes
096: * (the ESRI SDE model)
097: */
098: private boolean isSelfTouchingRingFormingHoleValid = false;
099: private boolean isChecked = false;
100: private TopologyValidationError validErr;
101:
102: public IsValidOp(Geometry parentGeometry) {
103: this .parentGeometry = parentGeometry;
104: }
105:
106: /**
107: * Sets whether polygons using <b>Self-Touching Rings</b> to form
108: * holes are reported as valid.
109: * If this flag is set, the following Self-Touching conditions
110: * are treated as being valid:
111: * <ul>
112: * <li>the shell ring self-touches to create a hole touching the shell
113: * <li>a hole ring self-touches to create two holes touching at a point
114: * </ul>
115: * <p>
116: * The default (following the OGC SFS standard)
117: * is that this condition is <b>not</b> valid (<code>false</code>).
118: * <p>
119: * This does not affect whether Self-Touching Rings
120: * disconnecting the polygon interior are considered valid
121: * (these are considered to be <b>invalid</b> under the SFS, and many other
122: * spatial models as well).
123: * This includes "bow-tie" shells,
124: * which self-touch at a single point causing the interior to
125: * be disconnected,
126: * and "C-shaped" holes which self-touch at a single point causing an island to be formed.
127: *
128: * @param isValid states whether geometry with this condition is valid
129: */
130: public void setSelfTouchingRingFormingHoleValid(boolean isValid) {
131: isSelfTouchingRingFormingHoleValid = isValid;
132: }
133:
134: public boolean isValid() {
135: checkValid(parentGeometry);
136: return validErr == null;
137: }
138:
139: public TopologyValidationError getValidationError() {
140: checkValid(parentGeometry);
141: return validErr;
142: }
143:
144: private void checkValid(Geometry g) {
145: if (isChecked)
146: return;
147: validErr = null;
148:
149: // empty geometries are always valid!
150: if (g.isEmpty())
151: return;
152:
153: if (g instanceof Point)
154: checkValid((Point) g);
155: else if (g instanceof MultiPoint)
156: checkValid((MultiPoint) g);
157: // LineString also handles LinearRings
158: else if (g instanceof LinearRing)
159: checkValid((LinearRing) g);
160: else if (g instanceof LineString)
161: checkValid((LineString) g);
162: else if (g instanceof Polygon)
163: checkValid((Polygon) g);
164: else if (g instanceof MultiPolygon)
165: checkValid((MultiPolygon) g);
166: else if (g instanceof GeometryCollection)
167: checkValid((GeometryCollection) g);
168: else
169: throw new UnsupportedOperationException(g.getClass()
170: .getName());
171: }
172:
173: /**
174: * Checks validity of a Point.
175: */
176: private void checkValid(Point g) {
177: checkInvalidCoordinates(g.getCoordinates());
178: }
179:
180: /**
181: * Checks validity of a MultiPoint.
182: */
183: private void checkValid(MultiPoint g) {
184: checkInvalidCoordinates(g.getCoordinates());
185: }
186:
187: /**
188: * Checks validity of a LineString. Almost anything goes for linestrings!
189: */
190: private void checkValid(LineString g) {
191: checkInvalidCoordinates(g.getCoordinates());
192: if (validErr != null)
193: return;
194: GeometryGraph graph = new GeometryGraph(0, g);
195: checkTooFewPoints(graph);
196: }
197:
198: /**
199: * Checks validity of a LinearRing.
200: */
201: private void checkValid(LinearRing g) {
202: checkInvalidCoordinates(g.getCoordinates());
203: if (validErr != null)
204: return;
205: checkClosedRing(g);
206: if (validErr != null)
207: return;
208:
209: GeometryGraph graph = new GeometryGraph(0, g);
210: checkTooFewPoints(graph);
211: if (validErr != null)
212: return;
213: LineIntersector li = new RobustLineIntersector();
214: graph.computeSelfNodes(li, true);
215: checkNoSelfIntersectingRings(graph);
216: }
217:
218: /**
219: * Checks the validity of a polygon.
220: * Sets the validErr flag.
221: */
222: private void checkValid(Polygon g) {
223: checkInvalidCoordinates(g);
224: if (validErr != null)
225: return;
226: checkClosedRings(g);
227: if (validErr != null)
228: return;
229:
230: GeometryGraph graph = new GeometryGraph(0, g);
231:
232: checkTooFewPoints(graph);
233: if (validErr != null)
234: return;
235: checkConsistentArea(graph);
236: if (validErr != null)
237: return;
238:
239: if (!isSelfTouchingRingFormingHoleValid) {
240: checkNoSelfIntersectingRings(graph);
241: if (validErr != null)
242: return;
243: }
244: checkHolesInShell(g, graph);
245: if (validErr != null)
246: return;
247: //SLOWcheckHolesNotNested(g);
248: checkHolesNotNested(g, graph);
249: if (validErr != null)
250: return;
251: checkConnectedInteriors(graph);
252: }
253:
254: private void checkValid(MultiPolygon g) {
255: for (int i = 0; i < g.getNumGeometries(); i++) {
256: Polygon p = (Polygon) g.getGeometryN(i);
257: checkInvalidCoordinates(p);
258: if (validErr != null)
259: return;
260: checkClosedRings(p);
261: if (validErr != null)
262: return;
263: }
264:
265: GeometryGraph graph = new GeometryGraph(0, g);
266:
267: checkTooFewPoints(graph);
268: if (validErr != null)
269: return;
270: checkConsistentArea(graph);
271: if (validErr != null)
272: return;
273: if (!isSelfTouchingRingFormingHoleValid) {
274: checkNoSelfIntersectingRings(graph);
275: if (validErr != null)
276: return;
277: }
278: for (int i = 0; i < g.getNumGeometries(); i++) {
279: Polygon p = (Polygon) g.getGeometryN(i);
280: checkHolesInShell(p, graph);
281: if (validErr != null)
282: return;
283: }
284: for (int i = 0; i < g.getNumGeometries(); i++) {
285: Polygon p = (Polygon) g.getGeometryN(i);
286: checkHolesNotNested(p, graph);
287: if (validErr != null)
288: return;
289: }
290: checkShellsNotNested(g, graph);
291: if (validErr != null)
292: return;
293: checkConnectedInteriors(graph);
294: }
295:
296: private void checkValid(GeometryCollection gc) {
297: for (int i = 0; i < gc.getNumGeometries(); i++) {
298: Geometry g = gc.getGeometryN(i);
299: checkValid(g);
300: if (validErr != null)
301: return;
302: }
303: }
304:
305: private void checkInvalidCoordinates(Coordinate[] coords) {
306: for (int i = 0; i < coords.length; i++) {
307: if (!isValid(coords[i])) {
308: validErr = new TopologyValidationError(
309: TopologyValidationError.INVALID_COORDINATE,
310: coords[i]);
311: return;
312: }
313: }
314: }
315:
316: private void checkInvalidCoordinates(Polygon poly) {
317: checkInvalidCoordinates(poly.getExteriorRing().getCoordinates());
318: if (validErr != null)
319: return;
320: for (int i = 0; i < poly.getNumInteriorRing(); i++) {
321: checkInvalidCoordinates(poly.getInteriorRingN(i)
322: .getCoordinates());
323: if (validErr != null)
324: return;
325: }
326: }
327:
328: private void checkClosedRings(Polygon poly) {
329: checkClosedRing((LinearRing) poly.getExteriorRing());
330: if (validErr != null)
331: return;
332: for (int i = 0; i < poly.getNumInteriorRing(); i++) {
333: checkClosedRing((LinearRing) poly.getInteriorRingN(i));
334: if (validErr != null)
335: return;
336: }
337: }
338:
339: private void checkClosedRing(LinearRing ring) {
340: if (!ring.isClosed())
341: validErr = new TopologyValidationError(
342: TopologyValidationError.RING_NOT_CLOSED, ring
343: .getCoordinateN(0));
344: }
345:
346: private void checkTooFewPoints(GeometryGraph graph) {
347: if (graph.hasTooFewPoints()) {
348: validErr = new TopologyValidationError(
349: TopologyValidationError.TOO_FEW_POINTS, graph
350: .getInvalidPoint());
351: return;
352: }
353: }
354:
355: /**
356: * Checks that the arrangement of edges in a polygonal geometry graph
357: * forms a consistent area.
358: *
359: * @param graph
360: *
361: * @see ConsistentAreaTester
362: */
363: private void checkConsistentArea(GeometryGraph graph) {
364: ConsistentAreaTester cat = new ConsistentAreaTester(graph);
365: boolean isValidArea = cat.isNodeConsistentArea();
366: if (!isValidArea) {
367: validErr = new TopologyValidationError(
368: TopologyValidationError.SELF_INTERSECTION, cat
369: .getInvalidPoint());
370: return;
371: }
372: if (cat.hasDuplicateRings()) {
373: validErr = new TopologyValidationError(
374: TopologyValidationError.DUPLICATE_RINGS, cat
375: .getInvalidPoint());
376: }
377: }
378:
379: /**
380: * Check that there is no ring which self-intersects (except of course at its endpoints).
381: * This is required by OGC topology rules (but not by other models
382: * such as ESRI SDE, which allow inverted shells and exverted holes).
383: *
384: * @param graph the topology graph of the geometry
385: */
386: private void checkNoSelfIntersectingRings(GeometryGraph graph) {
387: for (Iterator i = graph.getEdgeIterator(); i.hasNext();) {
388: Edge e = (Edge) i.next();
389: checkNoSelfIntersectingRing(e.getEdgeIntersectionList());
390: if (validErr != null)
391: return;
392: }
393: }
394:
395: /**
396: * Check that a ring does not self-intersect, except at its endpoints.
397: * Algorithm is to count the number of times each node along edge occurs.
398: * If any occur more than once, that must be a self-intersection.
399: */
400: private void checkNoSelfIntersectingRing(EdgeIntersectionList eiList) {
401: Set nodeSet = new TreeSet();
402: boolean isFirst = true;
403: for (Iterator i = eiList.iterator(); i.hasNext();) {
404: EdgeIntersection ei = (EdgeIntersection) i.next();
405: if (isFirst) {
406: isFirst = false;
407: continue;
408: }
409: if (nodeSet.contains(ei.coord)) {
410: validErr = new TopologyValidationError(
411: TopologyValidationError.RING_SELF_INTERSECTION,
412: ei.coord);
413: return;
414: } else {
415: nodeSet.add(ei.coord);
416: }
417: }
418: }
419:
420: /**
421: * Tests that each hole is inside the polygon shell.
422: * This routine assumes that the holes have previously been tested
423: * to ensure that all vertices lie on the shell oon the same side of it
424: * (i.e that the hole rings do not cross the shell ring).
425: * In other words, this test is only correct if the ConsistentArea test is passed first.
426: * Given this, a simple point-in-polygon test of a single point in the hole can be used,
427: * provided the point is chosen such that it does not lie on the shell.
428: *
429: * @param p the polygon to be tested for hole inclusion
430: * @param graph a GeometryGraph incorporating the polygon
431: */
432: private void checkHolesInShell(Polygon p, GeometryGraph graph) {
433: LinearRing shell = (LinearRing) p.getExteriorRing();
434:
435: //PointInRing pir = new SimplePointInRing(shell);
436: //PointInRing pir = new SIRtreePointInRing(shell);
437: PointInRing pir = new MCPointInRing(shell);
438:
439: for (int i = 0; i < p.getNumInteriorRing(); i++) {
440:
441: LinearRing hole = (LinearRing) p.getInteriorRingN(i);
442: Coordinate holePt = findPtNotNode(hole.getCoordinates(),
443: shell, graph);
444: /**
445: * If no non-node hole vertex can be found, the hole must
446: * split the polygon into disconnected interiors.
447: * This will be caught by a subsequent check.
448: */
449: if (holePt == null)
450: return;
451:
452: boolean outside = !pir.isInside(holePt);
453: if (outside) {
454: validErr = new TopologyValidationError(
455: TopologyValidationError.HOLE_OUTSIDE_SHELL,
456: holePt);
457: return;
458: }
459: }
460: }
461:
462: /*
463: private void OLDcheckHolesInShell(Polygon p)
464: {
465: LinearRing shell = (LinearRing) p.getExteriorRing();
466: Coordinate[] shellPts = shell.getCoordinates();
467: for (int i = 0; i < p.getNumInteriorRing(); i++) {
468: Coordinate holePt = findPtNotNode(p.getInteriorRingN(i).getCoordinates(), shell, arg[0]);
469: Assert.isTrue(holePt != null, "Unable to find a hole point not a vertex of the shell");
470: boolean onBdy = cga.isOnLine(holePt, shellPts);
471: boolean inside = cga.isPointInRing(holePt, shellPts);
472: boolean outside = ! (onBdy || inside);
473: if ( outside ) {
474: validErr = new TopologyValidationError(
475: TopologyValidationError.HOLE_OUTSIDE_SHELL,
476: holePt);
477: return;
478: }
479: }
480: }
481: */
482: /**
483: * Tests that no hole is nested inside another hole.
484: * This routine assumes that the holes are disjoint.
485: * To ensure this, holes have previously been tested
486: * to ensure that:
487: * <ul>
488: * <li>they do not partially overlap
489: * (checked by <code>checkRelateConsistency</code>)
490: * <li>they are not identical
491: * (checked by <code>checkRelateConsistency</code>)
492: * </ul>
493: */
494: private void checkHolesNotNested(Polygon p, GeometryGraph graph) {
495: QuadtreeNestedRingTester nestedTester = new QuadtreeNestedRingTester(
496: graph);
497: //SimpleNestedRingTester nestedTester = new SimpleNestedRingTester(arg[0]);
498: //SweeplineNestedRingTester nestedTester = new SweeplineNestedRingTester(arg[0]);
499:
500: for (int i = 0; i < p.getNumInteriorRing(); i++) {
501: LinearRing innerHole = (LinearRing) p.getInteriorRingN(i);
502: nestedTester.add(innerHole);
503: }
504: boolean isNonNested = nestedTester.isNonNested();
505: if (!isNonNested) {
506: validErr = new TopologyValidationError(
507: TopologyValidationError.NESTED_HOLES, nestedTester
508: .getNestedPoint());
509: }
510: }
511:
512: /*
513: private void SLOWcheckHolesNotNested(Polygon p)
514: {
515: for (int i = 0; i < p.getNumInteriorRing(); i++) {
516: LinearRing innerHole = (LinearRing) p.getInteriorRingN(i);
517: Coordinate[] innerHolePts = innerHole.getCoordinates();
518: for (int j = 0; j < p.getNumInteriorRing(); j++) {
519: // don't test hole against itself!
520: if (i == j) continue;
521:
522: LinearRing searchHole = (LinearRing) p.getInteriorRingN(j);
523:
524: // if envelopes don't overlap, holes are not nested
525: if (! innerHole.getEnvelopeInternal().overlaps(searchHole.getEnvelopeInternal()))
526: continue;
527:
528: Coordinate[] searchHolePts = searchHole.getCoordinates();
529: Coordinate innerholePt = findPtNotNode(innerHolePts, searchHole, arg[0]);
530: Assert.isTrue(innerholePt != null, "Unable to find a hole point not a node of the search hole");
531: boolean inside = cga.isPointInRing(innerholePt, searchHolePts);
532: if ( inside ) {
533: validErr = new TopologyValidationError(
534: TopologyValidationError.NESTED_HOLES,
535: innerholePt);
536: return;
537: }
538: }
539: }
540: }
541: */
542: /**
543: * Tests that no element polygon is wholly in the interior of another element polygon.
544: * <p>
545: * Preconditions:
546: * <ul>
547: * <li>shells do not partially overlap
548: * <li>shells do not touch along an edge
549: * <li>no duplicate rings exist
550: * </ul>
551: * This routine relies on the fact that while polygon shells may touch at one or
552: * more vertices, they cannot touch at ALL vertices.
553: */
554: private void checkShellsNotNested(MultiPolygon mp,
555: GeometryGraph graph) {
556: for (int i = 0; i < mp.getNumGeometries(); i++) {
557: Polygon p = (Polygon) mp.getGeometryN(i);
558: LinearRing shell = (LinearRing) p.getExteriorRing();
559: for (int j = 0; j < mp.getNumGeometries(); j++) {
560: if (i == j)
561: continue;
562: Polygon p2 = (Polygon) mp.getGeometryN(j);
563: checkShellNotNested(shell, p2, graph);
564: if (validErr != null)
565: return;
566: }
567: }
568: }
569:
570: /**
571: * Check if a shell is incorrectly nested within a polygon. This is the case
572: * if the shell is inside the polygon shell, but not inside a polygon hole.
573: * (If the shell is inside a polygon hole, the nesting is valid.)
574: * <p>
575: * The algorithm used relies on the fact that the rings must be properly contained.
576: * E.g. they cannot partially overlap (this has been previously checked by
577: * <code>checkRelateConsistency</code> )
578: */
579: private void checkShellNotNested(LinearRing shell, Polygon p,
580: GeometryGraph graph) {
581: Coordinate[] shellPts = shell.getCoordinates();
582: // test if shell is inside polygon shell
583: LinearRing polyShell = (LinearRing) p.getExteriorRing();
584: Coordinate[] polyPts = polyShell.getCoordinates();
585: Coordinate shellPt = findPtNotNode(shellPts, polyShell, graph);
586: // if no point could be found, we can assume that the shell is outside the polygon
587: if (shellPt == null)
588: return;
589: boolean insidePolyShell = CGAlgorithms.isPointInRing(shellPt,
590: polyPts);
591: if (!insidePolyShell)
592: return;
593:
594: // if no holes, this is an error!
595: if (p.getNumInteriorRing() <= 0) {
596: validErr = new TopologyValidationError(
597: TopologyValidationError.NESTED_SHELLS, shellPt);
598: return;
599: }
600:
601: /**
602: * Check if the shell is inside one of the holes.
603: * This is the case if one of the calls to checkShellInsideHole
604: * returns a null coordinate.
605: * Otherwise, the shell is not properly contained in a hole, which is an error.
606: */
607: Coordinate badNestedPt = null;
608: for (int i = 0; i < p.getNumInteriorRing(); i++) {
609: LinearRing hole = (LinearRing) p.getInteriorRingN(i);
610: badNestedPt = checkShellInsideHole(shell, hole, graph);
611: if (badNestedPt == null)
612: return;
613: }
614: validErr = new TopologyValidationError(
615: TopologyValidationError.NESTED_SHELLS, badNestedPt);
616: }
617:
618: /**
619: * This routine checks to see if a shell is properly contained in a hole.
620: * It assumes that the edges of the shell and hole do not
621: * properly intersect.
622: *
623: * @return <code>null</code> if the shell is properly contained, or
624: * a Coordinate which is not inside the hole if it is not
625: *
626: */
627: private Coordinate checkShellInsideHole(LinearRing shell,
628: LinearRing hole, GeometryGraph graph) {
629: Coordinate[] shellPts = shell.getCoordinates();
630: Coordinate[] holePts = hole.getCoordinates();
631: // TODO: improve performance of this - by sorting pointlists for instance?
632: Coordinate shellPt = findPtNotNode(shellPts, hole, graph);
633: // if point is on shell but not hole, check that the shell is inside the hole
634: if (shellPt != null) {
635: boolean insideHole = CGAlgorithms.isPointInRing(shellPt,
636: holePts);
637: if (!insideHole) {
638: return shellPt;
639: }
640: }
641: Coordinate holePt = findPtNotNode(holePts, shell, graph);
642: // if point is on hole but not shell, check that the hole is outside the shell
643: if (holePt != null) {
644: boolean insideShell = CGAlgorithms.isPointInRing(holePt,
645: shellPts);
646: if (insideShell) {
647: return holePt;
648: }
649: return null;
650: }
651: Assert
652: .shouldNeverReachHere("points in shell and hole appear to be equal");
653: return null;
654: }
655:
656: private void checkConnectedInteriors(GeometryGraph graph) {
657: ConnectedInteriorTester cit = new ConnectedInteriorTester(graph);
658: if (!cit.isInteriorsConnected())
659: validErr = new TopologyValidationError(
660: TopologyValidationError.DISCONNECTED_INTERIOR, cit
661: .getCoordinate());
662: }
663:
664: }
|