src/polygon.c

   1 /* $Id$ */
   2
   3 /*
   4  *                            COPYRIGHT
   5  *
   6  *  PCB, interactive printed circuit board design
   7  *  Copyright (C) 1994,1995,1996 Thomas Nau
   8  *
   9  *  This program is free software; you can redistribute it and/or modify
  10  *  it under the terms of the GNU General Public License as published by
  11  *  the Free Software Foundation; either version 2 of the License, or
  12  *  (at your option) any later version.
  13  *
  14  *  This program is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  *  GNU General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU General Public License
  20  *  along with this program; if not, write to the Free Software
  21  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  22  *
  23  *  Contact addresses for paper mail and Email:
  24  *  Thomas Nau, Schlehenweg 15, 88471 Baustetten, Germany
  25  *  Thomas.Nau@rz.uni-ulm.de
  26  *
  27  */
  28
  29
  30 /*
  31
  32 Here's a brief tour of the data and life of a polygon, courtesy of Ben
  33 Jackson:
  34
  35 A PCB PolygonType contains an array of points outlining the polygon.
  36 This is what is manipulated by the UI and stored in the saved PCB.
  37
  38 A PolygonType also contains a POLYAREA called 'Clipped' which is
  39 computed dynamically by InitClip every time a board is loaded.  The
  40 point array is coverted to a POLYAREA by original_poly and then holes
  41 are cut in it by clearPoly.  After that it is maintained dynamically
  42 as parts are added, moved or removed (this is why sometimes bugs can
  43 be fixed by just re-loading the board).
  44
  45 A POLYAREA consists of a linked list of PLINE structures.  The head of
  46 that list is POLYAREA.contours.  The first contour is an outline of a
  47 filled region.  All of the subsequent PLINEs are holes cut out of that
  48 first contour.  POLYAREAs are in a doubly-linked list and each member
  49 of the list is an independent (non-overlapping) area with its own
  50 outline and holes.  The function biggest() finds the largest POLYAREA
  51 so that PolygonType.Clipped points to that shape.  The rest of the
  52 polygon still exists, it's just ignored when turning the polygon into
  53 copper.
  54
  55 The first POLYAREA in PolygonType.Clipped is what is used for the vast
  56 majority of Polygon related tests.  The basic logic for an
  57 intersection is "is the target shape inside POLYAREA.contours and NOT
  58 fully enclosed in any of POLYAREA.contours.next... (the holes)".
  59
  60 The polygon dicer (NoHolesPolygonDicer and r_NoHolesPolygonDicer)
  61 emits a series of "simple" PLINE shapes.  That is, the PLINE isn't
  62 linked to any other "holes" oulines).  That's the meaning of the first
  63 test in r_NoHolesPolygonDicer.  It is testing to see if the PLINE
  64 contour (the first, making it a solid outline) has a valid next
  65 pointer (which would point to one or more holes).  The dicer works by
  66 recursively chopping the polygon in half through the first hole it
  67 sees (which is guaranteed to eliminate at least that one hole).  The
  68 dicer output is used for HIDs which cannot render things with holes
  69 (which would require erasure).
  70
  71 */
  72
  73 /* special polygon editing routines
  74  */
  75
  76 #ifdef HAVE_CONFIG_H
  77 #include "config.h"
  78 #endif
  79
  80 #include <assert.h>
  81 #include <math.h>
  82 #include <memory.h>
  83 #include <setjmp.h>
  84
  85 #include "global.h"
  86 #include "box.h"
  87 #include "create.h"
  88 #include "crosshair.h"
  89 #include "data.h"
  90 #include "draw.h"
  91 #include "error.h"
  92 #include "find.h"
  93 #include "misc.h"
  94 #include "move.h"
  95 #include "polygon.h"
  96 #include "remove.h"
  97 #include "rtree.h"
  98 #include "search.h"
  99 #include "set.h"
 100 #include "thermal.h"
 101 #include "undo.h"
 102
 103 #ifdef HAVE_LIBDMALLOC
 104 #include <dmalloc.h>
 105 #endif
 106
 107 RCSID ("$Id$");
 108
 109 #define ROUND(x) ((long)(((x) >= 0 ? (x) + 0.5  : (x) - 0.5)))
 110
 111 #define UNSUBTRACT_BLOAT 10
 112
 113 /* ---------------------------------------------------------------------------
 114  * local prototypes
 115  */
 116
 117 #define CIRC_SEGS 40
 118 static double circleVerticies[] = {
 119   1.0, 0.0,
 120   0.98768834059513777, 0.15643446504023087,
 121 };
 122
 123 Cardinal
 124 polygon_point_idx (PolygonTypePtr polygon, PointTypePtr point)
 125 {
 126   assert (point >= polygon->Points);
 127   assert (point <= polygon->Points + polygon->PointN);
 128   return ((char *)point - (char *)polygon->Points) / sizeof (PointType);
 129 }
 130
 131 /* Find contour number: 0 for outer, 1 for first hole etc.. */
 132 Cardinal
 133 polygon_point_contour (PolygonTypePtr polygon, Cardinal point)
 134 {
 135   Cardinal i;
 136   Cardinal contour = 0;
 137
 138   for (i = 0; i < polygon->HoleIndexN; i++)
 139     if (point >= polygon->HoleIndex[i])
 140       contour = i + 1;
 141   return contour;
 142 }
 143
 144 Cardinal
 145 next_contour_point (PolygonTypePtr polygon, Cardinal point)
 146 {
 147   Cardinal contour;
 148   Cardinal this_contour_start;
 149   Cardinal next_contour_start;
 150
 151   contour = polygon_point_contour (polygon, point);
 152
 153   this_contour_start = (contour == 0) ? 0 :
 154                                         polygon->HoleIndex[contour - 1];
 155   next_contour_start =
 156     (contour == polygon->HoleIndexN) ? polygon->PointN :
 157                                        polygon->HoleIndex[contour];
 158
 159   /* Wrap back to the start of the contour we're in if we pass the end */
 160   if (++point == next_contour_start)
 161     point = this_contour_start;
 162
 163   return point;
 164 }
 165
 166 Cardinal
 167 prev_contour_point (PolygonTypePtr polygon, Cardinal point)
 168 {
 169   Cardinal contour;
 170   Cardinal prev_contour_end;
 171   Cardinal this_contour_end;
 172
 173   contour = polygon_point_contour (polygon, point);
 174
 175   prev_contour_end = (contour == 0) ? 0 :
 176                                       polygon->HoleIndex[contour - 1];
 177   this_contour_end =
 178     (contour == polygon->HoleIndexN) ? polygon->PointN - 1:
 179                                        polygon->HoleIndex[contour] - 1;
 180
 181   /* Wrap back to the start of the contour we're in if we pass the end */
 182   if (point == prev_contour_end)
 183     point = this_contour_end;
 184   else
 185     point--;
 186
 187   return point;
 188 }
 189
 190 static void
 191 add_noholes_polyarea (PLINE *pline, void *user_data)
 192 {
 193   PolygonType *poly = user_data;
 194
 195   /* Prepend the pline into the NoHoles linked list */
 196   pline->next = poly->NoHoles;
 197   poly->NoHoles = pline;
 198 }
 199
 200 void
 201 ComputeNoHoles (PolygonType *poly)
 202 {
 203   poly_FreeContours (&poly->NoHoles);
 204   if (poly->Clipped)
 205     NoHolesPolygonDicer (poly, NULL, add_noholes_polyarea, poly);
 206   else
 207     printf ("Compute_noholes caught poly->Clipped = NULL\n");
 208   poly->NoHolesValid = 1;
 209 }
 210
 211 static POLYAREA *
 212 biggest (POLYAREA * p)
 213 {
 214   POLYAREA *n, *top = NULL;
 215   PLINE *pl;
 216   double big = -1;
 217   if (!p)
 218     return NULL;
 219   n = p;
 220   do
 221     {
 222 #if 0
 223       if (n->contours->area < PCB->IsleArea)
 224         {
 225           n->b->f = n->f;
 226           n->f->b = n->b;
 227           poly_DelContour (&n->contours);
 228           if (n == p)
 229             p = n->f;
 230           n = n->f;
 231           if (!n->contours)
 232             {
 233               free (n);
 234               return NULL;
 235             }
 236         }
 237 #endif
 238       if (n->contours->area > big)
 239         {
 240           top = n;
 241           big = n->contours->area;
 242         }
 243     }
 244   while ((n = n->f) != p);
 245   assert (top);
 246   if (top == p)
 247     return p;
 248   pl = top->contours;
 249   top->contours = p->contours;
 250   p->contours = pl;
 251   assert (pl);
 252   assert (p->f);
 253   assert (p->b);
 254   return p;
 255 }
 256
 257 POLYAREA *
 258 ContourToPoly (PLINE * contour)
 259 {
 260   POLYAREA *p;
 261   poly_PreContour (contour, TRUE);
 262   assert (contour->Flags.orient == PLF_DIR);
 263   if (!(p = poly_Create ()))
 264     return NULL;
 265   poly_InclContour (p, contour);
 266   assert (poly_Valid (p));
 267   return p;
 268 }
 269
 270 static POLYAREA *
 271 original_poly (PolygonType * p)
 272 {
 273   PLINE *contour = NULL;
 274   POLYAREA *np = NULL;
 275   Cardinal n;
 276   Vector v;
 277   int hole = 0;
 278
 279   if ((np = poly_Create ()) == NULL)
 280     return NULL;
 281
 282   /* first make initial polygon contour */
 283   for (n = 0; n < p->PointN; n++)
 284     {
 285       /* No current contour? Make a new one starting at point */
 286       /*   (or) Add point to existing contour */
 287
 288       v[0] = p->Points[n].X;
 289       v[1] = p->Points[n].Y;
 290       if (contour == NULL)
 291         {
 292           if ((contour = poly_NewContour (v)) == NULL)
 293             return NULL;
 294         }
 295       else
 296         {
 297           poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 298         }
 299
 300       /* Is current point last in contour? If so process it. */
 301       if (n == p->PointN - 1 ||
 302           (hole < p->HoleIndexN && n == p->HoleIndex[hole] - 1))
 303         {
 304           poly_PreContour (contour, TRUE);
 305
 306           /* make sure it is a positive contour (outer) or negative (hole) */
 307           if (contour->Flags.orient != (hole ? PLF_INV : PLF_DIR))
 308             poly_InvContour (contour);
 309           assert (contour->Flags.orient == (hole ? PLF_INV : PLF_DIR));
 310
 311           poly_InclContour (np, contour);
 312           contour = NULL;
 313           assert (poly_Valid (np));
 314
 315           hole++;
 316         }
 317   }
 318   return biggest (np);
 319 }
 320
 321 POLYAREA *
 322 PolygonToPoly (PolygonType *p)
 323 {
 324   return original_poly (p);
 325 }
 326
 327 POLYAREA *
 328 RectPoly (LocationType x1, LocationType x2, LocationType y1, LocationType y2)
 329 {
 330   PLINE *contour = NULL;
 331   Vector v;
 332
 333   assert (x2 > x1);
 334   assert (y2 > y1);
 335   v[0] = x1;
 336   v[1] = y1;
 337   if ((contour = poly_NewContour (v)) == NULL)
 338     return NULL;
 339   v[0] = x2;
 340   v[1] = y1;
 341   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 342   v[0] = x2;
 343   v[1] = y2;
 344   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 345   v[0] = x1;
 346   v[1] = y2;
 347   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 348   return ContourToPoly (contour);
 349 }
 350
 351 POLYAREA *
 352 OctagonPoly (LocationType x, LocationType y, BDimension radius)
 353 {
 354   PLINE *contour = NULL;
 355   Vector v;
 356
 357   v[0] = x + ROUND (radius * 0.5);
 358   v[1] = y + ROUND (radius * TAN_22_5_DEGREE_2);
 359   if ((contour = poly_NewContour (v)) == NULL)
 360     return NULL;
 361   v[0] = x + ROUND (radius * TAN_22_5_DEGREE_2);
 362   v[1] = y + ROUND (radius * 0.5);
 363   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 364   v[0] = x - (v[0] - x);
 365   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 366   v[0] = x - ROUND (radius * 0.5);
 367   v[1] = y + ROUND (radius * TAN_22_5_DEGREE_2);
 368   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 369   v[1] = y - (v[1] - y);
 370   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 371   v[0] = x - ROUND (radius * TAN_22_5_DEGREE_2);
 372   v[1] = y - ROUND (radius * 0.5);
 373   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 374   v[0] = x - (v[0] - x);
 375   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 376   v[0] = x + ROUND (radius * 0.5);
 377   v[1] = y - ROUND (radius * TAN_22_5_DEGREE_2);
 378   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 379   return ContourToPoly (contour);
 380 }
 381
 382 /* add verticies in a fractional-circle starting from v
 383  * centered at X, Y and going counter-clockwise
 384  * does not include the first point
 385  * last argument is 1 for a full circle
 386  * 2 for a half circle
 387  * or 4 for a quarter circle
 388  */
 389 void
 390 frac_circle (PLINE * c, LocationType X, LocationType Y, Vector v, int range)
 391 {
 392   double e1, e2, t1;
 393   int i;
 394
 395   poly_InclVertex (c->head.prev, poly_CreateNode (v));
 396   /* move vector to origin */
 397   e1 = v[0] - X;
 398   e2 = v[1] - Y;
 399
 400   /* NB: the caller adds the last vertex, hence the -1 */
 401   range = CIRC_SEGS / range - 1;
 402   for (i = 0; i < range; i++)
 403     {
 404       /* rotate the vector */
 405       t1 = e1 * circleVerticies[2] - e2 * circleVerticies[3];
 406       e2 = e1 * circleVerticies[3] + e2 * circleVerticies[2];
 407       e1 = t1;
 408       v[0] = X + ROUND (e1);
 409       v[1] = Y + ROUND (e2);
 410       poly_InclVertex (c->head.prev, poly_CreateNode (v));
 411     }
 412 }
 413
 414 /* create a circle approximation from lines */
 415 POLYAREA *
 416 CirclePoly (LocationType x, LocationType y, BDimension radius)
 417 {
 418   PLINE *contour;
 419   Vector v;
 420
 421   if (radius <= 0)
 422     return NULL;
 423   v[0] = x + radius;
 424   v[1] = y;
 425   if ((contour = poly_NewContour (v)) == NULL)
 426     return NULL;
 427   frac_circle (contour, x, y, v, 1);
 428   contour->is_round = TRUE;
 429   contour->cx = x;
 430   contour->cy = y;
 431   contour->radius = radius;
 432   return ContourToPoly (contour);
 433 }
 434
 435 /* make a rounded-corner rectangle with radius t beyond x1,x2,y1,y2 rectangle */
 436 POLYAREA *
 437 RoundRect (LocationType x1, LocationType x2, LocationType y1, LocationType y2,
 438            BDimension t)
 439 {
 440   PLINE *contour = NULL;
 441   Vector v;
 442
 443   assert (x2 > x1);
 444   assert (y2 > y1);
 445   v[0] = x1 - t;
 446   v[1] = y1;
 447   if ((contour = poly_NewContour (v)) == NULL)
 448     return NULL;
 449   frac_circle (contour, x1, y1, v, 4);
 450   v[0] = x2;
 451   v[1] = y1 - t;
 452   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 453   frac_circle (contour, x2, y1, v, 4);
 454   v[0] = x2 + t;
 455   v[1] = y2;
 456   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 457   frac_circle (contour, x2, y2, v, 4);
 458   v[0] = x1;
 459   v[1] = y2 + t;
 460   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 461   frac_circle (contour, x1, y2, v, 4);
 462   return ContourToPoly (contour);
 463 }
 464
 465 #define ARC_ANGLE 5
 466 static POLYAREA *
 467 ArcPolyNoIntersect (ArcType * a, BDimension thick)
 468 {
 469   PLINE *contour = NULL;
 470   POLYAREA *np = NULL;
 471   Vector v;
 472   BoxType *ends;
 473   int i, segs;
 474   double ang, da, rx, ry;
 475   long half;
 476
 477   if (thick <= 0)
 478     return NULL;
 479   if (a->Delta < 0)
 480     {
 481       a->StartAngle += a->Delta;
 482       a->Delta = -a->Delta;
 483     }
 484   half = (thick + 1) / 2;
 485   ends = GetArcEnds (a);
 486   /* start with inner radius */
 487   rx = MAX (a->Width - half, 0);
 488   ry = MAX (a->Height - half, 0);
 489   segs = a->Delta / ARC_ANGLE;
 490   ang = a->StartAngle;
 491   da = (1.0 * a->Delta) / segs;
 492   v[0] = a->X - rx * cos (ang * M180);
 493   v[1] = a->Y + ry * sin (ang * M180);
 494   if ((contour = poly_NewContour (v)) == NULL)
 495     return 0;
 496   for (i = 0; i < segs - 1; i++)
 497     {
 498       ang += da;
 499       v[0] = a->X - rx * cos (ang * M180);
 500       v[1] = a->Y + ry * sin (ang * M180);
 501       poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 502     }
 503   /* find last point */
 504   ang = a->StartAngle + a->Delta;
 505   v[0] = a->X - rx * cos (ang * M180);
 506   v[1] = a->Y + ry * sin (ang * M180);
 507   /* add the round cap at the end */
 508   frac_circle (contour, ends->X2, ends->Y2, v, 2);
 509   /* and now do the outer arc (going backwards) */
 510   rx = a->Width + half;
 511   ry = a->Width + half;
 512   da = -da;
 513   for (i = 0; i < segs; i++)
 514     {
 515       v[0] = a->X - rx * cos (ang * M180);
 516       v[1] = a->Y + ry * sin (ang * M180);
 517       poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 518       ang += da;
 519     }
 520   /* now add other round cap */
 521   ang = a->StartAngle;
 522   v[0] = a->X - rx * cos (ang * M180);
 523   v[1] = a->Y + ry * sin (ang * M180);
 524   frac_circle (contour, ends->X1, ends->Y1, v, 2);
 525   /* now we have the whole contour */
 526   if (!(np = ContourToPoly (contour)))
 527     return NULL;
 528   return np;
 529 }
 530
 531 #define MIN_CLEARANCE_BEFORE_BISECT 10.
 532 POLYAREA *
 533 ArcPoly (ArcType * a, BDimension thick)
 534 {
 535   double delta;
 536   ArcType seg1, seg2;
 537   POLYAREA *tmp1, *tmp2, *res;
 538
 539   delta = (a->Delta < 0) ? -a->Delta : a->Delta;
 540
 541   /* If the arc segment would self-intersect, we need to construct it as the union of
 542      two non-intersecting segments */
 543
 544   if (2 * M_PI * a->Width * (1. - (double)delta / 360.) - thick < MIN_CLEARANCE_BEFORE_BISECT)
 545     {
 546       int half_delta = a->Delta / 2;
 547
 548       seg1 = seg2 = *a;
 549       seg1.Delta = half_delta;
 550       seg2.Delta -= half_delta;
 551       seg2.StartAngle += half_delta;
 552
 553       tmp1 = ArcPolyNoIntersect (&seg1, thick);
 554       tmp2 = ArcPolyNoIntersect (&seg2, thick);
 555       poly_Boolean_free (tmp1, tmp2, &res, PBO_UNITE);
 556       return res;
 557     }
 558
 559   return ArcPolyNoIntersect (a, thick);
 560 }
 561
 562 POLYAREA *
 563 LinePoly (LineType * L, BDimension thick)
 564 {
 565   PLINE *contour = NULL;
 566   POLYAREA *np = NULL;
 567   Vector v;
 568   double d, dx, dy;
 569   long half;LineType _l=*L,*l=&_l;
 570
 571   if (thick <= 0)
 572     return NULL;
 573   half = (thick + 1) / 2;
 574   d =
 575     sqrt (SQUARE (l->Point1.X - l->Point2.X) +
 576           SQUARE (l->Point1.Y - l->Point2.Y));
 577   if (!TEST_FLAG (SQUAREFLAG,l))
 578     if (d == 0)                   /* line is a point */
 579       return CirclePoly (l->Point1.X, l->Point1.Y, half);
 580   if (d != 0)
 581     {
 582       d = half / d;
 583       dx = (l->Point1.Y - l->Point2.Y) * d;
 584       dy = (l->Point2.X - l->Point1.X) * d;
 585     }
 586   else
 587     {
 588       dx = half;
 589       dy = 0;
 590     }
 591   if (TEST_FLAG (SQUAREFLAG,l))/* take into account the ends */
 592     {
 593       l->Point1.X -= dy;
 594       l->Point1.Y += dx;
 595       l->Point2.X += dy;
 596       l->Point2.Y -= dx;
 597     }
 598   v[0] = l->Point1.X - dx;
 599   v[1] = l->Point1.Y - dy;
 600   if ((contour = poly_NewContour (v)) == NULL)
 601     return 0;
 602   v[0] = l->Point2.X - dx;
 603   v[1] = l->Point2.Y - dy;
 604   if (TEST_FLAG (SQUAREFLAG,l))
 605     poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 606   else
 607     frac_circle (contour, l->Point2.X, l->Point2.Y, v, 2);
 608   v[0] = l->Point2.X + dx;
 609   v[1] = l->Point2.Y + dy;
 610   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 611   v[0] = l->Point1.X + dx;
 612   v[1] = l->Point1.Y + dy;
 613   if (TEST_FLAG (SQUAREFLAG,l))
 614     poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 615   else
 616     frac_circle (contour, l->Point1.X, l->Point1.Y, v, 2);
 617   /* now we have the line contour */
 618   if (!(np = ContourToPoly (contour)))
 619     return NULL;
 620   return np;
 621 }
 622
 623 /* make a rounded-corner rectangle */
 624 POLYAREA *
 625 SquarePadPoly (PadType * pad, BDimension clear)
 626 {
 627   PLINE *contour = NULL;
 628   POLYAREA *np = NULL;
 629   Vector v;
 630   double d;
 631   double tx, ty;
 632   double cx, cy;
 633   PadType _t=*pad,*t=&_t;
 634   PadType _c=*pad,*c=&_c;
 635   int halfthick = (pad->Thickness + 1) / 2;
 636   int halfclear = (clear + 1) / 2;
 637
 638   d =
 639     sqrt (SQUARE (pad->Point1.X - pad->Point2.X) +
 640           SQUARE (pad->Point1.Y - pad->Point2.Y));
 641   if (d != 0)
 642     {
 643       double a = halfthick / d;
 644       tx = (t->Point1.Y - t->Point2.Y) * a;
 645       ty = (t->Point2.X - t->Point1.X) * a;
 646       a = halfclear / d;
 647       cx = (c->Point1.Y - c->Point2.Y) * a;
 648       cy = (c->Point2.X - c->Point1.X) * a;
 649
 650       t->Point1.X -= ty;
 651       t->Point1.Y += tx;
 652       t->Point2.X += ty;
 653       t->Point2.Y -= tx;
 654       c->Point1.X -= cy;
 655       c->Point1.Y += cx;
 656       c->Point2.X += cy;
 657       c->Point2.Y -= cx;
 658     }
 659   else
 660     {
 661       tx = halfthick;
 662       ty = 0;
 663       cx = halfclear;
 664       cy = 0;
 665
 666       t->Point1.Y += tx;
 667       t->Point2.Y -= tx;
 668       c->Point1.Y += cx;
 669       c->Point2.Y -= cx;
 670     }
 671
 672   v[0] = c->Point1.X - tx;
 673   v[1] = c->Point1.Y - ty;
 674   if ((contour = poly_NewContour (v)) == NULL)
 675     return 0;
 676   frac_circle (contour, (t->Point1.X - tx), (t->Point1.Y - ty), v, 4);
 677
 678   v[0] = t->Point2.X - cx;
 679   v[1] = t->Point2.Y - cy;
 680   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 681   frac_circle (contour, (t->Point2.X - tx), (t->Point2.Y - ty), v, 4);
 682
 683   v[0] = c->Point2.X + tx;
 684   v[1] = c->Point2.Y + ty;
 685   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 686   frac_circle (contour, (t->Point2.X + tx), (t->Point2.Y + ty), v, 4);
 687
 688   v[0] = t->Point1.X + cx;
 689   v[1] = t->Point1.Y + cy;
 690   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 691   frac_circle (contour, (t->Point1.X + tx), (t->Point1.Y + ty), v, 4);
 692
 693   /* now we have the line contour */
 694   if (!(np = ContourToPoly (contour)))
 695     return NULL;
 696   return np;
 697 }
 698
 699 /* clear np1 from the polygon */
 700 static int
 701 Subtract (POLYAREA * np1, PolygonType * p, bool fnp)
 702 {
 703   POLYAREA *merged = NULL, *np = np1;
 704   int x;
 705   assert (np);
 706   assert (p);
 707   if (!p->Clipped)
 708     {
 709       if (fnp)
 710         poly_Free (&np);
 711       return 1;
 712     }
 713   assert (poly_Valid (p->Clipped));
 714   assert (poly_Valid (np));
 715   if (fnp)
 716     x = poly_Boolean_free (p->Clipped, np, &merged, PBO_SUB);
 717   else
 718     {
 719       x = poly_Boolean (p->Clipped, np, &merged, PBO_SUB);
 720       poly_Free (&p->Clipped);
 721     }
 722   assert (!merged || poly_Valid (merged));
 723   if (x != err_ok)
 724     {
 725       fprintf (stderr, "Error while clipping PBO_SUB: %d\n", x);
 726       poly_Free (&merged);
 727       p->Clipped = NULL;
 728       if (p->NoHoles) printf ("Just leaked in Subtract\n");
 729       p->NoHoles = NULL;
 730       return -1;
 731     }
 732   p->Clipped = biggest (merged);
 733   assert (!p->Clipped || poly_Valid (p->Clipped));
 734   if (!p->Clipped)
 735     Message ("Polygon cleared out of existence near (%d, %d)\n",
 736              (p->BoundingBox.X1 + p->BoundingBox.X2) / 2,
 737              (p->BoundingBox.Y1 + p->BoundingBox.Y2) / 2);
 738   return 1;
 739 }
 740
 741 /* create a polygon of the pin clearance */
 742 POLYAREA *
 743 PinPoly (PinType * pin, BDimension thick, BDimension clear)
 744 {
 745   int size;
 746
 747   if (TEST_FLAG (SQUAREFLAG, pin))
 748     {
 749       size = (thick + 1) / 2;
 750       return RoundRect (pin->X - size, pin->X + size, pin->Y - size,
 751                         pin->Y + size, (clear + 1) / 2);
 752     }
 753   else
 754     {
 755       size = (thick + clear + 1) / 2;
 756       if (TEST_FLAG (OCTAGONFLAG, pin))
 757         {
 758           return OctagonPoly (pin->X, pin->Y, size + size);
 759         }
 760     }
 761   return CirclePoly (pin->X, pin->Y, size);
 762 }
 763
 764 POLYAREA *
 765 BoxPolyBloated (BoxType *box, BDimension bloat)
 766 {
 767   return RectPoly (box->X1 - bloat, box->X2 + bloat,
 768                    box->Y1 - bloat, box->Y2 + bloat);
 769 }
 770
 771 /* remove the pin clearance from the polygon */
 772 static int
 773 SubtractPin (DataType * d, PinType * pin, LayerType * l, PolygonType * p)
 774 {
 775   POLYAREA *np;
 776   Cardinal i;
 777
 778   if (pin->Clearance == 0)
 779     return 0;
 780   i = GetLayerNumber (d, l);
 781   if (TEST_THERM (i, pin))
 782     {
 783       np = ThermPoly ((PCBTypePtr) (d->pcb), pin, i);
 784       if (!np)
 785         return 0;
 786     }
 787   else
 788     {
 789       np = PinPoly (pin, pin->Thickness, pin->Clearance);
 790       if (!np)
 791         return -1;
 792     }
 793   return Subtract (np, p, TRUE);
 794 }
 795
 796 static int
 797 SubtractLine (LineType * line, PolygonType * p)
 798 {
 799   POLYAREA *np;
 800
 801   if (!TEST_FLAG (CLEARLINEFLAG, line))
 802     return 0;
 803   if (!(np = LinePoly (line, line->Thickness + line->Clearance)))
 804     return -1;
 805   return Subtract (np, p, true);
 806 }
 807
 808 static int
 809 SubtractArc (ArcType * arc, PolygonType * p)
 810 {
 811   POLYAREA *np;
 812
 813   if (!TEST_FLAG (CLEARLINEFLAG, arc))
 814     return 0;
 815   if (!(np = ArcPoly (arc, arc->Thickness + arc->Clearance)))
 816     return -1;
 817   return Subtract (np, p, true);
 818 }
 819
 820 static int
 821 SubtractText (TextType * text, PolygonType * p)
 822 {
 823   POLYAREA *np;
 824   const BoxType *b = &text->BoundingBox;
 825
 826   if (!TEST_FLAG (CLEARLINEFLAG, text))
 827     return 0;
 828   if (!(np = RoundRect (b->X1 + PCB->Bloat, b->X2 - PCB->Bloat,
 829                         b->Y1 + PCB->Bloat, b->Y2 - PCB->Bloat, PCB->Bloat)))
 830     return -1;
 831   return Subtract (np, p, true);
 832 }
 833
 834 static int
 835 SubtractPad (PadType * pad, PolygonType * p)
 836 {
 837   POLYAREA *np = NULL;
 838
 839   if (pad->Clearance == 0)
 840     return 0;
 841   if (TEST_FLAG (SQUAREFLAG, pad))
 842     {
 843       if (!
 844           (np = SquarePadPoly (pad, pad->Thickness + pad->Clearance)))
 845         return -1;
 846     }
 847   else
 848     {
 849       if (!
 850           (np = LinePoly ((LineType *) pad, pad->Thickness + pad->Clearance)))
 851         return -1;
 852     }
 853   return Subtract (np, p, true);
 854 }
 855
 856 struct cpInfo
 857 {
 858   const BoxType *other;
 859   DataType *data;
 860   LayerType *layer;
 861   PolygonType *polygon;
 862   bool solder;
 863   jmp_buf env;
 864 };
 865
 866 static int
 867 pin_sub_callback (const BoxType * b, void *cl)
 868 {
 869   PinTypePtr pin = (PinTypePtr) b;
 870   struct cpInfo *info = (struct cpInfo *) cl;
 871   PolygonTypePtr polygon;
 872
 873   /* don't subtract the object that was put back! */
 874   if (b == info->other)
 875     return 0;
 876   polygon = info->polygon;
 877   if (SubtractPin (info->data, pin, info->layer, polygon) < 0)
 878     longjmp (info->env, 1);
 879   return 1;
 880 }
 881
 882 static int
 883 arc_sub_callback (const BoxType * b, void *cl)
 884 {
 885   ArcTypePtr arc = (ArcTypePtr) b;
 886   struct cpInfo *info = (struct cpInfo *) cl;
 887   PolygonTypePtr polygon;
 888
 889   /* don't subtract the object that was put back! */
 890   if (b == info->other)
 891     return 0;
 892   if (!TEST_FLAG (CLEARLINEFLAG, arc))
 893     return 0;
 894   polygon = info->polygon;
 895   if (SubtractArc (arc, polygon) < 0)
 896     longjmp (info->env, 1);
 897   return 1;
 898 }
 899
 900 static int
 901 pad_sub_callback (const BoxType * b, void *cl)
 902 {
 903   PadTypePtr pad = (PadTypePtr) b;
 904   struct cpInfo *info = (struct cpInfo *) cl;
 905   PolygonTypePtr polygon;
 906
 907   /* don't subtract the object that was put back! */
 908   if (b == info->other)
 909     return 0;
 910   if (pad->Clearance == 0)
 911     return 0;
 912   polygon = info->polygon;
 913   if (XOR (TEST_FLAG (ONSOLDERFLAG, pad), !info->solder))
 914     {
 915       if (SubtractPad (pad, polygon) < 0)
 916         longjmp (info->env, 1);
 917       return 1;
 918     }
 919   return 0;
 920 }
 921
 922 static int
 923 line_sub_callback (const BoxType * b, void *cl)
 924 {
 925   LineTypePtr line = (LineTypePtr) b;
 926   struct cpInfo *info = (struct cpInfo *) cl;
 927   PolygonTypePtr polygon;
 928
 929   /* don't subtract the object that was put back! */
 930   if (b == info->other)
 931     return 0;
 932   if (!TEST_FLAG (CLEARLINEFLAG, line))
 933     return 0;
 934   polygon = info->polygon;
 935   if (SubtractLine (line, polygon) < 0)
 936     longjmp (info->env, 1);
 937   return 1;
 938 }
 939
 940 static int
 941 text_sub_callback (const BoxType * b, void *cl)
 942 {
 943   TextTypePtr text = (TextTypePtr) b;
 944   struct cpInfo *info = (struct cpInfo *) cl;
 945   PolygonTypePtr polygon;
 946
 947   /* don't subtract the object that was put back! */
 948   if (b == info->other)
 949     return 0;
 950   if (!TEST_FLAG (CLEARLINEFLAG, text))
 951     return 0;
 952   polygon = info->polygon;
 953   if (SubtractText (text, polygon) < 0)
 954     longjmp (info->env, 1);
 955   return 1;
 956 }
 957
 958 static int
 959 Group (DataTypePtr Data, Cardinal layer)
 960 {
 961   Cardinal i, j;
 962   for (i = 0; i < max_layer; i++)
 963     for (j = 0; j < ((PCBType *) (Data->pcb))->LayerGroups.Number[i]; j++)
 964       if (layer == ((PCBType *) (Data->pcb))->LayerGroups.Entries[i][j])
 965         return i;
 966   return i;
 967 }
 968
 969 static int
 970 clearPoly (DataTypePtr Data, LayerTypePtr Layer, PolygonType * polygon,
 971            const BoxType * here, BDimension expand)
 972 {
 973   int r = 0;
 974   BoxType region;
 975   struct cpInfo info;
 976   Cardinal group;
 977
 978   if (!TEST_FLAG (CLEARPOLYFLAG, polygon)
 979       || GetLayerNumber (Data, Layer) >= max_layer)
 980     return 0;
 981   group = Group (Data, GetLayerNumber (Data, Layer));
 982   info.solder = (group == Group (Data, max_layer + SOLDER_LAYER));
 983   info.data = Data;
 984   info.other = here;
 985   info.layer = Layer;
 986   info.polygon = polygon;
 987   if (here)
 988     region = clip_box (here, &polygon->BoundingBox);
 989   else
 990     region = polygon->BoundingBox;
 991   region = bloat_box (&region, expand);
 992
 993   if (setjmp (info.env) == 0)
 994     {
 995       r = r_search (Data->via_tree, &region, NULL, pin_sub_callback, &info);
 996       r += r_search (Data->pin_tree, &region, NULL, pin_sub_callback, &info);
 997       GROUP_LOOP (Data, group);
 998       {
 999         r +=
1000           r_search (layer->line_tree, &region, NULL, line_sub_callback,
1001                     &info);
1002         r +=
1003           r_search (layer->arc_tree, &region, NULL, arc_sub_callback, &info);
1004         r +=
1005           r_search (layer->text_tree, &region, NULL, text_sub_callback, &info);
1006       }
1007       END_LOOP;
1008       if (info.solder || group == Group (Data, max_layer + COMPONENT_LAYER))
1009         r += r_search (Data->pad_tree, &region, NULL, pad_sub_callback, &info);
1010     }
1011   polygon->NoHolesValid = 0;
1012   return r;
1013 }
1014
1015 static int
1016 Unsubtract (POLYAREA * np1, PolygonType * p)
1017 {
1018   POLYAREA *merged = NULL, *np = np1;
1019   POLYAREA *orig_poly, *clipped_np;
1020   int x;
1021   assert (np);
1022   assert (p && p->Clipped);
1023
1024   orig_poly = original_poly (p);
1025
1026   x = poly_Boolean_free (np, orig_poly, &clipped_np, PBO_ISECT);
1027   if (x != err_ok)
1028     {
1029       fprintf (stderr, "Error while clipping PBO_ISECT: %d\n", x);
1030       poly_Free (&clipped_np);
1031       goto fail;
1032     }
1033
1034   x = poly_Boolean_free (p->Clipped, clipped_np, &merged, PBO_UNITE);
1035   if (x != err_ok)
1036     {
1037       fprintf (stderr, "Error while clipping PBO_UNITE: %d\n", x);
1038       poly_Free (&merged);
1039       goto fail;
1040     }
1041   p->Clipped = biggest (merged);
1042   assert (!p->Clipped || poly_Valid (p->Clipped));
1043   return 1;
1044
1045 fail:
1046   p->Clipped = NULL;
1047   if (p->NoHoles) printf ("Just leaked in Unsubtract\n");
1048   p->NoHoles = NULL;
1049   return 0;
1050 }
1051
1052 static int
1053 UnsubtractPin (PinType * pin, LayerType * l, PolygonType * p)
1054 {
1055   POLYAREA *np;
1056
1057   /* overlap a bit to prevent gaps from rounding errors */
1058   np = BoxPolyBloated (&pin->BoundingBox, UNSUBTRACT_BLOAT);
1059
1060   if (!np)
1061     return 0;
1062   if (!Unsubtract (np, p))
1063     return 0;
1064   clearPoly (PCB->Data, l, p, (const BoxType *) pin, 2 * UNSUBTRACT_BLOAT);
1065   return 1;
1066 }
1067
1068 static int
1069 UnsubtractArc (ArcType * arc, LayerType * l, PolygonType * p)
1070 {
1071   POLYAREA *np;
1072
1073   if (!TEST_FLAG (CLEARLINEFLAG, arc))
1074     return 0;
1075
1076   /* overlap a bit to prevent gaps from rounding errors */
1077   np = BoxPolyBloated (&arc->BoundingBox, UNSUBTRACT_BLOAT);
1078
1079   if (!np)
1080     return 0;
1081   if (!Unsubtract (np, p))
1082     return 0;
1083   clearPoly (PCB->Data, l, p, (const BoxType *) arc, 2 * UNSUBTRACT_BLOAT);
1084   return 1;
1085 }
1086
1087 static int
1088 UnsubtractLine (LineType * line, LayerType * l, PolygonType * p)
1089 {
1090   POLYAREA *np;
1091
1092   if (!TEST_FLAG (CLEARLINEFLAG, line))
1093     return 0;
1094
1095   /* overlap a bit to prevent notches from rounding errors */
1096   np = BoxPolyBloated (&line->BoundingBox, UNSUBTRACT_BLOAT);
1097
1098   if (!np)
1099     return 0;
1100   if (!Unsubtract (np, p))
1101     return 0;
1102   clearPoly (PCB->Data, l, p, (const BoxType *) line, 2 * UNSUBTRACT_BLOAT);
1103   return 1;
1104 }
1105
1106 static int
1107 UnsubtractText (TextType * text, LayerType * l, PolygonType * p)
1108 {
1109   POLYAREA *np;
1110
1111   if (!TEST_FLAG (CLEARLINEFLAG, text))
1112     return 0;
1113
1114   /* overlap a bit to prevent notches from rounding errors */
1115   np = BoxPolyBloated (&text->BoundingBox, UNSUBTRACT_BLOAT);
1116
1117   if (!np)
1118     return -1;
1119   if (!Unsubtract (np, p))
1120     return 0;
1121   clearPoly (PCB->Data, l, p, (const BoxType *) text, 2 * UNSUBTRACT_BLOAT);
1122   return 1;
1123 }
1124
1125 static int
1126 UnsubtractPad (PadType * pad, LayerType * l, PolygonType * p)
1127 {
1128   POLYAREA *np;
1129
1130   /* overlap a bit to prevent notches from rounding errors */
1131   np = BoxPolyBloated (&pad->BoundingBox, UNSUBTRACT_BLOAT);
1132
1133   if (!np)
1134     return 0;
1135   if (!Unsubtract (np, p))
1136     return 0;
1137   clearPoly (PCB->Data, l, p, (const BoxType *) pad, 2 * UNSUBTRACT_BLOAT);
1138   return 1;
1139 }
1140
1141 static bool inhibit = false;
1142
1143 int
1144 InitClip (DataTypePtr Data, LayerTypePtr layer, PolygonType * p)
1145 {
1146   if (inhibit)
1147     return 0;
1148   if (p->Clipped)
1149     poly_Free (&p->Clipped);
1150   p->Clipped = original_poly (p);
1151   poly_FreeContours (&p->NoHoles);
1152   if (!p->Clipped)
1153     return 0;
1154   assert (poly_Valid (p->Clipped));
1155   if (TEST_FLAG (CLEARPOLYFLAG, p))
1156     clearPoly (Data, layer, p, NULL, 0);
1157   else
1158     p->NoHolesValid = 0;
1159   return 1;
1160 }
1161
1162 /* --------------------------------------------------------------------------
1163  * remove redundant polygon points. Any point that lies on the straight
1164  * line between the points on either side of it is redundant.
1165  * returns true if any points are removed
1166  */
1167 bool
1168 RemoveExcessPolygonPoints (LayerTypePtr Layer, PolygonTypePtr Polygon)
1169 {
1170   PointTypePtr p;
1171   Cardinal n, prev, next;
1172   LineType line;
1173   bool changed = false;
1174
1175   if (Undoing ())
1176     return (false);
1177
1178   for (n = 0; n < Polygon->PointN; n++)
1179     {
1180       prev = prev_contour_point (Polygon, n);
1181       next = next_contour_point (Polygon, n);
1182       p = &Polygon->Points[n];
1183
1184       line.Point1 = Polygon->Points[prev];
1185       line.Point2 = Polygon->Points[next];
1186       line.Thickness = 0;
1187       if (IsPointOnLine ((float) p->X, (float) p->Y, 0.0, &line))
1188         {
1189           RemoveObject (POLYGONPOINT_TYPE, Layer, Polygon, p);
1190           changed = true;
1191         }
1192     }
1193   return (changed);
1194 }
1195
1196 /* ---------------------------------------------------------------------------
1197  * returns the index of the polygon point which is the end
1198  * point of the segment with the lowest distance to the passed
1199  * coordinates
1200  */
1201 Cardinal
1202 GetLowestDistancePolygonPoint (PolygonTypePtr Polygon, LocationType X,
1203                                LocationType Y)
1204 {
1205   double mindistance = (double) MAX_COORD * MAX_COORD;
1206   PointTypePtr ptr1, ptr2;
1207   Cardinal n, result = 0;
1208
1209   /* we calculate the distance to each segment and choose the
1210    * shortest distance. If the closest approach between the
1211    * given point and the projected line (i.e. the segment extended)
1212    * is not on the segment, then the distance is the distance
1213    * to the segment end point.
1214    */
1215
1216   for (n = 0; n < Polygon->PointN; n++)
1217     {
1218       register double u, dx, dy;
1219       ptr1 = &Polygon->Points[prev_contour_point (Polygon, n)];
1220       ptr2 = &Polygon->Points[n];
1221
1222       dx = ptr2->X - ptr1->X;
1223       dy = ptr2->Y - ptr1->Y;
1224       if (dx != 0.0 || dy != 0.0)
1225         {
1226           /* projected intersection is at P1 + u(P2 - P1) */
1227           u = ((X - ptr1->X) * dx + (Y - ptr1->Y) * dy) / (dx * dx + dy * dy);
1228
1229           if (u < 0.0)
1230             {                   /* ptr1 is closest point */
1231               u = SQUARE (X - ptr1->X) + SQUARE (Y - ptr1->Y);
1232             }
1233           else if (u > 1.0)
1234             {                   /* ptr2 is closest point */
1235               u = SQUARE (X - ptr2->X) + SQUARE (Y - ptr2->Y);
1236             }
1237           else
1238             {                   /* projected intersection is closest point */
1239               u = SQUARE (X - ptr1->X * (1.0 - u) - u * ptr2->X) +
1240                 SQUARE (Y - ptr1->Y * (1.0 - u) - u * ptr2->Y);
1241             }
1242           if (u < mindistance)
1243             {
1244               mindistance = u;
1245               result = n;
1246             }
1247         }
1248     }
1249   return (result);
1250 }
1251
1252 /* ---------------------------------------------------------------------------
1253  * go back to the  previous point of the polygon
1254  */
1255 void
1256 GoToPreviousPoint (void)
1257 {
1258   switch (Crosshair.AttachedPolygon.PointN)
1259     {
1260       /* do nothing if mode has just been entered */
1261     case 0:
1262       break;
1263
1264       /* reset number of points and 'LINE_MODE' state */
1265     case 1:
1266       Crosshair.AttachedPolygon.PointN = 0;
1267       Crosshair.AttachedLine.State = STATE_FIRST;
1268       addedLines = 0;
1269       break;
1270
1271       /* back-up one point */
1272     default:
1273       {
1274         PointTypePtr points = Crosshair.AttachedPolygon.Points;
1275         Cardinal n = Crosshair.AttachedPolygon.PointN - 2;
1276
1277         Crosshair.AttachedPolygon.PointN--;
1278         Crosshair.AttachedLine.Point1.X = points[n].X;
1279         Crosshair.AttachedLine.Point1.Y = points[n].Y;
1280         break;
1281       }
1282     }
1283 }
1284
1285 /* ---------------------------------------------------------------------------
1286  * close polygon if possible
1287  */
1288 void
1289 ClosePolygon (void)
1290 {
1291   Cardinal n = Crosshair.AttachedPolygon.PointN;
1292
1293   /* check number of points */
1294   if (n >= 3)
1295     {
1296       /* if 45 degree lines are what we want do a quick check
1297        * if closing the polygon makes sense
1298        */
1299       if (!TEST_FLAG (ALLDIRECTIONFLAG, PCB))
1300         {
1301           BDimension dx, dy;
1302
1303           dx = abs (Crosshair.AttachedPolygon.Points[n - 1].X -
1304                     Crosshair.AttachedPolygon.Points[0].X);
1305           dy = abs (Crosshair.AttachedPolygon.Points[n - 1].Y -
1306                     Crosshair.AttachedPolygon.Points[0].Y);
1307           if (!(dx == 0 || dy == 0 || dx == dy))
1308             {
1309               Message
1310                 (_
1311                  ("Cannot close polygon because 45 degree lines are requested.\n"));
1312               return;
1313             }
1314         }
1315       CopyAttachedPolygonToLayer ();
1316       Draw ();
1317     }
1318   else
1319     Message (_("A polygon has to have at least 3 points\n"));
1320 }
1321
1322 /* ---------------------------------------------------------------------------
1323  * moves the data of the attached (new) polygon to the current layer
1324  */
1325 void
1326 CopyAttachedPolygonToLayer (void)
1327 {
1328   PolygonTypePtr polygon;
1329   int saveID;
1330
1331   /* move data to layer and clear attached struct */
1332   polygon = CreateNewPolygon (CURRENT, NoFlags ());
1333   saveID = polygon->ID;
1334   *polygon = Crosshair.AttachedPolygon;
1335   polygon->ID = saveID;
1336   SET_FLAG (CLEARPOLYFLAG, polygon);
1337   if (TEST_FLAG (NEWFULLPOLYFLAG, PCB))
1338     SET_FLAG (FULLPOLYFLAG, polygon);
1339   memset (&Crosshair.AttachedPolygon, 0, sizeof (PolygonType));
1340   SetPolygonBoundingBox (polygon);
1341   if (!CURRENT->polygon_tree)
1342     CURRENT->polygon_tree = r_create_tree (NULL, 0, 0);
1343   r_insert_entry (CURRENT->polygon_tree, (BoxType *) polygon, 0);
1344   InitClip (PCB->Data, CURRENT, polygon);
1345   DrawPolygon (CURRENT, polygon, 0);
1346   SetChangedFlag (true);
1347
1348   /* reset state of attached line */
1349   Crosshair.AttachedLine.State = STATE_FIRST;
1350   addedLines = 0;
1351
1352   /* add to undo list */
1353   AddObjectToCreateUndoList (POLYGON_TYPE, CURRENT, polygon, polygon);
1354   IncrementUndoSerialNumber ();
1355 }
1356
1357 /* find polygon holes in range, then call the callback function for
1358  * each hole. If the callback returns non-zero, stop
1359  * the search.
1360  */
1361 int
1362 PolygonHoles (PolygonType *polygon, const BoxType *range,
1363               int (*callback) (PLINE *contour, void *user_data),
1364               void *user_data)
1365 {
1366   POLYAREA *pa = polygon->Clipped;
1367   PLINE *pl;
1368   /* If this hole is so big the polygon doesn't exist, then it's not
1369    * really a hole.
1370    */
1371   if (!pa)
1372     return 0;
1373   for (pl = pa->contours->next; pl; pl = pl->next)
1374     {
1375       if (range != NULL &&
1376           (pl->xmin > range->X2 || pl->xmax < range->X1 ||
1377            pl->ymin > range->Y2 || pl->ymax < range->Y1))
1378         continue;
1379       if (callback (pl, user_data))
1380         {
1381           return 1;
1382         }
1383     }
1384   return 0;
1385 }
1386
1387 struct plow_info
1388 {
1389   int type;
1390   void *ptr1, *ptr2;
1391   LayerTypePtr layer;
1392   DataTypePtr data;
1393   int (*callback) (DataTypePtr, LayerTypePtr, PolygonTypePtr, int, void *,
1394                    void *);
1395 };
1396
1397 static int
1398 subtract_plow (DataTypePtr Data, LayerTypePtr Layer, PolygonTypePtr Polygon,
1399                int type, void *ptr1, void *ptr2)
1400 {
1401   if (!Polygon->Clipped)
1402     return 0;
1403   switch (type)
1404     {
1405     case PIN_TYPE:
1406     case VIA_TYPE:
1407       SubtractPin (Data, (PinTypePtr) ptr2, Layer, Polygon);
1408       Polygon->NoHolesValid = 0;
1409       return 1;
1410     case LINE_TYPE:
1411       SubtractLine ((LineTypePtr) ptr2, Polygon);
1412       Polygon->NoHolesValid = 0;
1413       return 1;
1414     case ARC_TYPE:
1415       SubtractArc ((ArcTypePtr) ptr2, Polygon);
1416       Polygon->NoHolesValid = 0;
1417       return 1;
1418     case PAD_TYPE:
1419       SubtractPad ((PadTypePtr) ptr2, Polygon);
1420       Polygon->NoHolesValid = 0;
1421       return 1;
1422     case TEXT_TYPE:
1423       SubtractText ((TextTypePtr) ptr2, Polygon);
1424       Polygon->NoHolesValid = 0;
1425       return 1;
1426     }
1427   return 0;
1428 }
1429
1430 static int
1431 add_plow (DataTypePtr Data, LayerTypePtr Layer, PolygonTypePtr Polygon,
1432           int type, void *ptr1, void *ptr2)
1433 {
1434   switch (type)
1435     {
1436     case PIN_TYPE:
1437     case VIA_TYPE:
1438       UnsubtractPin ((PinTypePtr) ptr2, Layer, Polygon);
1439       return 1;
1440     case LINE_TYPE:
1441       UnsubtractLine ((LineTypePtr) ptr2, Layer, Polygon);
1442       return 1;
1443     case ARC_TYPE:
1444       UnsubtractArc ((ArcTypePtr) ptr2, Layer, Polygon);
1445       return 1;
1446     case PAD_TYPE:
1447       UnsubtractPad ((PadTypePtr) ptr2, Layer, Polygon);
1448       return 1;
1449     case TEXT_TYPE:
1450       UnsubtractText ((TextTypePtr) ptr2, Layer, Polygon);
1451       return 1;
1452     }
1453   return 0;
1454 }
1455
1456 static int
1457 plow_callback (const BoxType * b, void *cl)
1458 {
1459   struct plow_info *plow = (struct plow_info *) cl;
1460   PolygonTypePtr polygon = (PolygonTypePtr) b;
1461
1462   if (TEST_FLAG (CLEARPOLYFLAG, polygon))
1463     return plow->callback (plow->data, plow->layer, polygon, plow->type,
1464                            plow->ptr1, plow->ptr2);
1465   return 0;
1466 }
1467
1468 int
1469 PlowsPolygon (DataType * Data, int type, void *ptr1, void *ptr2,
1470               int (*call_back) (DataTypePtr data, LayerTypePtr lay,
1471                                 PolygonTypePtr poly, int type, void *ptr1,
1472                                 void *ptr2))
1473 {
1474   BoxType sb = ((PinTypePtr) ptr2)->BoundingBox;
1475   int r = 0;
1476   struct plow_info info;
1477
1478   info.type = type;
1479   info.ptr1 = ptr1;
1480   info.ptr2 = ptr2;
1481   info.data = Data;
1482   info.callback = call_back;
1483   switch (type)
1484     {
1485     case PIN_TYPE:
1486     case VIA_TYPE:
1487       if (type == PIN_TYPE || ptr1 == ptr2 || ptr1 == NULL)
1488         {
1489           LAYER_LOOP (Data, max_layer);
1490           {
1491             info.layer = layer;
1492             r +=
1493               r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1494           }
1495           END_LOOP;
1496         }
1497       else
1498         {
1499           GROUP_LOOP (Data, GetLayerGroupNumberByNumber (GetLayerNumber (Data,
1500                                                                          ((LayerTypePtr) ptr1))));
1501           {
1502             info.layer = layer;
1503             r +=
1504               r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1505           }
1506           END_LOOP;
1507         }
1508       break;
1509     case LINE_TYPE:
1510     case ARC_TYPE:
1511     case TEXT_TYPE:
1512       /* the cast works equally well for lines and arcs */
1513       if (!TEST_FLAG (CLEARLINEFLAG, (LineTypePtr) ptr2))
1514         return 0;
1515       /* silk doesn't plow */
1516       if (GetLayerNumber (Data, ptr1) >= max_layer)
1517         return 0;
1518       GROUP_LOOP (Data, GetLayerGroupNumberByNumber (GetLayerNumber (Data,
1519                                                                      ((LayerTypePtr) ptr1))));
1520       {
1521         info.layer = layer;
1522         r += r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1523       }
1524       END_LOOP;
1525       break;
1526     case PAD_TYPE:
1527       {
1528         Cardinal group = TEST_FLAG (ONSOLDERFLAG,
1529                                     (PadType *) ptr2) ? SOLDER_LAYER :
1530           COMPONENT_LAYER;
1531         group = GetLayerGroupNumberByNumber (max_layer + group);
1532         GROUP_LOOP (Data, group);
1533         {
1534           info.layer = layer;
1535           r +=
1536             r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1537         }
1538         END_LOOP;
1539       }
1540       break;
1541
1542     case ELEMENT_TYPE:
1543       {
1544         PIN_LOOP ((ElementType *) ptr1);
1545         {
1546           PlowsPolygon (Data, PIN_TYPE, ptr1, pin, call_back);
1547         }
1548         END_LOOP;
1549         PAD_LOOP ((ElementType *) ptr1);
1550         {
1551           PlowsPolygon (Data, PAD_TYPE, ptr1, pad, call_back);
1552         }
1553         END_LOOP;
1554       }
1555       break;
1556     }
1557   return r;
1558 }
1559
1560 void
1561 RestoreToPolygon (DataType * Data, int type, void *ptr1, void *ptr2)
1562 {
1563   if (type == POLYGON_TYPE)
1564     InitClip (PCB->Data, (LayerTypePtr) ptr1, (PolygonTypePtr) ptr2);
1565   else
1566     PlowsPolygon (Data, type, ptr1, ptr2, add_plow);
1567 }
1568
1569 void
1570 ClearFromPolygon (DataType * Data, int type, void *ptr1, void *ptr2)
1571 {
1572   if (type == POLYGON_TYPE)
1573     InitClip (PCB->Data, (LayerTypePtr) ptr1, (PolygonTypePtr) ptr2);
1574   else
1575     PlowsPolygon (Data, type, ptr1, ptr2, subtract_plow);
1576 }
1577
1578 bool
1579 isects (POLYAREA * a, PolygonTypePtr p, bool fr)
1580 {
1581   POLYAREA *x;
1582   bool ans;
1583   ans = Touching (a, p->Clipped);
1584   /* argument may be register, so we must copy it */
1585   x = a;
1586   if (fr)
1587     poly_Free (&x);
1588   return ans;
1589 }
1590
1591
1592 bool
1593 IsPointInPolygon (LocationType X, LocationType Y, BDimension r,
1594                   PolygonTypePtr p)
1595 {
1596   POLYAREA *c;
1597   Vector v;
1598   v[0] = X;
1599   v[1] = Y;
1600   if (poly_CheckInside (p->Clipped, v))
1601     return true;
1602   if (r < 1)
1603     return false;
1604   if (!(c = CirclePoly (X, Y, r)))
1605     return false;
1606   return isects (c, p, true);
1607 }
1608
1609
1610 bool
1611 IsPointInPolygonIgnoreHoles (LocationType X, LocationType Y, PolygonTypePtr p)
1612 {
1613   Vector v;
1614   v[0] = X;
1615   v[1] = Y;
1616   return poly_InsideContour (p->Clipped->contours, v);
1617 }
1618
1619 bool
1620 IsRectangleInPolygon (LocationType X1, LocationType Y1, LocationType X2,
1621                       LocationType Y2, PolygonTypePtr p)
1622 {
1623   POLYAREA *s;
1624   if (!
1625       (s = RectPoly (min (X1, X2), max (X1, X2), min (Y1, Y2), max (Y1, Y2))))
1626     return false;
1627   return isects (s, p, true);
1628 }
1629
1630 /* NB: This function will free the passed POLYAREA.
1631  *     It must only be passed a single POLYAREA (pa->f == pa->b == pa)
1632  */
1633 static void
1634 r_NoHolesPolygonDicer (POLYAREA * pa,
1635                        void (*emit) (PLINE *, void *), void *user_data)
1636 {
1637   PLINE *p = pa->contours;
1638
1639   if (!pa->contours->next)                 /* no holes */
1640     {
1641       pa->contours = NULL; /* The callback now owns the contour */
1642       emit (p, user_data);
1643       poly_Free (&pa);
1644       return;
1645     }
1646   else
1647     {
1648       POLYAREA *poly2, *left, *right;
1649
1650       /* make a rectangle of the left region slicing through the middle of the first hole */
1651       poly2 = RectPoly (p->xmin, (p->next->xmin + p->next->xmax) / 2,
1652                         p->ymin, p->ymax);
1653       poly_AndSubtract_free (pa, poly2, &left, &right);
1654       if (left)
1655         {
1656           POLYAREA *cur, *next;
1657           cur = left;
1658           do
1659             {
1660               next = cur->f;
1661               cur->f = cur->b = cur; /* Detach this polygon piece */
1662               r_NoHolesPolygonDicer (cur, emit, user_data);
1663               /* NB: The POLYAREA was freed by its use in the recursive dicer */
1664             }
1665           while ((cur = next) != left);
1666         }
1667       if (right)
1668         {
1669           POLYAREA *cur, *next;
1670           cur = right;
1671           do
1672             {
1673               next = cur->f;
1674               cur->f = cur->b = cur; /* Detach this polygon piece */
1675               r_NoHolesPolygonDicer (cur, emit, user_data);
1676               /* NB: The POLYAREA was freed by its use in the recursive dicer */
1677             }
1678           while ((cur = next) != right);
1679         }
1680     }
1681 }
1682
1683 void
1684 NoHolesPolygonDicer (PolygonTypePtr p, const BoxType * clip,
1685                      void (*emit) (PLINE *, void *), void *user_data)
1686 {
1687   POLYAREA *save, *ans, *cur, *next;
1688
1689   ans = save = poly_Create ();
1690   /* copy the main poly only */
1691   poly_Copy1 (save, p->Clipped);
1692   /* clip to the bounding box */
1693   if (clip)
1694     {
1695       POLYAREA *cbox = RectPoly (clip->X1, clip->X2, clip->Y1, clip->Y2);
1696       if (cbox)
1697         {
1698           int r = poly_Boolean_free (save, cbox, &ans, PBO_ISECT);
1699           save = ans;
1700           if (r != err_ok)
1701             save = NULL;
1702         }
1703     }
1704   if (!save)
1705     return;
1706   /* Now dice it up.
1707    * NB: Could be more than one piece (because of the clip above)
1708    */
1709   cur = save;
1710   do
1711     {
1712       next = cur->f;
1713       cur->f = cur->b = cur; /* Detach this polygon piece */
1714       r_NoHolesPolygonDicer (cur, emit, user_data);
1715       /* NB: The POLYAREA was freed by its use in the recursive dicer */
1716     }
1717   while ((cur = next) != save);
1718 }
1719
1720 /* make a polygon split into multiple parts into multiple polygons */
1721 bool
1722 MorphPolygon (LayerTypePtr layer, PolygonTypePtr poly)
1723 {
1724   POLYAREA *p, *start;
1725   bool many = false;
1726   FlagType flags;
1727
1728   if (!poly->Clipped || TEST_FLAG (LOCKFLAG, poly))
1729     return false;
1730   if (poly->Clipped->f == poly->Clipped)
1731     return false;
1732   ErasePolygon (poly);
1733   start = p = poly->Clipped;
1734   /* This is ugly. The creation of the new polygons can cause
1735    * all of the polygon pointers (including the one we're called
1736    * with to change if there is a realloc in GetPolygonMemory().
1737    * That will invalidate our original "poly" argument, potentially
1738    * inside the loop. We need to steal the Clipped pointer and
1739    * hide it from the Remove call so that it still exists while
1740    * we do this dirty work.
1741    */
1742   poly->Clipped = NULL;
1743   if (poly->NoHoles) printf ("Just leaked in MorpyPolygon\n");
1744   poly->NoHoles = NULL;
1745   flags = poly->Flags;
1746   RemovePolygon (layer, poly);
1747   inhibit = true;
1748   do
1749     {
1750       VNODE *v;
1751       PolygonTypePtr new;
1752
1753       if (p->contours->area > PCB->IsleArea)
1754         {
1755           new = CreateNewPolygon (layer, flags);
1756           if (!new)
1757             return false;
1758           many = true;
1759           v = &p->contours->head;
1760           CreateNewPointInPolygon (new, v->point[0], v->point[1]);
1761           for (v = v->next; v != &p->contours->head; v = v->next)
1762             CreateNewPointInPolygon (new, v->point[0], v->point[1]);
1763           new->BoundingBox.X1 = p->contours->xmin;
1764           new->BoundingBox.X2 = p->contours->xmax + 1;
1765           new->BoundingBox.Y1 = p->contours->ymin;
1766           new->BoundingBox.Y2 = p->contours->ymax + 1;
1767           AddObjectToCreateUndoList (POLYGON_TYPE, layer, new, new);
1768           new->Clipped = p;
1769           p = p->f;             /* go to next pline */
1770           new->Clipped->b = new->Clipped->f = new->Clipped;     /* unlink from others */
1771           r_insert_entry (layer->polygon_tree, (BoxType *) new, 0);
1772           DrawPolygon (layer, new, 0);
1773         }
1774       else
1775         {
1776           POLYAREA *t = p;
1777
1778           p = p->f;
1779           poly_DelContour (&t->contours);
1780           free (t);
1781         }
1782     }
1783   while (p != start);
1784   inhibit = false;
1785   IncrementUndoSerialNumber ();
1786   return many;
1787 }
1788
1789 void debug_pline (PLINE *pl)
1790 {
1791   VNODE *v;
1792   fprintf (stderr, "\txmin %d xmax %d ymin %d ymax %d\n",
1793            pl->xmin, pl->xmax, pl->ymin, pl->ymax);
1794   v = &pl->head;
1795   while (v)
1796     {
1797       fprintf(stderr, "\t\tvnode: %d,%d\n", v->point[0], v->point[1]);
1798       v = v->next;
1799       if (v == &pl->head)
1800         break;
1801     }
1802 }
1803
1804 void
1805 debug_polyarea (POLYAREA *p)
1806 {
1807   PLINE *pl;
1808
1809   fprintf (stderr, "POLYAREA %p\n", p);
1810   for (pl=p->contours; pl; pl=pl->next)
1811     debug_pline (pl);
1812 }
1813
1814 void
1815 debug_polygon (PolygonType *p)
1816 {
1817   Cardinal i;
1818   POLYAREA *pa;
1819   fprintf (stderr, "POLYGON %p  %d pts\n", p, p->PointN);
1820   for (i=0; i<p->PointN; i++)
1821     fprintf(stderr, "\t%d: %d, %d\n", i, p->Points[i].X, p->Points[i].Y);
1822   if (p->HoleIndexN)
1823     {
1824       fprintf (stderr, "%d holes, starting at indices\n", p->HoleIndexN);
1825       for (i=0; i<p->HoleIndexN; i++)
1826         fprintf(stderr, "\t%d: %d\n", i, p->HoleIndex[i]);
1827     }
1828   else
1829     fprintf (stderr, "it has no holes\n");
1830   pa = p->Clipped;
1831   while (pa)
1832     {
1833       debug_polyarea (pa);
1834       pa = pa->f;
1835       if (pa == p->Clipped)
1836         break;
1837     }
1838 }
1839
1840 /* Convert a POLYAREA (and all linked POLYAREA) to
1841  * raw PCB polygons on the given layer.
1842  */
1843 void
1844 PolyToPolygonsOnLayer (DataType *Destination, LayerType *Layer,
1845                        POLYAREA *Input, FlagType Flags)
1846 {
1847   PolygonType *Polygon;
1848   POLYAREA *pa;
1849   PLINE *pline;
1850   VNODE *node;
1851   bool outer;
1852
1853   if (Input == NULL)
1854     return;
1855
1856   pa = Input;
1857   do
1858     {
1859       Polygon = CreateNewPolygon (Layer, Flags);
1860
1861       pline = pa->contours;
1862       outer = true;
1863
1864       do
1865         {
1866           if (!outer)
1867             CreateNewHoleInPolygon (Polygon);
1868           outer = false;
1869
1870           node = &pline->head;
1871           do
1872             {
1873               CreateNewPointInPolygon (Polygon, node->point[0],
1874                                                 node->point[1]);
1875             }
1876           while ((node = node->next) != &pline->head);
1877
1878         }
1879       while ((pline = pline->next) != NULL);
1880
1881       InitClip (Destination, Layer, Polygon);
1882       SetPolygonBoundingBox (Polygon);
1883       if (!Layer->polygon_tree)
1884         Layer->polygon_tree = r_create_tree (NULL, 0, 0);
1885       r_insert_entry (Layer->polygon_tree, (BoxType *) Polygon, 0);
1886
1887       DrawPolygon (Layer, Polygon, 0);
1888       /* add to undo list */
1889       AddObjectToCreateUndoList (POLYGON_TYPE, Layer, Polygon, Polygon);
1890     }
1891   while ((pa = pa->f) != Input);
1892
1893   SetChangedFlag (true);
1894 }