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.operation.polygonize;
034:
035: import java.util.*;
036: import com.vividsolutions.jts.geom.*;
037:
038: /**
039: * Polygonizes a set of Geometrys which contain linework that
040: * represents the edges of a planar graph.
041: * Any dimension of Geometry is handled - the constituent linework is extracted
042: * to form the edges.
043: * The edges must be correctly noded; that is, they must only meet
044: * at their endpoints. The Polygonizer will still run on incorrectly noded input
045: * but will not form polygons from incorrected noded edges.
046: * <p>
047: * The Polygonizer reports the follow kinds of errors:
048: * <ul>
049: * <li><b>Dangles</b> - edges which have one or both ends which are not incident on another edge endpoint
050: * <li><b>Cut Edges</b> - edges which are connected at both ends but which do not form part of polygon
051: * <li><b>Invalid Ring Lines</b> - edges which form rings which are invalid
052: * (e.g. the component lines contain a self-intersection)
053: * </ul>
054: *
055: * @version 1.7
056: */
057: public class Polygonizer {
058:
059: /**
060: * Add every linear element in a geometry into the polygonizer graph.
061: */
062: private class LineStringAdder implements GeometryComponentFilter {
063: public void filter(Geometry g) {
064: if (g instanceof LineString)
065: add((LineString) g);
066: }
067: }
068:
069: // default factory
070: private LineStringAdder lineStringAdder = new LineStringAdder();
071:
072: protected PolygonizeGraph graph;
073: // initialize with empty collections, in case nothing is computed
074: protected Collection dangles = new ArrayList();
075: protected List cutEdges = new ArrayList();
076: protected List invalidRingLines = new ArrayList();
077:
078: protected List holeList = null;
079: protected List shellList = null;
080: protected List polyList = null;
081:
082: /**
083: * Create a polygonizer with the same {@link GeometryFactory}
084: * as the input {@link Geometry}s
085: */
086: public Polygonizer() {
087: }
088:
089: /**
090: * Add a collection of geometries to be polygonized.
091: * May be called multiple times.
092: * Any dimension of Geometry may be added;
093: * the constituent linework will be extracted and used
094: *
095: * @param geomList a list of {@link Geometry}s with linework to be polygonized
096: */
097: public void add(Collection geomList) {
098: for (Iterator i = geomList.iterator(); i.hasNext();) {
099: Geometry geometry = (Geometry) i.next();
100: add(geometry);
101: }
102: }
103:
104: /**
105: * Add a geometry to the linework to be polygonized.
106: * May be called multiple times.
107: * Any dimension of Geometry may be added;
108: * the constituent linework will be extracted and used
109: *
110: * @param g a {@link Geometry} with linework to be polygonized
111: */
112: public void add(Geometry g) {
113: g.apply(lineStringAdder);
114: }
115:
116: /**
117: * Add a linestring to the graph of polygon edges.
118: *
119: * @param line the {@link LineString} to add
120: */
121: private void add(LineString line) {
122: // create a new graph using the factory from the input Geometry
123: if (graph == null)
124: graph = new PolygonizeGraph(line.getFactory());
125: graph.addEdge(line);
126: }
127:
128: /**
129: * Gets the list of polygons formed by the polygonization.
130: * @return a collection of {@link Polygon}s
131: */
132: public Collection getPolygons() {
133: polygonize();
134: return polyList;
135: }
136:
137: /**
138: * Get the list of dangling lines found during polygonization.
139: * @return a collection of the input {@link LineString}s which are dangles
140: */
141: public Collection getDangles() {
142: polygonize();
143: return dangles;
144: }
145:
146: /**
147: * Get the list of cut edges found during polygonization.
148: * @return a collection of the input {@link LineString}s which are cut edges
149: */
150: public Collection getCutEdges() {
151: polygonize();
152: return cutEdges;
153: }
154:
155: /**
156: * Get the list of lines forming invalid rings found during polygonization.
157: * @return a collection of the input {@link LineString}s which form invalid rings
158: */
159: public Collection getInvalidRingLines() {
160: polygonize();
161: return invalidRingLines;
162: }
163:
164: /**
165: * Perform the polygonization, if it has not already been carried out.
166: */
167: private void polygonize() {
168: // check if already computed
169: if (polyList != null)
170: return;
171: polyList = new ArrayList();
172:
173: // if no geometries were supplied it's possible graph could be null
174: if (graph == null)
175: return;
176:
177: dangles = graph.deleteDangles();
178: cutEdges = graph.deleteCutEdges();
179: List edgeRingList = graph.getEdgeRings();
180:
181: List validEdgeRingList = new ArrayList();
182: invalidRingLines = new ArrayList();
183: findValidRings(edgeRingList, validEdgeRingList,
184: invalidRingLines);
185:
186: findShellsAndHoles(validEdgeRingList);
187: assignHolesToShells(holeList, shellList);
188:
189: polyList = new ArrayList();
190: for (Iterator i = shellList.iterator(); i.hasNext();) {
191: EdgeRing er = (EdgeRing) i.next();
192: polyList.add(er.getPolygon());
193: }
194: }
195:
196: private void findValidRings(List edgeRingList,
197: List validEdgeRingList, List invalidRingList) {
198: for (Iterator i = edgeRingList.iterator(); i.hasNext();) {
199: EdgeRing er = (EdgeRing) i.next();
200: if (er.isValid())
201: validEdgeRingList.add(er);
202: else
203: invalidRingList.add(er.getLineString());
204: }
205: }
206:
207: private void findShellsAndHoles(List edgeRingList) {
208: holeList = new ArrayList();
209: shellList = new ArrayList();
210: for (Iterator i = edgeRingList.iterator(); i.hasNext();) {
211: EdgeRing er = (EdgeRing) i.next();
212: if (er.isHole())
213: holeList.add(er);
214: else
215: shellList.add(er);
216:
217: }
218: }
219:
220: private static void assignHolesToShells(List holeList,
221: List shellList) {
222: for (Iterator i = holeList.iterator(); i.hasNext();) {
223: EdgeRing holeER = (EdgeRing) i.next();
224: assignHoleToShell(holeER, shellList);
225: }
226: }
227:
228: private static void assignHoleToShell(EdgeRing holeER,
229: List shellList) {
230: EdgeRing shell = EdgeRing.findEdgeRingContaining(holeER,
231: shellList);
232: if (shell != null)
233: shell.addHole(holeER.getRing());
234: }
235:
236: }
|