Class DouglasPeuckerSimplifier

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 org.locationtech.jts.geom.Coordinate;
16	import org.locationtech.jts.geom.CoordinateSequence;
17	import org.locationtech.jts.geom.Geometry;
18	import org.locationtech.jts.geom.LinearRing;
19	import org.locationtech.jts.geom.MultiPolygon;
20	import org.locationtech.jts.geom.Polygon;
21	import org.locationtech.jts.geom.util.GeometryTransformer;
22
23	/**
24	* Simplifies a {@link Geometry} using the Douglas-Peucker algorithm.
25	* Ensures that any polygonal geometries returned are valid.
26	* Simple lines are not guaranteed to remain simple after simplification.
27	* All geometry types are handled.
28	* Empty and point geometries are returned unchanged.
29	* Empty geometry components are deleted.
30	* <p>
31	* Note that in general D-P does not preserve topology -
32	* e.g. polygons can be split, collapse to lines or disappear
33	* holes can be created or disappear,
34	* and lines can cross.
35	* To simplify geometry while preserving topology use {@link TopologyPreservingSimplifier}.
36	* (However, using D-P is significantly faster).
37	*<h2>KNOWN BUGS</h2>
38	*<ul>
39	*<li>In some cases the approach used to clean invalid simplified polygons
40	*can distort the output geometry severely.
41	*</ul>
42	*
43	*
44	* @version 1.7
45	* @see TopologyPreservingSimplifier
46	*/
47	public class DouglasPeuckerSimplifier
48	{
49
50	/**
51	* Simplifies a geometry using a given tolerance.
52	*
53	* @param geom geometry to simplify
54	* @param distanceTolerance the tolerance to use
55	* @return a simplified version of the geometry
56	*/
57	public static Geometry simplify(Geometry geom, double distanceTolerance)
58	{
59	DouglasPeuckerSimplifier tss = new DouglasPeuckerSimplifier(geom);
60	tss.setDistanceTolerance(distanceTolerance);
61	return tss.getResultGeometry();
62	}
63
64	private Geometry inputGeom;
65	private double distanceTolerance;
66	private boolean isEnsureValidTopology = true;
67
68	/**
69	* Creates a simplifier for a given geometry.
70	*
71	* @param inputGeom the geometry to simplify
72	*/
73	public DouglasPeuckerSimplifier(Geometry inputGeom)
74	{
75	this.inputGeom = inputGeom;
76	}
77
78	/**
79	* Sets the distance tolerance for the simplification.
80	* All vertices in the simplified geometry will be within this
81	* distance of the original geometry.
82	* The tolerance value must be non-negative.
83	*
84	* @param distanceTolerance the approximation tolerance to use
85	*/
86	public void setDistanceTolerance(double distanceTolerance) {
87	if (distanceTolerance < 0.0)
88	throw new IllegalArgumentException("Tolerance must be non-negative");
89	this.distanceTolerance = distanceTolerance;
90	}
91
92	/**
93	* Controls whether simplified polygons will be "fixed"
94	* to have valid topology.
95	* The caller may choose to disable this because:
96	* <ul>
97	* <li>valid topology is not required
98	* <li>fixing topology is a relative expensive operation
99	* <li>in some pathological cases the topology fixing operation may either fail or run for too long
100	* </ul>
101	*
102	* The default is to fix polygon topology.
103	*
104	* @param isEnsureValidTopology
105	*/
106	public void setEnsureValid(boolean isEnsureValidTopology)
107	{
108	this.isEnsureValidTopology = isEnsureValidTopology;
109	}
110
111	/**
112	* Gets the simplified geometry.
113	*
114	* @return the simplified geometry
115	*/
116	public Geometry getResultGeometry()
117	{
118	// empty input produces an empty result
119	if (inputGeom.isEmpty()) return inputGeom.copy();
120
121	return (new DPTransformer(isEnsureValidTopology, distanceTolerance)).transform(inputGeom);
122	}
123
124	static class DPTransformer
125	extends GeometryTransformer
126	{
127	private boolean isEnsureValidTopology = true;
128	private double distanceTolerance;
129
130	public DPTransformer(boolean isEnsureValidTopology, double distanceTolerance)
131	{
132	this.isEnsureValidTopology = isEnsureValidTopology;
133	this.distanceTolerance = distanceTolerance;
134	}
135
136	protected CoordinateSequence transformCoordinates(CoordinateSequence coords, Geometry parent)
137	{
138	Coordinate[] inputPts = coords.toCoordinateArray();
139	Coordinate[] newPts = null;
140	if (inputPts.length == 0) {
141	newPts = new Coordinate[0];
142	}
143	else {
144	newPts = DouglasPeuckerLineSimplifier.simplify(inputPts, distanceTolerance);
145	}
146	return factory.getCoordinateSequenceFactory().create(newPts);
147	}
148
149	/**
150	* Simplifies a polygon, fixing it if required.
151	*/
152	protected Geometry transformPolygon(Polygon geom, Geometry parent) {
153	// empty geometries are simply removed
154	if (geom.isEmpty())
155	return null;
156	Geometry rawGeom = super.transformPolygon(geom, parent);
157	// don't try and correct if the parent is going to do this
158	if (parent instanceof MultiPolygon) {
159	return rawGeom;
160	}
161	return createValidArea(rawGeom);
162	}
163
164	/**
165	* Simplifies a LinearRing. If the simplification results
166	* in a degenerate ring, remove the component.
167	*
168	* @return null if the simplification results in a degenerate ring
169	*/
170	protected Geometry transformLinearRing(LinearRing geom, Geometry parent)
171	{
172	boolean removeDegenerateRings = parent instanceof Polygon;
173	Geometry simpResult = super.transformLinearRing(geom, parent);
174	if (removeDegenerateRings && ! (simpResult instanceof LinearRing))
175	return null;;
176	return simpResult;
177	}
178
179	/**
180	* Simplifies a MultiPolygon, fixing it if required.
181	*/
182	protected Geometry transformMultiPolygon(MultiPolygon geom, Geometry parent) {
183	Geometry rawGeom = super.transformMultiPolygon(geom, parent);
184	return createValidArea(rawGeom);
185	}
186
187	/**
188	* Creates a valid area geometry from one that possibly has
189	* bad topology (i.e. self-intersections).
190	* Since buffer can handle invalid topology, but always returns
191	* valid geometry, constructing a 0-width buffer "corrects" the
192	* topology.
193	* Note this only works for area geometries, since buffer always returns
194	* areas. This also may return empty geometries, if the input
195	* has no actual area.
196	*
197	* @param rawAreaGeom an area geometry possibly containing self-intersections
198	* @return a valid area geometry
199	*/
200	private Geometry createValidArea(Geometry rawAreaGeom)
201	{
202	if ( isEnsureValidTopology)
203	return rawAreaGeom.buffer(0.0);
204	return rawAreaGeom;
205	}
206	}
207
208	}
209
210
211