Class BufferOp

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	/**
15	* @version 1.7
16	*/
17	import org.locationtech.jts.geom.Envelope;
18	import org.locationtech.jts.geom.Geometry;
19	import org.locationtech.jts.geom.Polygon;
20	import org.locationtech.jts.geom.PrecisionModel;
21	import org.locationtech.jts.geom.TopologyException;
22	import org.locationtech.jts.math.MathUtil;
23	import org.locationtech.jts.noding.Noder;
24	import org.locationtech.jts.noding.ScaledNoder;
25	import org.locationtech.jts.noding.snapround.MCIndexSnapRounder;
26
27	//import debug.*;
28
29	/**
30	* Computes the buffer of a geometry, for both positive and negative buffer distances.
31	* <p>
32	* In GIS, the positive (or negative) buffer of a geometry is defined as
33	* the Minkowski sum (or difference) of the geometry
34	* with a circle of radius equal to the absolute value of the buffer distance.
35	* In the CAD/CAM world buffers are known as <i>offset curves</i>.
36	* In morphological analysis the
37	* operation of positive and negative buffering
38	* is referred to as <i>erosion</i> and <i>dilation</i>
39	* <p>
40	* The buffer operation always returns a polygonal result.
41	* The negative or zero-distance buffer of lines and points is always an empty {@link Polygon}.
42	* <p>
43	* Since true buffer curves may contain circular arcs,
44	* computed buffer polygons are only approximations to the true geometry.
45	* The user can control the accuracy of the approximation by specifying
46	* the number of linear segments used to approximate arcs.
47	* This is specified via {@link BufferParameters#setQuadrantSegments(int)} or {@link #setQuadrantSegments(int)}.
48	* <p>
49	* The <b>end cap style</b> of a linear buffer may be {@link BufferParameters#setEndCapStyle(int) specified}. The
50	* following end cap styles are supported:
51	* <ul>
52	* <li>{@link BufferParameters#CAP_ROUND} - the usual round end caps
53	* <li>{@link BufferParameters#CAP_FLAT} - end caps are truncated flat at the line ends
54	* <li>{@link BufferParameters#CAP_SQUARE} - end caps are squared off at the buffer distance beyond the line ends
55	* </ul>
56	* <p>
57	* The <b>join style</b> of the corners in a buffer may be {@link BufferParameters#setJoinStyle(int) specified}. The
58	* following join styles are supported:
59	* <ul>
60	* <li>{@link BufferParameters#JOIN_ROUND} - the usual round join
61	* <li>{@link BufferParameters#JOIN_MITRE} - corners are "sharp" (up to a {@link BufferParameters#getMitreLimit() distance limit})
62	* <li>{@link BufferParameters#JOIN_BEVEL} - corners are beveled (clipped off).
63	* </ul>
64	* <p>
65	* The buffer algorithm can perform simplification on the input to increase performance.
66	* The simplification is performed a way that always increases the buffer area
67	* (so that the simplified input covers the original input).
68	* The degree of simplification can be {@link BufferParameters#setSimplifyFactor(double) specified},
69	* with a {@link BufferParameters#DEFAULT_SIMPLIFY_FACTOR default} used otherwise.
70	* Note that if the buffer distance is zero then so is the computed simplify tolerance,
71	* no matter what the simplify factor.
72	*
73	* @version 1.7
74	*/
75	public class BufferOp
76	{
77	/**
78	* Specifies a round line buffer end cap style.
79	* @deprecated use BufferParameters
80	*/
81	public static final int CAP_ROUND = BufferParameters.CAP_ROUND;
82	/**
83	* Specifies a butt (or flat) line buffer end cap style.
84	* @deprecated use BufferParameters
85	*/
86	public static final int CAP_BUTT = BufferParameters.CAP_FLAT;
87
88	/**
89	* Specifies a butt (or flat) line buffer end cap style.
90	* @deprecated use BufferParameters
91	*/
92	public static final int CAP_FLAT = BufferParameters.CAP_FLAT;
93	/**
94	* Specifies a square line buffer end cap style.
95	* @deprecated use BufferParameters
96	*/
97	public static final int CAP_SQUARE = BufferParameters.CAP_SQUARE;
98
99	/**
100	* A number of digits of precision which leaves some computational "headroom"
101	* for floating point operations.
102	*
103	* This value should be less than the decimal precision of double-precision values (16).
104	*/
105	private static int MAX_PRECISION_DIGITS = 12;
106
107	/**
108	* Compute a scale factor to limit the precision of
109	* a given combination of Geometry and buffer distance.
110	* The scale factor is determined by
111	* the number of digits of precision in the (geometry + buffer distance),
112	* limited by the supplied <code>maxPrecisionDigits</code> value.
113	* <p>
114	* The scale factor is based on the absolute magnitude of the (geometry + buffer distance).
115	* since this determines the number of digits of precision which must be handled.
116	*
117	* @param g the Geometry being buffered
118	* @param distance the buffer distance
119	* @param maxPrecisionDigits the max # of digits that should be allowed by
120	* the precision determined by the computed scale factor
121	*
122	* @return a scale factor for the buffer computation
123	*/
124	private static double precisionScaleFactor(Geometry g,
125	double distance,
126	int maxPrecisionDigits)
127	{
128	Envelope env = g.getEnvelopeInternal();
129	double envMax = MathUtil.max(
130	Math.abs(env.getMaxX()),
131	Math.abs(env.getMaxY()),
132	Math.abs(env.getMinX()),
133	Math.abs(env.getMinY())
134	);
135
136	double expandByDistance = distance > 0.0 ? distance : 0.0;
137	double bufEnvMax = envMax + 2 * expandByDistance;
138
139	// the smallest power of 10 greater than the buffer envelope
140	int bufEnvPrecisionDigits = (int) (Math.log(bufEnvMax) / Math.log(10) + 1.0);
141	int minUnitLog10 = maxPrecisionDigits - bufEnvPrecisionDigits;
142
143	double scaleFactor = Math.pow(10.0, minUnitLog10);
144	return scaleFactor;
145	}
146
147	/*
148	private static double OLDprecisionScaleFactor(Geometry g,
149	double distance,
150	int maxPrecisionDigits)
151	{
152	Envelope env = g.getEnvelopeInternal();
153	double envSize = Math.max(env.getHeight(), env.getWidth());
154	double expandByDistance = distance > 0.0 ? distance : 0.0;
155	double bufEnvSize = envSize + 2 * expandByDistance;
156
157	// the smallest power of 10 greater than the buffer envelope
158	int bufEnvLog10 = (int) (Math.log(bufEnvSize) / Math.log(10) + 1.0);
159	int minUnitLog10 = bufEnvLog10 - maxPrecisionDigits;
160	// scale factor is inverse of min Unit size, so flip sign of exponent
161	double scaleFactor = Math.pow(10.0, -minUnitLog10);
162	return scaleFactor;
163	}
164	*/
165
166	/**
167	* Computes the buffer of a geometry for a given buffer distance.
168	*
169	* @param g the geometry to buffer
170	* @param distance the buffer distance
171	* @return the buffer of the input geometry
172	*/
173	public static Geometry bufferOp(Geometry g, double distance)
174	{
175	BufferOp gBuf = new BufferOp(g);
176	Geometry geomBuf = gBuf.getResultGeometry(distance);
177	//BufferDebug.saveBuffer(geomBuf);
178	//BufferDebug.runCount++;
179	return geomBuf;
180	}
181
182	/**
183	* Computes the buffer for a geometry for a given buffer distance
184	* and accuracy of approximation.
185	*
186	* @param g the geometry to buffer
187	* @param distance the buffer distance
188	* @param params the buffer parameters to use
189	* @return the buffer of the input geometry
190	*
191	*/
192	public static Geometry bufferOp(Geometry g, double distance, BufferParameters params)
193	{
194	BufferOp bufOp = new BufferOp(g, params);
195	Geometry geomBuf = bufOp.getResultGeometry(distance);
196	return geomBuf;
197	}
198
199	/**
200	* Computes the buffer for a geometry for a given buffer distance
201	* and accuracy of approximation.
202	*
203	* @param g the geometry to buffer
204	* @param distance the buffer distance
205	* @param quadrantSegments the number of segments used to approximate a quarter circle
206	* @return the buffer of the input geometry
207	*
208	*/
209	public static Geometry bufferOp(Geometry g, double distance, int quadrantSegments)
210	{
211	BufferOp bufOp = new BufferOp(g);
212	bufOp.setQuadrantSegments(quadrantSegments);
213	Geometry geomBuf = bufOp.getResultGeometry(distance);
214	return geomBuf;
215	}
216
217	/**
218	* Computes the buffer for a geometry for a given buffer distance
219	* and accuracy of approximation.
220	*
221	* @param g the geometry to buffer
222	* @param distance the buffer distance
223	* @param quadrantSegments the number of segments used to approximate a quarter circle
224	* @param endCapStyle the end cap style to use
225	* @return the buffer of the input geometry
226	*
227	*/
228	public static Geometry bufferOp(Geometry g,
229	double distance,
230	int quadrantSegments,
231	int endCapStyle)
232	{
233	BufferOp bufOp = new BufferOp(g);
234	bufOp.setQuadrantSegments(quadrantSegments);
235	bufOp.setEndCapStyle(endCapStyle);
236	Geometry geomBuf = bufOp.getResultGeometry(distance);
237	return geomBuf;
238	}
239
240	private Geometry argGeom;
241	private double distance;
242
243	private BufferParameters bufParams = new BufferParameters();
244
245	private Geometry resultGeometry = null;
246	private RuntimeException saveException; // debugging only
247
248	/**
249	* Initializes a buffer computation for the given geometry
250	*
251	* @param g the geometry to buffer
252	*/
253	public BufferOp(Geometry g) {
254	argGeom = g;
255	}
256
257	/**
258	* Initializes a buffer computation for the given geometry
259	* with the given set of parameters
260	*
261	* @param g the geometry to buffer
262	* @param bufParams the buffer parameters to use
263	*/
264	public BufferOp(Geometry g, BufferParameters bufParams) {
265	argGeom = g;
266	this.bufParams = bufParams;
267	}
268
269	/**
270	* Specifies the end cap style of the generated buffer.
271	* The styles supported are {@link BufferParameters#CAP_ROUND}, {@link BufferParameters#CAP_FLAT}, and {@link BufferParameters#CAP_SQUARE}.
272	* The default is CAP_ROUND.
273	*
274	* @param endCapStyle the end cap style to specify
275	*/
276	public void setEndCapStyle(int endCapStyle)
277	{
278	bufParams.setEndCapStyle(endCapStyle);
279	}
280
281	/**
282	* Sets the number of segments used to approximate a angle fillet
283	*
284	* @param quadrantSegments the number of segments in a fillet for a quadrant
285	*/
286	public void setQuadrantSegments(int quadrantSegments)
287	{
288	bufParams.setQuadrantSegments(quadrantSegments);
289	}
290
291	/**
292	* Returns the buffer computed for a geometry for a given buffer distance.
293	*
294	* @param distance the buffer distance
295	* @return the buffer of the input geometry
296	*/
297	public Geometry getResultGeometry(double distance)
298	{
299	this.distance = distance;
300	computeGeometry();
301	return resultGeometry;
302	}
303
304	private void computeGeometry()
305	{
306	bufferOriginalPrecision();
307	if (resultGeometry != null) return;
308
309	PrecisionModel argPM = argGeom.getFactory().getPrecisionModel();
310	if (argPM.getType() == PrecisionModel.FIXED)
311	bufferFixedPrecision(argPM);
312	else
313	bufferReducedPrecision();
314	}
315
316	private void bufferReducedPrecision()
317	{
318	// try and compute with decreasing precision
319	for (int precDigits = MAX_PRECISION_DIGITS; precDigits >= 0; precDigits--) {
320	try {
321	bufferReducedPrecision(precDigits);
322	}
323	catch (TopologyException ex) {
324	// update the saved exception to reflect the new input geometry
325	saveException = ex;
326	// don't propagate the exception - it will be detected by fact that resultGeometry is null
327	}
328	if (resultGeometry != null) return;
329	}
330
331	// tried everything - have to bail
332	throw saveException;
333	}
334
335	private void bufferOriginalPrecision()
336	{
337	try {
338	// use fast noding by default
339	BufferBuilder bufBuilder = new BufferBuilder(bufParams);
340	resultGeometry = bufBuilder.buffer(argGeom, distance);
341	}
342	catch (RuntimeException ex) {
343	saveException = ex;
344	// don't propagate the exception - it will be detected by fact that resultGeometry is null
345
346	// testing ONLY - propagate exception
347	//throw ex;
348	}
349	}
350
351	private void bufferReducedPrecision(int precisionDigits)
352	{
353	double sizeBasedScaleFactor = precisionScaleFactor(argGeom, distance, precisionDigits);
354	// System.out.println("recomputing with precision scale factor = " + sizeBasedScaleFactor);
355
356	PrecisionModel fixedPM = new PrecisionModel(sizeBasedScaleFactor);
357	bufferFixedPrecision(fixedPM);
358	}
359
360	private void bufferFixedPrecision(PrecisionModel fixedPM)
361	{
362	Noder noder = new ScaledNoder(new MCIndexSnapRounder(new PrecisionModel(1.0)),
363	fixedPM.getScale());
364
365	BufferBuilder bufBuilder = new BufferBuilder(bufParams);
366	bufBuilder.setWorkingPrecisionModel(fixedPM);
367	bufBuilder.setNoder(noder);
368	// this may throw an exception, if robustness errors are encountered
369	resultGeometry = bufBuilder.buffer(argGeom, distance);
370	}
371	}
372