001 /* Polygon.java -- class representing a polygon
002 Copyright (C) 1999, 2002, 2004, 2005 Free Software Foundation, Inc.
003
004 This file is part of GNU Classpath.
005
006 GNU Classpath is free software; you can redistribute it and/or modify
007 it under the terms of the GNU General Public License as published by
008 the Free Software Foundation; either version 2, or (at your option)
009 any later version.
010
011 GNU Classpath is distributed in the hope that it will be useful, but
012 WITHOUT ANY WARRANTY; without even the implied warranty of
013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014 General Public License for more details.
015
016 You should have received a copy of the GNU General Public License
017 along with GNU Classpath; see the file COPYING. If not, write to the
018 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019 02110-1301 USA.
020
021 Linking this library statically or dynamically with other modules is
022 making a combined work based on this library. Thus, the terms and
023 conditions of the GNU General Public License cover the whole
024 combination.
025
026 As a special exception, the copyright holders of this library give you
027 permission to link this library with independent modules to produce an
028 executable, regardless of the license terms of these independent
029 modules, and to copy and distribute the resulting executable under
030 terms of your choice, provided that you also meet, for each linked
031 independent module, the terms and conditions of the license of that
032 module. An independent module is a module which is not derived from
033 or based on this library. If you modify this library, you may extend
034 this exception to your version of the library, but you are not
035 obligated to do so. If you do not wish to do so, delete this
036 exception statement from your version. */
037
038
039 package java.awt;
040
041 import java.awt.geom.AffineTransform;
042 import java.awt.geom.Line2D;
043 import java.awt.geom.PathIterator;
044 import java.awt.geom.Point2D;
045 import java.awt.geom.Rectangle2D;
046 import java.io.Serializable;
047
048 /**
049 * This class represents a polygon, a closed, two-dimensional region in a
050 * coordinate space. The region is bounded by an arbitrary number of line
051 * segments, between (x,y) coordinate vertices. The polygon has even-odd
052 * winding, meaning that a point is inside the shape if it crosses the
053 * boundary an odd number of times on the way to infinity.
054 *
055 * <p>There are some public fields; if you mess with them in an inconsistent
056 * manner, it is your own fault when you get NullPointerException,
057 * ArrayIndexOutOfBoundsException, or invalid results. Also, this class is
058 * not threadsafe.
059 *
060 * @author Aaron M. Renn (arenn@urbanophile.com)
061 * @author Eric Blake (ebb9@email.byu.edu)
062 * @since 1.0
063 * @status updated to 1.4
064 */
065 public class Polygon implements Shape, Serializable
066 {
067 /**
068 * Compatible with JDK 1.0+.
069 */
070 private static final long serialVersionUID = -6460061437900069969L;
071
072 /**
073 * This total number of endpoints.
074 *
075 * @serial the number of endpoints, possibly less than the array sizes
076 */
077 public int npoints;
078
079 /**
080 * The array of X coordinates of endpoints. This should not be null.
081 *
082 * @see #addPoint(int, int)
083 * @serial the x coordinates
084 */
085 public int[] xpoints;
086
087 /**
088 * The array of Y coordinates of endpoints. This should not be null.
089 *
090 * @see #addPoint(int, int)
091 * @serial the y coordinates
092 */
093 public int[] ypoints;
094
095 /**
096 * The bounding box of this polygon. This is lazily created and cached, so
097 * it must be invalidated after changing points.
098 *
099 * @see #getBounds()
100 * @serial the bounding box, or null
101 */
102 protected Rectangle bounds;
103
104 /** A big number, but not so big it can't survive a few float operations */
105 private static final double BIG_VALUE = java.lang.Double.MAX_VALUE / 10.0;
106
107 /**
108 * Initializes an empty polygon.
109 */
110 public Polygon()
111 {
112 // Leave room for growth.
113 xpoints = new int[4];
114 ypoints = new int[4];
115 }
116
117 /**
118 * Create a new polygon with the specified endpoints. The arrays are copied,
119 * so that future modifications to the parameters do not affect the polygon.
120 *
121 * @param xpoints the array of X coordinates for this polygon
122 * @param ypoints the array of Y coordinates for this polygon
123 * @param npoints the total number of endpoints in this polygon
124 * @throws NegativeArraySizeException if npoints is negative
125 * @throws IndexOutOfBoundsException if npoints exceeds either array
126 * @throws NullPointerException if xpoints or ypoints is null
127 */
128 public Polygon(int[] xpoints, int[] ypoints, int npoints)
129 {
130 this.xpoints = new int[npoints];
131 this.ypoints = new int[npoints];
132 System.arraycopy(xpoints, 0, this.xpoints, 0, npoints);
133 System.arraycopy(ypoints, 0, this.ypoints, 0, npoints);
134 this.npoints = npoints;
135 }
136
137 /**
138 * Reset the polygon to be empty. The arrays are left alone, to avoid object
139 * allocation, but the number of points is set to 0, and all cached data
140 * is discarded. If you are discarding a huge number of points, it may be
141 * more efficient to just create a new Polygon.
142 *
143 * @see #invalidate()
144 * @since 1.4
145 */
146 public void reset()
147 {
148 npoints = 0;
149 invalidate();
150 }
151
152 /**
153 * Invalidate or flush all cached data. After direct manipulation of the
154 * public member fields, this is necessary to avoid inconsistent results
155 * in methods like <code>contains</code>.
156 *
157 * @see #getBounds()
158 * @since 1.4
159 */
160 public void invalidate()
161 {
162 bounds = null;
163 }
164
165 /**
166 * Translates the polygon by adding the specified values to all X and Y
167 * coordinates. This updates the bounding box, if it has been calculated.
168 *
169 * @param dx the amount to add to all X coordinates
170 * @param dy the amount to add to all Y coordinates
171 * @since 1.1
172 */
173 public void translate(int dx, int dy)
174 {
175 int i = npoints;
176 while (--i >= 0)
177 {
178 xpoints[i] += dx;
179 ypoints[i] += dy;
180 }
181 if (bounds != null)
182 {
183 bounds.x += dx;
184 bounds.y += dy;
185 }
186 }
187
188 /**
189 * Adds the specified endpoint to the polygon. This updates the bounding
190 * box, if it has been created.
191 *
192 * @param x the X coordinate of the point to add
193 * @param y the Y coordiante of the point to add
194 */
195 public void addPoint(int x, int y)
196 {
197 if (npoints + 1 > xpoints.length)
198 {
199 int[] newx = new int[npoints + 1];
200 System.arraycopy(xpoints, 0, newx, 0, npoints);
201 xpoints = newx;
202 }
203 if (npoints + 1 > ypoints.length)
204 {
205 int[] newy = new int[npoints + 1];
206 System.arraycopy(ypoints, 0, newy, 0, npoints);
207 ypoints = newy;
208 }
209 xpoints[npoints] = x;
210 ypoints[npoints] = y;
211 npoints++;
212 if (bounds != null)
213 {
214 if (npoints == 1)
215 {
216 bounds.x = x;
217 bounds.y = y;
218 }
219 else
220 {
221 if (x < bounds.x)
222 {
223 bounds.width += bounds.x - x;
224 bounds.x = x;
225 }
226 else if (x > bounds.x + bounds.width)
227 bounds.width = x - bounds.x;
228 if (y < bounds.y)
229 {
230 bounds.height += bounds.y - y;
231 bounds.y = y;
232 }
233 else if (y > bounds.y + bounds.height)
234 bounds.height = y - bounds.y;
235 }
236 }
237 }
238
239 /**
240 * Returns the bounding box of this polygon. This is the smallest
241 * rectangle with sides parallel to the X axis that will contain this
242 * polygon.
243 *
244 * @return the bounding box for this polygon
245 * @see #getBounds2D()
246 * @since 1.1
247 */
248 public Rectangle getBounds()
249 {
250 return getBoundingBox();
251 }
252
253 /**
254 * Returns the bounding box of this polygon. This is the smallest
255 * rectangle with sides parallel to the X axis that will contain this
256 * polygon.
257 *
258 * @return the bounding box for this polygon
259 * @see #getBounds2D()
260 * @deprecated use {@link #getBounds()} instead
261 */
262 public Rectangle getBoundingBox()
263 {
264 if (bounds == null)
265 {
266 if (npoints == 0)
267 return bounds = new Rectangle();
268 int i = npoints - 1;
269 int minx = xpoints[i];
270 int maxx = minx;
271 int miny = ypoints[i];
272 int maxy = miny;
273 while (--i >= 0)
274 {
275 int x = xpoints[i];
276 int y = ypoints[i];
277 if (x < minx)
278 minx = x;
279 else if (x > maxx)
280 maxx = x;
281 if (y < miny)
282 miny = y;
283 else if (y > maxy)
284 maxy = y;
285 }
286 bounds = new Rectangle(minx, miny, maxx - minx, maxy - miny);
287 }
288 return bounds;
289 }
290
291 /**
292 * Tests whether or not the specified point is inside this polygon.
293 *
294 * @param p the point to test
295 * @return true if the point is inside this polygon
296 * @throws NullPointerException if p is null
297 * @see #contains(double, double)
298 */
299 public boolean contains(Point p)
300 {
301 return contains(p.getX(), p.getY());
302 }
303
304 /**
305 * Tests whether or not the specified point is inside this polygon.
306 *
307 * @param x the X coordinate of the point to test
308 * @param y the Y coordinate of the point to test
309 * @return true if the point is inside this polygon
310 * @see #contains(double, double)
311 * @since 1.1
312 */
313 public boolean contains(int x, int y)
314 {
315 return contains((double) x, (double) y);
316 }
317
318 /**
319 * Tests whether or not the specified point is inside this polygon.
320 *
321 * @param x the X coordinate of the point to test
322 * @param y the Y coordinate of the point to test
323 * @return true if the point is inside this polygon
324 * @see #contains(double, double)
325 * @deprecated use {@link #contains(int, int)} instead
326 */
327 public boolean inside(int x, int y)
328 {
329 return contains((double) x, (double) y);
330 }
331
332 /**
333 * Returns a high-precision bounding box of this polygon. This is the
334 * smallest rectangle with sides parallel to the X axis that will contain
335 * this polygon.
336 *
337 * @return the bounding box for this polygon
338 * @see #getBounds()
339 * @since 1.2
340 */
341 public Rectangle2D getBounds2D()
342 {
343 // For polygons, the integer version is exact!
344 return getBounds();
345 }
346
347 /**
348 * Tests whether or not the specified point is inside this polygon.
349 *
350 * @param x the X coordinate of the point to test
351 * @param y the Y coordinate of the point to test
352 * @return true if the point is inside this polygon
353 * @since 1.2
354 */
355 public boolean contains(double x, double y)
356 {
357 return ((evaluateCrossings(x, y, false, BIG_VALUE) & 1) != 0);
358 }
359
360 /**
361 * Tests whether or not the specified point is inside this polygon.
362 *
363 * @param p the point to test
364 * @return true if the point is inside this polygon
365 * @throws NullPointerException if p is null
366 * @see #contains(double, double)
367 * @since 1.2
368 */
369 public boolean contains(Point2D p)
370 {
371 return contains(p.getX(), p.getY());
372 }
373
374 /**
375 * Test if a high-precision rectangle intersects the shape. This is true
376 * if any point in the rectangle is in the shape. This implementation is
377 * precise.
378 *
379 * @param x the x coordinate of the rectangle
380 * @param y the y coordinate of the rectangle
381 * @param w the width of the rectangle, treated as point if negative
382 * @param h the height of the rectangle, treated as point if negative
383 * @return true if the rectangle intersects this shape
384 * @since 1.2
385 */
386 public boolean intersects(double x, double y, double w, double h)
387 {
388 /* Does any edge intersect? */
389 if (evaluateCrossings(x, y, false, w) != 0 /* top */
390 || evaluateCrossings(x, y + h, false, w) != 0 /* bottom */
391 || evaluateCrossings(x + w, y, true, h) != 0 /* right */
392 || evaluateCrossings(x, y, true, h) != 0) /* left */
393 return true;
394
395 /* No intersections, is any point inside? */
396 if ((evaluateCrossings(x, y, false, BIG_VALUE) & 1) != 0)
397 return true;
398
399 return false;
400 }
401
402 /**
403 * Test if a high-precision rectangle intersects the shape. This is true
404 * if any point in the rectangle is in the shape. This implementation is
405 * precise.
406 *
407 * @param r the rectangle
408 * @return true if the rectangle intersects this shape
409 * @throws NullPointerException if r is null
410 * @see #intersects(double, double, double, double)
411 * @since 1.2
412 */
413 public boolean intersects(Rectangle2D r)
414 {
415 return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
416 }
417
418 /**
419 * Test if a high-precision rectangle lies completely in the shape. This is
420 * true if all points in the rectangle are in the shape. This implementation
421 * is precise.
422 *
423 * @param x the x coordinate of the rectangle
424 * @param y the y coordinate of the rectangle
425 * @param w the width of the rectangle, treated as point if negative
426 * @param h the height of the rectangle, treated as point if negative
427 * @return true if the rectangle is contained in this shape
428 * @since 1.2
429 */
430 public boolean contains(double x, double y, double w, double h)
431 {
432 if (! getBounds2D().intersects(x, y, w, h))
433 return false;
434
435 /* Does any edge intersect? */
436 if (evaluateCrossings(x, y, false, w) != 0 /* top */
437 || evaluateCrossings(x, y + h, false, w) != 0 /* bottom */
438 || evaluateCrossings(x + w, y, true, h) != 0 /* right */
439 || evaluateCrossings(x, y, true, h) != 0) /* left */
440 return false;
441
442 /* No intersections, is any point inside? */
443 if ((evaluateCrossings(x, y, false, BIG_VALUE) & 1) != 0)
444 return true;
445
446 return false;
447 }
448
449 /**
450 * Test if a high-precision rectangle lies completely in the shape. This is
451 * true if all points in the rectangle are in the shape. This implementation
452 * is precise.
453 *
454 * @param r the rectangle
455 * @return true if the rectangle is contained in this shape
456 * @throws NullPointerException if r is null
457 * @see #contains(double, double, double, double)
458 * @since 1.2
459 */
460 public boolean contains(Rectangle2D r)
461 {
462 return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
463 }
464
465 /**
466 * Return an iterator along the shape boundary. If the optional transform
467 * is provided, the iterator is transformed accordingly. Each call returns
468 * a new object, independent from others in use. This class is not
469 * threadsafe to begin with, so the path iterator is not either.
470 *
471 * @param transform an optional transform to apply to the iterator
472 * @return a new iterator over the boundary
473 * @since 1.2
474 */
475 public PathIterator getPathIterator(final AffineTransform transform)
476 {
477 return new PathIterator()
478 {
479 /** The current vertex of iteration. */
480 private int vertex;
481
482 public int getWindingRule()
483 {
484 return WIND_EVEN_ODD;
485 }
486
487 public boolean isDone()
488 {
489 return vertex > npoints;
490 }
491
492 public void next()
493 {
494 vertex++;
495 }
496
497 public int currentSegment(float[] coords)
498 {
499 if (vertex >= npoints)
500 return SEG_CLOSE;
501 coords[0] = xpoints[vertex];
502 coords[1] = ypoints[vertex];
503 if (transform != null)
504 transform.transform(coords, 0, coords, 0, 1);
505 return vertex == 0 ? SEG_MOVETO : SEG_LINETO;
506 }
507
508 public int currentSegment(double[] coords)
509 {
510 if (vertex >= npoints)
511 return SEG_CLOSE;
512 coords[0] = xpoints[vertex];
513 coords[1] = ypoints[vertex];
514 if (transform != null)
515 transform.transform(coords, 0, coords, 0, 1);
516 return vertex == 0 ? SEG_MOVETO : SEG_LINETO;
517 }
518 };
519 }
520
521 /**
522 * Return an iterator along the flattened version of the shape boundary.
523 * Since polygons are already flat, the flatness parameter is ignored, and
524 * the resulting iterator only has SEG_MOVETO, SEG_LINETO and SEG_CLOSE
525 * points. If the optional transform is provided, the iterator is
526 * transformed accordingly. Each call returns a new object, independent
527 * from others in use. This class is not threadsafe to begin with, so the
528 * path iterator is not either.
529 *
530 * @param transform an optional transform to apply to the iterator
531 * @param flatness the maximum distance for deviation from the real boundary
532 * @return a new iterator over the boundary
533 * @since 1.2
534 */
535 public PathIterator getPathIterator(AffineTransform transform,
536 double flatness)
537 {
538 return getPathIterator(transform);
539 }
540
541 /**
542 * Helper for contains, intersects, calculates the number of intersections
543 * between the polygon and a line extending from the point (x, y) along
544 * the positive X, or Y axis, within a given interval.
545 *
546 * @return the winding number.
547 * @see #contains(double, double)
548 */
549 private int evaluateCrossings(double x, double y, boolean useYaxis,
550 double distance)
551 {
552 double x0;
553 double x1;
554 double y0;
555 double y1;
556 double epsilon = 0.0;
557 int crossings = 0;
558 int[] xp;
559 int[] yp;
560
561 if (useYaxis)
562 {
563 xp = ypoints;
564 yp = xpoints;
565 double swap;
566 swap = y;
567 y = x;
568 x = swap;
569 }
570 else
571 {
572 xp = xpoints;
573 yp = ypoints;
574 }
575
576 /* Get a value which is small but not insignificant relative the path. */
577 epsilon = 1E-7;
578
579 x0 = xp[0] - x;
580 y0 = yp[0] - y;
581 for (int i = 1; i < npoints; i++)
582 {
583 x1 = xp[i] - x;
584 y1 = yp[i] - y;
585
586 if (y0 == 0.0)
587 y0 -= epsilon;
588 if (y1 == 0.0)
589 y1 -= epsilon;
590 if (y0 * y1 < 0)
591 if (Line2D.linesIntersect(x0, y0, x1, y1, epsilon, 0.0, distance, 0.0))
592 ++crossings;
593
594 x0 = xp[i] - x;
595 y0 = yp[i] - y;
596 }
597
598 // end segment
599 x1 = xp[0] - x;
600 y1 = yp[0] - y;
601 if (y0 == 0.0)
602 y0 -= epsilon;
603 if (y1 == 0.0)
604 y1 -= epsilon;
605 if (y0 * y1 < 0)
606 if (Line2D.linesIntersect(x0, y0, x1, y1, epsilon, 0.0, distance, 0.0))
607 ++crossings;
608
609 return crossings;
610 }
611 } // class Polygon