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 static void
 124 add_noholes_polyarea (PLINE *pline, void *user_data)
 125 {
 126   PolygonType *poly = user_data;
 127
 128   /* Prepend the pline into the NoHoles linked list */
 129   pline->next = poly->NoHoles;
 130   poly->NoHoles = pline;
 131 }
 132
 133 void
 134 ComputeNoHoles (PolygonType *poly)
 135 {
 136   poly_FreeContours (&poly->NoHoles);
 137   if (poly->Clipped)
 138     NoHolesPolygonDicer (poly, NULL, add_noholes_polyarea, poly);
 139   else
 140     printf ("Compute_noholes caught poly->Clipped = NULL\n");
 141   poly->NoHolesValid = 1;
 142 }
 143
 144 static POLYAREA *
 145 biggest (POLYAREA * p)
 146 {
 147   POLYAREA *n, *top = NULL;
 148   PLINE *pl;
 149   double big = -1;
 150   if (!p)
 151     return NULL;
 152   n = p;
 153   do
 154     {
 155 #if 0
 156       if (n->contours->area < PCB->IsleArea)
 157         {
 158           n->b->f = n->f;
 159           n->f->b = n->b;
 160           poly_DelContour (&n->contours);
 161           if (n == p)
 162             p = n->f;
 163           n = n->f;
 164           if (!n->contours)
 165             {
 166               free (n);
 167               return NULL;
 168             }
 169         }
 170 #endif
 171       if (n->contours->area > big)
 172         {
 173           top = n;
 174           big = n->contours->area;
 175         }
 176     }
 177   while ((n = n->f) != p);
 178   assert (top);
 179   if (top == p)
 180     return p;
 181   pl = top->contours;
 182   top->contours = p->contours;
 183   p->contours = pl;
 184   assert (pl);
 185   assert (p->f);
 186   assert (p->b);
 187   return p;
 188 }
 189
 190 POLYAREA *
 191 ContourToPoly (PLINE * contour)
 192 {
 193   POLYAREA *p;
 194   poly_PreContour (contour, TRUE);
 195   assert (contour->Flags.orient == PLF_DIR);
 196   if (!(p = poly_Create ()))
 197     return NULL;
 198   poly_InclContour (p, contour);
 199   assert (poly_Valid (p));
 200   return p;
 201 }
 202
 203 static POLYAREA *
 204 original_poly (PolygonType * p)
 205 {
 206   PLINE *contour = NULL;
 207   POLYAREA *np = NULL;
 208   Vector v;
 209
 210   /* first make initial polygon contour */
 211   POLYGONPOINT_LOOP (p);
 212   {
 213     v[0] = point->X;
 214     v[1] = point->Y;
 215     if (contour == NULL)
 216       {
 217         if ((contour = poly_NewContour (v)) == NULL)
 218           return NULL;
 219       }
 220     else
 221       {
 222         poly_InclVertex (contour->head.prev, poly_CreateNode (v));
 223       }
 224   }
 225   END_LOOP;
 226   poly_PreContour (contour, TRUE);
 227   /* make sure it is a positive contour */
 228   if ((contour->Flags.orient) != PLF_DIR)
 229     poly_InvContour (contour);
 230   assert ((contour->Flags.orient) == PLF_DIR);
 231   if ((np = poly_Create ()) == NULL)
 232     return NULL;
 233   poly_InclContour (np, contour);
 234   assert (poly_Valid (np));
 235   return biggest (np);
 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   /* NB: the caller adds the last vertex, hence the -1 */
 312   range = CIRC_SEGS / range - 1;
 313   for (i = 0; i < range; i++)
 314     {
 315       /* rotate the vector */
 316       t1 = e1 * circleVerticies[2] - e2 * circleVerticies[3];
 317       e2 = e1 * circleVerticies[3] + e2 * circleVerticies[2];
 318       e1 = t1;
 319       v[0] = X + ROUND (e1);
 320       v[1] = Y + ROUND (e2);
 321       poly_InclVertex (c->head.prev, poly_CreateNode (v));
 322     }
 323 }
 324
 325 /* create a circle approximation from lines */
 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       if (p->NoHoles) printf ("Just leaked in Subtract\n");
 636       p->NoHoles = NULL;
 637       return -1;
 638     }
 639   p->Clipped = biggest (merged);
 640   assert (!p->Clipped || poly_Valid (p->Clipped));
 641   if (!p->Clipped)
 642     Message ("Polygon cleared out of existence near (%d, %d)\n",
 643              (p->BoundingBox.X1 + p->BoundingBox.X2) / 2,
 644              (p->BoundingBox.Y1 + p->BoundingBox.Y2) / 2);
 645   return 1;
 646 }
 647
 648 /* create a polygon of the pin clearance */
 649 POLYAREA *
 650 PinPoly (PinType * pin, BDimension thick, BDimension clear)
 651 {
 652   int size;
 653
 654   if (TEST_FLAG (SQUAREFLAG, pin))
 655     {
 656       size = (thick + 1) / 2;
 657       return RoundRect (pin->X - size, pin->X + size, pin->Y - size,
 658                         pin->Y + size, (clear + 1) / 2);
 659     }
 660   else
 661     {
 662       size = (thick + clear + 1) / 2;
 663       if (TEST_FLAG (OCTAGONFLAG, pin))
 664         {
 665           return OctagonPoly (pin->X, pin->Y, size + size);
 666         }
 667     }
 668   return CirclePoly (pin->X, pin->Y, size);
 669 }
 670
 671 POLYAREA *
 672 BoxPolyBloated (BoxType *box, BDimension bloat)
 673 {
 674   return RectPoly (box->X1 - bloat, box->X2 + bloat,
 675                    box->Y1 - bloat, box->Y2 + bloat);
 676 }
 677
 678 /* remove the pin clearance from the polygon */
 679 static int
 680 SubtractPin (DataType * d, PinType * pin, LayerType * l, PolygonType * p)
 681 {
 682   POLYAREA *np;
 683   Cardinal i;
 684
 685   if (pin->Clearance == 0)
 686     return 0;
 687   i = GetLayerNumber (d, l);
 688   if (TEST_THERM (i, pin))
 689     {
 690       np = ThermPoly ((PCBTypePtr) (d->pcb), pin, i);
 691       if (!np)
 692         return 0;
 693     }
 694   else
 695     {
 696       np = PinPoly (pin, pin->Thickness, pin->Clearance);
 697       if (!np)
 698         return -1;
 699     }
 700   return Subtract (np, p, TRUE);
 701 }
 702
 703 static int
 704 SubtractLine (LineType * line, PolygonType * p)
 705 {
 706   POLYAREA *np;
 707
 708   if (!TEST_FLAG (CLEARLINEFLAG, line))
 709     return 0;
 710   if (!(np = LinePoly (line, line->Thickness + line->Clearance)))
 711     return -1;
 712   return Subtract (np, p, True);
 713 }
 714
 715 static int
 716 SubtractArc (ArcType * arc, PolygonType * p)
 717 {
 718   POLYAREA *np;
 719
 720   if (!TEST_FLAG (CLEARLINEFLAG, arc))
 721     return 0;
 722   if (!(np = ArcPoly (arc, arc->Thickness + arc->Clearance)))
 723     return -1;
 724   return Subtract (np, p, True);
 725 }
 726
 727 static int
 728 SubtractText (TextType * text, PolygonType * p)
 729 {
 730   POLYAREA *np;
 731   const BoxType *b = &text->BoundingBox;
 732
 733   if (!TEST_FLAG (CLEARLINEFLAG, text))
 734     return 0;
 735   if (!(np = RoundRect (b->X1 + PCB->Bloat, b->X2 - PCB->Bloat,
 736                         b->Y1 + PCB->Bloat, b->Y2 - PCB->Bloat, PCB->Bloat)))
 737     return -1;
 738   return Subtract (np, p, True);
 739 }
 740
 741 static int
 742 SubtractPad (PadType * pad, PolygonType * p)
 743 {
 744   POLYAREA *np = NULL;
 745
 746   if (pad->Clearance == 0)
 747     return 0;
 748   if (TEST_FLAG (SQUAREFLAG, pad))
 749     {
 750       if (!
 751           (np = SquarePadPoly (pad, pad->Thickness + pad->Clearance)))
 752         return -1;
 753     }
 754   else
 755     {
 756       if (!
 757           (np = LinePoly ((LineType *) pad, pad->Thickness + pad->Clearance)))
 758         return -1;
 759     }
 760   return Subtract (np, p, True);
 761 }
 762
 763 struct cpInfo
 764 {
 765   const BoxType *other;
 766   DataType *data;
 767   LayerType *layer;
 768   PolygonType *polygon;
 769   Boolean solder;
 770   jmp_buf env;
 771 };
 772
 773 static int
 774 pin_sub_callback (const BoxType * b, void *cl)
 775 {
 776   PinTypePtr pin = (PinTypePtr) b;
 777   struct cpInfo *info = (struct cpInfo *) cl;
 778   PolygonTypePtr polygon;
 779
 780   /* don't subtract the object that was put back! */
 781   if (b == info->other)
 782     return 0;
 783   polygon = info->polygon;
 784   if (SubtractPin (info->data, pin, info->layer, polygon) < 0)
 785     longjmp (info->env, 1);
 786   return 1;
 787 }
 788
 789 static int
 790 arc_sub_callback (const BoxType * b, void *cl)
 791 {
 792   ArcTypePtr arc = (ArcTypePtr) b;
 793   struct cpInfo *info = (struct cpInfo *) cl;
 794   PolygonTypePtr polygon;
 795
 796   /* don't subtract the object that was put back! */
 797   if (b == info->other)
 798     return 0;
 799   if (!TEST_FLAG (CLEARLINEFLAG, arc))
 800     return 0;
 801   polygon = info->polygon;
 802   if (SubtractArc (arc, polygon) < 0)
 803     longjmp (info->env, 1);
 804   return 1;
 805 }
 806
 807 static int
 808 pad_sub_callback (const BoxType * b, void *cl)
 809 {
 810   PadTypePtr pad = (PadTypePtr) b;
 811   struct cpInfo *info = (struct cpInfo *) cl;
 812   PolygonTypePtr polygon;
 813
 814   /* don't subtract the object that was put back! */
 815   if (b == info->other)
 816     return 0;
 817   if (pad->Clearance == 0)
 818     return 0;
 819   polygon = info->polygon;
 820   if (XOR (TEST_FLAG (ONSOLDERFLAG, pad), !info->solder))
 821     {
 822       if (SubtractPad (pad, polygon) < 0)
 823         longjmp (info->env, 1);
 824       return 1;
 825     }
 826   return 0;
 827 }
 828
 829 static int
 830 line_sub_callback (const BoxType * b, void *cl)
 831 {
 832   LineTypePtr line = (LineTypePtr) b;
 833   struct cpInfo *info = (struct cpInfo *) cl;
 834   PolygonTypePtr polygon;
 835
 836   /* don't subtract the object that was put back! */
 837   if (b == info->other)
 838     return 0;
 839   if (!TEST_FLAG (CLEARLINEFLAG, line))
 840     return 0;
 841   polygon = info->polygon;
 842   if (SubtractLine (line, polygon) < 0)
 843     longjmp (info->env, 1);
 844   return 1;
 845 }
 846
 847 static int
 848 text_sub_callback (const BoxType * b, void *cl)
 849 {
 850   TextTypePtr text = (TextTypePtr) b;
 851   struct cpInfo *info = (struct cpInfo *) cl;
 852   PolygonTypePtr polygon;
 853
 854   /* don't subtract the object that was put back! */
 855   if (b == info->other)
 856     return 0;
 857   if (!TEST_FLAG (CLEARLINEFLAG, text))
 858     return 0;
 859   polygon = info->polygon;
 860   if (SubtractText (text, polygon) < 0)
 861     longjmp (info->env, 1);
 862   return 1;
 863 }
 864
 865 static int
 866 Group (DataTypePtr Data, Cardinal layer)
 867 {
 868   Cardinal i, j;
 869   for (i = 0; i < max_layer; i++)
 870     for (j = 0; j < ((PCBType *) (Data->pcb))->LayerGroups.Number[i]; j++)
 871       if (layer == ((PCBType *) (Data->pcb))->LayerGroups.Entries[i][j])
 872         return i;
 873   return i;
 874 }
 875
 876 static int
 877 clearPoly (DataTypePtr Data, LayerTypePtr Layer, PolygonType * polygon,
 878            const BoxType * here, BDimension expand)
 879 {
 880   int r = 0;
 881   BoxType region;
 882   struct cpInfo info;
 883   Cardinal group;
 884
 885   if (!TEST_FLAG (CLEARPOLYFLAG, polygon)
 886       || GetLayerNumber (Data, Layer) >= max_layer)
 887     return 0;
 888   group = Group (Data, GetLayerNumber (Data, Layer));
 889   info.solder = (group == Group (Data, max_layer + SOLDER_LAYER));
 890   info.data = Data;
 891   info.other = here;
 892   info.layer = Layer;
 893   info.polygon = polygon;
 894   if (here)
 895     region = clip_box (here, &polygon->BoundingBox);
 896   else
 897     region = polygon->BoundingBox;
 898   region = bloat_box (&region, expand);
 899
 900   if (setjmp (info.env) == 0)
 901     {
 902       r = r_search (Data->via_tree, &region, NULL, pin_sub_callback, &info);
 903       r += r_search (Data->pin_tree, &region, NULL, pin_sub_callback, &info);
 904       GROUP_LOOP (Data, group);
 905       {
 906         r +=
 907           r_search (layer->line_tree, &region, NULL, line_sub_callback,
 908                     &info);
 909         r +=
 910           r_search (layer->arc_tree, &region, NULL, arc_sub_callback, &info);
 911         r +=
 912           r_search (layer->text_tree, &region, NULL, text_sub_callback, &info);
 913       }
 914       END_LOOP;
 915       if (info.solder || group == Group (Data, max_layer + COMPONENT_LAYER))
 916         r += r_search (Data->pad_tree, &region, NULL, pad_sub_callback, &info);
 917     }
 918   polygon->NoHolesValid = 0;
 919   return r;
 920 }
 921
 922 static int
 923 Unsubtract (POLYAREA * np1, PolygonType * p)
 924 {
 925   POLYAREA *merged = NULL, *np = np1;
 926   POLYAREA *orig_poly, *clipped_np;
 927   int x;
 928   assert (np);
 929   assert (p && p->Clipped);
 930
 931   orig_poly = original_poly (p);
 932
 933   x = poly_Boolean_free (np, orig_poly, &clipped_np, PBO_ISECT);
 934   if (x != err_ok)
 935     {
 936       fprintf (stderr, "Error while clipping PBO_ISECT: %d\n", x);
 937       poly_Free (&clipped_np);
 938       goto fail;
 939     }
 940
 941   x = poly_Boolean_free (p->Clipped, clipped_np, &merged, PBO_UNITE);
 942   if (x != err_ok)
 943     {
 944       fprintf (stderr, "Error while clipping PBO_UNITE: %d\n", x);
 945       poly_Free (&merged);
 946       goto fail;
 947     }
 948   p->Clipped = biggest (merged);
 949   assert (!p->Clipped || poly_Valid (p->Clipped));
 950   return 1;
 951
 952 fail:
 953   p->Clipped = NULL;
 954   if (p->NoHoles) printf ("Just leaked in Unsubtract\n");
 955   p->NoHoles = NULL;
 956   return 0;
 957 }
 958
 959 static int
 960 UnsubtractPin (PinType * pin, LayerType * l, PolygonType * p)
 961 {
 962   POLYAREA *np;
 963
 964   /* overlap a bit to prevent gaps from rounding errors */
 965   np = BoxPolyBloated (&pin->BoundingBox, UNSUBTRACT_BLOAT);
 966
 967   if (!np)
 968     return 0;
 969   if (!Unsubtract (np, p))
 970     return 0;
 971   clearPoly (PCB->Data, l, p, (const BoxType *) pin, 2 * UNSUBTRACT_BLOAT);
 972   return 1;
 973 }
 974
 975 static int
 976 UnsubtractArc (ArcType * arc, LayerType * l, PolygonType * p)
 977 {
 978   POLYAREA *np;
 979
 980   if (!TEST_FLAG (CLEARLINEFLAG, arc))
 981     return 0;
 982
 983   /* overlap a bit to prevent gaps from rounding errors */
 984   np = BoxPolyBloated (&arc->BoundingBox, UNSUBTRACT_BLOAT);
 985
 986   if (!np)
 987     return 0;
 988   if (!Unsubtract (np, p))
 989     return 0;
 990   clearPoly (PCB->Data, l, p, (const BoxType *) arc, 2 * UNSUBTRACT_BLOAT);
 991   return 1;
 992 }
 993
 994 static int
 995 UnsubtractLine (LineType * line, LayerType * l, PolygonType * p)
 996 {
 997   POLYAREA *np;
 998
 999   if (!TEST_FLAG (CLEARLINEFLAG, line))
1000     return 0;
1001
1002   /* overlap a bit to prevent notches from rounding errors */
1003   np = BoxPolyBloated (&line->BoundingBox, UNSUBTRACT_BLOAT);
1004
1005   if (!np)
1006     return 0;
1007   if (!Unsubtract (np, p))
1008     return 0;
1009   clearPoly (PCB->Data, l, p, (const BoxType *) line, 2 * UNSUBTRACT_BLOAT);
1010   return 1;
1011 }
1012
1013 static int
1014 UnsubtractText (TextType * text, LayerType * l, PolygonType * p)
1015 {
1016   POLYAREA *np;
1017
1018   if (!TEST_FLAG (CLEARLINEFLAG, text))
1019     return 0;
1020
1021   /* overlap a bit to prevent notches from rounding errors */
1022   np = BoxPolyBloated (&text->BoundingBox, UNSUBTRACT_BLOAT);
1023
1024   if (!np)
1025     return -1;
1026   if (!Unsubtract (np, p))
1027     return 0;
1028   clearPoly (PCB->Data, l, p, (const BoxType *) text, 2 * UNSUBTRACT_BLOAT);
1029   return 1;
1030 }
1031
1032 static int
1033 UnsubtractPad (PadType * pad, LayerType * l, PolygonType * p)
1034 {
1035   POLYAREA *np;
1036
1037   /* overlap a bit to prevent notches from rounding errors */
1038   np = BoxPolyBloated (&pad->BoundingBox, UNSUBTRACT_BLOAT);
1039
1040   if (!np)
1041     return 0;
1042   if (!Unsubtract (np, p))
1043     return 0;
1044   clearPoly (PCB->Data, l, p, (const BoxType *) pad, 2 * UNSUBTRACT_BLOAT);
1045   return 1;
1046 }
1047
1048 static Boolean inhibit = False;
1049
1050 int
1051 InitClip (DataTypePtr Data, LayerTypePtr layer, PolygonType * p)
1052 {
1053   if (inhibit)
1054     return 0;
1055   if (p->Clipped)
1056     poly_Free (&p->Clipped);
1057   p->Clipped = original_poly (p);
1058   poly_FreeContours (&p->NoHoles);
1059   if (!p->Clipped)
1060     return 0;
1061   assert (poly_Valid (p->Clipped));
1062   if (TEST_FLAG (CLEARPOLYFLAG, p))
1063     clearPoly (Data, layer, p, NULL, 0);
1064   else
1065     p->NoHolesValid = 0;
1066   return 1;
1067 }
1068
1069 /* --------------------------------------------------------------------------
1070  * remove redundant polygon points. Any point that lies on the straight
1071  * line between the points on either side of it is redundant.
1072  * returns true if any points are removed
1073  */
1074 Boolean
1075 RemoveExcessPolygonPoints (LayerTypePtr Layer, PolygonTypePtr Polygon)
1076 {
1077   PointTypePtr pt1, pt2, pt3;
1078   Cardinal n;
1079   LineType line;
1080   Boolean changed = False;
1081
1082   if (Undoing ())
1083     return (False);
1084   /* there are always at least three points in a polygon */
1085   pt1 = &Polygon->Points[Polygon->PointN - 1];
1086   pt2 = &Polygon->Points[0];
1087   pt3 = &Polygon->Points[1];
1088   for (n = 0; n < Polygon->PointN; n++, pt1++, pt2++, pt3++)
1089     {
1090       /* wrap around polygon */
1091       if (n == 1)
1092         pt1 = &Polygon->Points[0];
1093       if (n == Polygon->PointN - 1)
1094         pt3 = &Polygon->Points[0];
1095       line.Point1 = *pt1;
1096       line.Point2 = *pt3;
1097       line.Thickness = 0;
1098       if (IsPointOnLine ((float) pt2->X, (float) pt2->Y, 0.0, &line))
1099         {
1100           RemoveObject (POLYGONPOINT_TYPE, (void *) Layer, (void *) Polygon,
1101                         (void *) pt2);
1102           changed = True;
1103         }
1104     }
1105   return (changed);
1106 }
1107
1108 /* ---------------------------------------------------------------------------
1109  * returns the index of the polygon point which is the end
1110  * point of the segment with the lowest distance to the passed
1111  * coordinates
1112  */
1113 Cardinal
1114 GetLowestDistancePolygonPoint (PolygonTypePtr Polygon, LocationType X,
1115                                LocationType Y)
1116 {
1117   double mindistance = (double) MAX_COORD * MAX_COORD;
1118   PointTypePtr ptr1 = &Polygon->Points[Polygon->PointN - 1],
1119     ptr2 = &Polygon->Points[0];
1120   Cardinal n, result = 0;
1121
1122   /* we calculate the distance to each segment and choose the
1123    * shortest distance. If the closest approach between the
1124    * given point and the projected line (i.e. the segment extended)
1125    * is not on the segment, then the distance is the distance
1126    * to the segment end point.
1127    */
1128
1129   for (n = 0; n < Polygon->PointN; n++, ptr2++)
1130     {
1131       register double u, dx, dy;
1132       dx = ptr2->X - ptr1->X;
1133       dy = ptr2->Y - ptr1->Y;
1134       if (dx != 0.0 || dy != 0.0)
1135         {
1136           /* projected intersection is at P1 + u(P2 - P1) */
1137           u = ((X - ptr1->X) * dx + (Y - ptr1->Y) * dy) / (dx * dx + dy * dy);
1138
1139           if (u < 0.0)
1140             {                   /* ptr1 is closest point */
1141               u = SQUARE (X - ptr1->X) + SQUARE (Y - ptr1->Y);
1142             }
1143           else if (u > 1.0)
1144             {                   /* ptr2 is closest point */
1145               u = SQUARE (X - ptr2->X) + SQUARE (Y - ptr2->Y);
1146             }
1147           else
1148             {                   /* projected intersection is closest point */
1149               u = SQUARE (X - ptr1->X * (1.0 - u) - u * ptr2->X) +
1150                 SQUARE (Y - ptr1->Y * (1.0 - u) - u * ptr2->Y);
1151             }
1152           if (u < mindistance)
1153             {
1154               mindistance = u;
1155               result = n;
1156             }
1157         }
1158       ptr1 = ptr2;
1159     }
1160   return (result);
1161 }
1162
1163 /* ---------------------------------------------------------------------------
1164  * go back to the  previous point of the polygon
1165  */
1166 void
1167 GoToPreviousPoint (void)
1168 {
1169   switch (Crosshair.AttachedPolygon.PointN)
1170     {
1171       /* do nothing if mode has just been entered */
1172     case 0:
1173       break;
1174
1175       /* reset number of points and 'LINE_MODE' state */
1176     case 1:
1177       Crosshair.AttachedPolygon.PointN = 0;
1178       Crosshair.AttachedLine.State = STATE_FIRST;
1179       addedLines = 0;
1180       break;
1181
1182       /* back-up one point */
1183     default:
1184       {
1185         PointTypePtr points = Crosshair.AttachedPolygon.Points;
1186         Cardinal n = Crosshair.AttachedPolygon.PointN - 2;
1187
1188         Crosshair.AttachedPolygon.PointN--;
1189         Crosshair.AttachedLine.Point1.X = points[n].X;
1190         Crosshair.AttachedLine.Point1.Y = points[n].Y;
1191         break;
1192       }
1193     }
1194 }
1195
1196 /* ---------------------------------------------------------------------------
1197  * close polygon if possible
1198  */
1199 void
1200 ClosePolygon (void)
1201 {
1202   Cardinal n = Crosshair.AttachedPolygon.PointN;
1203
1204   /* check number of points */
1205   if (n >= 3)
1206     {
1207       /* if 45 degree lines are what we want do a quick check
1208        * if closing the polygon makes sense
1209        */
1210       if (!TEST_FLAG (ALLDIRECTIONFLAG, PCB))
1211         {
1212           BDimension dx, dy;
1213
1214           dx = abs (Crosshair.AttachedPolygon.Points[n - 1].X -
1215                     Crosshair.AttachedPolygon.Points[0].X);
1216           dy = abs (Crosshair.AttachedPolygon.Points[n - 1].Y -
1217                     Crosshair.AttachedPolygon.Points[0].Y);
1218           if (!(dx == 0 || dy == 0 || dx == dy))
1219             {
1220               Message
1221                 (_
1222                  ("Cannot close polygon because 45 degree lines are requested.\n"));
1223               return;
1224             }
1225         }
1226       CopyAttachedPolygonToLayer ();
1227       Draw ();
1228     }
1229   else
1230     Message (_("A polygon has to have at least 3 points\n"));
1231 }
1232
1233 /* ---------------------------------------------------------------------------
1234  * moves the data of the attached (new) polygon to the current layer
1235  */
1236 void
1237 CopyAttachedPolygonToLayer (void)
1238 {
1239   PolygonTypePtr polygon;
1240   int saveID;
1241
1242   /* move data to layer and clear attached struct */
1243   polygon = CreateNewPolygon (CURRENT, NoFlags ());
1244   saveID = polygon->ID;
1245   *polygon = Crosshair.AttachedPolygon;
1246   polygon->ID = saveID;
1247   SET_FLAG (CLEARPOLYFLAG, polygon);
1248   if (TEST_FLAG (NEWFULLPOLYFLAG, PCB))
1249     SET_FLAG (FULLPOLYFLAG, polygon);
1250   memset (&Crosshair.AttachedPolygon, 0, sizeof (PolygonType));
1251   SetPolygonBoundingBox (polygon);
1252   if (!CURRENT->polygon_tree)
1253     CURRENT->polygon_tree = r_create_tree (NULL, 0, 0);
1254   r_insert_entry (CURRENT->polygon_tree, (BoxType *) polygon, 0);
1255   InitClip (PCB->Data, CURRENT, polygon);
1256   DrawPolygon (CURRENT, polygon, 0);
1257   SetChangedFlag (True);
1258
1259   /* reset state of attached line */
1260   Crosshair.AttachedLine.State = STATE_FIRST;
1261   addedLines = 0;
1262
1263   /* add to undo list */
1264   AddObjectToCreateUndoList (POLYGON_TYPE, CURRENT, polygon, polygon);
1265   IncrementUndoSerialNumber ();
1266 }
1267
1268 /* find polygon holes in range, then call the callback function for
1269  * each hole. If the callback returns non-zero, stop
1270  * the search.
1271  */
1272 int
1273 PolygonHoles (PolygonType *polygon, const BoxType *range,
1274               int (*callback) (PLINE *contour, void *user_data),
1275               void *user_data)
1276 {
1277   POLYAREA *pa = polygon->Clipped;
1278   PLINE *pl;
1279   /* If this hole is so big the polygon doesn't exist, then it's not
1280    * really a hole.
1281    */
1282   if (!pa)
1283     return 0;
1284   for (pl = pa->contours->next; pl; pl = pl->next)
1285     {
1286       if (range != NULL &&
1287           (pl->xmin > range->X2 || pl->xmax < range->X1 ||
1288            pl->ymin > range->Y2 || pl->ymax < range->Y1))
1289         continue;
1290       if (callback (pl, user_data))
1291         {
1292           return 1;
1293         }
1294     }
1295   return 0;
1296 }
1297
1298 struct plow_info
1299 {
1300   int type;
1301   void *ptr1, *ptr2;
1302   LayerTypePtr layer;
1303   DataTypePtr data;
1304   int (*callback) (DataTypePtr, LayerTypePtr, PolygonTypePtr, int, void *,
1305                    void *);
1306 };
1307
1308 static int
1309 subtract_plow (DataTypePtr Data, LayerTypePtr Layer, PolygonTypePtr Polygon,
1310                int type, void *ptr1, void *ptr2)
1311 {
1312   if (!Polygon->Clipped)
1313     return 0;
1314   switch (type)
1315     {
1316     case PIN_TYPE:
1317     case VIA_TYPE:
1318       SubtractPin (Data, (PinTypePtr) ptr2, Layer, Polygon);
1319       Polygon->NoHolesValid = 0;
1320       return 1;
1321     case LINE_TYPE:
1322       SubtractLine ((LineTypePtr) ptr2, Polygon);
1323       Polygon->NoHolesValid = 0;
1324       return 1;
1325     case ARC_TYPE:
1326       SubtractArc ((ArcTypePtr) ptr2, Polygon);
1327       Polygon->NoHolesValid = 0;
1328       return 1;
1329     case PAD_TYPE:
1330       SubtractPad ((PadTypePtr) ptr2, Polygon);
1331       Polygon->NoHolesValid = 0;
1332       return 1;
1333     case TEXT_TYPE:
1334       SubtractText ((TextTypePtr) ptr2, Polygon);
1335       Polygon->NoHolesValid = 0;
1336       return 1;
1337     }
1338   return 0;
1339 }
1340
1341 static int
1342 add_plow (DataTypePtr Data, LayerTypePtr Layer, PolygonTypePtr Polygon,
1343           int type, void *ptr1, void *ptr2)
1344 {
1345   switch (type)
1346     {
1347     case PIN_TYPE:
1348     case VIA_TYPE:
1349       UnsubtractPin ((PinTypePtr) ptr2, Layer, Polygon);
1350       return 1;
1351     case LINE_TYPE:
1352       UnsubtractLine ((LineTypePtr) ptr2, Layer, Polygon);
1353       return 1;
1354     case ARC_TYPE:
1355       UnsubtractArc ((ArcTypePtr) ptr2, Layer, Polygon);
1356       return 1;
1357     case PAD_TYPE:
1358       UnsubtractPad ((PadTypePtr) ptr2, Layer, Polygon);
1359       return 1;
1360     case TEXT_TYPE:
1361       UnsubtractText ((TextTypePtr) ptr2, Layer, Polygon);
1362       return 1;
1363     }
1364   return 0;
1365 }
1366
1367 static int
1368 plow_callback (const BoxType * b, void *cl)
1369 {
1370   struct plow_info *plow = (struct plow_info *) cl;
1371   PolygonTypePtr polygon = (PolygonTypePtr) b;
1372
1373   if (TEST_FLAG (CLEARPOLYFLAG, polygon))
1374     return plow->callback (plow->data, plow->layer, polygon, plow->type,
1375                            plow->ptr1, plow->ptr2);
1376   return 0;
1377 }
1378
1379 int
1380 PlowsPolygon (DataType * Data, int type, void *ptr1, void *ptr2,
1381               int (*call_back) (DataTypePtr data, LayerTypePtr lay,
1382                                 PolygonTypePtr poly, int type, void *ptr1,
1383                                 void *ptr2))
1384 {
1385   BoxType sb = ((PinTypePtr) ptr2)->BoundingBox;
1386   int r = 0;
1387   struct plow_info info;
1388
1389   info.type = type;
1390   info.ptr1 = ptr1;
1391   info.ptr2 = ptr2;
1392   info.data = Data;
1393   info.callback = call_back;
1394   switch (type)
1395     {
1396     case PIN_TYPE:
1397     case VIA_TYPE:
1398       if (type == PIN_TYPE || ptr1 == ptr2 || ptr1 == NULL)
1399         {
1400           LAYER_LOOP (Data, max_layer);
1401           {
1402             info.layer = layer;
1403             r +=
1404               r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1405           }
1406           END_LOOP;
1407         }
1408       else
1409         {
1410           GROUP_LOOP (Data, GetLayerGroupNumberByNumber (GetLayerNumber (Data,
1411                                                                          ((LayerTypePtr) ptr1))));
1412           {
1413             info.layer = layer;
1414             r +=
1415               r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1416           }
1417           END_LOOP;
1418         }
1419       break;
1420     case LINE_TYPE:
1421     case ARC_TYPE:
1422     case TEXT_TYPE:
1423       /* the cast works equally well for lines and arcs */
1424       if (!TEST_FLAG (CLEARLINEFLAG, (LineTypePtr) ptr2))
1425         return 0;
1426       /* silk doesn't plow */
1427       if (GetLayerNumber (Data, ptr1) >= max_layer)
1428         return 0;
1429       GROUP_LOOP (Data, GetLayerGroupNumberByNumber (GetLayerNumber (Data,
1430                                                                      ((LayerTypePtr) ptr1))));
1431       {
1432         info.layer = layer;
1433         r += r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1434       }
1435       END_LOOP;
1436       break;
1437     case PAD_TYPE:
1438       {
1439         Cardinal group = TEST_FLAG (ONSOLDERFLAG,
1440                                     (PadType *) ptr2) ? SOLDER_LAYER :
1441           COMPONENT_LAYER;
1442         group = GetLayerGroupNumberByNumber (max_layer + group);
1443         GROUP_LOOP (Data, group);
1444         {
1445           info.layer = layer;
1446           r +=
1447             r_search (layer->polygon_tree, &sb, NULL, plow_callback, &info);
1448         }
1449         END_LOOP;
1450       }
1451       break;
1452
1453     case ELEMENT_TYPE:
1454       {
1455         PIN_LOOP ((ElementType *) ptr1);
1456         {
1457           PlowsPolygon (Data, PIN_TYPE, ptr1, pin, call_back);
1458         }
1459         END_LOOP;
1460         PAD_LOOP ((ElementType *) ptr1);
1461         {
1462           PlowsPolygon (Data, PAD_TYPE, ptr1, pad, call_back);
1463         }
1464         END_LOOP;
1465       }
1466       break;
1467     }
1468   return r;
1469 }
1470
1471 void
1472 RestoreToPolygon (DataType * Data, int type, void *ptr1, void *ptr2)
1473 {
1474   if (type == POLYGON_TYPE)
1475     InitClip (PCB->Data, (LayerTypePtr) ptr1, (PolygonTypePtr) ptr2);
1476   else
1477     PlowsPolygon (Data, type, ptr1, ptr2, add_plow);
1478 }
1479
1480 void
1481 ClearFromPolygon (DataType * Data, int type, void *ptr1, void *ptr2)
1482 {
1483   if (type == POLYGON_TYPE)
1484     InitClip (PCB->Data, (LayerTypePtr) ptr1, (PolygonTypePtr) ptr2);
1485   else
1486     PlowsPolygon (Data, type, ptr1, ptr2, subtract_plow);
1487 }
1488
1489 Boolean
1490 isects (POLYAREA * a, PolygonTypePtr p, Boolean fr)
1491 {
1492   POLYAREA *x;
1493   Boolean ans;
1494   ans = Touching (a, p->Clipped);
1495   /* argument may be register, so we must copy it */
1496   x = a;
1497   if (fr)
1498     poly_Free (&x);
1499   return ans;
1500 }
1501
1502
1503 Boolean
1504 IsPointInPolygon (LocationType X, LocationType Y, BDimension r,
1505                   PolygonTypePtr p)
1506 {
1507   POLYAREA *c;
1508   Vector v;
1509   v[0] = X;
1510   v[1] = Y;
1511   if (poly_CheckInside (p->Clipped, v))
1512     return True;
1513   if (r < 1)
1514     return False;
1515   if (!(c = CirclePoly (X, Y, r)))
1516     return False;
1517   return isects (c, p, True);
1518 }
1519
1520
1521 Boolean
1522 IsPointInPolygonIgnoreHoles (LocationType X, LocationType Y, PolygonTypePtr p)
1523 {
1524   Vector v;
1525   v[0] = X;
1526   v[1] = Y;
1527   return poly_InsideContour (p->Clipped->contours, v);
1528 }
1529
1530 Boolean
1531 IsRectangleInPolygon (LocationType X1, LocationType Y1, LocationType X2,
1532                       LocationType Y2, PolygonTypePtr p)
1533 {
1534   POLYAREA *s;
1535   if (!
1536       (s = RectPoly (min (X1, X2), max (X1, X2), min (Y1, Y2), max (Y1, Y2))))
1537     return False;
1538   return isects (s, p, True);
1539 }
1540
1541 /* NB: This function will free the passed POLYAREA.
1542  *     It must only be passed a single POLYAREA (pa->f == pa->b == pa)
1543  */
1544 static void
1545 r_NoHolesPolygonDicer (POLYAREA * pa,
1546                        void (*emit) (PLINE *, void *), void *user_data)
1547 {
1548   PLINE *p = pa->contours;
1549
1550   if (!pa->contours->next)                 /* no holes */
1551     {
1552       pa->contours = NULL; /* The callback now owns the contour */
1553       emit (p, user_data);
1554       poly_Free (&pa);
1555       return;
1556     }
1557   else
1558     {
1559       POLYAREA *poly2, *left, *right;
1560
1561       /* make a rectangle of the left region slicing through the middle of the first hole */
1562       poly2 = RectPoly (p->xmin, (p->next->xmin + p->next->xmax) / 2,
1563                         p->ymin, p->ymax);
1564       poly_AndSubtract_free (pa, poly2, &left, &right);
1565       if (left)
1566         {
1567           POLYAREA *cur, *next;
1568           cur = left;
1569           do
1570             {
1571               next = cur->f;
1572               cur->f = cur->b = cur; /* Detach this polygon piece */
1573               r_NoHolesPolygonDicer (cur, emit, user_data);
1574               /* NB: The POLYAREA was freed by its use in the recursive dicer */
1575             }
1576           while ((cur = next) != left);
1577         }
1578       if (right)
1579         {
1580           POLYAREA *cur, *next;
1581           cur = right;
1582           do
1583             {
1584               next = cur->f;
1585               cur->f = cur->b = cur; /* Detach this polygon piece */
1586               r_NoHolesPolygonDicer (cur, emit, user_data);
1587               /* NB: The POLYAREA was freed by its use in the recursive dicer */
1588             }
1589           while ((cur = next) != right);
1590         }
1591     }
1592 }
1593
1594 void
1595 NoHolesPolygonDicer (PolygonTypePtr p, const BoxType * clip,
1596                      void (*emit) (PLINE *, void *), void *user_data)
1597 {
1598   POLYAREA *save, *ans, *cur, *next;
1599
1600   ans = save = poly_Create ();
1601   /* copy the main poly only */
1602   poly_Copy1 (save, p->Clipped);
1603   /* clip to the bounding box */
1604   if (clip)
1605     {
1606       POLYAREA *cbox = RectPoly (clip->X1, clip->X2, clip->Y1, clip->Y2);
1607       if (cbox)
1608         {
1609           int r = poly_Boolean_free (save, cbox, &ans, PBO_ISECT);
1610           save = ans;
1611           if (r != err_ok)
1612             save = NULL;
1613         }
1614     }
1615   if (!save)
1616     return;
1617   /* Now dice it up.
1618    * NB: Could be more than one piece (because of the clip above)
1619    */
1620   cur = save;
1621   do
1622     {
1623       next = cur->f;
1624       cur->f = cur->b = cur; /* Detach this polygon piece */
1625       r_NoHolesPolygonDicer (cur, emit, user_data);
1626       /* NB: The POLYAREA was freed by its use in the recursive dicer */
1627     }
1628   while ((cur = next) != save);
1629 }
1630
1631 /* make a polygon split into multiple parts into multiple polygons */
1632 Boolean
1633 MorphPolygon (LayerTypePtr layer, PolygonTypePtr poly)
1634 {
1635   POLYAREA *p, *start;
1636   Boolean many = False;
1637   FlagType flags;
1638
1639   if (!poly->Clipped || TEST_FLAG (LOCKFLAG, poly))
1640     return False;
1641   if (poly->Clipped->f == poly->Clipped)
1642     return False;
1643   ErasePolygon (poly);
1644   start = p = poly->Clipped;
1645   /* This is ugly. The creation of the new polygons can cause
1646    * all of the polygon pointers (including the one we're called
1647    * with to change if there is a realloc in GetPolygonMemory().
1648    * That will invalidate our original "poly" argument, potentially
1649    * inside the loop. We need to steal the Clipped pointer and
1650    * hide it from the Remove call so that it still exists while
1651    * we do this dirty work.
1652    */
1653   poly->Clipped = NULL;
1654   if (poly->NoHoles) printf ("Just leaked in MorpyPolygon\n");
1655   poly->NoHoles = NULL;
1656   flags = poly->Flags;
1657   RemovePolygon (layer, poly);
1658   inhibit = True;
1659   do
1660     {
1661       VNODE *v;
1662       PolygonTypePtr new;
1663
1664       if (p->contours->area > PCB->IsleArea)
1665         {
1666           new = CreateNewPolygon (layer, flags);
1667           if (!new)
1668             return False;
1669           many = True;
1670           v = &p->contours->head;
1671           CreateNewPointInPolygon (new, v->point[0], v->point[1]);
1672           for (v = v->next; v != &p->contours->head; v = v->next)
1673             CreateNewPointInPolygon (new, v->point[0], v->point[1]);
1674           new->BoundingBox.X1 = p->contours->xmin;
1675           new->BoundingBox.X2 = p->contours->xmax + 1;
1676           new->BoundingBox.Y1 = p->contours->ymin;
1677           new->BoundingBox.Y2 = p->contours->ymax + 1;
1678           AddObjectToCreateUndoList (POLYGON_TYPE, layer, new, new);
1679           new->Clipped = p;
1680           p = p->f;             /* go to next pline */
1681           new->Clipped->b = new->Clipped->f = new->Clipped;     /* unlink from others */
1682           r_insert_entry (layer->polygon_tree, (BoxType *) new, 0);
1683           DrawPolygon (layer, new, 0);
1684         }
1685       else
1686         {
1687           POLYAREA *t = p;
1688
1689           p = p->f;
1690           poly_DelContour (&t->contours);
1691           free (t);
1692         }
1693     }
1694   while (p != start);
1695   inhibit = False;
1696   IncrementUndoSerialNumber ();
1697   return many;
1698 }
1699
1700 void debug_pline (PLINE *pl)
1701 {
1702   VNODE *v;
1703   fprintf (stderr, "\txmin %d xmax %d ymin %d ymax %d\n",
1704            pl->xmin, pl->xmax, pl->ymin, pl->ymax);
1705   v = &pl->head;
1706   while (v)
1707     {
1708       fprintf(stderr, "\t\tvnode: %d,%d\n", v->point[0], v->point[1]);
1709       v = v->next;
1710       if (v == &pl->head)
1711         break;
1712     }
1713 }
1714
1715 void
1716 debug_polyarea (POLYAREA *p)
1717 {
1718   PLINE *pl;
1719
1720   fprintf (stderr, "POLYAREA %p\n", p);
1721   for (pl=p->contours; pl; pl=pl->next)
1722     debug_pline (pl);
1723 }
1724
1725 void
1726 debug_polygon (PolygonType *p)
1727 {
1728   int i;
1729   POLYAREA *pa;
1730   fprintf (stderr, "POLYGON %p  %d pts\n", p, p->PointN);
1731   for (i=0; i<p->PointN; i++)
1732     fprintf(stderr, "\t%d: %d, %d\n", i, p->Points[i].X, p->Points[i].Y);
1733   pa = p->Clipped;
1734   while (pa)
1735     {
1736       debug_polyarea (pa);
1737       pa = pa->f;
1738       if (pa == p->Clipped)
1739         break;
1740     }
1741 }