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