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:
034: package com.vividsolutions.jts.operation.polygonize;
035:
036: import java.util.*;
037: import com.vividsolutions.jts.algorithm.*;
038: import com.vividsolutions.jts.geom.*;
039: import com.vividsolutions.jts.planargraph.*;
040:
041: /**
042: * Represents a ring of {@link PolygonizeDirectedEdge}s which form
043: * a ring of a polygon. The ring may be either an outer shell or a hole.
044: *
045: * @version 1.7
046: */
047: public class EdgeRing {
048:
049: /**
050: * Find the innermost enclosing shell EdgeRing containing the argument EdgeRing, if any.
051: * The innermost enclosing ring is the <i>smallest</i> enclosing ring.
052: * The algorithm used depends on the fact that:
053: * <br>
054: * ring A contains ring B iff envelope(ring A) contains envelope(ring B)
055: * <br>
056: * This routine is only safe to use if the chosen point of the hole
057: * is known to be properly contained in a shell
058: * (which is guaranteed to be the case if the hole does not touch its shell)
059: *
060: * @return containing EdgeRing, if there is one
061: * @return null if no containing EdgeRing is found
062: */
063: public static EdgeRing findEdgeRingContaining(EdgeRing testEr,
064: List shellList) {
065: LinearRing testRing = testEr.getRing();
066: Envelope testEnv = testRing.getEnvelopeInternal();
067: Coordinate testPt = testRing.getCoordinateN(0);
068:
069: EdgeRing minShell = null;
070: Envelope minEnv = null;
071: for (Iterator it = shellList.iterator(); it.hasNext();) {
072: EdgeRing tryShell = (EdgeRing) it.next();
073: LinearRing tryRing = tryShell.getRing();
074: Envelope tryEnv = tryRing.getEnvelopeInternal();
075: if (minShell != null)
076: minEnv = minShell.getRing().getEnvelopeInternal();
077: boolean isContained = false;
078: // the hole envelope cannot equal the shell envelope
079: if (tryEnv.equals(testEnv))
080: continue;
081:
082: // testPt = ptNotInList(testRing.getCoordinates(), tryRing.getCoordinates());
083: testPt = CoordinateArrays.ptNotInList(testRing
084: .getCoordinates(), tryRing.getCoordinates());
085: if (tryEnv.contains(testEnv)
086: && cga.isPointInRing(testPt, tryRing
087: .getCoordinates()))
088: isContained = true;
089: // check if this new containing ring is smaller than the current minimum ring
090: if (isContained) {
091: if (minShell == null || minEnv.contains(tryEnv)) {
092: minShell = tryShell;
093: }
094: }
095: }
096: return minShell;
097: }
098:
099: /**
100: * Finds a point in a list of points which is not contained in another list of points
101: * @param testPts the {@link Coordinate}s to test
102: * @param pts an array of {@link Coordinate}s to test the input points against
103: * @return a {@link Coordinate} from <code>testPts</code> which is not in <code>pts</code>,
104: * @return null if there is no coordinate not in the list
105: */
106: public static Coordinate ptNotInList(Coordinate[] testPts,
107: Coordinate[] pts) {
108: for (int i = 0; i < testPts.length; i++) {
109: Coordinate testPt = testPts[i];
110: if (!isInList(testPt, pts))
111: return testPt;
112: }
113: return null;
114: }
115:
116: /**
117: * Tests whether a given point is in an array of points.
118: * Uses a value-based test.
119: *
120: * @param pt a {@link Coordinate} for the test point
121: * @param pts an array of {@link Coordinate}s to test
122: * @return <code>true</code> if the point is in the array
123: */
124: public static boolean isInList(Coordinate pt, Coordinate[] pts) {
125: for (int i = 0; i < pts.length; i++) {
126: if (pt.equals(pts[i]))
127: return true;
128: }
129: return false;
130: }
131:
132: private GeometryFactory factory;
133: private static CGAlgorithms cga = new CGAlgorithms();
134:
135: private List deList = new ArrayList();
136:
137: // cache the following data for efficiency
138: private LinearRing ring = null;
139:
140: private Coordinate[] ringPts = null;
141: private List holes;
142:
143: public EdgeRing(GeometryFactory factory) {
144: this .factory = factory;
145: }
146:
147: /**
148: * Adds a {@link DirectedEdge} which is known to form part of this ring.
149: * @param de the {@link DirectedEdge} to add.
150: */
151: public void add(DirectedEdge de) {
152: deList.add(de);
153: }
154:
155: /**
156: * Tests whether this ring is a hole.
157: * Due to the way the edges in the polyongization graph are linked,
158: * a ring is a hole if it is oriented counter-clockwise.
159: * @return <code>true</code> if this ring is a hole
160: */
161: public boolean isHole() {
162: LinearRing ring = getRing();
163: return cga.isCCW(ring.getCoordinates());
164: }
165:
166: /**
167: * Adds a hole to the polygon formed by this ring.
168: * @param hole the {@link LinearRing} forming the hole.
169: */
170: public void addHole(LinearRing hole) {
171: if (holes == null)
172: holes = new ArrayList();
173: holes.add(hole);
174: }
175:
176: /**
177: * Computes the {@link Polygon} formed by this ring and any contained holes.
178: *
179: * @return the {@link Polygon} formed by this ring and its holes.
180: */
181: public Polygon getPolygon() {
182: LinearRing[] holeLR = null;
183: if (holes != null) {
184: holeLR = new LinearRing[holes.size()];
185: for (int i = 0; i < holes.size(); i++) {
186: holeLR[i] = (LinearRing) holes.get(i);
187: }
188: }
189: Polygon poly = factory.createPolygon(ring, holeLR);
190: return poly;
191: }
192:
193: /**
194: * Tests if the {@link LinearRing} ring formed by this edge ring is topologically valid.
195: * @return
196: */
197: public boolean isValid() {
198: getCoordinates();
199: if (ringPts.length <= 3)
200: return false;
201: getRing();
202: return ring.isValid();
203: }
204:
205: /**
206: * Computes the list of coordinates which are contained in this ring.
207: * The coordinatea are computed once only and cached.
208: *
209: * @return an array of the {@link Coordinate}s in this ring
210: */
211: private Coordinate[] getCoordinates() {
212: if (ringPts == null) {
213: CoordinateList coordList = new CoordinateList();
214: for (Iterator i = deList.iterator(); i.hasNext();) {
215: DirectedEdge de = (DirectedEdge) i.next();
216: PolygonizeEdge edge = (PolygonizeEdge) de.getEdge();
217: addEdge(edge.getLine().getCoordinates(), de
218: .getEdgeDirection(), coordList);
219: }
220: ringPts = coordList.toCoordinateArray();
221: }
222: return ringPts;
223: }
224:
225: /**
226: * Gets the coordinates for this ring as a {@link LineString}.
227: * Used to return the coordinates in this ring
228: * as a valid geometry, when it has been detected that the ring is topologically
229: * invalid.
230: * @return a {@link LineString} containing the coordinates in this ring
231: */
232: public LineString getLineString() {
233: getCoordinates();
234: return factory.createLineString(ringPts);
235: }
236:
237: /**
238: * Returns this ring as a {@link LinearRing}, or null if an Exception occurs while
239: * creating it (such as a topology problem). Details of problems are written to
240: * standard output.
241: */
242: public LinearRing getRing() {
243: if (ring != null)
244: return ring;
245: getCoordinates();
246: if (ringPts.length < 3)
247: System.out.println(ringPts);
248: try {
249: ring = factory.createLinearRing(ringPts);
250: } catch (Exception ex) {
251: System.out.println(ringPts);
252: }
253: return ring;
254: }
255:
256: private static void addEdge(Coordinate[] coords, boolean isForward,
257: CoordinateList coordList) {
258: if (isForward) {
259: for (int i = 0; i < coords.length; i++) {
260: coordList.add(coords[i], false);
261: }
262: } else {
263: for (int i = coords.length - 1; i >= 0; i--) {
264: coordList.add(coords[i], false);
265: }
266: }
267: }
268: }
|