Class TaggedLineStringSimplifier

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.Iterator;
16	import java.util.List;
17
18	import org.locationtech.jts.algorithm.LineIntersector;
19	import org.locationtech.jts.algorithm.RobustLineIntersector;
20	import org.locationtech.jts.geom.Coordinate;
21	import org.locationtech.jts.geom.LineSegment;
22
23	/**
24	* Simplifies a TaggedLineString, preserving topology
25	* (in the sense that no new intersections are introduced).
26	* Uses the recursive Douglas-Peucker algorithm.
27	*
28	* @author Martin Davis
29	* @version 1.7
30	*/
31	public class TaggedLineStringSimplifier
32	{
33	private LineIntersector li = new RobustLineIntersector();
34	private LineSegmentIndex inputIndex = new LineSegmentIndex();
35	private LineSegmentIndex outputIndex = new LineSegmentIndex();
36	private TaggedLineString line;
37	private Coordinate[] linePts;
38	private double distanceTolerance = 0.0;
39
40	public TaggedLineStringSimplifier(LineSegmentIndex inputIndex,
41	LineSegmentIndex outputIndex)
42	{
43	this.inputIndex = inputIndex;
44	this.outputIndex = outputIndex;
45	}
46
47	/**
48	* Sets the distance tolerance for the simplification.
49	* All vertices in the simplified geometry will be within this
50	* distance of the original geometry.
51	*
52	* @param distanceTolerance the approximation tolerance to use
53	*/
54	public void setDistanceTolerance(double distanceTolerance) {
55	this.distanceTolerance = distanceTolerance;
56	}
57
58	/**
59	* Simplifies the given {@link TaggedLineString}
60	* using the distance tolerance specified.
61	*
62	* @param line the linestring to simplify
63	*/
64	void simplify(TaggedLineString line)
65	{
66	this.line = line;
67	linePts = line.getParentCoordinates();
68	simplifySection(0, linePts.length - 1, 0);
69	}
70
71	private void simplifySection(int i, int j, int depth)
72	{
73	depth += 1;
74	int[] sectionIndex = new int[2];
75	if((i+1) == j) {
76	LineSegment newSeg = line.getSegment(i);
77	line.addToResult(newSeg);
78	// leave this segment in the input index, for efficiency
79	return;
80	}
81
82	boolean isValidToSimplify = true;
83
84	/**
85	* Following logic ensures that there is enough points in the output line.
86	* If there is already more points than the minimum, there's nothing to check.
87	* Otherwise, if in the worst case there wouldn't be enough points,
88	* don't flatten this segment (which avoids the worst case scenario)
89	*/
90	if (line.getResultSize() < line.getMinimumSize()) {
91	int worstCaseSize = depth + 1;
92	if (worstCaseSize < line.getMinimumSize())
93	isValidToSimplify = false;
94	}
95
96	double[] distance = new double[1];
97	int furthestPtIndex = findFurthestPoint(linePts, i, j, distance);
98	// flattening must be less than distanceTolerance
99	if (distance[0] > distanceTolerance) isValidToSimplify = false;
100	// test if flattened section would cause intersection
101	LineSegment candidateSeg = new LineSegment();
102	candidateSeg.p0 = linePts[i];
103	candidateSeg.p1 = linePts[j];
104	sectionIndex[0] = i;
105	sectionIndex[1] = j;
106	if (hasBadIntersection(line, sectionIndex, candidateSeg)) isValidToSimplify = false;
107
108	if (isValidToSimplify) {
109	LineSegment newSeg = flatten(i, j);
110	line.addToResult(newSeg);
111	return;
112	}
113	simplifySection(i, furthestPtIndex, depth);
114	simplifySection(furthestPtIndex, j, depth);
115	}
116
117	private int findFurthestPoint(Coordinate[] pts, int i, int j, double[] maxDistance)
118	{
119	LineSegment seg = new LineSegment();
120	seg.p0 = pts[i];
121	seg.p1 = pts[j];
122	double maxDist = -1.0;
123	int maxIndex = i;
124	for (int k = i + 1; k < j; k++) {
125	Coordinate midPt = pts[k];
126	double distance = seg.distance(midPt);
127	if (distance > maxDist) {
128	maxDist = distance;
129	maxIndex = k;
130	}
131	}
132	maxDistance[0] = maxDist;
133	return maxIndex;
134	}
135
136	/**
137	* Flattens a section of the line between
138	* indexes <code>start</code> and <code>end</code>,
139	* replacing them with a line between the endpoints.
140	* The input and output indexes are updated
141	* to reflect this.
142	*
143	* @param start the start index of the flattened section
144	* @param end the end index of the flattened section
145	* @return the new segment created
146	*/
147	private LineSegment flatten(int start, int end)
148	{
149	// make a new segment for the simplified geometry
150	Coordinate p0 = linePts[start];
151	Coordinate p1 = linePts[end];
152	LineSegment newSeg = new LineSegment(p0, p1);
153	// update the indexes
154	remove(line, start, end);
155	outputIndex.add(newSeg);
156	return newSeg;
157	}
158
159	private boolean hasBadIntersection(TaggedLineString parentLine,
160	int[] sectionIndex,
161	LineSegment candidateSeg)
162	{
163	if (hasBadOutputIntersection(candidateSeg)) return true;
164	if (hasBadInputIntersection(parentLine, sectionIndex, candidateSeg)) return true;
165	return false;
166	}
167
168	private boolean hasBadOutputIntersection(LineSegment candidateSeg)
169	{
170	List querySegs = outputIndex.query(candidateSeg);
171	for (Iterator i = querySegs.iterator(); i.hasNext(); ) {
172	LineSegment querySeg = (LineSegment) i.next();
173	if (hasInteriorIntersection(querySeg, candidateSeg)) {
174	return true;
175	}
176	}
177	return false;
178	}
179
180	private boolean hasBadInputIntersection(TaggedLineString parentLine,
181	int[] sectionIndex,
182	LineSegment candidateSeg)
183	{
184	List querySegs = inputIndex.query(candidateSeg);
185	for (Iterator i = querySegs.iterator(); i.hasNext(); ) {
186	TaggedLineSegment querySeg = (TaggedLineSegment) i.next();
187	if (hasInteriorIntersection(querySeg, candidateSeg)) {
188	if (isInLineSection(parentLine, sectionIndex, querySeg))
189	continue;
190	return true;
191	}
192	}
193	return false;
194	}
195
196	/**
197	* Tests whether a segment is in a section of a TaggedLineString
198	* @param line
199	* @param sectionIndex
200	* @param seg
201	* @return
202	*/
203	private static boolean isInLineSection(
204	TaggedLineString line,
205	int[] sectionIndex,
206	TaggedLineSegment seg)
207	{
208	// not in this line
209	if (seg.getParent() != line.getParent())
210	return false;
211	int segIndex = seg.getIndex();
212	if (segIndex >= sectionIndex[0] && segIndex < sectionIndex[1])
213	return true;
214	return false;
215	}
216
217	private boolean hasInteriorIntersection(LineSegment seg0, LineSegment seg1)
218	{
219	li.computeIntersection(seg0.p0, seg0.p1, seg1.p0, seg1.p1);
220	return li.isInteriorIntersection();
221	}
222
223	/**
224	* Remove the segs in the section of the line
225	* @param line
226	* @param pts
227	* @param sectionStartIndex
228	* @param sectionEndIndex
229	*/
230	private void remove(TaggedLineString line,
231	int start, int end)
232	{
233	for (int i = start; i < end; i++) {
234	TaggedLineSegment seg = line.getSegment(i);
235	inputIndex.remove(seg);
236	}
237	}
238	}
239