Class LineDissolver

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
13	package org.locationtech.jts.dissolve;
14
15	import java.util.ArrayList;
16	import java.util.Collection;
17	import java.util.Iterator;
18	import java.util.List;
19	import java.util.Stack;
20
21	import org.locationtech.jts.edgegraph.HalfEdge;
22	import org.locationtech.jts.edgegraph.MarkHalfEdge;
23	import org.locationtech.jts.geom.Coordinate;
24	import org.locationtech.jts.geom.CoordinateList;
25	import org.locationtech.jts.geom.CoordinateSequence;
26	import org.locationtech.jts.geom.Geometry;
27	import org.locationtech.jts.geom.GeometryComponentFilter;
28	import org.locationtech.jts.geom.GeometryFactory;
29	import org.locationtech.jts.geom.LineString;
30
31
32
33	/**
34	* Dissolves the linear components
35	* from a collection of {@link Geometry}s
36	* into a set of maximal-length {@link Linestring}s
37	* in which every unique segment appears once only.
38	* The output linestrings run between node vertices
39	* of the input, which are vertices which have
40	* either degree 1, or degree 3 or greater.
41	* <p>
42	* Use cases for dissolving linear components
43	* include generalization
44	* (in particular, simplifying polygonal coverages),
45	* and visualization
46	* (in particular, avoiding symbology conflicts when
47	* depicting shared polygon boundaries).
48	* <p>
49	* This class does <b>not</b> node the input lines.
50	* If there are line segments crossing in the input,
51	* they will still cross in the output.
52	*
53	* @author Martin Davis
54	*
55	*/
56	public class LineDissolver
57	{
58	/**
59	* Dissolves the linear components in a geometry.
60	*
61	* @param g the geometry to dissolve
62	* @return the dissolved lines
63	*/
64	public static Geometry dissolve(Geometry g)
65	{
66	LineDissolver d = new LineDissolver();
67	d.add(g);
68	return d.getResult();
69	}
70
71	private Geometry result;
72	private GeometryFactory factory;
73	private DissolveEdgeGraph graph;
74	private List lines = new ArrayList();
75
76	public LineDissolver()
77	{
78	graph = new DissolveEdgeGraph();
79	}
80
81	/**
82	* Adds a {@link Geometry} to be dissolved.
83	* Any number of geometries may be added by calling this method multiple times.
84	* Any type of Geometry may be added. The constituent linework will be
85	* extracted to be dissolved.
86	*
87	* @param geometry geometry to be line-merged
88	*/
89	public void add(Geometry geometry) {
90	geometry.apply(new GeometryComponentFilter() {
91	public void filter(Geometry component) {
92	if (component instanceof LineString) {
93	add((LineString)component);
94	}
95	}
96	});
97	}
98	/**
99	* Adds a collection of Geometries to be processed. May be called multiple times.
100	* Any dimension of Geometry may be added; the constituent linework will be
101	* extracted.
102	*
103	* @param geometries the geometries to be line-merged
104	*/
105	public void add(Collection geometries)
106	{
107	for (Iterator i = geometries.iterator(); i.hasNext(); ) {
108	Geometry geometry = (Geometry) i.next();
109	add(geometry);
110	}
111	}
112
113	private void add(LineString lineString) {
114	if (factory == null) {
115	this.factory = lineString.getFactory();
116	}
117	CoordinateSequence seq = lineString.getCoordinateSequence();
118	boolean doneStart = false;
119	for (int i = 1; i < seq.size(); i++) {
120	DissolveHalfEdge e = (DissolveHalfEdge) graph.addEdge(seq.getCoordinate(i-1), seq.getCoordinate(i));
121	// skip zero-length edges
122	if (e == null) continue;
123	/**
124	* Record source initial segments, so that they can be reflected in output when needed
125	* (i.e. during formation of isolated rings)
126	*/
127	if (! doneStart) {
128	e.setStart();
129	doneStart = true;
130	}
131	}
132	}
133
134	/**
135	* Gets the dissolved result as a MultiLineString.
136	*
137	* @return the dissolved lines
138	*/
139	public Geometry getResult()
140	{
141	if (result == null)
142	computeResult();
143	return result;
144	}
145
146	private void computeResult() {
147	Collection edges = graph.getVertexEdges();
148	for (Iterator i = edges.iterator(); i.hasNext(); ) {
149	HalfEdge e = (HalfEdge) i.next();
150	if (MarkHalfEdge.isMarked(e)) continue;
151	process(e);
152	}
153	result = factory.buildGeometry(lines);
154	}
155
156	private Stack nodeEdgeStack = new Stack();
157
158	private void process(HalfEdge e) {
159	HalfEdge eNode = e.prevNode();
160	// if edge is in a ring, just process this edge
161	if (eNode == null)
162	eNode = e;
163	stackEdges(eNode);
164	// extract lines from node edges in stack
165	buildLines();
166	}
167
168	/**
169	* For each edge in stack
170	* (which must originate at a node)
171	* extracts the line it initiates.
172	*/
173	private void buildLines() {
174	while (! nodeEdgeStack.empty()) {
175	HalfEdge e = (HalfEdge) nodeEdgeStack.pop();
176	if (MarkHalfEdge.isMarked(e))
177	continue;
178	buildLine(e);
179	}
180	}
181
182	private DissolveHalfEdge ringStartEdge;
183
184	/**
185	* Updates the tracked ringStartEdge
186	* if the given edge has a lower origin
187	* (using the standard {@link Coordinate} ordering).
188	*
189	* Identifying the lowest starting node meets two goals:
190	* <ul>
191	* <li>It ensures that isolated input rings are created using the original node and orientation
192	* <li>For isolated rings formed from multiple input linestrings,
193	* it provides a canonical node and orientation for the output
194	* (rather than essentially random, and thus hard to test).
195	* </ul>
196	*
197	* @param e
198	*/
199	private void updateRingStartEdge(DissolveHalfEdge e)
200	{
201	if (! e.isStart()) {
202	e = (DissolveHalfEdge) e.sym();
203	if (! e.isStart()) return;
204	}
205	// here e is known to be a start edge
206	if (ringStartEdge == null) {
207	ringStartEdge = e;
208	return;
209	}
210	if (e.orig().compareTo(ringStartEdge.orig()) < 0) {
211	ringStartEdge = e;
212	}
213	}
214
215	/**
216	* Builds a line starting from the given edge.
217	* The start edge origin is a node (valence = 1 or >= 3),
218	* unless it is part of a pure ring.
219	* A pure ring has no other incident lines.
220	* In this case the start edge may occur anywhere on the ring.
221	*
222	* The line is built up to the next node encountered,
223	* or until the start edge is re-encountered
224	* (which happens if the edges form a ring).
225	*
226	* @param eStart
227	*/
228	private void buildLine(HalfEdge eStart) {
229	CoordinateList line = new CoordinateList();
230	DissolveHalfEdge e = (DissolveHalfEdge) eStart;
231	ringStartEdge = null;
232
233	MarkHalfEdge.markBoth(e);
234	line.add(e.orig().copy(), false);
235	// scan along the path until a node is found (if one exists)
236	while (e.sym().degree() == 2) {
237	updateRingStartEdge(e);
238	DissolveHalfEdge eNext = (DissolveHalfEdge) e.next();
239	// check if edges form a ring - if so, we're done
240	if (eNext == eStart) {
241	buildRing(ringStartEdge);
242	return;
243	}
244	// add point to line, and move to next edge
245	line.add(eNext.orig().copy(), false);
246	e = eNext;
247	MarkHalfEdge.markBoth(e);
248	}
249	// add final node
250	line.add(e.dest().clone(), false);
251
252	// queue up the final node edges
253	stackEdges(e.sym());
254	// store the scanned line
255	addLine(line);
256	}
257
258	private void buildRing(HalfEdge eStartRing) {
259	CoordinateList line = new CoordinateList();
260	HalfEdge e = eStartRing;
261
262	line.add(e.orig().copy(), false);
263	// scan along the path until a node is found (if one exists)
264	while (e.sym().degree() == 2) {
265	HalfEdge eNext = e.next();
266	// check if edges form a ring - if so, we're done
267	if (eNext == eStartRing)
268	break;
269
270	// add point to line, and move to next edge
271	line.add(eNext.orig().copy(), false);
272	e = eNext;
273	}
274	// add final node
275	line.add(e.dest().copy(), false);
276
277	// store the scanned line
278	addLine(line);
279	}
280
281	private void addLine(CoordinateList line) {
282	lines.add(factory.createLineString(line.toCoordinateArray()));
283	}
284
285	/**
286	* Adds edges around this node to the stack.
287	*
288	* @param node
289	*/
290	private void stackEdges(HalfEdge node) {
291	HalfEdge e = node;
292	do {
293	if (! MarkHalfEdge.isMarked(e))
294	nodeEdgeStack.add(e);
295	e = e.oNext();
296	} while (e != node);
297
298	}
299
300	}
301