Class UnaryUnionOp

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
15	import java.util.Collection;
16	import java.util.List;
17
18	import org.locationtech.jts.geom.Geometry;
19	import org.locationtech.jts.geom.GeometryCollection;
20	import org.locationtech.jts.geom.GeometryFactory;
21	import org.locationtech.jts.geom.LineString;
22	import org.locationtech.jts.geom.Point;
23	import org.locationtech.jts.geom.Polygon;
24	import org.locationtech.jts.geom.Puntal;
25	import org.locationtech.jts.operation.linemerge.LineMerger;
26	import org.locationtech.jts.operation.overlay.OverlayOp;
27	import org.locationtech.jts.operation.overlay.snap.SnapIfNeededOverlayOp;
28
29	/**
30	* Unions a <code>Collection</code> of {@link Geometry}s or a single Geometry
31	* (which may be a {@link GeoometryCollection}) together.
32	* By using this special-purpose operation over a collection of geometries
33	* it is possible to take advantage of various optimizations to improve performance.
34	* Heterogeneous {@link GeometryCollection}s are fully supported.
35	* <p>
36	* The result obeys the following contract:
37	* <ul>
38	* <li>Unioning a set of {@link Polygon}s has the effect of
39	* merging the areas (i.e. the same effect as
40	* iteratively unioning all individual polygons together).
41	*
42	* <li>Unioning a set of {@link LineString}s has the effect of <b>noding</b>
43	* and <b>dissolving</b> the input linework.
44	* In this context "fully noded" means that there will be
45	* an endpoint or node in the result
46	* for every endpoint or line segment crossing in the input.
47	* "Dissolved" means that any duplicate (i.e. coincident) line segments or portions
48	* of line segments will be reduced to a single line segment in the result.
49	* This is consistent with the semantics of the
50	* {@link Geometry#union(Geometry)} operation.
51	* If <b>merged</b> linework is required, the {@link LineMerger} class can be used.
52	*
53	* <li>Unioning a set of {@link Point}s has the effect of merging
54	* all identical points (producing a set with no duplicates).
55	* </ul>
56	*
57	* <tt>UnaryUnion</tt> always operates on the individual components of MultiGeometries.
58	* So it is possible to use it to "clean" invalid self-intersecting MultiPolygons
59	* (although the polygon components must all still be individually valid.)
60	*
61	* @author mbdavis
62	*
63	*/
64	public class UnaryUnionOp
65	{
66	/**
67	* Computes the geometric union of a {@link Collection}
68	* of {@link Geometry}s.
69	*
70	* @param geoms a collection of geometries
71	* @return the union of the geometries,
72	* or <code>null</code> if the input is empty
73	*/
74	public static Geometry union(Collection geoms)
75	{
76	UnaryUnionOp op = new UnaryUnionOp(geoms);
77	return op.union();
78	}
79
80	/**
81	* Computes the geometric union of a {@link Collection}
82	* of {@link Geometry}s.
83	*
84	* If no input geometries were provided but a {@link GeometryFactory} was provided,
85	* an empty {@link GeometryCollection} is returned.
86	*
87	* @param geoms a collection of geometries
88	* @param geomFact the geometry factory to use if the collection is empty
89	* @return the union of the geometries,
90	* or an empty GEOMETRYCOLLECTION
91	*/
92	public static Geometry union(Collection geoms, GeometryFactory geomFact)
93	{
94	UnaryUnionOp op = new UnaryUnionOp(geoms, geomFact);
95	return op.union();
96	}
97
98	/**
99	* Constructs a unary union operation for a {@link Geometry}
100	* (which may be a {@link GeometryCollection}).
101	*
102	* @param geom a geometry to union
103	* @return the union of the elements of the geometry
104	* or an empty GEOMETRYCOLLECTION
105	*/
106	public static Geometry union(Geometry geom)
107	{
108	UnaryUnionOp op = new UnaryUnionOp(geom);
109	return op.union();
110	}
111
112	private GeometryFactory geomFact = null;
113	private InputExtracter extracter;
114
115	/**
116	* Constructs a unary union operation for a {@link Collection}
117	* of {@link Geometry}s.
118	*
119	* @param geoms a collection of geometries
120	* @param geomFact the geometry factory to use if the collection is empty
121	*/
122	public UnaryUnionOp(Collection geoms, GeometryFactory geomFact)
123	{
124	this.geomFact = geomFact;
125	extract(geoms);
126	}
127
128	/**
129	* Constructs a unary union operation for a {@link Collection}
130	* of {@link Geometry}s, using the {@link GeometryFactory}
131	* of the input geometries.
132	*
133	* @param geoms a collection of geometries
134	*/
135	public UnaryUnionOp(Collection geoms)
136	{
137	extract(geoms);
138	}
139
140	/**
141	* Constructs a unary union operation for a {@link Geometry}
142	* (which may be a {@link GeometryCollection}).
143	* @param geom
144	*/
145	public UnaryUnionOp(Geometry geom)
146	{
147	extract(geom);
148	}
149
150	private void extract(Collection geoms)
151	{
152	extracter = InputExtracter.extract(geoms);
153	}
154
155	private void extract(Geometry geom)
156	{
157	extracter = InputExtracter.extract(geom);
158	}
159
160	/**
161	* Gets the union of the input geometries.
162	* <p>
163	* The result of empty input is determined as follows:
164	* <ol>
165	* <li>If the input is empty and a dimension can be
166	* determined (i.e. an empty geometry is present),
167	* an empty atomic geometry of that dimension is returned.
168	* <li>If no input geometries were provided but a {@link GeometryFactory} was provided,
169	* an empty {@link GeometryCollection} is returned.
170	* <li>Otherwise, the return value is <code>null</code>.
171	* </ol>
172	*
173	* @return a Geometry containing the union,
174	* or an empty atomic geometry, or an empty GEOMETRYCOLLECTION,
175	* or <code>null</code> if no GeometryFactory was provided
176	*/
177	public Geometry union()
178	{
179	if (geomFact == null)
180	geomFact = extracter.getFactory();
181
182	// Case 3
183	if (geomFact == null) {
184	return null;
185	}
186
187	// Case 1 & 2
188	if (extracter.isEmpty()) {
189	return geomFact.createEmpty( extracter.getDimension() );
190	}
191	List points = extracter.getExtract(0);
192	List lines = extracter.getExtract(1);
193	List polygons = extracter.getExtract(2);
194
195	/**
196	* For points and lines, only a single union operation is
197	* required, since the OGC model allows self-intersecting
198	* MultiPoint and MultiLineStrings.
199	* This is not the case for polygons, so Cascaded Union is required.
200	*/
201	Geometry unionPoints = null;
202	if (points.size() > 0) {
203	Geometry ptGeom = geomFact.buildGeometry(points);
204	unionPoints = unionNoOpt(ptGeom);
205	}
206
207	Geometry unionLines = null;
208	if (lines.size() > 0) {
209	Geometry lineGeom = geomFact.buildGeometry(lines);
210	unionLines = unionNoOpt(lineGeom);
211	}
212
213	Geometry unionPolygons = null;
214	if (polygons.size() > 0) {
215	unionPolygons = CascadedPolygonUnion.union(polygons);
216	}
217
218	/**
219	* Performing two unions is somewhat inefficient,
220	* but is mitigated by unioning lines and points first
221	*/
222	Geometry unionLA = unionWithNull(unionLines, unionPolygons);
223	Geometry union = null;
224	if (unionPoints == null)
225	union = unionLA;
226	else if (unionLA == null)
227	union = unionPoints;
228	else
229	union = PointGeometryUnion.union((Puntal) unionPoints, unionLA);
230
231	if (union == null)
232	return geomFact.createGeometryCollection();
233
234	return union;
235	}
236
237	/**
238	* Computes the union of two geometries,
239	* either of both of which may be null.
240	*
241	* @param g0 a Geometry
242	* @param g1 a Geometry
243	* @return the union of the input(s)
244	* or null if both inputs are null
245	*/
246	private Geometry unionWithNull(Geometry g0, Geometry g1)
247	{
248	if (g0 == null && g1 == null)
249	return null;
250
251	if (g1 == null)
252	return g0;
253	if (g0 == null)
254	return g1;
255
256	return g0.union(g1);
257	}
258
259	/**
260	* Computes a unary union with no extra optimization,
261	* and no short-circuiting.
262	* Due to the way the overlay operations
263	* are implemented, this is still efficient in the case of linear
264	* and puntal geometries.
265	* Uses robust version of overlay operation
266	* to ensure identical behaviour to the <tt>union(Geometry)</tt> operation.
267	*
268	* @param g0 a geometry
269	* @return the union of the input geometry
270	*/
271	private Geometry unionNoOpt(Geometry g0)
272	{
273	Geometry empty = geomFact.createPoint();
274	return SnapIfNeededOverlayOp.overlayOp(g0, empty, OverlayOp.UNION);
275	}
276
277	}
278