Class LineMerger

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.linemerge;
14
15	import java.util.ArrayList;
16	import java.util.Collection;
17	import java.util.Iterator;
18
19	import org.locationtech.jts.geom.Geometry;
20	import org.locationtech.jts.geom.GeometryComponentFilter;
21	import org.locationtech.jts.geom.GeometryFactory;
22	import org.locationtech.jts.geom.LineString;
23	import org.locationtech.jts.planargraph.GraphComponent;
24	import org.locationtech.jts.planargraph.Node;
25	import org.locationtech.jts.util.Assert;
26
27
28	/**
29	* Merges a collection of linear components to form maximal-length linestrings.
30	* <p>
31	* Merging stops at nodes of degree 1 or degree 3 or more.
32	* In other words, all nodes of degree 2 are merged together.
33	* The exception is in the case of an isolated loop, which only has degree-2 nodes.
34	* In this case one of the nodes is chosen as a starting point.
35	* <p>
36	* The direction of each
37	* merged LineString will be that of the majority of the LineStrings from which it
38	* was derived.
39	* <p>
40	* Any dimension of Geometry is handled - the constituent linework is extracted to
41	* form the edges. The edges must be correctly noded; that is, they must only meet
42	* at their endpoints. The LineMerger will accept non-noded input
43	* but will not merge non-noded edges.
44	* <p>
45	* Input lines which are empty or contain only a single unique coordinate are not included
46	* in the merging.
47	*
48	* @version 1.7
49	*/
50	public class LineMerger
51	{
52	private LineMergeGraph graph = new LineMergeGraph();
53	private Collection mergedLineStrings = null;
54	private GeometryFactory factory = null;
55
56	/**
57	* Creates a new line merger.
58	*
59	*/
60	public LineMerger()
61	{
62
63	}
64
65	/**
66	* Adds a Geometry to be processed. May be called multiple times.
67	* Any dimension of Geometry may be added; the constituent linework will be
68	* extracted.
69	*
70	* @param geometry geometry to be line-merged
71	*/
72	public void add(Geometry geometry) {
73	geometry.apply(new GeometryComponentFilter() {
74	public void filter(Geometry component) {
75	if (component instanceof LineString) {
76	add((LineString)component);
77	}
78	}
79	});
80	}
81	/**
82	* Adds a collection of Geometries to be processed. May be called multiple times.
83	* Any dimension of Geometry may be added; the constituent linework will be
84	* extracted.
85	*
86	* @param geometries the geometries to be line-merged
87	*/
88	public void add(Collection geometries)
89	{
90	mergedLineStrings = null;
91	for (Iterator i = geometries.iterator(); i.hasNext(); ) {
92	Geometry geometry = (Geometry) i.next();
93	add(geometry);
94	}
95	}
96	private void add(LineString lineString) {
97	if (factory == null) {
98	this.factory = lineString.getFactory();
99	}
100	graph.addEdge(lineString);
101	}
102
103	private Collection edgeStrings = null;
104
105	private void merge()
106	{
107	if (mergedLineStrings != null) { return; }
108
109	// reset marks (this allows incremental processing)
110	GraphComponent.setMarked(graph.nodeIterator(), false);
111	GraphComponent.setMarked(graph.edgeIterator(), false);
112
113	edgeStrings = new ArrayList();
114	buildEdgeStringsForObviousStartNodes();
115	buildEdgeStringsForIsolatedLoops();
116	mergedLineStrings = new ArrayList();
117	for (Iterator i = edgeStrings.iterator(); i.hasNext(); ) {
118	EdgeString edgeString = (EdgeString) i.next();
119	mergedLineStrings.add(edgeString.toLineString());
120	}
121	}
122
123	private void buildEdgeStringsForObviousStartNodes() {
124	buildEdgeStringsForNonDegree2Nodes();
125	}
126
127	private void buildEdgeStringsForIsolatedLoops() {
128	buildEdgeStringsForUnprocessedNodes();
129	}
130
131	private void buildEdgeStringsForUnprocessedNodes() {
132	for (Iterator i = graph.getNodes().iterator(); i.hasNext(); ) {
133	Node node = (Node) i.next();
134	if (!node.isMarked()) {
135	Assert.isTrue(node.getDegree() == 2);
136	buildEdgeStringsStartingAt(node);
137	node.setMarked(true);
138	}
139	}
140	}
141	private void buildEdgeStringsForNonDegree2Nodes() {
142	for (Iterator i = graph.getNodes().iterator(); i.hasNext(); ) {
143	Node node = (Node) i.next();
144	if (node.getDegree() != 2) {
145	buildEdgeStringsStartingAt(node);
146	node.setMarked(true);
147	}
148	}
149	}
150	private void buildEdgeStringsStartingAt(Node node) {
151	for (Iterator i = node.getOutEdges().iterator(); i.hasNext(); ) {
152	LineMergeDirectedEdge directedEdge = (LineMergeDirectedEdge) i.next();
153	if (directedEdge.getEdge().isMarked()) { continue; }
154	edgeStrings.add(buildEdgeStringStartingWith(directedEdge));
155	}
156	}
157
158	private EdgeString buildEdgeStringStartingWith(LineMergeDirectedEdge start) {
159	EdgeString edgeString = new EdgeString(factory);
160	LineMergeDirectedEdge current = start;
161	do {
162	edgeString.add(current);
163	current.getEdge().setMarked(true);
164	current = current.getNext();
165	} while (current != null && current != start);
166	return edgeString;
167	}
168
169	/**
170	* Gets the {@link LineString}s created by the merging process.
171	*
172	* @return the collection of merged LineStrings
173	*/
174	public Collection getMergedLineStrings() {
175	merge();
176	return mergedLineStrings;
177	}
178	}
179