Source for java.awt.geom.Area

   1: /* Area.java -- represents a shape built by constructive area geometry
   2:    Copyright (C) 2002, 2004 Free Software Foundation
   3: 
   4: This file is part of GNU Classpath.
   5: 
   6: GNU Classpath is free software; you can redistribute it and/or modify
   7: it under the terms of the GNU General Public License as published by
   8: the Free Software Foundation; either version 2, or (at your option)
   9: any later version.
  10: 
  11: GNU Classpath is distributed in the hope that it will be useful, but
  12: WITHOUT ANY WARRANTY; without even the implied warranty of
  13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14: General Public License for more details.
  15: 
  16: You should have received a copy of the GNU General Public License
  17: along with GNU Classpath; see the file COPYING.  If not, write to the
  18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19: 02110-1301 USA.
  20: 
  21: Linking this library statically or dynamically with other modules is
  22: making a combined work based on this library.  Thus, the terms and
  23: conditions of the GNU General Public License cover the whole
  24: combination.
  25: 
  26: As a special exception, the copyright holders of this library give you
  27: permission to link this library with independent modules to produce an
  28: executable, regardless of the license terms of these independent
  29: modules, and to copy and distribute the resulting executable under
  30: terms of your choice, provided that you also meet, for each linked
  31: independent module, the terms and conditions of the license of that
  32: module.  An independent module is a module which is not derived from
  33: or based on this library.  If you modify this library, you may extend
  34: this exception to your version of the library, but you are not
  35: obligated to do so.  If you do not wish to do so, delete this
  36: exception statement from your version. */
  37: 
  38: package java.awt.geom;
  39: 
  40: import java.awt.Rectangle;
  41: import java.awt.Shape;
  42: import java.util.Vector;
  43: 
  44: 
  45: /**
  46:  * The Area class represents any area for the purpose of
  47:  * Constructive Area Geometry (CAG) manipulations. CAG manipulations
  48:  * work as an area-wise form of boolean logic, where the basic operations are:
  49:  * <P><li>Add (in boolean algebra: A <B>or</B> B)<BR>
  50:  * <li>Subtract (in boolean algebra: A <B>and</B> (<B>not</B> B) )<BR>
  51:  * <li>Intersect (in boolean algebra: A <B>and</B> B)<BR>
  52:  * <li>Exclusive Or <BR>
  53:  * <img src="doc-files/Area-1.png" width="342" height="302"
  54:  * alt="Illustration of CAG operations" /><BR>
  55:  * Above is an illustration of the CAG operations on two ring shapes.<P>
  56:  *
  57:  * The contains and intersects() methods are also more accurate than the
  58:  * specification of #Shape requires.<P>
  59:  *
  60:  * Please note that constructing an Area can be slow
  61:  * (Self-intersection resolving is proportional to the square of
  62:  * the number of segments).<P>
  63:  * @see #add(Area)
  64:  * @see #subtract(Area)
  65:  * @see #intersect(Area)
  66:  * @see #exclusiveOr(Area)
  67:  *
  68:  * @author Sven de Marothy (sven@physto.se)
  69:  *
  70:  * @since 1.2
  71:  * @status Works, but could be faster and more reliable.
  72:  */
  73: public class Area implements Shape, Cloneable
  74: {
  75:   /**
  76:    * General numerical precision
  77:    */
  78:   private static final double EPSILON = 1E-11;
  79: 
  80:   /**
  81:    * recursive subdivision epsilon - (see getRecursionDepth)
  82:    */
  83:   private static final double RS_EPSILON = 1E-13;
  84: 
  85:   /**
  86:    * Snap distance - points within this distance are considered equal
  87:    */
  88:   private static final double PE_EPSILON = 1E-11;
  89: 
  90:   /**
  91:    * Segment vectors containing solid areas and holes
  92:    * This is package-private to avoid an accessor method.
  93:    */
  94:   Vector solids;
  95: 
  96:   /**
  97:    * Segment vectors containing solid areas and holes
  98:    * This is package-private to avoid an accessor method.
  99:    */
 100:   Vector holes;
 101: 
 102:   /**
 103:    * Vector (temporary) storing curve-curve intersections
 104:    */
 105:   private Vector cc_intersections;
 106: 
 107:   /**
 108:    * Winding rule WIND_NON_ZERO used, after construction,
 109:    * this is irrelevant.
 110:    */
 111:   private int windingRule;
 112: 
 113:   /**
 114:    * Constructs an empty Area
 115:    */
 116:   public Area()
 117:   {
 118:     solids = new Vector();
 119:     holes = new Vector();
 120:   }
 121: 
 122:   /**
 123:    * Constructs an Area from any given Shape. <P>
 124:    *
 125:    * If the Shape is self-intersecting, the created Area will consist
 126:    * of non-self-intersecting subpaths, and any inner paths which
 127:    * are found redundant in accordance with the Shape's winding rule
 128:    * will not be included.
 129:    * 
 130:    * @param s  the shape (<code>null</code> not permitted).
 131:    * 
 132:    * @throws NullPointerException if <code>s</code> is <code>null</code>.
 133:    */
 134:   public Area(Shape s)
 135:   {
 136:     this();
 137: 
 138:     Vector p = makeSegment(s);
 139: 
 140:     // empty path
 141:     if (p == null)
 142:       return;
 143: 
 144:     // delete empty paths
 145:     for (int i = 0; i < p.size(); i++)
 146:       if (((Segment) p.elementAt(i)).getSignedArea() == 0.0)
 147:     p.remove(i--);
 148: 
 149:     /*
 150:      * Resolve self intersecting paths into non-intersecting
 151:      * solids and holes.
 152:      * Algorithm is as follows:
 153:      * 1: Create nodes at all self intersections
 154:      * 2: Put all segments into a list
 155:      * 3: Grab a segment, follow it, change direction at each node,
 156:      *    removing segments from the list in the process
 157:      * 4: Repeat (3) until no segments remain in the list
 158:      * 5: Remove redundant paths and sort into solids and holes
 159:      */
 160:     Vector paths = new Vector();
 161:     Segment v;
 162: 
 163:     for (int i = 0; i < p.size(); i++)
 164:       {
 165:     Segment path = (Segment) p.elementAt(i);
 166:     createNodesSelf(path);
 167:       }
 168: 
 169:     if (p.size() > 1)
 170:       {
 171:     for (int i = 0; i < p.size() - 1; i++)
 172:       for (int j = i + 1; j < p.size(); j++)
 173:         {
 174:           Segment path1 = (Segment) p.elementAt(i);
 175:           Segment path2 = (Segment) p.elementAt(j);
 176:           createNodes(path1, path2);
 177:         }
 178:       }
 179: 
 180:     // we have intersecting points.
 181:     Vector segments = new Vector();
 182: 
 183:     for (int i = 0; i < p.size(); i++)
 184:       {
 185:     Segment path = v = (Segment) p.elementAt(i);
 186:     do
 187:       {
 188:         segments.add(v);
 189:         v = v.next;
 190:       }
 191:     while (v != path);
 192:       }
 193: 
 194:     paths = weilerAtherton(segments);
 195:     deleteRedundantPaths(paths);
 196:   }
 197: 
 198:   /**
 199:    * Performs an add (union) operation on this area with another Area.<BR>
 200:    * @param area - the area to be unioned with this one
 201:    */
 202:   public void add(Area area)
 203:   {
 204:     if (equals(area))
 205:       return;
 206:     if (area.isEmpty())
 207:       return;
 208: 
 209:     Area B = (Area) area.clone();
 210: 
 211:     Vector pathA = new Vector();
 212:     Vector pathB = new Vector();
 213:     pathA.addAll(solids);
 214:     pathA.addAll(holes);
 215:     pathB.addAll(B.solids);
 216:     pathB.addAll(B.holes);
 217: 
 218:     int nNodes = 0;
 219: 
 220:     for (int i = 0; i < pathA.size(); i++)
 221:       {
 222:     Segment a = (Segment) pathA.elementAt(i);
 223:     for (int j = 0; j < pathB.size(); j++)
 224:       {
 225:         Segment b = (Segment) pathB.elementAt(j);
 226:         nNodes += createNodes(a, b);
 227:       }
 228:       }
 229: 
 230:     Vector paths = new Vector();
 231:     Segment v;
 232: 
 233:     // we have intersecting points.
 234:     Vector segments = new Vector();
 235: 
 236:     // In a union operation, we keep all
 237:     // segments of A oustide B and all B outside A
 238:     for (int i = 0; i < pathA.size(); i++)
 239:       {
 240:     v = (Segment) pathA.elementAt(i);
 241:     Segment path = v;
 242:     do
 243:       {
 244:         if (v.isSegmentOutside(area))
 245:           segments.add(v);
 246:         v = v.next;
 247:       }
 248:     while (v != path);
 249:       }
 250: 
 251:     for (int i = 0; i < pathB.size(); i++)
 252:       {
 253:     v = (Segment) pathB.elementAt(i);
 254:     Segment path = v;
 255:     do
 256:       {
 257:         if (v.isSegmentOutside(this))
 258:           segments.add(v);
 259:         v = v.next;
 260:       }
 261:     while (v != path);
 262:       }
 263: 
 264:     paths = weilerAtherton(segments);
 265:     deleteRedundantPaths(paths);
 266:   }
 267: 
 268:   /**
 269:    * Performs a subtraction operation on this Area.<BR>
 270:    * @param area the area to be subtracted from this area.
 271:    * @throws NullPointerException if <code>area</code> is <code>null</code>.
 272:    */
 273:   public void subtract(Area area)
 274:   {
 275:     if (isEmpty() || area.isEmpty())
 276:       return;
 277: 
 278:     if (equals(area))
 279:       {
 280:     reset();
 281:     return;
 282:       }
 283: 
 284:     Vector pathA = new Vector();
 285:     Area B = (Area) area.clone();
 286:     pathA.addAll(solids);
 287:     pathA.addAll(holes);
 288: 
 289:     // reverse the directions of B paths.
 290:     setDirection(B.holes, true);
 291:     setDirection(B.solids, false);
 292: 
 293:     Vector pathB = new Vector();
 294:     pathB.addAll(B.solids);
 295:     pathB.addAll(B.holes);
 296: 
 297:     int nNodes = 0;
 298: 
 299:     // create nodes
 300:     for (int i = 0; i < pathA.size(); i++)
 301:       {
 302:     Segment a = (Segment) pathA.elementAt(i);
 303:     for (int j = 0; j < pathB.size(); j++)
 304:       {
 305:         Segment b = (Segment) pathB.elementAt(j);
 306:         nNodes += createNodes(a, b);
 307:       }
 308:       }
 309: 
 310:     Vector paths = new Vector();
 311: 
 312:     // we have intersecting points.
 313:     Vector segments = new Vector();
 314: 
 315:     // In a subtraction operation, we keep all
 316:     // segments of A oustide B and all B within A
 317:     // We outsideness-test only one segment in each path
 318:     // and the segments before and after any node
 319:     for (int i = 0; i < pathA.size(); i++)
 320:       {
 321:     Segment v = (Segment) pathA.elementAt(i);
 322:     Segment path = v;
 323:     if (v.isSegmentOutside(area) && v.node == null)
 324:       segments.add(v);
 325:     boolean node = false;
 326:     do
 327:       {
 328:         if ((v.node != null || node))
 329:           {
 330:         node = (v.node != null);
 331:         if (v.isSegmentOutside(area))
 332:           segments.add(v);
 333:           }
 334:         v = v.next;
 335:       }
 336:     while (v != path);
 337:       }
 338: 
 339:     for (int i = 0; i < pathB.size(); i++)
 340:       {
 341:     Segment v = (Segment) pathB.elementAt(i);
 342:     Segment path = v;
 343:     if (! v.isSegmentOutside(this) && v.node == null)
 344:       segments.add(v);
 345:     v = v.next;
 346:     boolean node = false;
 347:     do
 348:       {
 349:         if ((v.node != null || node))
 350:           {
 351:         node = (v.node != null);
 352:         if (! v.isSegmentOutside(this))
 353:           segments.add(v);
 354:           }
 355:         v = v.next;
 356:       }
 357:     while (v != path);
 358:       }
 359: 
 360:     paths = weilerAtherton(segments);
 361:     deleteRedundantPaths(paths);
 362:   }
 363: 
 364:   /**
 365:    * Performs an intersection operation on this Area.<BR>
 366:    * @param area - the area to be intersected with this area.
 367:    * @throws NullPointerException if <code>area</code> is <code>null</code>.
 368:    */
 369:   public void intersect(Area area)
 370:   {
 371:     if (isEmpty() || area.isEmpty())
 372:       {
 373:     reset();
 374:     return;
 375:       }
 376:     if (equals(area))
 377:       return;
 378: 
 379:     Vector pathA = new Vector();
 380:     Area B = (Area) area.clone();
 381:     pathA.addAll(solids);
 382:     pathA.addAll(holes);
 383: 
 384:     Vector pathB = new Vector();
 385:     pathB.addAll(B.solids);
 386:     pathB.addAll(B.holes);
 387: 
 388:     int nNodes = 0;
 389: 
 390:     // create nodes
 391:     for (int i = 0; i < pathA.size(); i++)
 392:       {
 393:     Segment a = (Segment) pathA.elementAt(i);
 394:     for (int j = 0; j < pathB.size(); j++)
 395:       {
 396:         Segment b = (Segment) pathB.elementAt(j);
 397:         nNodes += createNodes(a, b);
 398:       }
 399:       }
 400: 
 401:     Vector paths = new Vector();
 402: 
 403:     // we have intersecting points.
 404:     Vector segments = new Vector();
 405: 
 406:     // In an intersection operation, we keep all
 407:     // segments of A within B and all B within A
 408:     // (The rest must be redundant)
 409:     // We outsideness-test only one segment in each path
 410:     // and the segments before and after any node
 411:     for (int i = 0; i < pathA.size(); i++)
 412:       {
 413:     Segment v = (Segment) pathA.elementAt(i);
 414:     Segment path = v;
 415:     if (! v.isSegmentOutside(area) && v.node == null)
 416:       segments.add(v);
 417:     boolean node = false;
 418:     do
 419:       {
 420:         if ((v.node != null || node))
 421:           {
 422:         node = (v.node != null);
 423:         if (! v.isSegmentOutside(area))
 424:           segments.add(v);
 425:           }
 426:         v = v.next;
 427:       }
 428:     while (v != path);
 429:       }
 430: 
 431:     for (int i = 0; i < pathB.size(); i++)
 432:       {
 433:     Segment v = (Segment) pathB.elementAt(i);
 434:     Segment path = v;
 435:     if (! v.isSegmentOutside(this) && v.node == null)
 436:       segments.add(v);
 437:     v = v.next;
 438:     boolean node = false;
 439:     do
 440:       {
 441:         if ((v.node != null || node))
 442:           {
 443:         node = (v.node != null);
 444:         if (! v.isSegmentOutside(this))
 445:           segments.add(v);
 446:           }
 447:         v = v.next;
 448:       }
 449:     while (v != path);
 450:       }
 451: 
 452:     paths = weilerAtherton(segments);
 453:     deleteRedundantPaths(paths);
 454:   }
 455: 
 456:   /**
 457:    * Performs an exclusive-or operation on this Area.<BR>
 458:    * @param area - the area to be XORed with this area.
 459:    * @throws NullPointerException if <code>area</code> is <code>null</code>.
 460:    */
 461:   public void exclusiveOr(Area area)
 462:   {
 463:     if (area.isEmpty())
 464:       return;
 465: 
 466:     if (isEmpty())
 467:       {
 468:     Area B = (Area) area.clone();
 469:     solids = B.solids;
 470:     holes = B.holes;
 471:     return;
 472:       }
 473:     if (equals(area))
 474:       {
 475:     reset();
 476:     return;
 477:       }
 478: 
 479:     Vector pathA = new Vector();
 480: 
 481:     Area B = (Area) area.clone();
 482:     Vector pathB = new Vector();
 483:     pathA.addAll(solids);
 484:     pathA.addAll(holes);
 485: 
 486:     // reverse the directions of B paths.
 487:     setDirection(B.holes, true);
 488:     setDirection(B.solids, false);
 489:     pathB.addAll(B.solids);
 490:     pathB.addAll(B.holes);
 491: 
 492:     int nNodes = 0;
 493: 
 494:     for (int i = 0; i < pathA.size(); i++)
 495:       {
 496:     Segment a = (Segment) pathA.elementAt(i);
 497:     for (int j = 0; j < pathB.size(); j++)
 498:       {
 499:         Segment b = (Segment) pathB.elementAt(j);
 500:         nNodes += createNodes(a, b);
 501:       }
 502:       }
 503: 
 504:     Vector paths = new Vector();
 505:     Segment v;
 506: 
 507:     // we have intersecting points.
 508:     Vector segments = new Vector();
 509: 
 510:     // In an XOR operation, we operate on all segments
 511:     for (int i = 0; i < pathA.size(); i++)
 512:       {
 513:     v = (Segment) pathA.elementAt(i);
 514:     Segment path = v;
 515:     do
 516:       {
 517:         segments.add(v);
 518:         v = v.next;
 519:       }
 520:     while (v != path);
 521:       }
 522: 
 523:     for (int i = 0; i < pathB.size(); i++)
 524:       {
 525:     v = (Segment) pathB.elementAt(i);
 526:     Segment path = v;
 527:     do
 528:       {
 529:         segments.add(v);
 530:         v = v.next;
 531:       }
 532:     while (v != path);
 533:       }
 534: 
 535:     paths = weilerAtherton(segments);
 536:     deleteRedundantPaths(paths);
 537:   }
 538: 
 539:   /**
 540:    * Clears the Area object, creating an empty area.
 541:    */
 542:   public void reset()
 543:   {
 544:     solids = new Vector();
 545:     holes = new Vector();
 546:   }
 547: 
 548:   /**
 549:    * Returns whether this area encloses any area.
 550:    * @return true if the object encloses any area.
 551:    */
 552:   public boolean isEmpty()
 553:   {
 554:     if (solids.size() == 0)
 555:       return true;
 556: 
 557:     double totalArea = 0;
 558:     for (int i = 0; i < solids.size(); i++)
 559:       totalArea += Math.abs(((Segment) solids.elementAt(i)).getSignedArea());
 560:     for (int i = 0; i < holes.size(); i++)
 561:       totalArea -= Math.abs(((Segment) holes.elementAt(i)).getSignedArea());
 562:     if (totalArea <= EPSILON)
 563:       return true;
 564: 
 565:     return false;
 566:   }
 567: 
 568:   /**
 569:    * Determines whether the Area consists entirely of line segments
 570:    * @return true if the Area lines-only, false otherwise
 571:    */
 572:   public boolean isPolygonal()
 573:   {
 574:     for (int i = 0; i < holes.size(); i++)
 575:       if (! ((Segment) holes.elementAt(i)).isPolygonal())
 576:     return false;
 577:     for (int i = 0; i < solids.size(); i++)
 578:       if (! ((Segment) solids.elementAt(i)).isPolygonal())
 579:     return false;
 580:     return true;
 581:   }
 582: 
 583:   /**
 584:    * Determines if the Area is rectangular.<P>
 585:    *
 586:    * This is strictly qualified. An area is considered rectangular if:<BR>
 587:    * <li>It consists of a single polygonal path.<BR>
 588:    * <li>It is oriented parallel/perpendicular to the xy axis<BR>
 589:    * <li>It must be exactly rectangular, i.e. small errors induced by
 590:    * transformations may cause a false result, although the area is
 591:    * visibly rectangular.<P>
 592:    * @return true if the above criteria are met, false otherwise
 593:    */
 594:   public boolean isRectangular()
 595:   {
 596:     if (isEmpty())
 597:       return true;
 598: 
 599:     if (holes.size() != 0 || solids.size() != 1)
 600:       return false;
 601: 
 602:     Segment path = (Segment) solids.elementAt(0);
 603:     if (! path.isPolygonal())
 604:       return false;
 605: 
 606:     int nCorners = 0;
 607:     Segment s = path;
 608:     do
 609:       {
 610:     Segment s2 = s.next;
 611:     double d1 = (s.P2.getX() - s.P1.getX())*(s2.P2.getX() - s2.P1.getX())/
 612:         ((s.P1.distance(s.P2)) * (s2.P1.distance(s2.P2)));
 613:     double d2 = (s.P2.getY() - s.P1.getY())*(s2.P2.getY() - s2.P1.getY())/ 
 614:         ((s.P1.distance(s.P2)) * (s2.P1.distance(s2.P2)));
 615:     double dotproduct = d1 + d2;
 616: 
 617:     // For some reason, only rectangles on the XY axis count.
 618:     if (d1 != 0 && d2 != 0)
 619:       return false;
 620: 
 621:     if (Math.abs(dotproduct) == 0) // 90 degree angle
 622:       nCorners++;
 623:     else if ((Math.abs(1.0 - dotproduct) > 0)) // 0 degree angle?
 624:       return false; // if not, return false
 625: 
 626:     s = s.next;
 627:       }
 628:     while (s != path);
 629: 
 630:     return nCorners == 4;
 631:   }
 632: 
 633:   /**
 634:    * Returns whether the Area consists of more than one simple
 635:    * (non self-intersecting) subpath.
 636:    *
 637:    * @return true if the Area consists of none or one simple subpath,
 638:    * false otherwise.
 639:    */
 640:   public boolean isSingular()
 641:   {
 642:     return (holes.size() == 0 && solids.size() <= 1);
 643:   }
 644: 
 645:   /**
 646:    * Returns the bounding box of the Area.<P> Unlike the CubicCurve2D and
 647:    * QuadraticCurve2D classes, this method will return the tightest possible
 648:    * bounding box, evaluating the extreme points of each curved segment.<P>
 649:    * @return the bounding box
 650:    */
 651:   public Rectangle2D getBounds2D()
 652:   {
 653:     if (solids.size() == 0)
 654:       return new Rectangle2D.Double(0.0, 0.0, 0.0, 0.0);
 655: 
 656:     double xmin;
 657:     double xmax;
 658:     double ymin;
 659:     double ymax;
 660:     xmin = xmax = ((Segment) solids.elementAt(0)).P1.getX();
 661:     ymin = ymax = ((Segment) solids.elementAt(0)).P1.getY();
 662: 
 663:     for (int path = 0; path < solids.size(); path++)
 664:       {
 665:     Rectangle2D r = ((Segment) solids.elementAt(path)).getPathBounds();
 666:     xmin = Math.min(r.getMinX(), xmin);
 667:     ymin = Math.min(r.getMinY(), ymin);
 668:     xmax = Math.max(r.getMaxX(), xmax);
 669:     ymax = Math.max(r.getMaxY(), ymax);
 670:       }
 671: 
 672:     return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin)));
 673:   }
 674: 
 675:   /**
 676:    * Returns the bounds of this object in Rectangle format.
 677:    * Please note that this may lead to loss of precision.
 678:    * 
 679:    * @return The bounds.
 680:    * @see #getBounds2D()
 681:    */
 682:   public Rectangle getBounds()
 683:   {
 684:     return getBounds2D().getBounds();
 685:   }
 686: 
 687:   /**
 688:    * Create a new area of the same run-time type with the same contents as
 689:    * this one.
 690:    *
 691:    * @return the clone
 692:    */
 693:   public Object clone()
 694:   {
 695:     try
 696:       {
 697:     Area clone = new Area();
 698:     for (int i = 0; i < solids.size(); i++)
 699:       clone.solids.add(((Segment) solids.elementAt(i)).cloneSegmentList());
 700:     for (int i = 0; i < holes.size(); i++)
 701:       clone.holes.add(((Segment) holes.elementAt(i)).cloneSegmentList());
 702:     return clone;
 703:       }
 704:     catch (CloneNotSupportedException e)
 705:       {
 706:     throw (Error) new InternalError().initCause(e); // Impossible
 707:       }
 708:   }
 709: 
 710:   /**
 711:    * Compares two Areas.
 712:    * 
 713:    * @param area  the area to compare against this area (<code>null</code>
 714:    *              permitted).
 715:    * @return <code>true</code> if the areas are equal, and <code>false</code>
 716:    *         otherwise.
 717:    */
 718:   public boolean equals(Area area)
 719:   {
 720:     if (area == null)
 721:       return false;
 722: 
 723:     if (! getBounds2D().equals(area.getBounds2D()))
 724:       return false;
 725: 
 726:     if (solids.size() != area.solids.size()
 727:         || holes.size() != area.holes.size())
 728:       return false;
 729: 
 730:     Vector pathA = new Vector();
 731:     pathA.addAll(solids);
 732:     pathA.addAll(holes);
 733:     Vector pathB = new Vector();
 734:     pathB.addAll(area.solids);
 735:     pathB.addAll(area.holes);
 736: 
 737:     int nPaths = pathA.size();
 738:     boolean[][] match = new boolean[2][nPaths];
 739: 
 740:     for (int i = 0; i < nPaths; i++)
 741:       {
 742:     for (int j = 0; j < nPaths; j++)
 743:       {
 744:         Segment p1 = (Segment) pathA.elementAt(i);
 745:         Segment p2 = (Segment) pathB.elementAt(j);
 746:         if (! match[0][i] && ! match[1][j])
 747:           if (p1.pathEquals(p2))
 748:         match[0][i] = match[1][j] = true;
 749:       }
 750:       }
 751: 
 752:     boolean result = true;
 753:     for (int i = 0; i < nPaths; i++)
 754:       result = result && match[0][i] && match[1][i];
 755:     return result;
 756:   }
 757: 
 758:   /**
 759:    * Transforms this area by the AffineTransform at.
 760:    * 
 761:    * @param at  the transform.
 762:    */
 763:   public void transform(AffineTransform at)
 764:   {
 765:     for (int i = 0; i < solids.size(); i++)
 766:       ((Segment) solids.elementAt(i)).transformSegmentList(at);
 767:     for (int i = 0; i < holes.size(); i++)
 768:       ((Segment) holes.elementAt(i)).transformSegmentList(at);
 769: 
 770:     // Note that the orientation is not invariant under inversion
 771:     if ((at.getType() & AffineTransform.TYPE_FLIP) != 0)
 772:       {
 773:     setDirection(holes, false);
 774:     setDirection(solids, true);
 775:       }
 776:   }
 777: 
 778:   /**
 779:    * Returns a new Area equal to this one, transformed
 780:    * by the AffineTransform at.
 781:    * @param at  the transform.
 782:    * @return the transformed area
 783:    * @throws NullPointerException if <code>at</code> is <code>null</code>.
 784:    */
 785:   public Area createTransformedArea(AffineTransform at)
 786:   {
 787:     Area a = (Area) clone();
 788:     a.transform(at);
 789:     return a;
 790:   }
 791: 
 792:   /**
 793:    * Determines if the point (x,y) is contained within this Area.
 794:    *
 795:    * @param x the x-coordinate of the point.
 796:    * @param y the y-coordinate of the point.
 797:    * @return true if the point is contained, false otherwise.
 798:    */
 799:   public boolean contains(double x, double y)
 800:   {
 801:     int n = 0;
 802:     for (int i = 0; i < solids.size(); i++)
 803:       if (((Segment) solids.elementAt(i)).contains(x, y))
 804:     n++;
 805: 
 806:     for (int i = 0; i < holes.size(); i++)
 807:       if (((Segment) holes.elementAt(i)).contains(x, y))
 808:     n--;
 809: 
 810:     return (n != 0);
 811:   }
 812: 
 813:   /**
 814:    * Determines if the Point2D p is contained within this Area.
 815:    *
 816:    * @param p the point.
 817:    * @return <code>true</code> if the point is contained, <code>false</code> 
 818:    *         otherwise.
 819:    * @throws NullPointerException if <code>p</code> is <code>null</code>.
 820:    */
 821:   public boolean contains(Point2D p)
 822:   {
 823:     return contains(p.getX(), p.getY());
 824:   }
 825: 
 826:   /**
 827:    * Determines if the rectangle specified by (x,y) as the upper-left
 828:    * and with width w and height h is completely contained within this Area,
 829:    * returns false otherwise.<P>
 830:    *
 831:    * This method should always produce the correct results, unlike for other
 832:    * classes in geom.
 833:    * 
 834:    * @param x the x-coordinate of the rectangle.
 835:    * @param