Class BufferInputLineSimplifier

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	package org.locationtech.jts.operation.buffer;
13
14	import org.locationtech.jts.algorithm.Distance;
15	import org.locationtech.jts.algorithm.Orientation;
16	import org.locationtech.jts.geom.Coordinate;
17	import org.locationtech.jts.geom.CoordinateList;
18
19	/**
20	* Simplifies a buffer input line to
21	* remove concavities with shallow depth.
22	* <p>
23	* The most important benefit of doing this
24	* is to reduce the number of points and the complexity of
25	* shape which will be buffered.
26	* It also reduces the risk of gores created by
27	* the quantized fillet arcs (although this issue
28	* should be eliminated in any case by the
29	* offset curve generation logic).
30	* <p>
31	* A key aspect of the simplification is that it
32	* affects inside (concave or inward) corners only.
33	* Convex (outward) corners are preserved, since they
34	* are required to ensure that the generated buffer curve
35	* lies at the correct distance from the input geometry.
36	* <p>
37	* Another important heuristic used is that the end segments
38	* of the input are never simplified. This ensures that
39	* the client buffer code is able to generate end caps faithfully.
40	* <p>
41	* No attempt is made to avoid self-intersections in the output.
42	* This is acceptable for use for generating a buffer offset curve,
43	* since the buffer algorithm is insensitive to invalid polygonal
44	* geometry. However,
45	* this means that this algorithm
46	* cannot be used as a general-purpose polygon simplification technique.
47	*
48	* @author Martin Davis
49	*
50	*/
51	public class BufferInputLineSimplifier
52	{
53	/**
54	* Simplify the input coordinate list.
55	* If the distance tolerance is positive,
56	* concavities on the LEFT side of the line are simplified.
57	* If the supplied distance tolerance is negative,
58	* concavities on the RIGHT side of the line are simplified.
59	*
60	* @param inputLine the coordinate list to simplify
61	* @param distanceTol simplification distance tolerance to use
62	* @return the simplified coordinate list
63	*/
64	public static Coordinate[] simplify(Coordinate[] inputLine, double distanceTol)
65	{
66	BufferInputLineSimplifier simp = new BufferInputLineSimplifier(inputLine);
67	return simp.simplify(distanceTol);
68	}
69
70	private static final int INIT = 0;
71	private static final int DELETE = 1;
72	private static final int KEEP = 1;
73
74
75	private Coordinate[] inputLine;
76	private double distanceTol;
77	private byte[] isDeleted;
78	private int angleOrientation = Orientation.COUNTERCLOCKWISE;
79
80	public BufferInputLineSimplifier(Coordinate[] inputLine) {
81	this.inputLine = inputLine;
82	}
83
84	/**
85	* Simplify the input coordinate list.
86	* If the distance tolerance is positive,
87	* concavities on the LEFT side of the line are simplified.
88	* If the supplied distance tolerance is negative,
89	* concavities on the RIGHT side of the line are simplified.
90	*
91	* @param distanceTol simplification distance tolerance to use
92	* @return the simplified coordinate list
93	*/
94	public Coordinate[] simplify(double distanceTol)
95	{
96	this.distanceTol = Math.abs(distanceTol);
97	if (distanceTol < 0)
98	angleOrientation = Orientation.CLOCKWISE;
99
100	// rely on fact that boolean array is filled with false value
101	isDeleted = new byte[inputLine.length];
102
103	boolean isChanged = false;
104	do {
105	isChanged = deleteShallowConcavities();
106	} while (isChanged);
107
108	return collapseLine();
109	}
110
111	/**
112	* Uses a sliding window containing 3 vertices to detect shallow angles
113	* in which the middle vertex can be deleted, since it does not
114	* affect the shape of the resulting buffer in a significant way.
115	* @return
116	*/
117	private boolean deleteShallowConcavities()
118	{
119	/**
120	* Do not simplify end line segments of the line string.
121	* This ensures that end caps are generated consistently.
122	*/
123	int index = 1;
124
125	int midIndex = findNextNonDeletedIndex(index);
126	int lastIndex = findNextNonDeletedIndex(midIndex);
127
128	boolean isChanged = false;
129	while (lastIndex < inputLine.length) {
130	// test triple for shallow concavity
131	boolean isMiddleVertexDeleted = false;
132	if (isDeletable(index, midIndex, lastIndex,
133	distanceTol)) {
134	isDeleted[midIndex] = DELETE;
135	isMiddleVertexDeleted = true;
136	isChanged = true;
137	}
138	// move simplification window forward
139	if (isMiddleVertexDeleted)
140	index = lastIndex;
141	else
142	index = midIndex;
143
144	midIndex = findNextNonDeletedIndex(index);
145	lastIndex = findNextNonDeletedIndex(midIndex);
146	}
147	return isChanged;
148	}
149
150	/**
151	* Finds the next non-deleted index, or the end of the point array if none
152	* @param index
153	* @return the next non-deleted index, if any
154	* or inputLine.length if there are no more non-deleted indices
155	*/
156	private int findNextNonDeletedIndex(int index)
157	{
158	int next = index + 1;
159	while (next < inputLine.length && isDeleted[next] == DELETE)
160	next++;
161	return next;
162	}
163
164	private Coordinate[] collapseLine()
165	{
166	CoordinateList coordList = new CoordinateList();
167	for (int i = 0; i < inputLine.length; i++) {
168	if (isDeleted[i] != DELETE)
169	coordList.add(inputLine[i]);
170	}
171	// if (coordList.size() < inputLine.length) System.out.println("Simplified " + (inputLine.length - coordList.size()) + " pts");
172	return coordList.toCoordinateArray();
173	}
174
175	private boolean isDeletable(int i0, int i1, int i2, double distanceTol)
176	{
177	Coordinate p0 = inputLine[i0];
178	Coordinate p1 = inputLine[i1];
179	Coordinate p2 = inputLine[i2];
180
181	if (! isConcave(p0, p1, p2)) return false;
182	if (! isShallow(p0, p1, p2, distanceTol)) return false;
183
184	// MD - don't use this heuristic - it's too restricting
185	// if (p0.distance(p2) > distanceTol) return false;
186
187	return isShallowSampled(p0, p1, i0, i2, distanceTol);
188	}
189
190	private boolean isShallowConcavity(Coordinate p0, Coordinate p1, Coordinate p2, double distanceTol)
191	{
192	int orientation = Orientation.index(p0, p1, p2);
193	boolean isAngleToSimplify = (orientation == angleOrientation);
194	if (! isAngleToSimplify)
195	return false;
196
197	double dist = Distance.pointToSegment(p1, p0, p2);
198	return dist < distanceTol;
199	}
200
201	private static final int NUM_PTS_TO_CHECK = 10;
202
203	/**
204	* Checks for shallowness over a sample of points in the given section.
205	* This helps prevents the simplification from incrementally
206	* "skipping" over points which are in fact non-shallow.
207	*
208	* @param p0 start coordinate of section
209	* @param p2 end coordinate of section
210	* @param i0 start index of section
211	* @param i2 end index of section
212	* @param distanceTol distance tolerance
213	* @return
214	*/
215	private boolean isShallowSampled(Coordinate p0, Coordinate p2, int i0, int i2, double distanceTol)
216	{
217	// check every n'th point to see if it is within tolerance
218	int inc = (i2 - i0) / NUM_PTS_TO_CHECK;
219	if (inc <= 0) inc = 1;
220
221	for (int i = i0; i < i2; i += inc) {
222	if (! isShallow(p0, p2, inputLine[i], distanceTol)) return false;
223	}
224	return true;
225	}
226
227	private boolean isShallow(Coordinate p0, Coordinate p1, Coordinate p2, double distanceTol)
228	{
229	double dist = Distance.pointToSegment(p1, p0, p2);
230	return dist < distanceTol;
231	}
232
233
234	private boolean isConcave(Coordinate p0, Coordinate p1, Coordinate p2)
235	{
236	int orientation = Orientation.index(p0, p1, p2);
237	boolean isConcave = (orientation == angleOrientation);
238	return isConcave;
239	}
240	}
241