Class VariableBuffer

1	/*
2	* Copyright (c) 2019 Martin Davis.
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 java.util.ArrayList;
15	import java.util.List;
16
17	import org.locationtech.jts.algorithm.Angle;
18	import org.locationtech.jts.geom.Coordinate;
19	import org.locationtech.jts.geom.CoordinateList;
20	import org.locationtech.jts.geom.Geometry;
21	import org.locationtech.jts.geom.GeometryCollection;
22	import org.locationtech.jts.geom.GeometryFactory;
23	import org.locationtech.jts.geom.LineSegment;
24	import org.locationtech.jts.geom.LineString;
25	import org.locationtech.jts.geom.Polygon;
26
27	/**
28	* Creates a buffer polygon with a varying buffer distance
29	* at each vertex along a line.
30	* <p>
31	* Only single lines are supported as input, since buffer widths
32	* are typically specified individually for each line.
33	*
34	* @author Martin Davis
35	*
36	*/
37	public class VariableBuffer {
38
39	/**
40	* Creates a buffer polygon along a line with the buffer distance interpolated
41	* between a start distance and an end distance.
42	*
43	* @param line the line to buffer
44	* @param startDistance the buffer width at the start of the line
45	* @param endDistance the buffer width at the end of the line
46	* @return the variable-distance buffer polygon
47	*/
48	public static Geometry buffer(Geometry line, double startDistance,
49	double endDistance) {
50	double[] distance = interpolate((LineString) line,
51	startDistance, endDistance);
52	VariableBuffer vb = new VariableBuffer(line, distance);
53	return vb.getResult();
54	}
55
56	/**
57	* Creates a buffer polygon along a line with the buffer distance interpolated
58	* between a start distance, a middle distance and an end distance.
59	* The middle distance is attained at
60	* the vertex at or just past the half-length of the line.
61	* For smooth buffering of a {@link LinearRing} (or the rings of a {@link Polygon})
62	* the start distance and end distance should be equal.
63	*
64	* @param line the line to buffer
65	* @param startDistance the buffer width at the start of the line
66	* @param midDistance the buffer width at the middle vertex of the line
67	* @param endDistance the buffer width at the end of the line
68	* @return the variable-distance buffer polygon
69	*/
70	public static Geometry buffer(Geometry line, double startDistance,
71	double midDistance,
72	double endDistance) {
73	double[] distance = interpolate((LineString) line,
74	startDistance, midDistance, endDistance);
75	VariableBuffer vb = new VariableBuffer(line, distance);
76	return vb.getResult();
77	}
78
79	/**
80	* Creates a buffer polygon along a line with the distance specified
81	* at each vertex.
82	*
83	* @param line the line to buffer
84	* @param distance the buffer distance for each vertex of the line
85	* @return the variable-distance buffer polygon
86	*/
87	public static Geometry buffer(Geometry line, double[] distance) {
88	VariableBuffer vb = new VariableBuffer(line, distance);
89	return vb.getResult();
90	}
91
92	/**
93	* Computes a list of values for the points along a line by
94	* interpolating between values for the start and end point.
95	* The interpolation is
96	* based on the distance of each point along the line
97	* relative to the total line length.
98	*
99	* @param line the line to interpolate along
100	* @param startValue the start value
101	* @param endValue the end value
102	* @return the array of interpolated values
103	*/
104	private static double[] interpolate(LineString line,
105	double startValue,
106	double endValue) {
107	startValue = Math.abs(startValue);
108	endValue = Math.abs(endValue);
109	double[] values = new double[line.getNumPoints()];
110	values[0] = startValue;
111	values[values.length - 1] = endValue;
112
113	double totalLen = line.getLength();
114	Coordinate[] pts = line.getCoordinates();
115	double currLen = 0;
116	for (int i = 1; i < values.length - 1; i++) {
117	double segLen = pts[i].distance(pts[i - 1]);
118	currLen += segLen;
119	double lenFrac = currLen / totalLen;
120	double delta = lenFrac * (endValue - startValue);
121	values[i] = startValue + delta;
122	}
123	return values;
124	}
125
126	/**
127	* Computes a list of values for the points along a line by
128	* interpolating between values for the start, middle and end points.
129	* The interpolation is
130	* based on the distance of each point along the line
131	* relative to the total line length.
132	* The middle distance is attained at
133	* the vertex at or just past the half-length of the line.
134	*
135	* @param line the line to interpolate along
136	* @param startValue the start value
137	* @param midValue the start value
138	* @param endValue the end value
139	* @return the array of interpolated values
140	*/
141	private static double[] interpolate(LineString line,
142	double startValue,
143	double midValue,
144	double endValue)
145	{
146	startValue = Math.abs(startValue);
147	midValue = Math.abs(midValue);
148	endValue = Math.abs(endValue);
149
150	double[] values = new double[line.getNumPoints()];
151	values[0] = startValue;
152	values[values.length - 1] = endValue;
153
154	Coordinate[] pts = line.getCoordinates();
155	double lineLen = line.getLength();
156	int midIndex = indexAtLength(pts, lineLen / 2 );
157
158	double delMidStart = midValue - startValue;
159	double delEndMid = endValue - midValue;
160
161	double lenSM = length(pts, 0, midIndex);
162	double currLen = 0;
163	for (int i = 1; i <= midIndex; i++) {
164	double segLen = pts[i].distance(pts[i - 1]);
165	currLen += segLen;
166	double lenFrac = currLen / lenSM;
167	double val = startValue + lenFrac * delMidStart;
168	values[i] = val;
169	}
170
171	double lenME = length(pts, midIndex, pts.length - 1);
172	currLen = 0;
173	for (int i = midIndex + 1; i < values.length - 1; i++) {
174	double segLen = pts[i].distance(pts[i - 1]);
175	currLen += segLen;
176	double lenFrac = currLen / lenME;
177	double val = midValue + lenFrac * delEndMid;
178	values[i] = val;
179	}
180	return values;
181	}
182
183	private static int indexAtLength(Coordinate[] pts, double targetLen) {
184	double len = 0;
185	for (int i = 1; i < pts.length; i++) {
186	len += pts[i].distance(pts[i-1]);
187	if (len > targetLen)
188	return i;
189	}
190	return pts.length - 1;
191	}
192
193	private static double length(Coordinate[] pts, int i1, int i2) {
194	double len = 0;
195	for (int i = i1 + 1; i <= i2; i++) {
196	len += pts[i].distance(pts[i-1]);
197	}
198	return len;
199	}
200
201	private LineString line;
202	private double[] distance;
203	private GeometryFactory geomFactory;
204	private int quadrantSegs = BufferParameters.DEFAULT_QUADRANT_SEGMENTS;
205
206	/**
207	* Creates a generator for a variable-distance line buffer.
208	*
209	* @param line the linestring to buffer
210	* @param distance the buffer distance for each vertex of the line
211	*/
212	public VariableBuffer(Geometry line, double[] distance) {
213	this.line = (LineString) line;
214	this.distance = distance;
215	geomFactory = line.getFactory();
216
217	if (distance.length != this.line.getNumPoints()) {
218	throw new IllegalArgumentException("Number of distances is not equal to number of vertices");
219	}
220	}
221
222	/**
223	* Computes the buffer polygon.
224	*
225	* @return a buffer polygon
226	*/
227	public Geometry getResult() {
228	List<Geometry> parts = new ArrayList<Geometry>();
229
230	Coordinate[] pts = line.getCoordinates();
231	// construct segment buffers
232	for (int i = 1; i < pts.length; i++) {
233	double dist0 = distance[i - 1];
234	double dist1 = distance[i];
235	if (dist0 > 0 \|\| dist1 > 0) {
236	Polygon poly = segmentBuffer(pts[i - 1], pts[i], dist0, dist1);
237	if (poly != null)
238	parts.add(poly);
239	}
240	}
241
242	GeometryCollection partsGeom = geomFactory
243	.createGeometryCollection(GeometryFactory.toGeometryArray(parts));
244	Geometry buffer = partsGeom.union();
245
246	// ensure an empty polygon is returned if needed
247	if (buffer.isEmpty()) {
248	return geomFactory.createPolygon();
249	}
250	return buffer;
251	}
252
253	/**
254	* Computes a variable buffer polygon for a single segment,
255	* with the given endpoints and buffer distances.
256	* The individual segment buffers are unioned
257	* to form the final buffer.
258	*
259	* @param p0 the segment start point
260	* @param p1 the segment end point
261	* @param dist0 the buffer distance at the start point
262	* @param dist1 the buffer distance at the end point
263	* @return the segment buffer.
264	*/
265	private Polygon segmentBuffer(Coordinate p0, Coordinate p1,
266	double dist0, double dist1) {
267	/**
268	* Compute for increasing distance only, so flip if needed
269	*/
270	if (dist0 > dist1) {
271	return segmentBuffer(p1, p0, dist1, dist0);
272	}
273
274	// forward tangent line
275	LineSegment tangent = outerTangent(p0, dist0, p1, dist1);
276
277	// if tangent is null then compute a buffer for largest circle
278	if (tangent == null) {
279	Coordinate center = p0;
280	double dist = dist0;
281	if (dist1 > dist0) {
282	center = p1;
283	dist = dist1;
284	}
285	return circle(center, dist);
286	}
287
288	Coordinate t0 = tangent.getCoordinate(0);
289	Coordinate t1 = tangent.getCoordinate(1);
290
291	// reverse tangent line on other side of segment
292	LineSegment seg = new LineSegment(p0, p1);
293	Coordinate tr0 = seg.reflect(t0);
294	Coordinate tr1 = seg.reflect(t1);
295
296	CoordinateList coords = new CoordinateList();
297	coords.add(t0);
298	coords.add(t1);
299
300	// end cap
301	addCap(p1, dist1, t1, tr1, coords);
302
303	coords.add(tr1);
304	coords.add(tr0);
305
306	// start cap
307	addCap(p0, dist0, tr0, t0, coords);
308
309	// close
310	coords.add(t0);
311
312	Coordinate[] pts = coords.toCoordinateArray();
313	Polygon polygon = geomFactory.createPolygon(pts);
314	return polygon;
315	}
316
317	/**
318	* Returns a circular polygon.
319	*
320	* @param center the circle center point
321	* @param radius the radius
322	* @return a polygon, or null if the radius is 0
323	*/
324	private Polygon circle(Coordinate center, double radius) {
325	if (radius <= 0)
326	return null;
327	int nPts = 4 * quadrantSegs;
328	Coordinate[] pts = new Coordinate[nPts + 1];
329	double angInc = Math.PI / 2 / quadrantSegs;
330	for (int i = 0; i < nPts; i++) {
331	pts[i] = projectPolar(center, radius, i * angInc);
332	}
333	pts[pts.length - 1] = pts[0].copy();
334	return geomFactory.createPolygon(pts);
335	}
336
337	/**
338	* Adds a semi-circular cap CCW around the point p.
339	*
340	* @param p the centre point of the cap
341	* @param r the cap radius
342	* @param t1 the starting point of the cap
343	* @param t2 the ending point of the cap
344	* @param coords the coordinate list to add to
345	*/
346	private void addCap(Coordinate p, double r, Coordinate t1, Coordinate t2, CoordinateList coords) {
347
348	double angStart = Angle.angle(p, t1);
349	double angEnd = Angle.angle(p, t2);
350	if (angStart < angEnd)
351	angStart += 2 * Math.PI;
352
353	int indexStart = capAngleIndex(angStart);
354	int indexEnd = capAngleIndex(angEnd);
355
356	for (int i = indexStart; i > indexEnd; i--) {
357	// use negative increment to create points CW
358	double ang = capAngle(i);
359	coords.add( projectPolar(p, r, ang) );
360	}
361	}
362
363	/**
364	* Computes the angle for the given cap point index.
365	*
366	* @param index the fillet angle index
367	* @return
368	*/
369	private double capAngle(int index) {
370	double capSegAng = Math.PI / 2 / quadrantSegs;
371	return index * capSegAng;
372	}
373
374	/**
375	* Computes the canonical cap point index for a given angle.
376	* The angle is rounded down to the next lower
377	* index.
378	* <p>
379	* In order to reduce the number of points created by overlapping end caps,
380	* cap points are generated at the same locations around a circle.
381	* The index is the index of the points around the circle,
382	* with 0 being the point at (1,0).
383	* The total number of points around the circle is
384	* <code>4 * quadrantSegs</code>.
385	*
386	* @param ang the angle
387	* @return the index for the angle.
388	*/
389	private int capAngleIndex(double ang) {
390	double capSegAng = Math.PI / 2 / quadrantSegs;
391	int index = (int) (ang / capSegAng);
392	return index;
393	}
394
395	/**
396	* Computes the two circumference points defining the outer tangent line
397	* between two circles.
398	* <p>
399	* For the algorithm see <a href='https://en.wikipedia.org/wiki/Tangent_lines_to_circles#Outer_tangent'>Wikipedia</a>.
400	*
401	* @param c1 the centre of circle 1
402	* @param r1 the radius of circle 1
403	* @param c2 the centre of circle 2
404	* @param r2 the center of circle 2
405	* @return the outer tangent line segment, or null if none exists
406	*/
407	private static LineSegment outerTangent(Coordinate c1, double r1, Coordinate c2, double r2) {
408	/**
409	* If distances are inverted then flip to compute and flip result back.
410	*/
411	if (r1 > r2) {
412	LineSegment seg = outerTangent(c2, r2, c1, r1);
413	return new LineSegment(seg.p1, seg.p0);
414	}
415	double x1 = c1.getX();
416	double y1 = c1.getY();
417	double x2 = c2.getX();
418	double y2 = c2.getY();
419	// TODO: handle r1 == r2?
420	double a3 = - Math.atan2(y2 - y1, x2 - x1);
421
422	double dr = r2 - r1;
423	double d = Math.sqrt((x2 - x1)(x2 - x1) + (y2 - y1)(y2 - y1));
424
425	double a2 = Math.asin(dr / d);
426	// check if no tangent exists
427	if (Double.isNaN(a2))
428	return null;
429
430	double a1 = a3 - a2;
431
432	double aa = Math.PI/2 - a1;
433	double x3 = x1 + r1 * Math.cos(aa);
434	double y3 = y1 + r1 * Math.sin(aa);
435	double x4 = x2 + r2 * Math.cos(aa);
436	double y4 = y2 + r2 * Math.sin(aa);
437
438	return new LineSegment(x3, y3, x4, y4);
439	}
440
441
442	private static Coordinate projectPolar(Coordinate p, double r, double ang) {
443	double x = p.getX() + r * snapTrig(Math.cos(ang));
444	double y = p.getY() + r * snapTrig(Math.sin(ang));
445	return new Coordinate(x, y);
446	}
447
448	private static final double SNAP_TRIG_TOL = 1e-6;
449
450	/**
451	* Snap trig values to integer values for better consistency.
452	*
453	* @param x the result of a trigonometric function
454	* @return x snapped to the integer interval
455	*/
456	private static double snapTrig(double x) {
457	if (x > (1 - SNAP_TRIG_TOL)) return 1;
458	if (x < (-1 + SNAP_TRIG_TOL)) return -1;
459	if (Math.abs(x) < SNAP_TRIG_TOL) return 0;
460	return x;
461	}
462	}
463