001: /*
002: * The JTS Topology Suite is a collection of Java classes that
003: * implement the fundamental operations required to validate a given
004: * geo-spatial data set to a known topological specification.
005: *
006: * Copyright (C) 2001 Vivid Solutions
007: *
008: * This library is free software; you can redistribute it and/or
009: * modify it under the terms of the GNU Lesser General Public
010: * License as published by the Free Software Foundation; either
011: * version 2.1 of the License, or (at your option) any later version.
012: *
013: * This library is distributed in the hope that it will be useful,
014: * but WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * Lesser General Public License for more details.
017: *
018: * You should have received a copy of the GNU Lesser General Public
019: * License along with this library; if not, write to the Free Software
020: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
021: *
022: * For more information, contact:
023: *
024: * Vivid Solutions
025: * Suite #1A
026: * 2328 Government Street
027: * Victoria BC V8T 5G5
028: * Canada
029: *
030: * (250)385-6040
031: * www.vividsolutions.com
032: */
033: package com.vividsolutions.jts.noding;
034:
035: import java.util.*;
036: import com.vividsolutions.jts.algorithm.*;
037: import com.vividsolutions.jts.geom.*;
038: import com.vividsolutions.jts.util.*;
039:
040: /**
041: * Validates that a collection of {@link SegmentString}s is correctly noded.
042: * Throws an appropriate exception if an noding error is found.
043: *
044: * @version 1.7
045: */
046: public class NodingValidator {
047:
048: private LineIntersector li = new RobustLineIntersector();
049:
050: private Collection segStrings;
051:
052: /**
053: * Creates a new validator for the given collection
054: * of {@link SegmentString}s.
055: *
056: * @param segStrings a collection of SegmentStrings
057: */
058: public NodingValidator(Collection segStrings) {
059: this .segStrings = segStrings;
060: }
061:
062: /**
063: * Checks whether the supplied segment strings
064: * are correctly noded. Throws an exception if they are not.
065: *
066: * @throws RuntimeException if the SegmentStrings are not correctly noded
067: *
068: */
069: public void checkValid() {
070: checkEndPtVertexIntersections();
071: checkInteriorIntersections();
072: checkCollapses();
073: }
074:
075: /**
076: * Checks if a segment string contains a segment pattern a-b-a (which implies a self-intersection)
077: */
078: private void checkCollapses() {
079: for (Iterator i = segStrings.iterator(); i.hasNext();) {
080: SegmentString ss = (SegmentString) i.next();
081: checkCollapses(ss);
082: }
083: }
084:
085: private void checkCollapses(SegmentString ss) {
086: Coordinate[] pts = ss.getCoordinates();
087: for (int i = 0; i < pts.length - 2; i++) {
088: checkCollapse(pts[i], pts[i + 1], pts[i + 2]);
089: }
090: }
091:
092: private void checkCollapse(Coordinate p0, Coordinate p1,
093: Coordinate p2) {
094: if (p0.equals(p2))
095: throw new RuntimeException("found non-noded collapse at "
096: + Debug.toLine(p0, p1, p2));
097: }
098:
099: /**
100: * Checks all pairs of segments for intersections at an interior point of a segment
101: */
102: private void checkInteriorIntersections() {
103: for (Iterator i = segStrings.iterator(); i.hasNext();) {
104: SegmentString ss0 = (SegmentString) i.next();
105: for (Iterator j = segStrings.iterator(); j.hasNext();) {
106: SegmentString ss1 = (SegmentString) j.next();
107:
108: checkInteriorIntersections(ss0, ss1);
109: }
110: }
111: }
112:
113: private void checkInteriorIntersections(SegmentString ss0,
114: SegmentString ss1) {
115: Coordinate[] pts0 = ss0.getCoordinates();
116: Coordinate[] pts1 = ss1.getCoordinates();
117: for (int i0 = 0; i0 < pts0.length - 1; i0++) {
118: for (int i1 = 0; i1 < pts1.length - 1; i1++) {
119: checkInteriorIntersections(ss0, i0, ss1, i1);
120: }
121: }
122: }
123:
124: private void checkInteriorIntersections(SegmentString e0,
125: int segIndex0, SegmentString e1, int segIndex1) {
126: if (e0 == e1 && segIndex0 == segIndex1)
127: return;
128: //numTests++;
129: Coordinate p00 = e0.getCoordinates()[segIndex0];
130: Coordinate p01 = e0.getCoordinates()[segIndex0 + 1];
131: Coordinate p10 = e1.getCoordinates()[segIndex1];
132: Coordinate p11 = e1.getCoordinates()[segIndex1 + 1];
133:
134: li.computeIntersection(p00, p01, p10, p11);
135: if (li.hasIntersection()) {
136:
137: if (li.isProper() || hasInteriorIntersection(li, p00, p01)
138: || hasInteriorIntersection(li, p10, p11)) {
139: throw new RuntimeException(
140: "found non-noded intersection at " + p00 + "-"
141: + p01 + " and " + p10 + "-" + p11);
142: }
143: }
144: }
145:
146: /**
147: *@return true if there is an intersection point which is not an endpoint of the segment p0-p1
148: */
149: private boolean hasInteriorIntersection(LineIntersector li,
150: Coordinate p0, Coordinate p1) {
151: for (int i = 0; i < li.getIntersectionNum(); i++) {
152: Coordinate intPt = li.getIntersection(i);
153: if (!(intPt.equals(p0) || intPt.equals(p1)))
154: return true;
155: }
156: return false;
157: }
158:
159: /**
160: * Checks for intersections between an endpoint of a segment string
161: * and an interior vertex of another segment string
162: */
163: private void checkEndPtVertexIntersections() {
164: for (Iterator i = segStrings.iterator(); i.hasNext();) {
165: SegmentString ss = (SegmentString) i.next();
166: Coordinate[] pts = ss.getCoordinates();
167: checkEndPtVertexIntersections(pts[0], segStrings);
168: checkEndPtVertexIntersections(pts[pts.length - 1],
169: segStrings);
170: }
171: }
172:
173: private void checkEndPtVertexIntersections(Coordinate testPt,
174: Collection segStrings) {
175: for (Iterator i = segStrings.iterator(); i.hasNext();) {
176: SegmentString ss = (SegmentString) i.next();
177: Coordinate[] pts = ss.getCoordinates();
178: for (int j = 1; j < pts.length - 1; j++) {
179: if (pts[j].equals(testPt))
180: throw new RuntimeException(
181: "found endpt/interior pt intersection at index "
182: + j + " :pt " + testPt);
183: }
184: }
185: }
186:
187: }
|