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 clearly
29 * states that the <code>Shape.getBounds2D()</code> method may return a rectangle larger than the bounds of the actual shape, so
30 * 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 this
89 * 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) throws EmptyPathException
94 {
95 PathIterator i = shape.getPathIterator(transform);
96 return getBounds(i, r);
97 }
98
99 /**
100 * This calculates the precise bounds of a shape.
101 * @param shape the shape you want the bounds of. This method throws a NullPointerException if this is null.
102 * @param r if this is non-null, then the result is stored in this rectangle. This is useful when you need to call this
103 * method repeatedly without allocating a lot of memory.
104 * @return the bounds of <code>shape</code>.
105 * @throws EmptyPathException if the shape argument is empty.
106 */
107 public static Rectangle2D getBounds(Shape shape, Rectangle2D r) throws EmptyPathException
108 {
109 return getBounds(shape, null, r);
110 }
111
112 /**
113 * This calculates the precise bounds of a shape.
114 * @param i the shape you want the bounds of. This method throws a NullPointerException if this is null.
115 * @return the bounds of <code>i</code>.
116 */
117 public static Rectangle2D getBounds(PathIterator i)
118 {
119 return getBounds(i, null);
120 }
121
122 /**
123 * This calculates the precise bounds of a shape.
124 * @param i the shape you want the bounds of. This method throws a NullPointerException if this is null.
125 * @param r if this is non-null, then the result is stored in this rectangle. This is useful when you need to call this
126 * method repeatedly without allocating a lot of memory.
127 * @return the bounds of <code>i</code>.
128 */
129 public static Rectangle2D getBounds(PathIterator i, Rectangle2D r)
130 {
131 float[] f = new float[6];
132
133 int k;
134
135 /** left, top, right, and bottom bounds */
136 float[] bounds = null;
137
138 float lastX = 0;
139 float lastY = 0;
140
141 // A, B, C, and D in the equation x = a*t^3+b*t^2+c*t+d
142 // or A, B, and C in the equation x = a*t^2+b*t+c
143 float[] x_coeff = new float[4];
144 float[] y_coeff = new float[4];
145
146 float t, x, y, det;
147 while (i.isDone() == false)
148 {
149 k = i.currentSegment(f);
150 if (k == PathIterator.SEG_MOVETO)
151 {
152 lastX = f[0];
153 lastY = f[1];
154 }
155 else if (k == PathIterator.SEG_CLOSE)
156 {
157 // do nothing
158 // note if we had a simple MOVETO and SEG_CLOSE then
159 // we haven't changed "bounds". This is intentional,
160 // so if the shape is badly defined the bounds
161 // should still make sense.
162 }
163 else
164 {
165 if (bounds == null)
166 {
167 bounds = new float[] {lastX, lastY, lastX, lastY};
168 }
169 else
170 {
171 if (lastX < bounds[0])
172 bounds[0] = lastX;
173 if (lastY < bounds[1])
174 bounds[1] = lastY;
175 if (lastX > bounds[2])
176 bounds[2] = lastX;
177 if (lastY > bounds[3])
178 bounds[3] = lastY;
179 }
180
181 if (k == PathIterator.SEG_LINETO)
182 {
183 if (f[0] < bounds[0])
184 bounds[0] = f[0];
185 if (f[1] < bounds[1])
186 bounds[1] = f[1];
187 if (f[0] > bounds[2])
188 bounds[2] = f[0];
189 if (f[1] > bounds[3])
190 bounds[3] = f[1];
191 lastX = f[0];
192 lastY = f[1];
193 }
194 else if (k == PathIterator.SEG_QUADTO)
195 {
196 // check the end point
197 if (f[2] < bounds[0])
198 bounds[0] = f[2];
199 if (f[3] < bounds[1])
200 bounds[1] = f[3];
201 if (f[2] > bounds[2])
202 bounds[2] = f[2];
203 if (f[3] > bounds[3])
204 bounds[3] = f[3];
205
206 // find the extrema
207 x_coeff[0] = lastX - 2 * f[0] + f[2];
208 x_coeff[1] = -2 * lastX + 2 * f[0];
209 x_coeff[2] = lastX;
210 y_coeff[0] = lastY - 2 * f[1] + f[3];
211 y_coeff[1] = -2 * lastY + 2 * f[1];
212 y_coeff[2] = lastY;
213
214 // x = a*t^2+b*t+c
215 // dx/dt = 0 = 2*a*t+b
216 // t = -b/(2a)
217 t = -x_coeff[1] / (2 * x_coeff[0]);
218 if (t > 0 && t < 1)
219 {
220 x = x_coeff[0] * t * t + x_coeff[1] * t + x_coeff[2];
221 if (x < bounds[0])
222 bounds[0] = x;
223 if (x > bounds[2])
224 bounds[2] = x;
225 }
226 t = -y_coeff[1] / (2 * y_coeff[0]);
227 if (t > 0 && t < 1)
228 {
229 y = y_coeff[0] * t * t + y_coeff[1] * t + y_coeff[2];
230 if (y < bounds[1])
231 bounds[1] = y;
232 if (y > bounds[3])
233 bounds[3] = y;
234 }
235 lastX = f[2];
236 lastY = f[3];
237 }
238 else if (k == PathIterator.SEG_CUBICTO)
239 {
240 if (f[4] < bounds[0])
241 bounds[0] = f[4];
242 if (f[5] < bounds[1])
243 bounds[1] = f[5];
244 if (f[4] > bounds[2])
245 bounds[2] = f[4];
246 if (f[5] > bounds[3])
247 bounds[3] = f[5];
248
249 x_coeff[0] = -lastX + 3 * f[0] - 3 * f[2] + f[4];
250 x_coeff[1] = 3 * lastX - 6 * f[0] + 3 * f[2];
251 x_coeff[2] = -3 * lastX + 3 * f[0];
252 x_coeff[3] = lastX;
253
254 y_coeff[0] = -lastY + 3 * f[1] - 3 * f[3] + f[5];
255 y_coeff[1] = 3 * lastY - 6 * f[1] + 3 * f[3];
256 y_coeff[2] = -3 * lastY + 3 * f[1];
257 y_coeff[3] = lastY;
258
259 // x = a*t*t*t+b*t*t+c*t+d
260 // dx/dt = 3*a*t*t+2*b*t+c
261 // t = [-B+-sqrt(B^2-4*A*C)]/(2A)
262 // A = 3*a
263 // B = 2*b
264 // C = c
265 // t = (-2*b+-sqrt(4*b*b-12*a*c)]/(6*a)
266 det = (4 * x_coeff[1] * x_coeff[1] - 12 * x_coeff[0] * x_coeff[2]);
267 if (det < 0)
268 {
269 // there are no solutions! nothing to do here
270 }
271 else if (det == 0)
272 {
273 // there is 1 solution
274 t = -2 * x_coeff[1] / (6 * x_coeff[0]);
275 if (t > 0 && t < 1)
276 {
277 x = x_coeff[0] * t * t * t + x_coeff[1] * t * t + x_coeff[2] * t + x_coeff[3];
278 if (x < bounds[0])
279 bounds[0] = x;
280 if (x > bounds[2])
281 bounds[2] = x;
282 }
283 }
284 else
285 {
286 // there are 2 solutions:
287 det = (float) Math.sqrt(det);
288 t = (-2 * x_coeff[1] + det) / (6 * x_coeff[0]);
289 if (t > 0 && t < 1)
290 {
291 x = x_coeff[0] * t * t * t + x_coeff[1] * t * t + x_coeff[2] * t + x_coeff[3];
292 if (x < bounds[0])
293 bounds[0] = x;
294 if (x > bounds[2])
295 bounds[2] = x;
296 }
297
298 t = (-2 * x_coeff[1] - det) / (6 * x_coeff[0]);
299 if (t > 0 && t < 1)
300 {
301 x = x_coeff[0] * t * t * t + x_coeff[1] * t * t + x_coeff[2] * t + x_coeff[3];
302 if (x < bounds[0])
303 bounds[0] = x;
304 if (x > bounds[2])
305 bounds[2] = x;
306 }
307 }
308
309 det = (4 * y_coeff[1] * y_coeff[1] - 12 * y_coeff[0] * y_coeff[2]);
310 if (det < 0)
311 {
312 // there are no solutions! nothing to do here
313 }
314 else if (det == 0)
315 {
316 // there is 1 solution
317 t = -2 * y_coeff[1] / (6 * y_coeff[0]);
318 if (t > 0 && t < 1)
319 {
320 y = y_coeff[0] * t * t * t + y_coeff[1] * t * t + y_coeff[2] * t + y_coeff[3];
321 if (y < bounds[1])
322 bounds[1] = y;
323 if (y > bounds[3])
324 bounds[3] = y;
325 }
326 }
327 else
328 {
329 // there are 2 solutions:
330 det = (float) Math.sqrt(det);
331 t = (-2 * y_coeff[1] + det) / (6 * y_coeff[0]);
332 if (t > 0 && t < 1)
333 {
334 y = y_coeff[0] * t * t * t + y_coeff[1] * t * t + y_coeff[2] * t + y_coeff[3];
335 if (y < bounds[1])
336 bounds[1] = y;
337 if (y > bounds[3])
338 bounds[3] = y;
339 }
340
341 t = (-2 * y_coeff[1] - det) / (6 * y_coeff[0]);
342 if (t > 0 && t < 1)
343 {
344 y = y_coeff[0] * t * t * t + y_coeff[1] * t * t + y_coeff[2] * t + y_coeff[3];
345 if (y < bounds[1])
346 bounds[1] = y;
347 if (y > bounds[3])
348 bounds[3] = y;
349 }
350 }
351
352 lastX = f[4];
353 lastY = f[5];
354 }
355 }
356 i.next();
357 }
358
359 if (bounds == null)
360 {
361 throw new EmptyPathException();
362 }
363 if (r != null)
364 {
365 r.setFrame(bounds[0], bounds[1], bounds[2] - bounds[0], bounds[3] - bounds[1]);
366 return r;
367 }
368 return new Rectangle2D.Float(bounds[0], bounds[1], bounds[2] - bounds[0], bounds[3] - bounds[1]);
369 }
370 }