Class CascadedPolygonUnion

1	/*
2	* Copyright (c) 2016 Vivid Solutions.
3	*
4	* All rights reserved. This program and the accompanying materials
5	* are made available under the terms of the Eclipse Public License 2.0
6	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8	* and the Eclipse Distribution License is available at
9	*
10	* http://www.eclipse.org/org/documents/edl-v10.php.
11	*/
12	package org.locationtech.jts.operation.union;
13
14	import java.util.ArrayList;
15	import java.util.Collection;
16	import java.util.Iterator;
17	import java.util.List;
18
19	import org.locationtech.jts.geom.Envelope;
20	import org.locationtech.jts.geom.Geometry;
21	import org.locationtech.jts.geom.GeometryFactory;
22	import org.locationtech.jts.geom.Polygon;
23	import org.locationtech.jts.geom.Polygonal;
24	import org.locationtech.jts.geom.util.GeometryCombiner;
25	import org.locationtech.jts.geom.util.PolygonExtracter;
26	import org.locationtech.jts.index.strtree.STRtree;
27
28
29	/**
30	* Provides an efficient method of unioning a collection of
31	* {@link Polygonal} geometries.
32	* The geometries are indexed using a spatial index,
33	* and unioned recursively in index order.
34	* For geometries with a high degree of overlap,
35	* this has the effect of reducing the number of vertices
36	* early in the process, which increases speed
37	* and robustness.
38	* <p>
39	* This algorithm is faster and more robust than
40	* the simple iterated approach of
41	* repeatedly unioning each polygon to a result geometry.
42	* <p>
43	* The <tt>buffer(0)</tt> trick is sometimes faster, but can be less robust and
44	* can sometimes take a long time to complete.
45	* This is particularly the case where there is a high degree of overlap
46	* between the polygons. In this case, <tt>buffer(0)</tt> is forced to compute
47	* with <i>all</i> line segments from the outset,
48	* whereas cascading can eliminate many segments
49	* at each stage of processing.
50	* The best situation for using <tt>buffer(0)</tt> is the trivial case
51	* where there is <i>no</i> overlap between the input geometries.
52	* However, this case is likely rare in practice.
53	*
54	* @author Martin Davis
55	*
56	*/
57	public class CascadedPolygonUnion
58	{
59	/**
60	* Computes the union of
61	* a collection of {@link Polygonal} {@link Geometry}s.
62	*
63	* @param polys a collection of {@link Polygonal} {@link Geometry}s
64	*/
65	public static Geometry union(Collection polys)
66	{
67	CascadedPolygonUnion op = new CascadedPolygonUnion(polys);
68	return op.union();
69	}
70
71	private Collection inputPolys;
72	private GeometryFactory geomFactory = null;
73
74	/**
75	* Creates a new instance to union
76	* the given collection of {@link Geometry}s.
77	*
78	* @param polys a collection of {@link Polygonal} {@link Geometry}s
79	*/
80	public CascadedPolygonUnion(Collection polys)
81	{
82	this.inputPolys = polys;
83	// guard against null input
84	if (inputPolys == null)
85	inputPolys = new ArrayList();
86	}
87
88	/**
89	* The effectiveness of the index is somewhat sensitive
90	* to the node capacity.
91	* Testing indicates that a smaller capacity is better.
92	* For an STRtree, 4 is probably a good number (since
93	* this produces 2x2 "squares").
94	*/
95	private static final int STRTREE_NODE_CAPACITY = 4;
96
97	/**
98	* Computes the union of the input geometries.
99	* <p>
100	* This method discards the input geometries as they are processed.
101	* In many input cases this reduces the memory retained
102	* as the operation proceeds.
103	* Optimal memory usage is achieved
104	* by disposing of the original input collection
105	* before calling this method.
106	*
107	* @return the union of the input geometries
108	* or null if no input geometries were provided
109	* @throws IllegalStateException if this method is called more than once
110	*/
111	public Geometry union()
112	{
113	if (inputPolys == null)
114	throw new IllegalStateException("union() method cannot be called twice");
115	if (inputPolys.isEmpty())
116	return null;
117	geomFactory = ((Geometry) inputPolys.iterator().next()).getFactory();
118
119	/**
120	* A spatial index to organize the collection
121	* into groups of close geometries.
122	* This makes unioning more efficient, since vertices are more likely
123	* to be eliminated on each round.
124	*/
125	// STRtree index = new STRtree();
126	STRtree index = new STRtree(STRTREE_NODE_CAPACITY);
127	for (Iterator i = inputPolys.iterator(); i.hasNext(); ) {
128	Geometry item = (Geometry) i.next();
129	index.insert(item.getEnvelopeInternal(), item);
130	}
131	// To avoiding holding memory remove references to the input geometries,
132	inputPolys = null;
133
134	List itemTree = index.itemsTree();
135	// printItemEnvelopes(itemTree);
136	Geometry unionAll = unionTree(itemTree);
137	return unionAll;
138	}
139
140	private Geometry unionTree(List geomTree)
141	{
142	/**
143	* Recursively unions all subtrees in the list into single geometries.
144	* The result is a list of Geometrys only
145	*/
146	List geoms = reduceToGeometries(geomTree);
147	// Geometry union = bufferUnion(geoms);
148	Geometry union = binaryUnion(geoms);
149
150	// print out union (allows visualizing hierarchy)
151	// System.out.println(union);
152
153	return union;
154	}
155
156	//========================================================
157	/*
158	* The following methods are for experimentation only
159	*/
160
161	private Geometry repeatedUnion(List geoms)
162	{
163	Geometry union = null;
164	for (Iterator i = geoms.iterator(); i.hasNext(); ) {
165	Geometry g = (Geometry) i.next();
166	if (union == null)
167	union = g.copy();
168	else
169	union = union.union(g);
170	}
171	return union;
172	}
173
174	private Geometry bufferUnion(List geoms)
175	{
176	GeometryFactory factory = ((Geometry) geoms.get(0)).getFactory();
177	Geometry gColl = factory.buildGeometry(geoms);
178	Geometry unionAll = gColl.buffer(0.0);
179	return unionAll;
180	}
181
182	private Geometry bufferUnion(Geometry g0, Geometry g1)
183	{
184	GeometryFactory factory = g0.getFactory();
185	Geometry gColl = factory.createGeometryCollection(new Geometry[] { g0, g1 } );
186	Geometry unionAll = gColl.buffer(0.0);
187	return unionAll;
188	}
189
190	//=======================================
191
192	/**
193	* Unions a list of geometries
194	* by treating the list as a flattened binary tree,
195	* and performing a cascaded union on the tree.
196	*/
197	private Geometry binaryUnion(List geoms)
198	{
199	return binaryUnion(geoms, 0, geoms.size());
200	}
201
202	/**
203	* Unions a section of a list using a recursive binary union on each half
204	* of the section.
205	*
206	* @param geoms the list of geometries containing the section to union
207	* @param start the start index of the section
208	* @param end the index after the end of the section
209	* @return the union of the list section
210	*/
211	private Geometry binaryUnion(List geoms, int start, int end)
212	{
213	if (end - start <= 1) {
214	Geometry g0 = getGeometry(geoms, start);
215	return unionSafe(g0, null);
216	}
217	else if (end - start == 2) {
218	return unionSafe(getGeometry(geoms, start), getGeometry(geoms, start + 1));
219	}
220	else {
221	// recurse on both halves of the list
222	int mid = (end + start) / 2;
223	Geometry g0 = binaryUnion(geoms, start, mid);
224	Geometry g1 = binaryUnion(geoms, mid, end);
225	return unionSafe(g0, g1);
226	}
227	}
228
229	/**
230	* Gets the element at a given list index, or
231	* null if the index is out of range.
232	*
233	* @param list
234	* @param index
235	* @return the geometry at the given index
236	* or null if the index is out of range
237	*/
238	private static Geometry getGeometry(List list, int index)
239	{
240	if (index >= list.size()) return null;
241	return (Geometry) list.get(index);
242	}
243
244	/**
245	* Reduces a tree of geometries to a list of geometries
246	* by recursively unioning the subtrees in the list.
247	*
248	* @param geomTree a tree-structured list of geometries
249	* @return a list of Geometrys
250	*/
251	private List reduceToGeometries(List geomTree)
252	{
253	List geoms = new ArrayList();
254	for (Iterator i = geomTree.iterator(); i.hasNext(); ) {
255	Object o = i.next();
256	Geometry geom = null;
257	if (o instanceof List) {
258	geom = unionTree((List) o);
259	}
260	else if (o instanceof Geometry) {
261	geom = (Geometry) o;
262	}
263	geoms.add(geom);
264	}
265	return geoms;
266	}
267
268	/**
269	* Computes the union of two geometries,
270	* either or both of which may be null.
271	*
272	* @param g0 a Geometry
273	* @param g1 a Geometry
274	* @return the union of the input(s)
275	* or null if both inputs are null
276	*/
277	private Geometry unionSafe(Geometry g0, Geometry g1)
278	{
279	if (g0 == null && g1 == null)
280	return null;
281
282	if (g0 == null)
283	return g1.copy();
284	if (g1 == null)
285	return g0.copy();
286
287	return unionActual( g0, g1 );
288	}
289
290	/**
291	* Encapsulates the actual unioning of two polygonal geometries.
292	*
293	* @param g0
294	* @param g1
295	* @return
296	*/
297	private Geometry unionActual(Geometry g0, Geometry g1)
298	{
299	Geometry union = OverlapUnion.union(g0, g1);;
300	return restrictToPolygons( union );
301	}
302
303	/**
304	* Computes a {@link Geometry} containing only {@link Polygonal} components.
305	* Extracts the {@link Polygon}s from the input
306	* and returns them as an appropriate {@link Polygonal} geometry.
307	* <p>
308	* If the input is already <tt>Polygonal</tt>, it is returned unchanged.
309	* <p>
310	* A particular use case is to filter out non-polygonal components
311	* returned from an overlay operation.
312	*
313	* @param g the geometry to filter
314	* @return a Polygonal geometry
315	*/
316	private static Geometry restrictToPolygons(Geometry g)
317	{
318	if (g instanceof Polygonal) {
319	return g;
320	}
321	List polygons = PolygonExtracter.getPolygons(g);
322	if (polygons.size() == 1)
323	return (Polygon) polygons.get(0);
324	return g.getFactory().createMultiPolygon(GeometryFactory.toPolygonArray(polygons));
325	}
326	}
327