Class OverlapUnion

1	/*
2	* Copyright (c) 2019 Martin Davis.
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
13	package org.locationtech.jts.operation.union;
14
15	import java.util.ArrayList;
16	import java.util.HashSet;
17	import java.util.List;
18	import java.util.Set;
19
20	import org.locationtech.jts.geom.Coordinate;
21	import org.locationtech.jts.geom.CoordinateSequence;
22	import org.locationtech.jts.geom.CoordinateSequenceFilter;
23	import org.locationtech.jts.geom.Envelope;
24	import org.locationtech.jts.geom.Geometry;
25	import org.locationtech.jts.geom.GeometryFactory;
26	import org.locationtech.jts.geom.LineSegment;
27	import org.locationtech.jts.geom.TopologyException;
28	import org.locationtech.jts.geom.util.GeometryCombiner;
29
30	/**
31	* Unions MultiPolygons efficiently by
32	* using full topological union only for polygons which may overlap
33	* by virtue of intersecting the common area of the inputs.
34	* Other polygons are simply combined with the union result,
35	* which is much more performant.
36	* <p>
37	* This situation is likely to occur during cascaded polygon union,
38	* since the partitioning of polygons is done heuristically
39	* and thus may group disjoint polygons which can lie far apart.
40	* It may also occur in real world data which contains many disjoint polygons
41	* (e.g. polygons representing parcels on different street blocks).
42	* <h2>Algorithm</h2>
43	* The overlap region is determined as the common envelope of intersection.
44	* The input polygons are partitioned into two sets:
45	* <ul>
46	* <li>Overlapping: Polygons which intersect the overlap region, and thus potentially overlap each other
47	* <li>Disjoint: Polygons which are disjoint from (lie wholly outside) the overlap region
48	* </ul>
49	* The Overlapping set is fully unioned, and then combined with the Disjoint set.
50	* Performing a simple combine works because
51	* the disjoint polygons do not interact with each
52	* other (since the inputs are valid MultiPolygons).
53	* They also do not interact with the Overlapping polygons,
54	* since they are outside their envelope.
55	*
56	* <h2>Verification</h2>
57	* In the general case the Overlapping set of polygons will
58	* extend beyond the overlap envelope. This means that the union result
59	* will extend beyond the overlap region.
60	* There is a small chance that the topological
61	* union of the overlap region will shift the result linework enough
62	* that the result geometry intersects one of the Disjoint geometries.
63	* This case is detected and if it occurs
64	* is remedied by falling back to performing a full union of the original inputs.
65	* Detection is done by a fairly efficient comparison of edge segments which
66	* extend beyond the overlap region. If any segments have changed
67	* then there is a risk of introduced intersections, and full union is performed.
68	* <p>
69	* This situation has not been observed in JTS using floating precision,
70	* but it could happen due to snapping. It has been observed
71	* in other APIs (e.g. GEOS) due to more aggressive snapping.
72	* And it will be more likely to happen if a snap-rounding overlay is used.
73	*
74	* @author mbdavis
75	*
76	*/
77	public class OverlapUnion
78	{
79	/**
80	* Union a pair of geometries,
81	* using the more performant overlap union algorithm if possible.
82	*
83	* @param g0 a geometry to union
84	* @param g1 a geometry to union
85	* @return the union of the inputs
86	*/
87	public static Geometry union(Geometry g0, Geometry g1)
88	{
89	OverlapUnion union = new OverlapUnion(g0, g1);
90	return union.union();
91	}
92
93	private GeometryFactory geomFactory;
94
95	private Geometry g0;
96	private Geometry g1;
97
98	private boolean isUnionSafe;
99
100
101	/**
102	* Creates a new instance for unioning the given geometries.
103	*
104	* @param g0 a geometry to union
105	* @param g1 a geometry to union
106	*/
107	public OverlapUnion(Geometry g0, Geometry g1)
108	{
109	this.g0 = g0;
110	this.g1 = g1;
111	geomFactory = g0.getFactory();
112	}
113
114	/**
115	* Unions the input geometries,
116	* using the more performant overlap union algorithm if possible.
117	*
118	* @return the union of the inputs
119	*/
120	public Geometry union()
121	{
122	Envelope overlapEnv = overlapEnvelope(g0, g1);
123
124	/**
125	* If no overlap, can just combine the geometries
126	*/
127	if (overlapEnv.isNull()) {
128	Geometry g0Copy = g0.copy();
129	Geometry g1Copy = g1.copy();
130	return GeometryCombiner.combine(g0Copy, g1Copy);
131	}
132
133	List<Geometry> disjointPolys = new ArrayList<Geometry>();
134
135	Geometry g0Overlap = extractByEnvelope(overlapEnv, g0, disjointPolys);
136	Geometry g1Overlap = extractByEnvelope(overlapEnv, g1, disjointPolys);
137
138	// System.out.println("# geoms in common: " + intersectingPolys.size());
139	Geometry unionGeom = unionFull(g0Overlap, g1Overlap);
140
141	Geometry result = null;
142	isUnionSafe = isBorderSegmentsSame(unionGeom, overlapEnv);
143	if (! isUnionSafe) {
144	// overlap union changed border segments... need to do full union
145	//System.out.println("OverlapUnion: Falling back to full union");
146	result = unionFull(g0, g1);
147	}
148	else {
149	//System.out.println("OverlapUnion: fast path");
150	result = combine(unionGeom, disjointPolys);
151	}
152	return result;
153	}
154
155	/**
156	* Allows checking whether the optimized
157	* or full union was performed.
158	* Used for unit testing.
159	*
160	* @return true if the optimized union was performed
161	*/
162	boolean isUnionOptimized() {
163	return isUnionSafe;
164	}
165
166	private static Envelope overlapEnvelope(Geometry g0, Geometry g1) {
167	Envelope g0Env = g0.getEnvelopeInternal();
168	Envelope g1Env = g1.getEnvelopeInternal();
169	Envelope overlapEnv = g0Env.intersection(g1Env);
170	return overlapEnv;
171	}
172
173	private Geometry combine(Geometry unionGeom, List<Geometry> disjointPolys) {
174	if (disjointPolys.size() <= 0)
175	return unionGeom;
176
177	disjointPolys.add(unionGeom);
178	Geometry result = GeometryCombiner.combine(disjointPolys);
179	return result;
180	}
181
182	private Geometry extractByEnvelope(Envelope env, Geometry geom,
183	List<Geometry> disjointGeoms)
184	{
185	List<Geometry> intersectingGeoms = new ArrayList<Geometry>();
186	for (int i = 0; i < geom.getNumGeometries(); i++) {
187	Geometry elem = geom.getGeometryN(i);
188	if (elem.getEnvelopeInternal().intersects(env)) {
189	intersectingGeoms.add(elem);
190	}
191	else {
192	Geometry copy = elem.copy();
193	disjointGeoms.add(copy);
194	}
195	}
196	return geomFactory.buildGeometry(intersectingGeoms);
197	}
198
199	private Geometry unionFull(Geometry geom0, Geometry geom1) {
200	try {
201	return geom0.union(geom1);
202	}
203	catch (TopologyException ex) {
204	/**
205	* If the overlay union fails,
206	* try a buffer union, which often succeeds
207	*/
208	return unionBuffer(geom0, geom1);
209	}
210	}
211
212	/**
213	* Implements union using the buffer-by-zero trick.
214	* This seems to be more robust than overlay union,
215	* for reasons somewhat unknown.
216	*
217	* @param g0 a geometry
218	* @param g1 a geometry
219	* @return the union of the geometries
220	*/
221	private static Geometry unionBuffer(Geometry g0, Geometry g1)
222	{
223	GeometryFactory factory = g0.getFactory();
224	Geometry gColl = factory.createGeometryCollection(new Geometry[] { g0, g1 } );
225	Geometry union = gColl.buffer(0.0);
226	return union;
227	}
228
229	private boolean isBorderSegmentsSame(Geometry result, Envelope env) {
230	List<LineSegment> segsBefore = extractBorderSegments(g0, g1, env);
231
232	List<LineSegment> segsAfter = new ArrayList<LineSegment>();
233	extractBorderSegments(result, env, segsAfter);
234
235	//System.out.println("# seg before: " + segsBefore.size() + " - # seg after: " + segsAfter.size());
236	return isEqual(segsBefore, segsAfter);
237	}
238
239	private boolean isEqual(List<LineSegment> segs0, List<LineSegment> segs1) {
240	if (segs0.size() != segs1.size())
241	return false;
242
243	Set<LineSegment> segIndex = new HashSet<LineSegment>(segs0);
244
245	for (LineSegment seg : segs1) {
246	if (! segIndex.contains(seg)) {
247	//System.out.println("Found changed border seg: " + seg);
248	return false;
249	}
250	}
251	return true;
252	}
253
254	private List<LineSegment> extractBorderSegments(Geometry geom0, Geometry geom1, Envelope env) {
255	List<LineSegment> segs = new ArrayList<LineSegment>();
256	extractBorderSegments(geom0, env, segs);
257	if (geom1 != null)
258	extractBorderSegments(geom1, env, segs);
259	return segs;
260	}
261
262	private static boolean intersects(Envelope env, Coordinate p0, Coordinate p1) {
263	return env.intersects(p0) \|\| env.intersects(p1);
264	}
265
266	private static boolean containsProperly(Envelope env, Coordinate p0, Coordinate p1) {
267	return containsProperly(env, p0) && containsProperly(env, p1);
268	}
269
270	private static boolean containsProperly(Envelope env, Coordinate p) {
271	if (env.isNull()) return false;
272	return p.getX() > env.getMinX() &&
273	p.getX() < env.getMaxX() &&
274	p.getY() > env.getMinY() &&
275	p.getY() < env.getMaxY();
276	}
277
278	private static void extractBorderSegments(Geometry geom, Envelope env, List<LineSegment> segs) {
279	geom.apply(new CoordinateSequenceFilter() {
280
281	public void filter(CoordinateSequence seq, int i) {
282	if (i <= 0) return;
283
284	// extract LineSegment
285	Coordinate p0 = seq.getCoordinate(i - 1);
286	Coordinate p1 = seq.getCoordinate(i);
287	boolean isBorder = intersects(env, p0, p1) && ! containsProperly(env, p0, p1);
288	if (isBorder) {
289	LineSegment seg = new LineSegment(p0, p1);
290	segs.add(seg);
291	}
292	}
293
294	public boolean isDone() { return false; }
295
296	public boolean isGeometryChanged() { return false; }
297
298	});
299	}
300
301	}
302
303