1 /*
2 * @(#)ShapeBounds.java
3 *
4 * $Date: 2014-06-06 13:04:49 -0500 (Fri, 06 Jun 2014) $
5 *
6 * Copyright (c) 2011 by Jeremy Wood.
7 * All rights reserved.
8 *
9 * The copyright of this software is owned by Jeremy Wood.
10 * You may not use, copy or modify this software, except in
11 * accordance with the license agreement you entered into with
12 * Jeremy Wood. For details see accompanying license terms.
13 *
14 * This software is probably, but not necessarily, discussed here:
15 * https://javagraphics.java.net/
16 *
17 * That site should also contain the most recent official version
18 * of this software. (See the SVN repository for more details.)
19 */
20 package com.bric.multislider;
21
22 import java.awt.Shape;
23 import java.awt.geom.AffineTransform;
24 import java.awt.geom.PathIterator;
25 import java.awt.geom.Rectangle2D;
26
27 /**
28 * This class features an efficient and accurate <code>getBounds()</code> method. The <code>java.awt.Shape</code> API
29 * clearly states that the <code>Shape.getBounds2D()</code> method may return a rectangle larger than the bounds of the
30 * actual shape, so here I present a method to get the bounds without resorting to the very-accurate-but-very-slow
31 * <code>java.awt.geom.Area</code> class.
32 */
33 public class ShapeBounds
34 {
35 /**
36 * This calculates the precise bounds of a shape.
37 * @param shape the shape you want the bounds of. This method throws a NullPointerException if this is null.
38 * @return the bounds of <code>shape</code>.
39 * @throws EmptyPathException if the shape argument is empty.
40 */
41 public static Rectangle2D getBounds(Shape shape) throws EmptyPathException
42 {
43 return getBounds(shape, null, null);
44 }
45
46 public static Rectangle2D getBounds(Shape[] shapes)
47 {
48 Rectangle2D r = null;
49 for (int a = 0; a < shapes.length; a++)
50 {
51 try
52 {
53 Rectangle2D t = getBounds(shapes[a]);
54 if (r == null)
55 {
56 r = t;
57 }
58 else
59 {
60 r.add(t);
61 }
62 }
63 catch (EmptyPathException e)
64 {
65 }
66 }
67 return r;
68 }
69
70 /**
71 * This calculates the precise bounds of a shape.
72 * @param shape the shape you want the bounds of. This method throws a NullPointerException if this is null.
73 * @param transform if this is non-null, then this method returns the bounds of <code>shape</code> as seen through
74 * <code>t</code>.
75 * @return the bounds of <code>shape</code>, as seen through <code>transform</code>.
76 * @throws EmptyPathException if the shape argument is empty.
77 */
78 public static Rectangle2D getBounds(Shape shape, AffineTransform transform) throws EmptyPathException
79 {
80 return getBounds(shape, transform, null);
81 }
82
83 /**
84 * This calculates the precise bounds of a shape.
85 * @param shape the shape you want the bounds of. This method throws a NullPointerException if this is null.
86 * @param transform if this is non-null, then this method returns the bounds of <code>shape</code> as seen through
87 * <code>t</code>.
88 * @param r if this is non-null, then the result is stored in this rectangle. This is useful when you need to call
89 * this method repeatedly without allocating a lot of memory.
90 * @return the bounds of <code>shape</code>, as seen through <code>transform</code>.
91 * @throws EmptyPathException if the shape argument is empty.
92 */
93 public static Rectangle2D getBounds(Shape shape, AffineTransform transform, Rectangle2D r)
94 throws EmptyPathException
95 {
96 PathIterator i = shape.getPathIterator(transform);
97 return getBounds(i, r);
98 }
99
100 /**
101 * This calculates the precise bounds of a shape.
102 * @param shape the shape you want the bounds of. This method throws a NullPointerException if this is null.
103 * @param r if this is non-null, then the result is stored in this rectangle. This is useful when you need to call
104 * this method repeatedly without allocating a lot of memory.
105 * @return the bounds of <code>shape</code>.
106 * @throws EmptyPathException if the shape argument is empty.
107 */
108 public static Rectangle2D getBounds(Shape shape, Rectangle2D r) throws EmptyPathException
109 {
110 return getBounds(shape, null, r);
111 }
112
113 /**
114 * This calculates the precise bounds of a shape.
115 * @param i the shape you want the bounds of. This method throws a NullPointerException if this is null.
116 * @return the bounds of <code>i</code>.
117 */
118 public static Rectangle2D getBounds(PathIterator i)
119 {
120 return getBounds(i, null);
121 }
122
123 /**
124 * This calculates the precise bounds of a shape.
125 * @param i the shape you want the bounds of. This method throws a NullPointerException if this is null.
126 * @param r if this is non-null, then the result is stored in this rectangle. This is useful when you need to call
127 * this method repeatedly without allocating a lot of memory.
128 * @return the bounds of <code>i</code>.
129 */
130 public static Rectangle2D getBounds(PathIterator i, Rectangle2D r)
131 {
132 float[] f = new float[6];
133
134 int k;
135
136 /** left, top, right, and bottom bounds */
137 float[] bounds = null;
138
139 float lastX = 0;
140 float lastY = 0;
141
142 // A, B, C, and D in the equation x = a*t^3+b*t^2+c*t+d
143 // or A, B, and C in the equation x = a*t^2+b*t+c
144 float[] x_coeff = new float[4];
145 float[] y_coeff = new float[4];
146
147 float t, x, y, det;
148 while (i.isDone() == false)
149 {
150 k = i.currentSegment(f);
151 if (k == PathIterator.SEG_MOVETO)
152 {
153 lastX = f[0];
154 lastY = f[1];
155 }
156 else if (k == PathIterator.SEG_CLOSE)
157 {
158 // do nothing
159 // note if we had a simple MOVETO and SEG_CLOSE then
160 // we haven't changed "bounds". This is intentional,
161 // so if the shape is badly defined the bounds
162 // should still make sense.
163 }
164 else
165 {
166 if (bounds == null)
167 {
168 bounds = new float[]{lastX, lastY, lastX, lastY};
169 }
170 else
171 {
172 if (lastX < bounds[0])
173 bounds[0] = lastX;
174 if (lastY < bounds[1])
175 bounds[1] = lastY;
176 if (lastX > bounds[2])
177 bounds[2] = lastX;
178 if (lastY > bounds[3])
179 bounds[3] = lastY;
180 }
181
182 if (k == PathIterator.SEG_LINETO)
183 {
184 if (f[0] < bounds[0])
185 bounds[0] = f[0];
186 if (f[1] < bounds[1])
187 bounds[1] = f[1];
188 if (f[0] > bounds[2])
189 bounds[2] = f[0];
190 if (f[1] > bounds[3])
191 bounds[3] = f[1];
192 lastX = f[0];
193 lastY = f[1];
194 }
195 else if (k == PathIterator.SEG_QUADTO)
196 {
197 // check the end point
198 if (f[2] < bounds[0])
199 bounds[0] = f[2];
200 if (f[3] < bounds[1])
201 bounds[1] = f[3];
202 if (f[2] > bounds[2])
203 bounds[2] = f[2];
204 if (f[3] > bounds[3])
205 bounds[3] = f[3];
206
207 // find the extrema
208 x_coeff[0] = lastX - 2 * f[0] + f[2];
209 x_coeff[1] = -2 * lastX + 2 * f[0];
210 x_coeff[2] = lastX;
211 y_coeff[0] = lastY - 2 * f[1] + f[3];
212 y_coeff[1] = -2 * lastY + 2 * f[1];
213 y_coeff[2] = lastY;
214
215 // x = a*t^2+b*t+c
216 // dx/dt = 0 = 2*a*t+b
217 // t = -b/(2a)
218 t = -x_coeff[1] / (2 * x_coeff[0]);
219 if (t > 0 && t < 1)
220 {
221 x = x_coeff[0] * t * t + x_coeff[1] * t + x_coeff[2];
222 if (x < bounds[0])
223 bounds[0] = x;
224 if (x > bounds[2])
225 bounds[2] = x;
226 }
227 t = -y_coeff[1] / (2 * y_coeff[0]);
228 if (t > 0 && t < 1)
229 {
230 y = y_coeff[0] * t * t + y_coeff[1] * t + y_coeff[2];
231 if (y < bounds[1])
232 bounds[1] = y;
233 if (y > bounds[3])
234 bounds[3] = y;
235 }
236 lastX = f[2];
237 lastY = f[3];
238 }
239 else if (k == PathIterator.SEG_CUBICTO)
240 {
241 if (f[4] < bounds[0])
242 bounds[0] = f[4];
243 if (f[5] < bounds[1])
244 bounds[1] = f[5];
245 if (f[4] > bounds[2])
246 bounds[2] = f[4];
247 if (f[5] > bounds[3])
248 bounds[3] = f[5];
249
250 x_coeff[0] = -lastX + 3 * f[0] - 3 * f[2] + f[4];
251 x_coeff[1] = 3 * lastX - 6 * f[0] + 3 * f[2];
252 x_coeff[2] = -3 * lastX + 3 * f[0];
253 x_coeff[3] = lastX;
254
255 y_coeff[0] = -lastY + 3 * f[1] - 3 * f[3] + f[5];
256 y_coeff[1] = 3 * lastY - 6 * f[1] + 3 * f[3];
257 y_coeff[2] = -3 * lastY + 3 * f[1];
258 y_coeff[3] = lastY;
259
260 // x = a*t*t*t+b*t*t+c*t+d
261 // dx/dt = 3*a*t*t+2*b*t+c
262 // t = [-B+-sqrt(B^2-4*A*C)]/(2A)
263 // A = 3*a
264 // B = 2*b
265 // C = c
266 // t = (-2*b+-sqrt(4*b*b-12*a*c)]/(6*a)
267 det = (4 * x_coeff[1] * x_coeff[1] - 12 * x_coeff[0] * x_coeff[2]);
268 if (det < 0)
269 {
270 // there are no solutions! nothing to do here
271 }
272 else if (det == 0)
273 {
274 // there is 1 solution
275 t = -2 * x_coeff[1] / (6 * x_coeff[0]);
276 if (t > 0 && t < 1)
277 {
278 x = x_coeff[0] * t * t * t + x_coeff[1] * t * t + x_coeff[2] * t + x_coeff[3];
279 if (x < bounds[0])
280 bounds[0] = x;
281 if (x > bounds[2])
282 bounds[2] = x;
283 }
284 }
285 else
286 {
287 // there are 2 solutions:
288 det = (float) Math.sqrt(det);
289 t = (-2 * x_coeff[1] + det) / (6 * x_coeff[0]);
290 if (t > 0 && t < 1)
291 {
292 x = x_coeff[0] * t * t * t + x_coeff[1] * t * t + x_coeff[2] * t + x_coeff[3];
293 if (x < bounds[0])
294 bounds[0] = x;
295 if (x > bounds[2])
296 bounds[2] = x;
297 }
298
299 t = (-2 * x_coeff[1] - det) / (6 * x_coeff[0]);
300 if (t > 0 && t < 1)
301 {
302 x = x_coeff[0] * t * t * t + x_coeff[1] * t * t + x_coeff[2] * t + x_coeff[3];
303 if (x < bounds[0])
304 bounds[0] = x;
305 if (x > bounds[2])
306 bounds[2] = x;
307 }
308 }
309
310 det = (4 * y_coeff[1] * y_coeff[1] - 12 * y_coeff[0] * y_coeff[2]);
311 if (det < 0)
312 {
313 // there are no solutions! nothing to do here
314 }
315 else if (det == 0)
316 {
317 // there is 1 solution
318 t = -2 * y_coeff[1] / (6 * y_coeff[0]);
319 if (t > 0 && t < 1)
320 {
321 y = y_coeff[0] * t * t * t + y_coeff[1] * t * t + y_coeff[2] * t + y_coeff[3];
322 if (y < bounds[1])
323 bounds[1] = y;
324 if (y > bounds[3])
325 bounds[3] = y;
326 }
327 }
328 else
329 {
330 // there are 2 solutions:
331 det = (float) Math.sqrt(det);
332 t = (-2 * y_coeff[1] + det) / (6 * y_coeff[0]);
333 if (t > 0 && t < 1)
334 {
335 y = y_coeff[0] * t * t * t + y_coeff[1] * t * t + y_coeff[2] * t + y_coeff[3];
336 if (y < bounds[1])
337 bounds[1] = y;
338 if (y > bounds[3])
339 bounds[3] = y;
340 }
341
342 t = (-2 * y_coeff[1] - det) / (6 * y_coeff[0]);
343 if (t > 0 && t < 1)
344 {
345 y = y_coeff[0] * t * t * t + y_coeff[1] * t * t + y_coeff[2] * t + y_coeff[3];
346 if (y < bounds[1])
347 bounds[1] = y;
348 if (y > bounds[3])
349 bounds[3] = y;
350 }
351 }
352
353 lastX = f[4];
354 lastY = f[5];
355 }
356 }
357 i.next();
358 }
359
360 if (bounds == null)
361 {
362 throw new EmptyPathException();
363 }
364 if (r != null)
365 {
366 r.setFrame(bounds[0], bounds[1], bounds[2] - bounds[0], bounds[3] - bounds[1]);
367 return r;
368 }
369 return new Rectangle2D.Float(bounds[0], bounds[1], bounds[2] - bounds[0], bounds[3] - bounds[1]);
370 }
371 }