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