Class Polygonizer

1
2	/*
3	* Copyright (c) 2016 Vivid Solutions.
4	*
5	* All rights reserved. This program and the accompanying materials
6	* are made available under the terms of the Eclipse Public License 2.0
7	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
8	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
9	* and the Eclipse Distribution License is available at
10	*
11	* http://www.eclipse.org/org/documents/edl-v10.php.
12	*/
13	package org.locationtech.jts.operation.polygonize;
14
15	import java.util.ArrayList;
16	import java.util.Collection;
17	import java.util.Collections;
18	import java.util.Iterator;
19	import java.util.List;
20
21	import org.locationtech.jts.geom.Geometry;
22	import org.locationtech.jts.geom.GeometryComponentFilter;
23	import org.locationtech.jts.geom.GeometryFactory;
24	import org.locationtech.jts.geom.LineString;
25	import org.locationtech.jts.geom.Polygon;
26
27
28	/**
29	* Polygonizes a set of {@link Geometry}s which contain linework that
30	* represents the edges of a planar graph.
31	* All types of Geometry are accepted as input;
32	* the constituent linework is extracted as the edges to be polygonized.
33	* The processed edges must be correctly noded; that is, they must only meet
34	* at their endpoints. Polygonization will accept incorrectly noded input
35	* but will not form polygons from non-noded edges,
36	* and reports them as errors.
37	* <p>
38	* The Polygonizer reports the follow kinds of errors:
39	* <ul>
40	* <li><b>{@link #getDangles() Dangles}</b> - edges which have one or both ends which are not incident on another edge endpoint
41	* <li><b>{@link #getCutEdges() Cut Edges}</b> - edges which are connected at both ends but which do not form part of polygon
42	* <li><b>{@link #getInvalidRingLines() Invalid Ring Lines}</b> - edges which form rings which are invalid
43	* (e.g. the component lines contain a self-intersection)
44	* </ul>
45	* The {@link #Polygonizer(boolean)} constructor allows
46	* extracting only polygons which form a valid polygonal result.
47	* The set of extracted polygons is guaranteed to be edge-disjoint.
48	* This is useful where it is known that the input lines form a
49	* valid polygonal geometry (which may include holes or nested polygons).
50	*
51	* @version 1.7
52	*/
53	public class Polygonizer
54	{
55	/**
56	* Adds every linear element in a {@link Geometry} into the polygonizer graph.
57	*/
58	private static class LineStringAdder
59	implements GeometryComponentFilter
60	{
61	Polygonizer p;
62
63	LineStringAdder(Polygonizer p) {
64	this.p = p;
65	}
66
67	public void filter(Geometry g) {
68	if (g instanceof LineString)
69	p.add((LineString) g);
70	}
71	}
72
73	// default factory
74	private LineStringAdder lineStringAdder = new LineStringAdder(this);
75
76	protected PolygonizeGraph graph;
77	// initialize with empty collections, in case nothing is computed
78	protected Collection dangles = new ArrayList();
79	protected List cutEdges = new ArrayList();
80	protected List invalidRingLines = new ArrayList();
81
82	protected List holeList = null;
83	protected List shellList = null;
84	protected List polyList = null;
85
86	private boolean isCheckingRingsValid = true;
87	private boolean extractOnlyPolygonal;
88
89	private GeometryFactory geomFactory = null;
90
91	/**
92	* Creates a polygonizer that extracts all polygons.
93	*/
94	public Polygonizer()
95	{
96	this(false);
97	}
98
99	/**
100	* Creates a polygonizer, specifying whether a valid polygonal geometry must be created.
101	* If the argument is <code>true</code>
102	* then areas may be discarded in order to
103	* ensure that the extracted geometry is a valid polygonal geometry.
104	*
105	* @param extractOnlyPolygonal true if a valid polygonal geometry should be extracted
106	*/
107	public Polygonizer(boolean extractOnlyPolygonal)
108	{
109	this.extractOnlyPolygonal = extractOnlyPolygonal;
110	}
111
112	/**
113	* Adds a collection of geometries to the edges to be polygonized.
114	* May be called multiple times.
115	* Any dimension of Geometry may be added;
116	* the constituent linework will be extracted and used.
117	*
118	* @param geomList a list of {@link Geometry}s with linework to be polygonized
119	*/
120	public void add(Collection geomList)
121	{
122	for (Iterator i = geomList.iterator(); i.hasNext(); ) {
123	Geometry geometry = (Geometry) i.next();
124	add(geometry);
125	}
126	}
127
128	/**
129	* Add a {@link Geometry} to the edges to be polygonized.
130	* May be called multiple times.
131	* Any dimension of Geometry may be added;
132	* the constituent linework will be extracted and used
133	*
134	* @param g a {@link Geometry} with linework to be polygonized
135	*/
136	public void add(Geometry g)
137	{
138	g.apply(lineStringAdder);
139	}
140
141	/**
142	* Adds a linestring to the graph of polygon edges.
143	*
144	* @param line the {@link LineString} to add
145	*/
146	private void add(LineString line)
147	{
148	// record the geometry factory for later use
149	geomFactory = line.getFactory();
150	// create a new graph using the factory from the input Geometry
151	if (graph == null)
152	graph = new PolygonizeGraph(geomFactory);
153	graph.addEdge(line);
154	}
155
156	/**
157	* Allows disabling the valid ring checking,
158	* to optimize situations where invalid rings are not expected.
159	* <p>
160	* The default is <code>true</code>.
161	*
162	* @param isCheckingRingsValid true if generated rings should be checked for validity
163	*/
164	public void setCheckRingsValid(boolean isCheckingRingsValid)
165	{
166	this.isCheckingRingsValid = isCheckingRingsValid;
167	}
168
169	/**
170	* Gets the list of polygons formed by the polygonization.
171	* @return a collection of {@link Polygon}s
172	*/
173	public Collection getPolygons()
174	{
175	polygonize();
176	return polyList;
177	}
178
179	/**
180	* Gets a geometry representing the polygons formed by the polygonization.
181	* If a valid polygonal geometry was extracted the result is a {@link Polygonal} geometry.
182	*
183	* @return a geometry containing the polygons
184	*/
185	public Geometry getGeometry()
186	{
187	if (geomFactory == null) geomFactory = new GeometryFactory();
188	polygonize();
189	if (extractOnlyPolygonal) {
190	return geomFactory.buildGeometry(polyList);
191	}
192	// result may not be valid Polygonal, so return as a GeometryCollection
193	return geomFactory.createGeometryCollection(GeometryFactory.toGeometryArray(polyList));
194	}
195
196	/**
197	* Gets the list of dangling lines found during polygonization.
198	* @return a collection of the input {@link LineString}s which are dangles
199	*/
200	public Collection getDangles()
201	{
202	polygonize();
203	return dangles;
204	}
205
206	/**
207	* Gets the list of cut edges found during polygonization.
208	* @return a collection of the input {@link LineString}s which are cut edges
209	*/
210	public Collection getCutEdges()
211	{
212	polygonize();
213	return cutEdges;
214	}
215
216	/**
217	* Gets the list of lines forming invalid rings found during polygonization.
218	* @return a collection of the input {@link LineString}s which form invalid rings
219	*/
220	public Collection getInvalidRingLines()
221	{
222	polygonize();
223	return invalidRingLines;
224	}
225
226	/**
227	* Performs the polygonization, if it has not already been carried out.
228	*/
229	private void polygonize()
230	{
231	// check if already computed
232	if (polyList != null) return;
233	polyList = new ArrayList();
234
235	// if no geometries were supplied it's possible that graph is null
236	if (graph == null) return;
237
238	dangles = graph.deleteDangles();
239	cutEdges = graph.deleteCutEdges();
240	List edgeRingList = graph.getEdgeRings();
241
242	//Debug.printTime("Build Edge Rings");
243
244	List validEdgeRingList = new ArrayList();
245	invalidRingLines = new ArrayList();
246	if (isCheckingRingsValid) {
247	findValidRings(edgeRingList, validEdgeRingList, invalidRingLines);
248	}
249	else {
250	validEdgeRingList = edgeRingList;
251	}
252	//Debug.printTime("Validate Rings");
253
254	findShellsAndHoles(validEdgeRingList);
255	HoleAssigner.assignHolesToShells(holeList, shellList);
256
257	// order the shells to make any subsequent processing deterministic
258	Collections.sort(shellList, new EdgeRing.EnvelopeComparator());
259
260	//Debug.printTime("Assign Holes");
261
262	boolean includeAll = true;
263	if (extractOnlyPolygonal) {
264	findDisjointShells(shellList);
265	includeAll = false;
266	}
267	polyList = extractPolygons(shellList, includeAll);
268	}
269
270	private void findValidRings(List edgeRingList, List validEdgeRingList, List invalidRingList)
271	{
272	for (Iterator i = edgeRingList.iterator(); i.hasNext(); ) {
273	EdgeRing er = (EdgeRing) i.next();
274	if (er.isValid())
275	validEdgeRingList.add(er);
276	else
277	invalidRingList.add(er.getLineString());
278	}
279	}
280
281	private void findShellsAndHoles(List edgeRingList)
282	{
283	holeList = new ArrayList();
284	shellList = new ArrayList();
285	for (Iterator i = edgeRingList.iterator(); i.hasNext(); ) {
286	EdgeRing er = (EdgeRing) i.next();
287	er.computeHole();
288	if (er.isHole())
289	holeList.add(er);
290	else
291	shellList.add(er);
292	}
293	}
294
295	private static void findDisjointShells(List shellList) {
296	findOuterShells(shellList);
297
298	boolean isMoreToScan;
299	do {
300	isMoreToScan = false;
301	for (Iterator i = shellList.iterator(); i.hasNext(); ) {
302	EdgeRing er = (EdgeRing) i.next();
303	if (er.isIncludedSet())
304	continue;
305	er.updateIncluded();
306	if (! er.isIncludedSet()) {
307	isMoreToScan = true;
308	}
309	}
310	} while (isMoreToScan);
311	}
312
313	/**
314	* For each outer hole finds and includes a single outer shell.
315	* This seeds the traversal algorithm for finding only polygonal shells.
316	*
317	* @param shellList the list of shell EdgeRings
318	*/
319	private static void findOuterShells(List shellList) {
320
321	for (Iterator i = shellList.iterator(); i.hasNext();) {
322	EdgeRing er = (EdgeRing) i.next();
323	EdgeRing outerHoleER = er.getOuterHole();
324	if (outerHoleER != null && ! outerHoleER.isProcessed()) {
325	er.setIncluded(true);
326	outerHoleER.setProcessed(true);
327	}
328	}
329	}
330
331	private static List extractPolygons(List shellList, boolean includeAll) {
332	List polyList = new ArrayList();
333	for (Iterator i = shellList.iterator(); i.hasNext();) {
334	EdgeRing er = (EdgeRing) i.next();
335	if (includeAll \|\| er.isIncluded()) {
336	polyList.add(er.getPolygon());
337	}
338	}
339	return polyList;
340	}
341	}
342