Class TopologyPreservingSimplifier

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.simplify;
14
15	import java.util.HashMap;
16	import java.util.Map;
17
18	import org.locationtech.jts.geom.CoordinateSequence;
19	import org.locationtech.jts.geom.Geometry;
20	import org.locationtech.jts.geom.GeometryComponentFilter;
21	import org.locationtech.jts.geom.LineString;
22	import org.locationtech.jts.geom.LinearRing;
23	import org.locationtech.jts.geom.MultiPolygon;
24	import org.locationtech.jts.geom.Polygon;
25	import org.locationtech.jts.geom.util.GeometryTransformer;
26
27	/**
28	* Simplifies a geometry and ensures that
29	* the result is a valid geometry having the
30	* same dimension and number of components as the input,
31	* and with the components having the same topological
32	* relationship.
33	* <p>
34	* If the input is a polygonal geometry
35	* ( {@link Polygon} or {@link MultiPolygon} ):
36	* <ul>
37	* <li>The result has the same number of shells and holes as the input,
38	* with the same topological structure
39	* <li>The result rings touch at <b>no more</b> than the number of touching points in the input
40	* (although they may touch at fewer points).
41	* The key implication of this statement is that if the
42	* input is topologically valid, so is the simplified output.
43	* </ul>
44	* For linear geometries, if the input does not contain
45	* any intersecting line segments, this property
46	* will be preserved in the output.
47	* <p>
48	* For all geometry types, the result will contain
49	* enough vertices to ensure validity. For polygons
50	* and closed linear geometries, the result will have at
51	* least 4 vertices; for open linestrings the result
52	* will have at least 2 vertices.
53	* <p>
54	* All geometry types are handled.
55	* Empty and point geometries are returned unchanged.
56	* Empty geometry components are deleted.
57	* <p>
58	* The simplification uses a maximum-distance difference algorithm
59	* similar to the Douglas-Peucker algorithm.
60	*
61	* <h3>KNOWN BUGS</h3>
62	* <ul>
63	* <li>May create invalid topology if there are components which are
64	* small relative to the tolerance value.
65	* In particular, if a small hole is very near an edge, it is possible for the edge to be moved by
66	* a relatively large tolerance value and end up with the hole outside the result shell
67	* (or inside another hole).
68	* Similarly, it is possible for a small polygon component to end up inside
69	* a nearby larger polygon.
70	* A workaround is to test for this situation in post-processing and remove
71	* any invalid holes or polygons.
72	* </ul>
73	*
74	* @author Martin Davis
75	* @see DouglasPeuckerSimplifier
76	*
77	*/
78	public class TopologyPreservingSimplifier
79	{
80	public static Geometry simplify(Geometry geom, double distanceTolerance)
81	{
82	TopologyPreservingSimplifier tss = new TopologyPreservingSimplifier(geom);
83	tss.setDistanceTolerance(distanceTolerance);
84	return tss.getResultGeometry();
85	}
86
87	private Geometry inputGeom;
88	private TaggedLinesSimplifier lineSimplifier = new TaggedLinesSimplifier();
89	private Map linestringMap;
90
91	public TopologyPreservingSimplifier(Geometry inputGeom)
92	{
93	this.inputGeom = inputGeom;
94	}
95
96	/**
97	* Sets the distance tolerance for the simplification.
98	* All vertices in the simplified geometry will be within this
99	* distance of the original geometry.
100	* The tolerance value must be non-negative. A tolerance value
101	* of zero is effectively a no-op.
102	*
103	* @param distanceTolerance the approximation tolerance to use
104	*/
105	public void setDistanceTolerance(double distanceTolerance) {
106	if (distanceTolerance < 0.0)
107	throw new IllegalArgumentException("Tolerance must be non-negative");
108	lineSimplifier.setDistanceTolerance(distanceTolerance);
109	}
110
111	public Geometry getResultGeometry()
112	{
113	// empty input produces an empty result
114	if (inputGeom.isEmpty()) return inputGeom.copy();
115
116	linestringMap = new HashMap();
117	inputGeom.apply(new LineStringMapBuilderFilter(this));
118	lineSimplifier.simplify(linestringMap.values());
119	Geometry result = (new LineStringTransformer(linestringMap)).transform(inputGeom);
120	return result;
121	}
122
123	static class LineStringTransformer
124	extends GeometryTransformer
125	{
126	private Map linestringMap;
127
128	public LineStringTransformer(Map linestringMap) {
129	this.linestringMap = linestringMap;
130	}
131
132	protected CoordinateSequence transformCoordinates(CoordinateSequence coords, Geometry parent)
133	{
134	if (coords.size() == 0) return null;
135	// for linear components (including rings), simplify the linestring
136	if (parent instanceof LineString) {
137	TaggedLineString taggedLine = (TaggedLineString) linestringMap.get(parent);
138	return createCoordinateSequence(taggedLine.getResultCoordinates());
139	}
140	// for anything else (e.g. points) just copy the coordinates
141	return super.transformCoordinates(coords, parent);
142	}
143	}
144
145	/**
146	* A filter to add linear geometries to the linestring map
147	* with the appropriate minimum size constraint.
148	* Closed {@link LineString}s (including {@link LinearRing}s
149	* have a minimum output size constraint of 4,
150	* to ensure the output is valid.
151	* For all other linestrings, the minimum size is 2 points.
152	*
153	* @author Martin Davis
154	*
155	*/
156	static class LineStringMapBuilderFilter
157	implements GeometryComponentFilter
158	{
159	TopologyPreservingSimplifier tps;
160
161	LineStringMapBuilderFilter(TopologyPreservingSimplifier tps) {
162	this.tps = tps;
163	}
164
165	/**
166	* Filters linear geometries.
167	*
168	* geom a geometry of any type
169	*/
170	public void filter(Geometry geom)
171	{
172	if (geom instanceof LineString) {
173	LineString line = (LineString) geom;
174	// skip empty geometries
175	if (line.isEmpty()) return;
176
177	int minSize = ((LineString) line).isClosed() ? 4 : 2;
178	TaggedLineString taggedLine = new TaggedLineString((LineString) line, minSize);
179	tps.linestringMap.put(line, taggedLine);
180	}
181	}
182	}
183
184	}
185
186