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 36
 118 static double circleVerticies[] = {
 119   1.0, 0.0,
 120   0.98480775301221, 0.17364817766693,
 121 };
 122
 123
 124 static POLYAREA *
 125 biggest (POLYAREA * p)
 126 {
 127   POLYAREA *n, *top = NULL;
 128   PLINE *pl;
 129   double big = -1;
 130   if (!p)
 131     return NULL;
 132   n = p;
 133   do
 134     {
 135 #if 0
 136       if (n->contours->area < PCB->IsleArea)
 137         {
 138           n->b->f = n->f;
 139           n->f->b = n->b;
 140           poly_DelContour (&n->contours);
 141           if (n == p)
 142             p = n->f;
 143           n = n->f;
 144           if (!n->contours)
 145             {
 146               free (n);
 147               return NULL;
 148             }
 149         }
 150 #endif
 151       if (n->contours->area > big)
 152         {
 153           top = n;
 154           big = n->contours->area;
 155         }
 156     }
 157   while ((n = n->f) != p);
 158   assert (top);
 159   if (top == p)
 160     return p;
 161   pl = top->contours;
 162   top->contours = p->contours;
 163   p->contours = pl;
 164   assert (pl);
 165   assert (p->f);
 166   assert (p->b);
 167   return p;
 168 }
 169
 170 POLYAREA *
 171 ContourToPoly (PLINE * contour)
 172 {
 173   POLYAREA *p;
 174   poly_PreContour (contour, TRUE);
 175   assert (contour->Flags.orient == PLF_DIR);
 176   if (!(p = poly_Create ()))
 177     return NULL;
 178   poly_InclContour (p, contour);
 179   assert (poly_Valid (p));
 180   return p;
 181 }
 182
 183 static POLYAREA *
 184 original_poly (PolygonType * p)
 185 {
 186   PLINE *contour = NULL;
 187   POLYAREA *np = NULL;
 188   Vector v;
 189
 190   /* first make initial polygon contour */
 191   POLYGONPOINT_LOOP (p);
 192   {
 193     v[0] = point->X;
 194     v[1] = point->Y;
 195     if (contour == NULL)
 196       {
 197         if ((contour = poly_NewContour (v)) == NULL)
 198           return NULL;
 199       }
 200     else
 201       {
 202         poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 203       }
 204   }
 205   END_LOOP;
 206   poly_PreContour (contour, TRUE);
 207   /* make sure it is a positive contour */
 208   if ((contour->Flags.orient) != PLF_DIR)
 209     poly_InvContour (contour);
 210   assert ((contour->Flags.orient) == PLF_DIR);
 211   if ((np = poly_Create ()) == NULL)
 212     return NULL;
 213   poly_InclContour (np, contour);
 214   assert (poly_Valid (np));
 215   return biggest (np);
 216 }
 217
 218 static int
 219 ClipOriginal (PolygonType * poly)
 220 {
 221   POLYAREA *p, *result;
 222   int r;
 223
 224   p = original_poly (poly);
 225   r = poly_Boolean_free (poly->Clipped, p, &result, PBO_ISECT);
 226   if (r != err_ok)
 227     {
 228       fprintf (stderr, "Error while clipping PBO_ISECT: %d\n", r);
 229       poly_Free (&result);
 230       poly->Clipped = NULL;
 231       return 0;
 232     }
 233   poly->Clipped = biggest (result);
 234   assert (!poly->Clipped || poly_Valid (poly->Clipped));
 235   return 1;
 236 }
 237
 238 POLYAREA *
 239 RectPoly (LocationType x1, LocationType x2, LocationType y1, LocationType y2)
 240 {
 241   PLINE *contour = NULL;
 242   Vector v;
 243
 244   assert (x2 > x1);
 245   assert (y2 > y1);
 246   v[0] = x1;
 247   v[1] = y1;
 248   if ((contour = poly_NewContour (v)) == NULL)
 249     return NULL;
 250   v[0] = x2;
 251   v[1] = y1;
 252   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 253   v[0] = x2;
 254   v[1] = y2;
 255   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 256   v[0] = x1;
 257   v[1] = y2;
 258   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 259   return ContourToPoly (contour);
 260 }
 261
 262 POLYAREA *
 263 OctagonPoly (LocationType x, LocationType y, BDimension radius)
 264 {
 265   PLINE *contour = NULL;
 266   Vector v;
 267
 268   v[0] = x + ROUND (radius * 0.5);
 269   v[1] = y + ROUND (radius * TAN_22_5_DEGREE_2);
 270   if ((contour = poly_NewContour (v)) == NULL)
 271     return NULL;
 272   v[0] = x + ROUND (radius * TAN_22_5_DEGREE_2);
 273   v[1] = y + ROUND (radius * 0.5);
 274   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 275   v[0] = x - (v[0] - x);
 276   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 277   v[0] = x - ROUND (radius * 0.5);
 278   v[1] = y + ROUND (radius * TAN_22_5_DEGREE_2);
 279   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 280   v[1] = y - (v[1] - y);
 281   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 282   v[0] = x - ROUND (radius * TAN_22_5_DEGREE_2);
 283   v[1] = y - ROUND (radius * 0.5);
 284   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 285   v[0] = x - (v[0] - x);
 286   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 287   v[0] = x + ROUND (radius * 0.5);
 288   v[1] = y - ROUND (radius * TAN_22_5_DEGREE_2);
 289   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 290   return ContourToPoly (contour);
 291 }
 292
 293 /* add verticies in a fractional-circle starting from v
 294  * centered at X, Y and going counter-clockwise
 295  * does not include the first point
 296  * last argument is 1 for a full circle
 297  * 2 for a half circle
 298  * or 4 for a quarter circle
 299  */
 300 void
 301 frac_circle (PLINE * c, LocationType X, LocationType Y, Vector v, int range)
 302 {
 303   double e1, e2, t1;
 304   int i;
 305
 306   poly_InclVertex (c->head.prev, poly_CreateNode (v));
 307   /* move vector to origin */
 308   e1 = v[0] - X;
 309   e2 = v[1] - Y;
 310
 311   range = range == 1 ? CIRC_SEGS-1 : (CIRC_SEGS / range);
 312   for (i = 0; i < range; i++)
 313     {
 314       /* rotate the vector */
 315       t1 = e1 * circleVerticies[2] - e2 * circleVerticies[3];
 316       e2 = e1 * circleVerticies[3] + e2 * circleVerticies[2];
 317       e1 = t1;
 318       v[0] = X + ROUND (e1);
 319       v[1] = Y + ROUND (e2);
 320       poly_InclVertex (c->head.prev, poly_CreateNode (v));
 321     }
 322 }
 323
 324 #define COARSE_CIRCLE 0
 325 /* create a 35-vertex circle approximation */
 326 POLYAREA *
 327 CirclePoly (LocationType x, LocationType y, BDimension radius)
 328 {
 329   PLINE *contour;
 330   Vector v;
 331
 332   if (radius <= 0)
 333     return NULL;
 334   v[0] = x + radius;
 335   v[1] = y;
 336   if ((contour = poly_NewContour (v)) == NULL)
 337     return NULL;
 338   frac_circle (contour, x, y, v, 1);
 339   return ContourToPoly (contour);
 340 }
 341
 342 /* make a rounded-corner rectangle with radius t beyond x1,x2,y1,y2 rectangle */
 343 POLYAREA *
 344 RoundRect (LocationType x1, LocationType x2, LocationType y1, LocationType y2,
 345            BDimension t)
 346 {
 347   PLINE *contour = NULL;
 348   Vector v;
 349
 350   assert (x2 > x1);
 351   assert (y2 > y1);
 352   v[0] = x1 - t;
 353   v[1] = y1;
 354   if ((contour = poly_NewContour (v)) == NULL)
 355     return NULL;
 356   frac_circle (contour, x1, y1, v, 4);
 357   v[0] = x2;
 358   v[1] = y1 - t;
 359   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 360   frac_circle (contour, x2, y1, v, 4);
 361   v[0] = x2 + t;
 362   v[1] = y2;
 363   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 364   frac_circle (contour, x2, y2, v, 4);
 365   v[0] = x1;
 366   v[1] = y2 + t;
 367   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 368   frac_circle (contour, x1, y2, v, 4);
 369   return ContourToPoly (contour);
 370 }
 371
 372 #define ARC_ANGLE 5
 373 static POLYAREA *
 374 ArcPolyNoIntersect (ArcType * a, BDimension thick)
 375 {
 376   PLINE *contour = NULL;
 377   POLYAREA *np = NULL;
 378   Vector v;
 379   BoxType *ends;
 380   int i, segs;
 381   double ang, da, rx, ry;
 382   long half;
 383
 384   if (thick <= 0)
 385     return NULL;
 386   if (a->Delta < 0)
 387     {
 388       a->StartAngle += a->Delta;
 389       a->Delta = -a->Delta;
 390     }
 391   half = (thick + 1) / 2;
 392   ends = GetArcEnds (a);
 393   /* start with inner radius */
 394   rx = MAX (a->Width - half, 0);
 395   ry = MAX (a->Height - half, 0);
 396   segs = a->Delta / ARC_ANGLE;
 397   ang = a->StartAngle;
 398   da = (1.0 * a->Delta) / segs;
 399   v[0] = a->X - rx * cos (ang * M180);
 400   v[1] = a->Y + ry * sin (ang * M180);
 401   if ((contour = poly_NewContour (v)) == NULL)
 402     return 0;
 403   for (i = 0; i < segs - 1; i++)
 404     {
 405       ang += da;
 406       v[0] = a->X - rx * cos (ang * M180);
 407       v[1] = a->Y + ry * sin (ang * M180);
 408       poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 409     }
 410   /* find last point */
 411   ang = a->StartAngle + a->Delta;
 412   v[0] = a->X - rx * cos (ang * M180);
 413   v[1] = a->Y + ry * sin (ang * M180);
 414   /* add the round cap at the end */
 415   frac_circle (contour, ends->X2, ends->Y2, v, 2);
 416   /* and now do the outer arc (going backwards) */
 417   rx = a->Width + half;
 418   ry = a->Width + half;
 419   da = -da;
 420   for (i = 0; i < segs; i++)
 421     {
 422       v[0] = a->X - rx * cos (ang * M180);
 423       v[1] = a->Y + ry * sin (ang * M180);
 424       poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 425       ang += da;
 426     }
 427   /* now add other round cap */
 428   ang = a->StartAngle;
 429   v[0] = a->X - rx * cos (ang * M180);
 430   v[1] = a->Y + ry * sin (ang * M180);
 431   frac_circle (contour, ends->X1, ends->Y1, v, 2);
 432   /* now we have the whole contour */
 433   if (!(np = ContourToPoly (contour)))
 434     return NULL;
 435   return np;
 436 }
 437
 438 #define MIN_CLEARANCE_BEFORE_BISECT 10.
 439 POLYAREA *
 440 ArcPoly (ArcType * a, BDimension thick)
 441 {
 442   double delta;
 443   ArcType seg1, seg2;
 444   POLYAREA *tmp1, *tmp2, *res;
 445
 446   delta = (a->Delta < 0) ? -a->Delta : a->Delta;
 447
 448   /* If the arc segment would self-intersect, we need to construct it as the union of
 449      two non-intersecting segments */
 450
 451   if (2 * M_PI * a->Width * (1. - (double)delta / 360.) - thick < MIN_CLEARANCE_BEFORE_BISECT)
 452     {
 453       int half_delta = a->Delta / 2;
 454
 455       seg1 = seg2 = *a;
 456       seg1.Delta = half_delta;
 457       seg2.Delta -= half_delta;
 458       seg2.StartAngle += half_delta;
 459
 460       tmp1 = ArcPolyNoIntersect (&seg1, thick);
 461       tmp2 = ArcPolyNoIntersect (&seg2, thick);
 462       poly_Boolean_free (tmp1, tmp2, &res, PBO_UNITE);
 463       return res;
 464     }
 465
 466   return ArcPolyNoIntersect (a, thick);
 467 }
 468
 469 POLYAREA *
 470 LinePoly (LineType * L, BDimension thick)
 471 {
 472   PLINE *contour = NULL;
 473   POLYAREA *np = NULL;
 474   Vector v;
 475   double d, dx, dy;
 476   long half;LineType _l=*L,*l=&_l;
 477
 478   if (thick <= 0)
 479     return NULL;
 480   half = (thick + 1) / 2;
 481   d =
 482     sqrt (SQUARE (l->Point1.X - l->Point2.X) +
 483           SQUARE (l->Point1.Y - l->Point2.Y));
 484   if (!TEST_FLAG (SQUAREFLAG,l))
 485     if (d == 0)                   /* line is a point */
 486       return CirclePoly (l->Point1.X, l->Point1.Y, half);
 487   if (d != 0)
 488     {
 489       d = half / d;
 490       dx = (l->Point1.Y - l->Point2.Y) * d;
 491       dy = (l->Point2.X - l->Point1.X) * d;
 492     }
 493   else
 494     {
 495       dx = half;
 496       dy = 0;
 497     }
 498   if (TEST_FLAG (SQUAREFLAG,l))/* take into account the ends */
 499     {
 500       l->Point1.X -= dy;
 501       l->Point1.Y += dx;
 502       l->Point2.X += dy;
 503       l->Point2.Y -= dx;
 504     }
 505   v[0] = l->Point1.X - dx;
 506   v[1] = l->Point1.Y - dy;
 507   if ((contour = poly_NewContour (v)) == NULL)
 508     return 0;
 509   v[0] = l->Point2.X - dx;
 510   v[1] = l->Point2.Y - dy;
 511   if (TEST_FLAG (SQUAREFLAG,l))
 512     poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 513   else
 514     frac_circle (contour, l->Point2.X, l->Point2.Y, v, 2);
 515   v[0] = l->Point2.X + dx;
 516   v[1] = l->Point2.Y + dy;
 517   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 518   v[0] = l->Point1.X + dx;
 519   v[1] = l->Point1.Y + dy;
 520   if (TEST_FLAG (SQUAREFLAG,l))
 521     poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 522   else
 523     frac_circle (contour, l->Point1.X, l->Point1.Y, v, 2);
 524   /* now we have the line contour */
 525   if (!(np = ContourToPoly (contour)))
 526     return NULL;
 527   return np;
 528 }
 529
 530 /* make a rounded-corner rectangle */
 531 POLYAREA *
 532 SquarePadPoly (PadType * pad, BDimension clear)
 533 {
 534   PLINE *contour = NULL;
 535   POLYAREA *np = NULL;
 536   Vector v;
 537   double d;
 538   double tx, ty;
 539   double cx, cy;
 540   PadType _t=*pad,*t=&_t;
 541   PadType _c=*pad,*c=&_c;
 542   int halfthick = (pad->Thickness + 1) / 2;
 543   int halfclear = (clear + 1) / 2;
 544
 545   d =
 546     sqrt (SQUARE (pad->Point1.X - pad->Point2.X) +
 547           SQUARE (pad->Point1.Y - pad->Point2.Y));
 548   if (d != 0)
 549     {
 550       double a = halfthick / d;
 551       tx = (t->Point1.Y - t->Point2.Y) * a;
 552       ty = (t->Point2.X - t->Point1.X) * a;
 553       a = halfclear / d;
 554       cx = (c->Point1.Y - c->Point2.Y) * a;
 555       cy = (c->Point2.X - c->Point1.X) * a;
 556
 557       t->Point1.X -= ty;
 558       t->Point1.Y += tx;
 559       t->Point2.X += ty;
 560       t->Point2.Y -= tx;
 561       c->Point1.X -= cy;
 562       c->Point1.Y += cx;
 563       c->Point2.X += cy;
 564       c->Point2.Y -= cx;
 565     }
 566   else
 567     {
 568       tx = halfthick;
 569       ty = 0;
 570       cx = halfclear;
 571       cy = 0;
 572
 573       t->Point1.Y += tx;
 574       t->Point2.Y -= tx;
 575       c->Point1.Y += cx;
 576       c->Point2.Y -= cx;
 577     }
 578
 579   v[0] = c->Point1.X - tx;
 580   v[1] = c->Point1.Y - ty;
 581   if ((contour = poly_NewContour (v)) == NULL)
 582     return 0;
 583   frac_circle (contour, (t->Point1.X - tx), (t->Point1.Y - ty), v, 4);
 584
 585   v[0] = t->Point2.X - cx;
 586   v[1] = t->Point2.Y - cy;
 587   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 588   frac_circle (contour, (t->Point2.X - tx), (t->Point2.Y - ty), v, 4);
 589
 590   v[0] = c->Point2.X + tx;
 591   v[1] = c->Point2.Y + ty;
 592   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 593   frac_circle (contour, (t->Point2.X + tx), (t->Point2.Y + ty), v, 4);
 594
 595   v[0] = t->Point1.X + cx;
 596   v[1] = t->Point1.Y + cy;
 597   poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 598   frac_circle (contour, (t->Point1.X + tx), (t->Point1.Y + ty), v, 4);
 599
 600   /* now we have the line contour */
 601   if (!(np = ContourToPoly (contour)))
 602     return NULL;
 603   return np;
 604 }
 605
 606 /* clear np1 from the polygon */
 607 static int
 608 Subtract (POLYAREA * np1, PolygonType * p, Boolean fnp)
 609 {
 610   POLYAREA *merged = NULL, *np = np1;
 611   int x;
 612   assert (np);
 613   assert (p);
 614   if (!p->Clipped)
 615     {
 616       if (fnp)
 617         poly_Free (&np);
 618       return 1;
 619     }
 620   assert (poly_Valid (p->Clipped));
 621   assert (poly_Valid (np));
 622   if (fnp)
 623     x = poly_Boolean_free (p->Clipped, np, &merged, PBO_SUB);
 624   else
 625     {
 626       x = poly_Boolean (p->Clipped, np, &merged, PBO_SUB);
 627       poly_Free (&p->Clipped);
 628     }
 629   assert (!merged || poly_Valid (merged));
 630   if (x != err_ok)
 631     {
 632       fprintf (stderr, "Error while clipping PBO_SUB: %d\n", x);
 633       poly_Free (&merged);
 634       p->Clipped = NULL;
 635       return -1;
 636     }
 637   p->Clipped = biggest (merged);
 638   assert (!p->Clipped || poly_Valid (p->Clipped));
 639   if (!p->Clipped)
 640     Message ("Polygon cleared out of existence near (%d, %d)\n",
 641              (p->BoundingBox.X1 + p->BoundingBox.X2) / 2,
 642              (p->BoundingBox.Y1 + p->BoundingBox.Y2) / 2);
 643   return 1;
 644 }
 645
 646 /* create a polygon of the pin clearance */
 647 POLYAREA *
 648 PinPoly (PinType * pin, BDimension thick, BDimension clear)
 649 {
 650   int size;
 651
 652   if (TEST_FLAG (SQUAREFLAG, pin))
 653     {
 654       size = (thick + 1) / 2;
 655       return RoundRect (pin->X - size, pin->X + size, pin->Y - size,
 656                         pin->Y + size, (clear + 1) / 2);
 657     }
 658   else
 659     {
 660       size = (thick + clear + 1) / 2;
 661       if (TEST_FLAG (OCTAGONFLAG, pin))
 662         {
 663           return OctagonPoly (pin->X, pin->Y, size + size);
 664         }
 665     }
 666   return CirclePoly (pin->X, pin->Y, size);
 667 }
 668
 669 POLYAREA *
 670 BoxPolyBloated (BoxType *box, BDimension bloat)
 671 {
 672   return RectPoly (box->X1 - bloat, box->X2 + bloat,
 673                    box->Y1 - bloat, box->Y2 + bloat);
 674 }
 675
 676 /* remove the pin clearance from the polygon */
 677 static int
 678 SubtractPin (DataType * d, PinType * pin, LayerType * l, PolygonType * p)
 679 {
 680   POLYAREA *np;
 681   Cardinal i;
 682
 683   if (pin->Clearance == 0)
 684     return 0;
 685   i = GetLayerNumber (d, l);
 686   if (TEST_THERM (i, pin))
 687     {
 688       np = ThermPoly ((PCBTypePtr) (d->pcb), pin, i);
 689       if (!np)
 690         return 0;
 691     }
 692   else
 693     {
 694       np = PinPoly (pin, pin->Thickness, pin->Clearance);
 695       if (!np)
 696         return -1;
 697     }
 698   return Subtract (np, p, TRUE);
 699 }
 700
 701 static int
 702 SubtractLine (LineType * line, PolygonType * p)
 703 {
 704   POLYAREA *np;
 705
 706   if (!TEST_FLAG (CLEARLINEFLAG, line))
 707     return 0;
 708   if (!(np = LinePoly (line, line->Thickness + line->Clearance)))
 709     return -1;
 710   return Subtract (np, p, True);
 711 }
 712
 713 static int
 714 SubtractArc (ArcType * arc, PolygonType * p)
 715 {
 716   POLYAREA *np;
 717
 718   if (!TEST_FLAG (CLEARLINEFLAG, arc))
 719     return 0;
 720   if (!(np = ArcPoly (arc, arc->Thickness + arc->Clearance)))
 721     return -1;
 722   return Subtract (np, p, True);
 723 }
 724
 725 static int
 726 SubtractText (TextType * text, PolygonType * p)
 727 {
 728   POLYAREA *np;
 729   const BoxType *b = &text->BoundingBox;
 730
 731   if (!TEST_FLAG (CLEARLINEFLAG, text))
 732     return 0;
 733   if (!(np = RoundRect (b->X1 + PCB->Bloat, b->X2 - PCB->Bloat,
 734                         b->Y1 + PCB->Bloat, b->Y2 - PCB->Bloat, PCB->Bloat)))
 735     return -1;
 736   return Subtract (np, p, True);
 737 }
 738
 739 static int
 740 SubtractPad (PadType * pad, PolygonType * p)
 741 {
 742   POLYAREA *np = NULL;
 743
 744   if (TEST_FLAG (SQUAREFLAG, pad))
 745     {
 746       if (!
 747           (np = SquarePadPoly (pad, pad->Thickness + pad->Clearance)))
 748         return -1;
 749     }
 750   else
 751     {
 752       if (!
 753           (np = LinePoly ((LineType *) pad, pad->Thickness + pad->Clearance)))
 754         return -1;
 755     }
 756   return Subtract (np, p, True);
 757 }
 758
 759 struct cpInfo
 760 {
 761   const BoxType *other;
 762   DataType *data;
 763   LayerType *layer;
 764   PolygonType *polygon;
 765   Boolean solder;
 766   jmp_buf env;
 767 };
 768
 769 static int
 770 pin_sub_callback (const BoxType * b, void *cl)
 771 {
 772   PinTypePtr pin = (PinTypePtr) b;
 773   struct cpInfo *info = (struct cpInfo *) cl;
 774   PolygonTypePtr polygon;
 775
 776   /* don't subtract the object that was put back! */
 777   if (b == info->other)
 778     return 0;
 779   polygon = info->polygon;
 780   if (SubtractPin (info->data, pin, info->layer, polygon) < 0)
 781     longjmp (info->env, 1);
 782   return 1;
 783 }
 784
 785 static int
 786 arc_sub_callback (const BoxType * b, void *cl)
 787 {
 788   ArcTypePtr arc = (ArcTypePtr) b;
 789   struct cpInfo *info = (struct cpInfo *) cl;
 790   PolygonTypePtr polygon;
 791
 792   /* don't subtract the object that was put back! */
 793   if (b == info->other)
 794     return 0;
 795   if (!TEST_FLAG (CLEARLINEFLAG, arc))
 796     return 0;
 797   polygon = info->polygon;
 798   if (SubtractArc (arc, polygon) < 0)
 799     longjmp (info->env, 1);
 800   return 1;
 801 }
 802
 803 static int
 804 pad_sub_callback (const BoxType * b, void *cl)
 805 {
 806   PadTypePtr pad = (PadTypePtr) b;
 807   struct cpInfo *info = (struct cpInfo *) cl;
 808   PolygonTypePtr polygon;
 809
 810   /* don't subtract the object that was put back! */
 811   if (b == info->other)
 812     return 0;
 813   polygon = info->polygon;
 814   if (XOR (TEST_FLAG (ONSOLDERFLAG, pad), !info->solder))
 815     {
 816       if (SubtractPad (pad, polygon) < 0)
 817         longjmp (info->env, 1);
 818       return 1;
 819     }
 820   return 0;
 821 }
 822
 823 static int
 824 line_sub_callback (const BoxType * b, void *cl)
 825 {
 826   LineTypePtr line = (LineTypePtr) b;
 827   struct cpInfo *info = (struct cpInfo *) cl;
 828   PolygonTypePtr polygon;
 829
 830   /* don't subtract the object that was put back! */
 831   if (b == info->other)
 832     return 0;
 833   if (!TEST_FLAG (CLEARLINEFLAG, line))
 834     return 0;
 835   polygon = info->polygon;
 836   if (SubtractLine (line, polygon) < 0)
 837     longjmp (info->env, 1);
 838   return 1;
 839 }
 840
 841 static int
 842 text_sub_callback (const BoxType * b, void *cl)
 843 {
 844   TextTypePtr text = (TextTypePtr) b;
 845   struct cpInfo *info = (struct cpInfo *) cl;
 846   PolygonTypePtr polygon;
 847
 848   /* don't subtract the object that was put back! */
 849   if (b == info->other)
 850     return 0;
 851   if (!TEST_FLAG (CLEARLINEFLAG, text))
 852     return 0;
 853   polygon = info->polygon;
 854   if (SubtractText (text, polygon) < 0)
 855     longjmp (info->env, 1);
 856   return 1;
 857 }
 858
 859 static int
 860 Group (DataTypePtr Data, Cardinal layer)
 861 {
 862   Cardinal i, j;
 863   for (i = 0; i < max_layer; i++)
 864     for (j = 0; j < ((PCBType *) (Data->pcb))->LayerGroups.Number[i]; j++)
 865       if (layer == ((PCBType *) (Data->pcb))->LayerGroups.Entries[i][j])
 866         return i;
 867   return i;
 868 }
 869
 870 static int
 871 clearPoly (DataTypePtr Data, LayerTypePtr Layer, PolygonType * polygon,
 872            const BoxType * here, BDimension expand)
 873 {
 874   int r = 0;
 875   BoxType region;
 876   struct cpInfo info;
 877   Cardinal group;
 878
 879   if (!TEST_FLAG (CLEARPOLYFLAG, polygon)
 880       || GetLayerNumber (Data, Layer) >= max_layer)
 881     return 0;
 882   group = Group (Data, GetLayerNumber (Data, Layer));
 883   info.solder = (group == Group (Data, max_layer + SOLDER_LAYER));
 884   info.data = Data;
 885   info.other = here;
 886   info.layer = Layer;
 887   info.polygon = polygon;
 888   if (here)
 889     region = clip_box (here, &polygon->BoundingBox);
 890   else
 891     region = polygon->BoundingBox;
 892   region = bloat_box (&region, expand);
 893
 894   if (setjmp (info.env) == 0)
 895     {
 896       r = r_search (Data->via_tree, &region, NULL, pin_sub_callback, &info);
 897       r += r_search (Data->pin_tree, &region, NULL, pin_sub_callback, &info);
 898       GROUP_LOOP (Data, group);
 899       {
 900         r +=
 901           r_search (layer->line_tree, &region, NULL, line_sub_callback,
 902                     &info);
 903         r +=
 904           r_search (layer->arc_tree, &region, NULL, arc_sub_callback, &info);
 905         r +=
 906           r_search (layer->text_tree, &region, NULL, text_sub_callback, &info);
 907       }
 908       END_LOOP;
 909       if (info.solder || group == Group (Data, max_layer + COMPONENT_LAYER))
 910         r += r_search (Data->pad_tree, &region, NULL, pad_sub_callback, &info);
 911     }
 912   return r;
 913 }
 914
 915 static int
 916 Unsubtract (POLYAREA * np1, PolygonType * p)
 917 {
 918   POLYAREA *merged = NULL, *np = np1;
 919   int x;
 920   assert (np);
 921   assert (p && p->Clipped);
 922   x = poly_Boolean_free (p->Clipped, np, &merged, PBO_UNITE);
 923   if (x != err_ok)
 924     {
 925       fprintf (stderr, "Error while clipping PBO_UNITE: %d\n", x);
 926       poly_Free (&merged);
 927       p->Clipped = NULL;
 928       return 0;
 929     }
 930   p->Clipped = biggest (merged);
 931   assert (!p->Clipped || poly_Valid (p->Clipped));
 932   return ClipOriginal (p);
 933 }
 934
 935 static int
 936 UnsubtractPin (PinType * pin, LayerType * l, PolygonType * p)
 937 {
 938   POLYAREA *np;
 939
 940   /* overlap a bit to prevent gaps from rounding errors */
 941   np = BoxPolyBloated (&pin->BoundingBox, UNSUBTRACT_BLOAT);
 942
 943   if (!np)
 944     return 0;
 945   if (!Unsubtract (np, p))
 946     return 0;
 947   clearPoly (PCB->Data, l, p, (const BoxType *) pin, 2 * UNSUBTRACT_BLOAT);
 948   return 1;
 949 }
 950
 951 static int
 952 UnsubtractArc (ArcType * arc, LayerType * l, PolygonType * p)
 953 {
 954   POLYAREA *np;
 955
 956   if (!TEST_FLAG (CLEARLINEFLAG, arc))
 957     return 0;
 958
 959   /* overlap a bit to prevent gaps from rounding errors */
 960   np = BoxPolyBloated (&arc->BoundingBox, UNSUBTRACT_BLOAT);
 961
 962   if (!np)
 963     return 0;
 964   if (!Unsubtract (np, p))
 965     return 0;
 966   clearPoly (PCB->Data, l, p, (const BoxType *) arc, 2 * UNSUBTRACT_BLOAT);
 967   return 1;
 968 }
 969
 970 static int
 971 UnsubtractLine (LineType * line, LayerType * l, PolygonType * p)
 972 {
 973   POLYAREA *np;
 974
 975   if (!TEST_FLAG (CLEARLINEFLAG, line))
 976     return 0;
 977
 978   /* overlap a bit to prevent notches from rounding errors */
 979   np = BoxPolyBloated (&line->BoundingBox, UNSUBTRACT_BLOAT);
 980
 981   if (!np)
 982     return 0;
 983   if (!Unsubtract (np, p))
 984     return 0;
 985   clearPoly (PCB->Data, l, p, (const BoxType *) line, 2 * UNSUBTRACT_BLOAT);
 986   return 1;
 987 }
 988
 989 static int
 990 UnsubtractText (TextType * text, LayerType * l, PolygonType * p)
 991 {
 992   POLYAREA *np;
 993
 994   if (!TEST_FLAG (CLEARLINEFLAG, text))
 995     return 0;
 996
 997   /* overlap a bit to prevent notches from rounding errors */
 998   np = BoxPolyBloated (&text->BoundingBox, UNSUBTRACT_BLOAT);
 999
1000   if (!np)
1001     return -1;
1002   if (!Unsubtract (np, p))
1003     return 0;
1004   clearPoly (PCB->Data, l, p, (const BoxType *) text, 2 * UNSUBTRACT_BLOAT);
1005   return 1;
1006 }
1007
1008 static int
1009 UnsubtractPad (PadType * pad, LayerType * l, PolygonType * p)
1010 {
1011   POLYAREA *np;
1012
1013   /* overlap a bit to prevent notches from rounding errors */
1014   np = BoxPolyBloated (&pad->BoundingBox, UNSUBTRACT_BLOAT);
1015
1016   if (!np)
1017     return 0;
1018   if (!Unsubtract (np, p))
1019     return 0;
1020   clearPoly (PCB->Data, l, p, (const BoxType *) pad, 2 * UNSUBTRACT_BLOAT);
1021   return 1;
1022 }
1023
1024 static Boolean inhibit = False;
1025
1026 int
1027 InitClip (DataTypePtr Data, LayerTypePtr layer, PolygonType * p)
1028 {
1029   if (inhibit)
1030     return 0;
1031   if (p->Clipped)
1032     poly_Free (&p->Clipped);
1033   p->Clipped = original_poly (p);
1034   if (!p->Clipped)
1035     return 0;
1036   assert (poly_Valid (p->Clipped));
1037   if (TEST_FLAG (CLEARPOLYFLAG, p))
1038     clearPoly (Data, layer, p, NULL, 0);
1039   return 1;
1040 }
1041
1042 /* --------------------------------------------------------------------------
1043  * remove redundant polygon points. Any point that lies on the straight
1044  * line between the points on either side of it is redundant.
1045  * returns true if any points are removed
1046  */
1047 Boolean
1048 RemoveExcessPolygonPoints (LayerTypePtr Layer, PolygonTypePtr Polygon)
1049 {
1050   PointTypePtr pt1, pt2, pt3;
1051   Cardinal n;
1052   LineType line;
1053   Boolean changed = False;
1054
1055   if (Undoing ())
1056     return (False);
1057   /* there are always at least three points in a polygon */
1058   pt1 = &Polygon->Points[Polygon->PointN - 1];
1059   pt2 = &Polygon->Points[0];
1060   pt3 = &Polygon->Points[1];
1061   for (n = 0; n < Polygon->PointN; n++, pt1++, pt2++, pt3++)
1062     {
1063       /* wrap around polygon */
1064       if (n == 1)
1065         pt1 = &Polygon->Points[0];
1066       if (n == Polygon->PointN - 1)
1067         pt3 = &Polygon->Points[0];
1068       line.Point1 = *pt1;
1069       line.Point2 = *pt3;
1070       line.Thickness = 0;
1071       if (IsPointOnLine ((float) pt2->X, (float) pt2->Y, 0.0, &line))
1072         {
1073           RemoveObject (POLYGONPOINT_TYPE, (void *) Layer, (void *) Polygon,
1074                         (void *) pt2);
1075           changed = True;
1076         }
1077     }
1078   return (changed);
1079 }
1080
1081 /* ---------------------------------------------------------------------------
1082  * returns the index of the polygon point which is the end
1083  * point of the segment with the lowest distance to the passed
1084  * coordinates
1085  */
1086 Cardinal
1087 GetLowestDistancePolygonPoint (PolygonTypePtr Polygon, LocationType X,
1088                                LocationType Y)
1089 {
1090   double mindistance = (double) MAX_COORD * MAX_COORD;
1091   PointTypePtr ptr1 = &Polygon->Points[Polygon->PointN - 1],
1092     ptr2 = &Polygon->Points[0];
1093   Cardinal n, result = 0;
1094
1095   /* we calculate the distance to each segment and choose the
1096    * shortest distance. If the closest approach between the
1097    * given point and the projected line (i.e. the segment extended)
1098    * is not on the segment, then the distance is the distance
1099    * to the segment end point.
1100    */
1101
1102   for (n = 0; n < Polygon->PointN; n++, ptr2++)
1103     {
1104       register double u, dx, dy;
1105       dx = ptr2->X - ptr1->X;
1106       dy = ptr2->Y - ptr1->Y;
1107       if (dx != 0.0 || dy != 0.0)
1108         {
1109           /* projected intersection is at P1 + u(P2 - P1) */
1110           u = ((X - ptr1->X) * dx + (Y - ptr1->Y) * dy) / (dx * dx + dy * dy);
1111
1112           if (u < 0.0)
1113             {                   /* ptr1 is closest point */
1114               u = SQUARE (X - ptr1->X) + SQUARE (Y - ptr1->Y);
1115             }
1116           else if (u > 1.0)
1117             {                   /* ptr2 is closest point */
1118               u = SQUARE (X - ptr2->X) + SQUARE (Y - ptr2->Y);
1119             }
1120           else
1121             {                   /* projected intersection is closest point */
1122               u = SQUARE (X - ptr1->X * (1.0 - u) - u * ptr2->X) +
1123                 SQUARE (Y - ptr1->Y * (1.0 - u) - u * ptr2->Y);
1124             }
1125           if (u < mindistance)
1126             {
1127               mindistance = u;
1128               result = n;
1129             }
1130         }
1131       ptr1 = ptr2;
1132     }
1133   return (result);
1134 }
1135
1136 /* ---------------------------------------------------------------------------
1137  * go back to the  previous point of the polygon
1138  */
1139 void
1140 GoToPreviousPoint (void)
1141 {
1142   switch (Crosshair.AttachedPolygon.PointN)
1143     {
1144       /* do nothing if mode has just been entered */
1145     case 0:
1146       break;
1147
1148       /* reset number of points and 'LINE_MODE' state */
1149     case 1:
1150       Crosshair.AttachedPolygon.PointN = 0;
1151       Crosshair.AttachedLine.State = STATE_FIRST;
1152       addedLines = 0;
1153       break;
1154
1155       /* back-up one point */
1156     default:
1157       {
1158         PointTypePtr points = Crosshair.AttachedPolygon.Points;
1159         Cardinal n = Crosshair.AttachedPolygon.PointN - 2;
1160
1161         Crosshair.AttachedPolygon.PointN--;
1162         Crosshair.AttachedLine.Point1.X = points[n].X;
1163         Crosshair.AttachedLine.Point1.Y = points[n].Y;
1164         break;
1165       }
1166     }
1167 }
1168
1169 /* ---------------------------------------------------------------------------
1170  * close polygon if possible
1171  */
1172 void
1173 ClosePolygon (void)
1174 {
1175   Cardinal n = Crosshair.AttachedPolygon.PointN;
1176
1177   /* check number of points */
1178   if (n >= 3)
1179     {
1180       /* if 45 degree lines are what we want do a quick check
1181        * if closing the polygon makes sense
1182        */
1183       if (!TEST_FLAG (ALLDIRECTIONFLAG, PCB))
1184         {
1185           BDimension dx, dy;
1186
1187           dx = abs (Crosshair.AttachedPolygon.Points[n - 1].X -
1188                     Crosshair.AttachedPolygon.Points[0].X);
1189           dy = abs (Crosshair.AttachedPolygon.Points[n - 1].Y -
1190                     Crosshair.AttachedPolygon.Points[0].Y);
1191           if (!(dx == 0 || dy == 0 || dx == dy))
1192             {
1193               Message
1194                 (_
1195                  ("Cannot close polygon because 45 degree lines are requested.\n"));
1196               return;
1197             }
1198         }
1199       CopyAttachedPolygonToLayer ();
1200       Draw ();
1201     }
1202   else
1203     Message (_("A polygon has to have at least 3 points\n"));
1204 }
1205
1206 /* ---------------------------------------------------------------------------
1207  * moves the data of the attached (new) polygon to the current layer
1208  */
1209 void
1210 CopyAttachedPolygonToLayer (void)
1211 {
1212   PolygonTypePtr polygon;
1213   int saveID;
1214
1215   /* move data to layer and clear attached struct */
1216   polygon = CreateNewPolygon (CURRENT, NoFlags ());
1217   saveID = polygon->ID;
1218   *polygon = Crosshair.AttachedPolygon;
1219   polygon->ID = saveID;
1220   SET_FLAG (CLEARPOLYFLAG, polygon);
1221   if (TEST_FLAG (NEWFULLPOLYFLAG, PCB))
1222     SET_FLAG (FULLPOLYFLAG, polygon);
1223   memset (&Crosshair.AttachedPolygon, 0, sizeof (PolygonType));
1224   SetPolygonBoundingBox (polygon);
1225   if (!CURRENT->polygon_tree)
1226     CURRENT->polygon_tree = r_create_tree (NULL, 0, 0);
1227   r_insert_entry (CURRENT->polygon_tree, (BoxType *) polygon, 0);
1228   InitClip (PCB->Data, CURRENT, polygon);
1229   DrawPolygon (CURRENT, polygon, 0);
1230   SetChangedFlag (True);
1231
1232   /* reset state of attached line */
1233   Crosshair.AttachedLine.State = STATE_FIRST;
1234   addedLines = 0;
1235
1236   /* add to undo list */
1237   AddObjectToCreateUndoList (POLYGON_TYPE, CURRENT, polygon, polygon);
1238   IncrementUndoSerialNumber ();
1239 }
1240
1241 /* find polygon holes in range, then call the callback function for
1242  * each hole. If the callback returns non-zero, stop
1243  * the search.
1244  */
1245 int
1246 PolygonHoles (PolygonType *polygon, const BoxType *range,
1247               int (*callback) (PLINE *contour, void *user_data),
1248               void *user_data)
1249 {
1250   POLYAREA *pa = polygon->Clipped;
1251   PLINE *pl;
1252   /* If this hole is so big the polygon doesn't exist, then it's not
1253    * really a hole.
1254    */
1255   if (!pa)
1256     return 0;
1257   for (pl = pa->contours->next; pl; pl = pl->next)
1258     {
1259       if (pl->xmin > range->X2 || pl->xmax < range->X1 ||
1260           pl->ymin > range->Y2 || pl->ymax < range->Y1)
1261         continue;
1262       if (callback (pl, user_data))
1263         {
1264           return 1;
1265         }
1266     }
1267   return 0;
1268 }
1269
1270 struct plow_info
1271 {
1272   int type;
1273   void *ptr1, *ptr2;
1274   LayerTypePtr layer;
1275   DataTypePtr data;
1276   int (*callback) (DataTypePtr, LayerTypePtr, PolygonTypePtr, int, void *,
1277                    void *);
1278 };
1279
1280 static int
1281 subtract_plow (DataTypePtr Data, LayerTypePtr Layer, PolygonTypePtr Polygon,
1282                int type, void *ptr1, void *ptr2)
1283 {
1284   if (!Polygon->Clipped)
1285     return 0;
1286   switch (type)
1287     {
1288     case PIN_TYPE:
1289     case VIA_TYPE:
1290       SubtractPin (Data, (PinTypePtr) ptr2, Layer, Polygon);
1291       return 1;
1292     case LINE_TYPE:
1293       SubtractLine ((LineTypePtr) ptr2, Polygon);
1294       return 1;
1295     case ARC_TYPE:
1296       SubtractArc ((ArcTypePtr) ptr2, Polygon);
1297       return 1;
1298     case PAD_TYPE:
1299       SubtractPad ((PadTypePtr) ptr2, Polygon);
1300       return 1;
1301     case TEXT_TYPE:
1302       SubtractText ((TextTypePtr) ptr2, Polygon);
1303       return 1;
1304     }
1305   return 0;
1306 }
1307
1308 static int
1309 add_plow (DataTypePtr Data, LayerTypePtr Layer, PolygonTypePtr Polygon,
1310           int type, void *ptr1, void *ptr2)
1311 {
1312   switch (type)
1313     {
1314     case PIN_TYPE:
1315     case VIA_TYPE:
1316       UnsubtractPin ((PinTypePtr) ptr2, Layer, Polygon);
1317       return 1;
1318     case LINE_TYPE:
1319       UnsubtractLine ((LineTypePtr) ptr2, Layer, Polygon);
1320       return 1;
1321     case ARC_TYPE:
1322       UnsubtractArc ((ArcTypePtr) ptr2, Layer, Polygon);
1323       return 1;
1324     case PAD_TYPE:
1325       UnsubtractPad ((PadTypePtr) ptr2, Layer, Polygon);
1326       return 1;
1327     case TEXT_TYPE:
1328       UnsubtractText ((TextTypePtr) ptr2, Layer, Polygon);
1329       return 1;
1330     }
1331   return 0;
1332 }
1333
1334 static int
1335 plow_callback (const BoxType * b, void *cl)
1336 {
1337   struct plow_info *plow = (struct plow_info *) cl;
1338   PolygonTypePtr polygon = (PolygonTypePtr) b;
1339
1340   if (TEST_FLAG (CLEARPOLYFLAG, polygon))
1341     return plow->callback (plow->data, plow->layer, polygon, plow->type,
1342                            plow->ptr1, plow->ptr2);
1343   return 0;
1344 }
1345
1346 int
1347 PlowsPolygon (DataType * Data, int type, void *ptr1, void *ptr2,
1348               int (*call_back) (DataTypePtr data, LayerTypePtr lay,
1349                                 PolygonTypePtr poly, int type, void *ptr1,
1350                                 void *ptr2))
1351 {
1352   BoxType sb = ((PinTypePtr) ptr2)->BoundingBox;
1353   int r = 0;
1354   struct plow_info info;
1355
1356   info.type = type;
1357   info.ptr1 = ptr1;
1358   info.ptr2 = ptr2;
1359   info.data = Data;
1360   info.callback = call_back;
1361   switch (type)
1362     {
1363     case PIN_TYPE:
1364     case VIA_TYPE:
1365       if (type == PIN_TYPE || ptr1 == ptr2 || ptr1 == NULL)
1366         {
1367           LAYER_LOOP (Data, max_layer);
1368           {
1369             info.layer = layer;
1370             r +=
1371               r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1372           }
1373           END_LOOP;
1374         }
1375       else
1376         {
1377           GROUP_LOOP (Data, GetLayerGroupNumberByNumber (GetLayerNumber (Data,
1378                                                                          ((LayerTypePtr) ptr1))));
1379           {
1380             info.layer = layer;
1381             r +=
1382               r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1383           }
1384           END_LOOP;
1385         }
1386       break;
1387     case LINE_TYPE:
1388     case ARC_TYPE:
1389     case TEXT_TYPE:
1390       /* the cast works equally well for lines and arcs */
1391       if (!TEST_FLAG (CLEARLINEFLAG, (LineTypePtr) ptr2))
1392         return 0;
1393       /* silk doesn't plow */
1394       if (GetLayerNumber (Data, ptr1) >= max_layer)
1395         return 0;
1396       GROUP_LOOP (Data, GetLayerGroupNumberByNumber (GetLayerNumber (Data,
1397                                                                      ((LayerTypePtr) ptr1))));
1398       {
1399         info.layer = layer;
1400         r += r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1401       }
1402       END_LOOP;
1403       break;
1404     case PAD_TYPE:
1405       {
1406         Cardinal group = TEST_FLAG (ONSOLDERFLAG,
1407                                     (PadType *) ptr2) ? SOLDER_LAYER :
1408           COMPONENT_LAYER;
1409         group = GetLayerGroupNumberByNumber (max_layer + group);
1410         GROUP_LOOP (Data, group);
1411         {
1412           info.layer = layer;
1413           r +=
1414             r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1415         }
1416         END_LOOP;
1417       }
1418       break;
1419
1420     case ELEMENT_TYPE:
1421       {
1422         PIN_LOOP ((ElementType *) ptr1);
1423         {
1424           PlowsPolygon (Data, PIN_TYPE, ptr1, pin, call_back);
1425         }
1426         END_LOOP;
1427         PAD_LOOP ((ElementType *) ptr1);
1428         {
1429           PlowsPolygon (Data, PAD_TYPE, ptr1, pad, call_back);
1430         }
1431         END_LOOP;
1432       }
1433       break;
1434     }
1435   return r;
1436 }
1437
1438 void
1439 RestoreToPolygon (DataType * Data, int type, void *ptr1, void *ptr2)
1440 {
1441   if (type == POLYGON_TYPE)
1442     InitClip (PCB->Data, (LayerTypePtr) ptr1, (PolygonTypePtr) ptr2);
1443   else
1444     PlowsPolygon (Data, type, ptr1, ptr2, add_plow);
1445 }
1446
1447 void
1448 ClearFromPolygon (DataType * Data, int type, void *ptr1, void *ptr2)
1449 {
1450   if (type == POLYGON_TYPE)
1451     InitClip (PCB->Data, (LayerTypePtr) ptr1, (PolygonTypePtr) ptr2);
1452   else
1453     PlowsPolygon (Data, type, ptr1, ptr2, subtract_plow);
1454 }
1455
1456 Boolean
1457 isects (POLYAREA * a, PolygonTypePtr p, Boolean fr)
1458 {
1459   POLYAREA *x;
1460   Boolean ans;
1461   ans = Touching (a, p->Clipped);
1462   /* argument may be register, so we must copy it */
1463   x = a;
1464   if (fr)
1465     poly_Free (&x);
1466   return ans;
1467 }
1468
1469
1470 Boolean
1471 IsPointInPolygon (LocationType X, LocationType Y, BDimension r,
1472                   PolygonTypePtr p)
1473 {
1474   POLYAREA *c;
1475   Vector v;
1476   v[0] = X;
1477   v[1] = Y;
1478   if (poly_CheckInside (p->Clipped, v))
1479     return True;
1480   if (r < 1)
1481     return False;
1482   if (!(c = CirclePoly (X, Y, r)))
1483     return False;
1484   return isects (c, p, True);
1485 }
1486
1487
1488 Boolean
1489 IsPointInPolygonIgnoreHoles (LocationType X, LocationType Y, PolygonTypePtr p)
1490 {
1491   Vector v;
1492   v[0] = X;
1493   v[1] = Y;
1494   return poly_InsideContour (p->Clipped->contours, v);
1495 }
1496
1497 Boolean
1498 IsRectangleInPolygon (LocationType X1, LocationType Y1, LocationType X2,
1499                       LocationType Y2, PolygonTypePtr p)
1500 {
1501   POLYAREA *s;
1502   if (!
1503       (s = RectPoly (min (X1, X2), max (X1, X2), min (Y1, Y2), max (Y1, Y2))))
1504     return False;
1505   return isects (s, p, True);
1506 }
1507
1508 static void
1509 r_NoHolesPolygonDicer (PLINE * p,
1510                        void (*emit) (PLINE *, void *), void *user_data)
1511 {
1512   POLYAREA *pa;
1513
1514   pa = (POLYAREA *) malloc (sizeof (*pa));
1515   pa->b = pa->f = pa;
1516   pa->contours = p;
1517   if (!p->next)                 /* no holes */
1518     {
1519       emit (p, user_data);
1520       poly_Free (&pa);
1521       return;
1522     }
1523   else
1524     {
1525       POLYAREA *poly2, *left, *right;
1526
1527       /* make a rectangle of the left region slicing through the middle of the first hole */
1528       poly2 =
1529         RectPoly (p->xmin, (p->next->xmin + p->next->xmax) / 2, p->ymin,
1530                   p->ymax);
1531       poly_AndSubtract_free (pa, poly2, &left, &right);
1532       if (left)
1533         {
1534           POLYAREA *x, *y;
1535           x = left;
1536           do
1537             {
1538               PLINE *pl = x->contours;
1539               r_NoHolesPolygonDicer (pl, emit, user_data);
1540               y = x->f;
1541               /* the pline was already freed by its use int he recursive dicer */
1542               free (x);
1543             }
1544           while ((x = y) != left);
1545         }
1546       if (right)
1547         {
1548           POLYAREA *x, *y;
1549           x = right;
1550           do
1551             {
1552               PLINE *pl = x->contours;
1553               r_NoHolesPolygonDicer (pl, emit, user_data);
1554               y = x->f;
1555               free (x);
1556             }
1557           while ((x = y) != right);
1558         }
1559     }
1560 }
1561
1562 void
1563 NoHolesPolygonDicer (PolygonTypePtr p, const BoxType * clip,
1564                      void (*emit) (PLINE *, void *), void *user_data)
1565 {
1566   POLYAREA *save, *ans;
1567
1568   ans = save = poly_Create ();
1569   /* copy the main poly only */
1570   poly_Copy1 (save, p->Clipped);
1571   /* clip to the bounding box */
1572   if (clip)
1573     {
1574       POLYAREA *cbox = RectPoly (clip->X1, clip->X2, clip->Y1, clip->Y2);
1575       if (cbox)
1576         {
1577           int r = poly_Boolean_free (save, cbox, &ans, PBO_ISECT);
1578           save = ans;
1579           if (r != err_ok)
1580             save = NULL;
1581         }
1582     }
1583   if (!save)
1584     return;
1585   /* now dice it up */
1586   do
1587     {
1588       POLYAREA *prev;
1589       r_NoHolesPolygonDicer (save->contours, emit, user_data);
1590       /* go to next poly (could be one because of clip) */
1591       prev = save;
1592       save = prev->f;
1593       /* free the previouse POLYAREA. Note the contour was consumed in the dicer */
1594       free (prev);
1595     }
1596   while (save != ans);
1597 }
1598
1599 /* make a polygon split into multiple parts into multiple polygons */
1600 Boolean
1601 MorphPolygon (LayerTypePtr layer, PolygonTypePtr poly)
1602 {
1603   POLYAREA *p, *start;
1604   Boolean many = False;
1605   FlagType flags;
1606
1607   if (!poly->Clipped || TEST_FLAG (LOCKFLAG, poly))
1608     return False;
1609   if (poly->Clipped->f == poly->Clipped)
1610     return False;
1611   ErasePolygon (poly);
1612   start = p = poly->Clipped;
1613   /* This is ugly. The creation of the new polygons can cause
1614    * all of the polygon pointers (including the one we're called
1615    * with to change if there is a realloc in GetPolygonMemory().
1616    * That will invalidate our original "poly" argument, potentially
1617    * inside the loop. We need to steal the Clipped pointer and
1618    * hide it from the Remove call so that it still exists while
1619    * we do this dirty work.
1620    */
1621   poly->Clipped = NULL;
1622   flags = poly->Flags;
1623   RemovePolygon (layer, poly);
1624   inhibit = True;
1625   do
1626     {
1627       VNODE *v;
1628       PolygonTypePtr new;
1629
1630       if (p->contours->area > PCB->IsleArea)
1631         {
1632           new = CreateNewPolygon (layer, flags);
1633           if (!new)
1634             return False;
1635           many = True;
1636           v = &p->contours->head;
1637           CreateNewPointInPolygon (new, v->point[0], v->point[1]);
1638           for (v = v->next; v != &p->contours->head; v = v->next)
1639             CreateNewPointInPolygon (new, v->point[0], v->point[1]);
1640           new->BoundingBox.X1 = p->contours->xmin;
1641           new->BoundingBox.X2 = p->contours->xmax + 1;
1642           new->BoundingBox.Y1 = p->contours->ymin;
1643           new->BoundingBox.Y2 = p->contours->ymax + 1;
1644           AddObjectToCreateUndoList (POLYGON_TYPE, layer, new, new);
1645           new->Clipped = p;
1646           p = p->f;             /* go to next pline */
1647           new->Clipped->b = new->Clipped->f = new->Clipped;     /* unlink from others */
1648           r_insert_entry (layer->polygon_tree, (BoxType *) new, 0);
1649           DrawPolygon (layer, new, 0);
1650         }
1651       else
1652         {
1653           POLYAREA *t = p;
1654
1655           p = p->f;
1656           poly_DelContour (&t->contours);
1657           free (t);
1658         }
1659     }
1660   while (p != start);
1661   inhibit = False;
1662   IncrementUndoSerialNumber ();
1663   return many;
1664 }
1665
1666 void debug_pline (PLINE *pl)
1667 {
1668   VNODE *v;
1669   fprintf (stderr, "\txmin %d xmax %d ymin %d ymax %d\n",
1670            pl->xmin, pl->xmax, pl->ymin, pl->ymax);
1671   v = &pl->head;
1672   while (v)
1673     {
1674       fprintf(stderr, "\t\tvnode: %d,%d\n", v->point[0], v->point[1]);
1675       v = v->next;
1676       if (v == &pl->head)
1677         break;
1678     }
1679 }
1680
1681 void
1682 debug_polyarea (POLYAREA *p)
1683 {
1684   PLINE *pl;
1685
1686   fprintf (stderr, "POLYAREA %p\n", p);
1687   for (pl=p->contours; pl; pl=pl->next)
1688     debug_pline (pl);
1689 }
1690
1691 void
1692 debug_polygon (PolygonType *p)
1693 {
1694   int i;
1695   POLYAREA *pa;
1696   fprintf (stderr, "POLYGON %p  %d pts\n", p, p->PointN);
1697   for (i=0; i<p->PointN; i++)
1698     fprintf(stderr, "\t%d: %d, %d\n", i, p->Points[i].X, p->Points[i].Y);
1699   pa = p->Clipped;
1700   while (pa)
1701     {
1702       debug_polyarea (pa);
1703       pa = pa->f;
1704       if (pa == p->Clipped)
1705         break;
1706     }
1707 }