src/find.c

   1 /*
   2  *
   3  *                            COPYRIGHT
   4  *
   5  *  PCB, interactive printed circuit board design
   6  *  Copyright (C) 1994,1995,1996, 2005 Thomas Nau
   7  *
   8  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  This program is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with this program; if not, write to the Free Software
  20  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  21  *
  22  *  Contact addresses for paper mail and Email:
  23  *  Thomas Nau, Schlehenweg 15, 88471 Baustetten, Germany
  24  *  Thomas.Nau@rz.uni-ulm.de
  25  *
  26  */
  27
  28
  29 /*
  30  * short description:
  31  * - lists for pins and vias, lines, arcs, pads and for polygons are created.
  32  *   Every object that has to be checked is added to its list.
  33  *   Coarse searching is accomplished with the data rtrees.
  34  * - there's no 'speed-up' mechanism for polygons because they are not used
  35  *   as often as other objects
  36  * - the maximum distance between line and pin ... would depend on the angle
  37  *   between them. To speed up computation the limit is set to one half
  38  *   of the thickness of the objects (cause of square pins).
  39  *
  40  * PV:  means pin or via (objects that connect layers)
  41  * LO:  all non PV objects (layer objects like lines, arcs, polygons, pads)
  42  *
  43  * 1. first, the LO or PV at the given coordinates is looked up
  44  * 2. all LO connections to that PV are looked up next
  45  * 3. lookup of all LOs connected to LOs from (2).
  46  *    This step is repeated until no more new connections are found.
  47  * 4. lookup all PVs connected to the LOs from (2) and (3)
  48  * 5. start again with (1) for all new PVs from (4)
  49  *
  50  * Intersection of line <--> circle:
  51  * - calculate the signed distance from the line to the center,
  52  *   return false if abs(distance) > R
  53  * - get the distance from the line <--> distancevector intersection to
  54  *   (X1,Y1) in range [0,1], return true if 0 <= distance <= 1
  55  * - depending on (r > 1.0 or r < 0.0) check the distance of X2,Y2 or X1,Y1
  56  *   to X,Y
  57  *
  58  * Intersection of line <--> line:
  59  * - see the description of 'LineLineIntersect()'
  60  */
  61
  62 /* routines to find connections between pins, vias, lines...
  63  */
  64 #ifdef HAVE_CONFIG_H
  65 #include "config.h"
  66 #endif
  67
  68 #include <stdlib.h>
  69 #ifdef HAVE_STRING_H
  70 #include <string.h>
  71 #endif
  72 #include <math.h>
  73 #include <setjmp.h>
  74 #include <assert.h>
  75
  76 #ifdef HAVE_SYS_TIMES_H
  77 #include <sys/times.h>
  78 #endif
  79
  80 #include "global.h"
  81
  82 #include "crosshair.h"
  83 #include "data.h"
  84 #include "draw.h"
  85 #include "error.h"
  86 #include "find.h"
  87 #include "mymem.h"
  88 #include "misc.h"
  89 #include "rtree.h"
  90 #include "polygon.h"
  91 #include "pcb-printf.h"
  92 #include "search.h"
  93 #include "set.h"
  94 #include "undo.h"
  95 #include "rats.h"
  96
  97 #ifdef HAVE_LIBDMALLOC
  98 #include <dmalloc.h>
  99 #endif
 100
 101 #undef DEBUG
 102
 103 /* ---------------------------------------------------------------------------
 104  * some local macros
 105  */
 106
 107 #define EXPAND_BOUNDS(p) if (Bloat > 0) {\
 108        (p)->BoundingBox.X1 -= Bloat; \
 109        (p)->BoundingBox.X2 += Bloat; \
 110        (p)->BoundingBox.Y1 -= Bloat; \
 111        (p)->BoundingBox.Y2 += Bloat;}
 112
 113 #define SEPARATE(FP)                                                    \
 114         {                                                                                       \
 115                 int     i;                                                                      \
 116                 fputc('#', (FP));                                               \
 117                 for (i = Settings.CharPerLine; i; i--)  \
 118                         fputc('=', (FP));                                       \
 119                 fputc('\n', (FP));                                              \
 120         }
 121
 122 #define PADLIST_ENTRY(L,I)      \
 123         (((PadType **)PadList[(L)].Data)[(I)])
 124
 125 #define LINELIST_ENTRY(L,I)     \
 126         (((LineType **)LineList[(L)].Data)[(I)])
 127
 128 #define ARCLIST_ENTRY(L,I)      \
 129         (((ArcType **)ArcList[(L)].Data)[(I)])
 130
 131 #define RATLIST_ENTRY(I)        \
 132         (((RatType **)RatList.Data)[(I)])
 133
 134 #define POLYGONLIST_ENTRY(L,I)  \
 135         (((PolygonType **)PolygonList[(L)].Data)[(I)])
 136
 137 #define PVLIST_ENTRY(I) \
 138         (((PinType **)PVList.Data)[(I)])
 139
 140 #define IS_PV_ON_RAT(PV, Rat) \
 141         (IsPointOnLineEnd((PV)->X,(PV)->Y, (Rat)))
 142
 143 #define IS_PV_ON_ARC(PV, Arc)   \
 144         (TEST_FLAG(SQUAREFLAG, (PV)) ? \
 145                 IsArcInRectangle( \
 146                         (PV)->X -MAX(((PV)->Thickness+1)/2 +Bloat,0), (PV)->Y -MAX(((PV)->Thickness+1)/2 +Bloat,0), \
 147                         (PV)->X +MAX(((PV)->Thickness+1)/2 +Bloat,0), (PV)->Y +MAX(((PV)->Thickness+1)/2 +Bloat,0), \
 148                         (Arc)) : \
 149                 IsPointOnArc((PV)->X,(PV)->Y,MAX((PV)->Thickness/2.0 + Bloat,0.0), (Arc)))
 150
 151 #define IS_PV_ON_PAD(PV,Pad) \
 152         ( IsPointInPad((PV)->X, (PV)->Y, MAX((PV)->Thickness/2 +Bloat,0), (Pad)))
 153
 154 static DrcViolationType
 155 *pcb_drc_violation_new (const char *title,
 156                         const char *explanation,
 157                         Coord x, Coord y,
 158                         Angle angle,
 159                         bool have_measured,
 160                         Coord measured_value,
 161                         Coord required_value,
 162                         int object_count,
 163                         long int *object_id_list,
 164                         int *object_type_list)
 165 {
 166   DrcViolationType *violation = (DrcViolationType *)malloc (sizeof (DrcViolationType));
 167
 168   violation->title = strdup (title);
 169   violation->explanation = strdup (explanation);
 170   violation->x = x;
 171   violation->y = y;
 172   violation->angle = angle;
 173   violation->have_measured = have_measured;
 174   violation->measured_value = measured_value;
 175   violation->required_value = required_value;
 176   violation->object_count = object_count;
 177   violation->object_id_list = object_id_list;
 178   violation->object_type_list = object_type_list;
 179
 180   return violation;
 181 }
 182
 183 static void
 184 pcb_drc_violation_free (DrcViolationType *violation)
 185 {
 186   free (violation->title);
 187   free (violation->explanation);
 188   free (violation);
 189 }
 190
 191 static GString *drc_dialog_message;
 192 static void
 193 reset_drc_dialog_message(void)
 194 {
 195   if (drc_dialog_message)
 196     g_string_free (drc_dialog_message, FALSE);
 197   drc_dialog_message = g_string_new ("");
 198   if (gui->drc_gui != NULL)
 199     {
 200       gui->drc_gui->reset_drc_dialog_message ();
 201     }
 202 }
 203 static void
 204 append_drc_dialog_message(const char *fmt, ...)
 205 {
 206   gchar *new_str;
 207   va_list ap;
 208   va_start (ap, fmt);
 209   new_str = pcb_vprintf (fmt, ap);
 210   g_string_append (drc_dialog_message, new_str);
 211   va_end (ap);
 212   g_free (new_str);
 213 }
 214
 215 static void GotoError (void);
 216
 217 static void
 218 append_drc_violation (DrcViolationType *violation)
 219 {
 220   if (gui->drc_gui != NULL)
 221     {
 222       gui->drc_gui->append_drc_violation (violation);
 223     }
 224   else
 225     {
 226       /* Fallback to formatting the violation message as text */
 227       append_drc_dialog_message ("%s\n", violation->title);
 228       append_drc_dialog_message (_("%m+near %$mD\n"),
 229                                  Settings.grid_unit->allow,
 230                                  violation->x, violation->y);
 231       GotoError ();
 232     }
 233
 234   if (gui->drc_gui == NULL || gui->drc_gui->log_drc_violations )
 235     {
 236       Message (_("WARNING!  Design Rule error - %s\n"), violation->title);
 237       Message (_("%m+near location %$mD\n"),
 238                Settings.grid_unit->allow,
 239                violation->x, violation->y);
 240     }
 241 }
 242 /*
 243  * message when asked about continuing DRC checks after next
 244  * violation is found.
 245  */
 246 #define DRC_CONTINUE _("Press Next to continue DRC checking")
 247 #define DRC_NEXT _("Next")
 248 #define DRC_CANCEL _("Cancel")
 249
 250 static int
 251 throw_drc_dialog(void)
 252 {
 253   int r;
 254
 255   if (gui->drc_gui != NULL)
 256     {
 257       r = gui->drc_gui->throw_drc_dialog ();
 258     }
 259   else
 260     {
 261       /* Fallback to formatting the violation message as text */
 262       append_drc_dialog_message (DRC_CONTINUE);
 263       r = gui->confirm_dialog (drc_dialog_message->str, DRC_CANCEL, DRC_NEXT);
 264       reset_drc_dialog_message();
 265     }
 266   return r;
 267 }
 268
 269 /* ---------------------------------------------------------------------------
 270  * some local types
 271  *
 272  * the two 'dummy' structs for PVs and Pads are necessary for creating
 273  * connection lists which include the element's name
 274  */
 275 typedef struct
 276 {
 277   void **Data;                  /* pointer to index data */
 278   Cardinal Location,            /* currently used position */
 279     DrawLocation, Number,       /* number of objects in list */
 280     Size;
 281 } ListType;
 282
 283 /* ---------------------------------------------------------------------------
 284  * some local identifiers
 285  */
 286 static Coord Bloat = 0;
 287 static int TheFlag = FOUNDFLAG;
 288 static void *thing_ptr1, *thing_ptr2, *thing_ptr3;
 289 static int thing_type;
 290 static bool User = false;    /* user action causing this */
 291 static bool drc = false;     /* whether to stop if finding something not found */
 292 static bool IsBad = false;
 293 static Cardinal drcerr_count;   /* count of drc errors */
 294 static Cardinal TotalP, TotalV, NumberOfPads[2];
 295 static ListType LineList[MAX_LAYER],    /* list of objects to */
 296   PolygonList[MAX_LAYER], ArcList[MAX_LAYER], PadList[2], RatList, PVList;
 297
 298 /* ---------------------------------------------------------------------------
 299  * some local prototypes
 300  */
 301 static bool LookupLOConnectionsToPVList (bool);
 302 static bool LookupLOConnectionsToLOList (bool);
 303 static bool LookupPVConnectionsToLOList (bool);
 304 static bool LookupPVConnectionsToPVList (void);
 305 static bool LookupLOConnectionsToLine (LineType *, Cardinal, bool);
 306 static bool LookupLOConnectionsToPad (PadType *, Cardinal);
 307 static bool LookupLOConnectionsToPolygon (PolygonType *, Cardinal);
 308 static bool LookupLOConnectionsToArc (ArcType *, Cardinal);
 309 static bool LookupLOConnectionsToRatEnd (PointType *, Cardinal);
 310 static bool IsRatPointOnLineEnd (PointType *, LineType *);
 311 static bool ArcArcIntersect (ArcType *, ArcType *);
 312 static bool PrepareNextLoop (FILE *);
 313 static bool PrintElementConnections (ElementType *, FILE *, bool);
 314 static bool ListsEmpty (bool);
 315 static bool DoIt (bool, bool);
 316 static void PrintElementNameList (ElementType *, FILE *);
 317 static void PrintConnectionElementName (ElementType *, FILE *);
 318 static void PrintConnectionListEntry (char *, ElementType *,
 319                                       bool, FILE *);
 320 static void PrintPadConnections (Cardinal, FILE *, bool);
 321 static void PrintPinConnections (FILE *, bool);
 322 static bool PrintAndSelectUnusedPinsAndPadsOfElement (ElementType *,
 323                                                          FILE *);
 324 static void DrawNewConnections (void);
 325 static void DumpList (void);
 326 static void LocateError (Coord *, Coord *);
 327 static void BuildObjectList (int *, long int **, int **);
 328 static void GotoError (void);
 329 static bool DRCFind (int, void *, void *, void *);
 330 static bool ListStart (int, void *, void *, void *);
 331 static bool SetThing (int, void *, void *, void *);
 332 static bool IsArcInPolygon (ArcType *, PolygonType *);
 333 static bool IsLineInPolygon (LineType *, PolygonType *);
 334 static bool IsPadInPolygon (PadType *, PolygonType *);
 335 static bool IsPolygonInPolygon (PolygonType *, PolygonType *);
 336
 337 /* ---------------------------------------------------------------------------
 338  * some of the 'pad' routines are the same as for lines because the 'pad'
 339  * struct starts with a line struct. See global.h for details
 340  */
 341 bool
 342 LinePadIntersect (LineType *Line, PadType *Pad)
 343 {
 344   return LineLineIntersect ((Line), (LineType *)Pad);
 345 }
 346
 347 bool
 348 ArcPadIntersect (ArcType *Arc, PadType *Pad)
 349 {
 350   return LineArcIntersect ((LineType *) (Pad), (Arc));
 351 }
 352
 353 static bool
 354 ADD_PV_TO_LIST (PinType *Pin)
 355 {
 356   if (User)
 357     AddObjectToFlagUndoList (Pin->Element ? PIN_TYPE : VIA_TYPE,
 358                              Pin->Element ? Pin->Element : Pin, Pin, Pin);
 359   SET_FLAG (TheFlag, Pin);
 360   PVLIST_ENTRY (PVList.Number) = Pin;
 361   PVList.Number++;
 362 #ifdef DEBUG
 363   if (PVList.Number > PVList.Size)
 364     printf ("ADD_PV_TO_LIST overflow! num=%d size=%d\n", PVList.Number,
 365             PVList.Size);
 366 #endif
 367   if (drc && !TEST_FLAG (SELECTEDFLAG, Pin))
 368     return (SetThing (PIN_TYPE, Pin->Element, Pin, Pin));
 369   return false;
 370 }
 371
 372 static bool
 373 ADD_PAD_TO_LIST (Cardinal L, PadType *Pad)
 374 {
 375   if (User)
 376     AddObjectToFlagUndoList (PAD_TYPE, Pad->Element, Pad, Pad);
 377   SET_FLAG (TheFlag, Pad);
 378   PADLIST_ENTRY ((L), PadList[(L)].Number) = Pad;
 379   PadList[(L)].Number++;
 380 #ifdef DEBUG
 381   if (PadList[(L)].Number > PadList[(L)].Size)
 382     printf ("ADD_PAD_TO_LIST overflow! lay=%d, num=%d size=%d\n", L,
 383             PadList[(L)].Number, PadList[(L)].Size);
 384 #endif
 385   if (drc && !TEST_FLAG (SELECTEDFLAG, Pad))
 386     return (SetThing (PAD_TYPE, Pad->Element, Pad, Pad));
 387   return false;
 388 }
 389
 390 static bool
 391 ADD_LINE_TO_LIST (Cardinal L, LineType *Ptr)
 392 {
 393   if (User)
 394     AddObjectToFlagUndoList (LINE_TYPE, LAYER_PTR (L), (Ptr), (Ptr));
 395   SET_FLAG (TheFlag, (Ptr));
 396   LINELIST_ENTRY ((L), LineList[(L)].Number) = (Ptr);
 397   LineList[(L)].Number++;
 398 #ifdef DEBUG
 399   if (LineList[(L)].Number > LineList[(L)].Size)
 400     printf ("ADD_LINE_TO_LIST overflow! lay=%d, num=%d size=%d\n", L,
 401             LineList[(L)].Number, LineList[(L)].Size);
 402 #endif
 403   if (drc && !TEST_FLAG (SELECTEDFLAG, (Ptr)))
 404     return (SetThing (LINE_TYPE, LAYER_PTR (L), (Ptr), (Ptr)));
 405   return false;
 406 }
 407
 408 static bool
 409 ADD_ARC_TO_LIST (Cardinal L, ArcType *Ptr)
 410 {
 411   if (User)
 412     AddObjectToFlagUndoList (ARC_TYPE, LAYER_PTR (L), (Ptr), (Ptr));
 413   SET_FLAG (TheFlag, (Ptr));
 414   ARCLIST_ENTRY ((L), ArcList[(L)].Number) = (Ptr);
 415   ArcList[(L)].Number++;
 416 #ifdef DEBUG
 417   if (ArcList[(L)].Number > ArcList[(L)].Size)
 418     printf ("ADD_ARC_TO_LIST overflow! lay=%d, num=%d size=%d\n", L,
 419             ArcList[(L)].Number, ArcList[(L)].Size);
 420 #endif
 421   if (drc && !TEST_FLAG (SELECTEDFLAG, (Ptr)))
 422     return (SetThing (ARC_TYPE, LAYER_PTR (L), (Ptr), (Ptr)));
 423   return false;
 424 }
 425
 426 static bool
 427 ADD_RAT_TO_LIST (RatType *Ptr)
 428 {
 429   if (User)
 430     AddObjectToFlagUndoList (RATLINE_TYPE, (Ptr), (Ptr), (Ptr));
 431   SET_FLAG (TheFlag, (Ptr));
 432   RATLIST_ENTRY (RatList.Number) = (Ptr);
 433   RatList.Number++;
 434 #ifdef DEBUG
 435   if (RatList.Number > RatList.Size)
 436     printf ("ADD_RAT_TO_LIST overflow! num=%d size=%d\n",
 437             RatList.Number, RatList.Size);
 438 #endif
 439   if (drc && !TEST_FLAG (SELECTEDFLAG, (Ptr)))
 440     return (SetThing (RATLINE_TYPE, (Ptr), (Ptr), (Ptr)));
 441   return false;
 442 }
 443
 444 static bool
 445 ADD_POLYGON_TO_LIST (Cardinal L, PolygonType *Ptr)
 446 {
 447   if (User)
 448     AddObjectToFlagUndoList (POLYGON_TYPE, LAYER_PTR (L), (Ptr), (Ptr));
 449   SET_FLAG (TheFlag, (Ptr));
 450   POLYGONLIST_ENTRY ((L), PolygonList[(L)].Number) = (Ptr);
 451   PolygonList[(L)].Number++;
 452 #ifdef DEBUG
 453   if (PolygonList[(L)].Number > PolygonList[(L)].Size)
 454     printf ("ADD_ARC_TO_LIST overflow! lay=%d, num=%d size=%d\n", L,
 455             PolygonList[(L)].Number, PolygonList[(L)].Size);
 456 #endif
 457   if (drc && !TEST_FLAG (SELECTEDFLAG, (Ptr)))
 458     return (SetThing (POLYGON_TYPE, LAYER_PTR (L), (Ptr), (Ptr)));
 459   return false;
 460 }
 461
 462 bool
 463 PinLineIntersect (PinType *PV, LineType *Line)
 464 {
 465   /* IsLineInRectangle already has Bloat factor */
 466   return TEST_FLAG (SQUAREFLAG,
 467                     PV) ? IsLineInRectangle (PV->X - (PIN_SIZE (PV) + 1) / 2,
 468                                              PV->Y - (PIN_SIZE (PV) + 1) / 2,
 469                                              PV->X + (PIN_SIZE (PV) + 1) / 2,
 470                                              PV->Y + (PIN_SIZE (PV) + 1) / 2,
 471                                              Line) : IsPointInPad (PV->X,
 472                                                                     PV->Y,
 473                                                                    MAX (PIN_SIZE (PV)
 474                                                                          /
 475                                                                          2.0 +
 476                                                                          Bloat,
 477                                                                          0.0),
 478                                                                     (PadType *)Line);
 479 }
 480
 481
 482 bool
 483 SetThing (int type, void *ptr1, void *ptr2, void *ptr3)
 484 {
 485   thing_ptr1 = ptr1;
 486   thing_ptr2 = ptr2;
 487   thing_ptr3 = ptr3;
 488   thing_type = type;
 489   if (type == PIN_TYPE && ptr1 == NULL)
 490     {
 491       thing_ptr1 = ptr3;
 492       thing_type = VIA_TYPE;
 493     }
 494   return true;
 495 }
 496
 497 bool
 498 BoxBoxIntersection (BoxType *b1, BoxType *b2)
 499 {
 500   if (b2->X2 < b1->X1 || b2->X1 > b1->X2)
 501     return false;
 502   if (b2->Y2 < b1->Y1 || b2->Y1 > b1->Y2)
 503     return false;
 504   return true;
 505 }
 506
 507 static bool
 508 PadPadIntersect (PadType *p1, PadType *p2)
 509 {
 510   return LinePadIntersect ((LineType *) p1, p2);
 511 }
 512
 513 static inline bool
 514 PV_TOUCH_PV (PinType *PV1, PinType *PV2)
 515 {
 516   double t1, t2;
 517   BoxType b1, b2;
 518
 519   t1 = MAX (PV1->Thickness / 2.0 + Bloat, 0);
 520   t2 = MAX (PV2->Thickness / 2.0 + Bloat, 0);
 521   if (IsPointOnPin (PV1->X, PV1->Y, t1, PV2)
 522       || IsPointOnPin (PV2->X, PV2->Y, t2, PV1))
 523     return true;
 524   if (!TEST_FLAG (SQUAREFLAG, PV1) || !TEST_FLAG (SQUAREFLAG, PV2))
 525     return false;
 526   /* check for square/square overlap */
 527   b1.X1 = PV1->X - t1;
 528   b1.X2 = PV1->X + t1;
 529   b1.Y1 = PV1->Y - t1;
 530   b1.Y2 = PV1->Y + t1;
 531   t2 = PV2->Thickness / 2.0;
 532   b2.X1 = PV2->X - t2;
 533   b2.X2 = PV2->X + t2;
 534   b2.Y1 = PV2->Y - t2;
 535   b2.Y2 = PV2->Y + t2;
 536   return BoxBoxIntersection (&b1, &b2);
 537 }
 538
 539 /* ---------------------------------------------------------------------------
 540  * releases all allocated memory
 541  */
 542 void
 543 FreeLayoutLookupMemory (void)
 544 {
 545   Cardinal i;
 546
 547   for (i = 0; i < max_copper_layer; i++)
 548     {
 549       free (LineList[i].Data);
 550       LineList[i].Data = NULL;
 551       free (ArcList[i].Data);
 552       ArcList[i].Data = NULL;
 553       free (PolygonList[i].Data);
 554       PolygonList[i].Data = NULL;
 555     }
 556   free (PVList.Data);
 557   PVList.Data = NULL;
 558   free (RatList.Data);
 559   RatList.Data = NULL;
 560 }
 561
 562 void
 563 FreeComponentLookupMemory (void)
 564 {
 565   free (PadList[0].Data);
 566   PadList[0].Data = NULL;
 567   free (PadList[1].Data);
 568   PadList[1].Data = NULL;
 569 }
 570
 571 /* ---------------------------------------------------------------------------
 572  * allocates memory for component related stacks ...
 573  * initializes index and sorts it by X1 and X2
 574  */
 575 void
 576 InitComponentLookup (void)
 577 {
 578   Cardinal i;
 579
 580   /* initialize pad data; start by counting the total number
 581    * on each of the two possible layers
 582    */
 583   NumberOfPads[COMPONENT_LAYER] = NumberOfPads[SOLDER_LAYER] = 0;
 584   ALLPAD_LOOP (PCB->Data);
 585   {
 586     if (TEST_FLAG (ONSOLDERFLAG, pad))
 587       NumberOfPads[SOLDER_LAYER]++;
 588     else
 589       NumberOfPads[COMPONENT_LAYER]++;
 590   }
 591   ENDALL_LOOP;
 592   for (i = 0; i < 2; i++)
 593     {
 594       /* allocate memory for working list */
 595       PadList[i].Data = (void **)calloc (NumberOfPads[i], sizeof (PadType *));
 596
 597       /* clear some struct members */
 598       PadList[i].Location = 0;
 599       PadList[i].DrawLocation = 0;
 600       PadList[i].Number = 0;
 601       PadList[i].Size = NumberOfPads[i];
 602     }
 603 }
 604
 605 /* ---------------------------------------------------------------------------
 606  * allocates memory for component related stacks ...
 607  * initializes index and sorts it by X1 and X2
 608  */
 609 void
 610 InitLayoutLookup (void)
 611 {
 612   Cardinal i;
 613
 614   /* initialize line arc and polygon data */
 615   for (i = 0; i < max_copper_layer; i++)
 616     {
 617       LayerType *layer = LAYER_PTR (i);
 618
 619       if (layer->LineN)
 620         {
 621           /* allocate memory for line pointer lists */
 622           LineList[i].Data = (void **)calloc (layer->LineN, sizeof (LineType *));
 623           LineList[i].Size = layer->LineN;
 624         }
 625       if (layer->ArcN)
 626         {
 627           ArcList[i].Data = (void **)calloc (layer->ArcN, sizeof (ArcType *));
 628           ArcList[i].Size = layer->ArcN;
 629         }
 630
 631
 632       /* allocate memory for polygon list */
 633       if (layer->PolygonN)
 634         {
 635           PolygonList[i].Data = (void **)calloc (layer->PolygonN, sizeof (PolygonType *));
 636           PolygonList[i].Size = layer->PolygonN;
 637         }
 638
 639       /* clear some struct members */
 640       LineList[i].Location = 0;
 641       LineList[i].DrawLocation = 0;
 642       LineList[i].Number = 0;
 643       ArcList[i].Location = 0;
 644       ArcList[i].DrawLocation = 0;
 645       ArcList[i].Number = 0;
 646       PolygonList[i].Location = 0;
 647       PolygonList[i].DrawLocation = 0;
 648       PolygonList[i].Number = 0;
 649     }
 650
 651   if (PCB->Data->pin_tree)
 652     TotalP = PCB->Data->pin_tree->size;
 653   else
 654     TotalP = 0;
 655   if (PCB->Data->via_tree)
 656     TotalV = PCB->Data->via_tree->size;
 657   else
 658     TotalV = 0;
 659   /* allocate memory for 'new PV to check' list and clear struct */
 660   PVList.Data = (void **)calloc (TotalP + TotalV, sizeof (PinType *));
 661   PVList.Size = TotalP + TotalV;
 662   PVList.Location = 0;
 663   PVList.DrawLocation = 0;
 664   PVList.Number = 0;
 665   /* Initialize ratline data */
 666   RatList.Data = (void **)calloc (PCB->Data->RatN, sizeof (RatType *));
 667   RatList.Size = PCB->Data->RatN;
 668   RatList.Location = 0;
 669   RatList.DrawLocation = 0;
 670   RatList.Number = 0;
 671 }
 672
 673 struct pv_info
 674 {
 675   Cardinal layer;
 676   PinType pv;
 677   jmp_buf env;
 678 };
 679
 680 static int
 681 LOCtoPVline_callback (const BoxType * b, void *cl)
 682 {
 683   LineType *line = (LineType *) b;
 684   struct pv_info *i = (struct pv_info *) cl;
 685
 686   if (!TEST_FLAG (TheFlag, line) && PinLineIntersect (&i->pv, line) &&
 687       !TEST_FLAG (HOLEFLAG, &i->pv))
 688     {
 689       if (ADD_LINE_TO_LIST (i->layer, line))
 690         longjmp (i->env, 1);
 691     }
 692   return 0;
 693 }
 694
 695 static int
 696 LOCtoPVarc_callback (const BoxType * b, void *cl)
 697 {
 698   ArcType *arc = (ArcType *) b;
 699   struct pv_info *i = (struct pv_info *) cl;
 700
 701   if (!TEST_FLAG (TheFlag, arc) && IS_PV_ON_ARC (&i->pv, arc) &&
 702       !TEST_FLAG (HOLEFLAG, &i->pv))
 703     {
 704       if (ADD_ARC_TO_LIST (i->layer, arc))
 705         longjmp (i->env, 1);
 706     }
 707   return 0;
 708 }
 709
 710 static int
 711 LOCtoPVpad_callback (const BoxType * b, void *cl)
 712 {
 713   PadType *pad = (PadType *) b;
 714   struct pv_info *i = (struct pv_info *) cl;
 715
 716   if (!TEST_FLAG (TheFlag, pad) && IS_PV_ON_PAD (&i->pv, pad) &&
 717       !TEST_FLAG (HOLEFLAG, &i->pv) &&
 718       ADD_PAD_TO_LIST (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER :
 719                        COMPONENT_LAYER, pad))
 720     longjmp (i->env, 1);
 721   return 0;
 722 }
 723
 724 static int
 725 LOCtoPVrat_callback (const BoxType * b, void *cl)
 726 {
 727   RatType *rat = (RatType *) b;
 728   struct pv_info *i = (struct pv_info *) cl;
 729
 730   if (!TEST_FLAG (TheFlag, rat) && IS_PV_ON_RAT (&i->pv, rat) &&
 731       ADD_RAT_TO_LIST (rat))
 732     longjmp (i->env, 1);
 733   return 0;
 734 }
 735 static int
 736 LOCtoPVpoly_callback (const BoxType * b, void *cl)
 737 {
 738   PolygonType *polygon = (PolygonType *) b;
 739   struct pv_info *i = (struct pv_info *) cl;
 740
 741   /* if the pin doesn't have a therm and polygon is clearing
 742    * then it can't touch due to clearance, so skip the expensive
 743    * test. If it does have a therm, you still need to test
 744    * because it might not be inside the polygon, or it could
 745    * be on an edge such that it doesn't actually touch.
 746    */
 747   if (!TEST_FLAG (TheFlag, polygon) && !TEST_FLAG (HOLEFLAG, &i->pv) &&
 748                                        (TEST_THERM (i->layer, &i->pv) ||
 749                                         !TEST_FLAG (CLEARPOLYFLAG,
 750                                                     polygon)
 751                                         || !i->pv.Clearance))
 752     {
 753       double wide = MAX (0.5 * i->pv.Thickness + Bloat, 0);
 754       if (TEST_FLAG (SQUAREFLAG, &i->pv))
 755         {
 756           Coord x1 = i->pv.X - (i->pv.Thickness + 1 + Bloat) / 2;
 757           Coord x2 = i->pv.X + (i->pv.Thickness + 1 + Bloat) / 2;
 758           Coord y1 = i->pv.Y - (i->pv.Thickness + 1 + Bloat) / 2;
 759           Coord y2 = i->pv.Y + (i->pv.Thickness + 1 + Bloat) / 2;
 760           if (IsRectangleInPolygon (x1, y1, x2, y2, polygon)
 761               && ADD_POLYGON_TO_LIST (i->layer, polygon))
 762             longjmp (i->env, 1);
 763         }
 764       else if (TEST_FLAG (OCTAGONFLAG, &i->pv))
 765         {
 766           POLYAREA *oct = OctagonPoly (i->pv.X, i->pv.Y, i->pv.Thickness / 2);
 767           if (isects (oct, polygon, true)
 768               && ADD_POLYGON_TO_LIST (i->layer, polygon))
 769             longjmp (i->env, 1);
 770         }
 771       else if (IsPointInPolygon (i->pv.X, i->pv.Y, wide,
 772                                  polygon)
 773                && ADD_POLYGON_TO_LIST (i->layer, polygon))
 774         longjmp (i->env, 1);
 775     }
 776   return 0;
 777 }
 778
 779 /* ---------------------------------------------------------------------------
 780  * checks if a PV is connected to LOs, if it is, the LO is added to
 781  * the appropriate list and the 'used' flag is set
 782  */
 783 static bool
 784 LookupLOConnectionsToPVList (bool AndRats)
 785 {
 786   Cardinal layer;
 787   struct pv_info info;
 788
 789   /* loop over all PVs currently on list */
 790   while (PVList.Location < PVList.Number)
 791     {
 792       /* get pointer to data */
 793       info.pv = *(PVLIST_ENTRY (PVList.Location));
 794       EXPAND_BOUNDS (&info.pv);
 795
 796       /* check pads */
 797       if (setjmp (info.env) == 0)
 798         r_search (PCB->Data->pad_tree, (BoxType *) & info.pv, NULL,
 799                   LOCtoPVpad_callback, &info);
 800       else
 801         return true;
 802
 803       /* now all lines, arcs and polygons of the several layers */
 804       for (layer = 0; layer < max_copper_layer; layer++)
 805         {
 806           if (LAYER_PTR (layer)->no_drc)
 807              continue;
 808           info.layer = layer;
 809           /* add touching lines */
 810           if (setjmp (info.env) == 0)
 811             r_search (LAYER_PTR (layer)->line_tree, (BoxType *) & info.pv,
 812                       NULL, LOCtoPVline_callback, &info);
 813           else
 814             return true;
 815           /* add touching arcs */
 816           if (setjmp (info.env) == 0)
 817             r_search (LAYER_PTR (layer)->arc_tree, (BoxType *) & info.pv,
 818                       NULL, LOCtoPVarc_callback, &info);
 819           else
 820             return true;
 821           /* check all polygons */
 822           if (setjmp (info.env) == 0)
 823             r_search (LAYER_PTR (layer)->polygon_tree, (BoxType *) & info.pv,
 824                       NULL, LOCtoPVpoly_callback, &info);
 825           else
 826             return true;
 827         }
 828       /* Check for rat-lines that may intersect the PV */
 829       if (AndRats)
 830         {
 831           if (setjmp (info.env) == 0)
 832             r_search (PCB->Data->rat_tree, (BoxType *) & info.pv, NULL,
 833                       LOCtoPVrat_callback, &info);
 834           else
 835             return true;
 836         }
 837       PVList.Location++;
 838     }
 839   return false;
 840 }
 841
 842 /* ---------------------------------------------------------------------------
 843  * find all connections between LO at the current list position and new LOs
 844  */
 845 static bool
 846 LookupLOConnectionsToLOList (bool AndRats)
 847 {
 848   bool done;
 849   Cardinal i, group, layer, ratposition,
 850     lineposition[MAX_LAYER],
 851     polyposition[MAX_LAYER], arcposition[MAX_LAYER], padposition[2];
 852
 853   /* copy the current LO list positions; the original data is changed
 854    * by 'LookupPVConnectionsToLOList()' which has to check the same
 855    * list entries plus the new ones
 856    */
 857   for (i = 0; i < max_copper_layer; i++)
 858     {
 859       lineposition[i] = LineList[i].Location;
 860       polyposition[i] = PolygonList[i].Location;
 861       arcposition[i]  = ArcList[i].Location;
 862     }
 863   for (i = 0; i < 2; i++)
 864     padposition[i] = PadList[i].Location;
 865   ratposition = RatList.Location;
 866
 867   /* loop over all new LOs in the list; recurse until no
 868    * more new connections in the layergroup were found
 869    */
 870   do
 871     {
 872       Cardinal *position;
 873
 874       if (AndRats)
 875         {
 876           position = &ratposition;
 877           for (; *position < RatList.Number; (*position)++)
 878             {
 879               group = RATLIST_ENTRY (*position)->group1;
 880               if (LookupLOConnectionsToRatEnd
 881                   (&(RATLIST_ENTRY (*position)->Point1), group))
 882                 return (true);
 883               group = RATLIST_ENTRY (*position)->group2;
 884               if (LookupLOConnectionsToRatEnd
 885                   (&(RATLIST_ENTRY (*position)->Point2), group))
 886                 return (true);
 887             }
 888         }
 889       /* loop over all layergroups */
 890       for (group = 0; group < max_group; group++)
 891         {
 892           Cardinal entry;
 893
 894           for (entry = 0; entry < PCB->LayerGroups.Number[group]; entry++)
 895             {
 896               layer = PCB->LayerGroups.Entries[group][entry];
 897
 898               /* be aware that the layer number equal max_copper_layer
 899                * and max_copper_layer+1 have a special meaning for pads
 900                */
 901               if (layer < max_copper_layer)
 902                 {
 903                   /* try all new lines */
 904                   position = &lineposition[layer];
 905                   for (; *position < LineList[layer].Number; (*position)++)
 906                     if (LookupLOConnectionsToLine
 907                         (LINELIST_ENTRY (layer, *position), group, true))
 908                       return (true);
 909
 910                   /* try all new arcs */
 911                   position = &arcposition[layer];
 912                   for (; *position < ArcList[layer].Number; (*position)++)
 913                     if (LookupLOConnectionsToArc
 914                         (ARCLIST_ENTRY (layer, *position), group))
 915                       return (true);
 916
 917                   /* try all new polygons */
 918                   position = &polyposition[layer];
 919                   for (; *position < PolygonList[layer].Number; (*position)++)
 920                     if (LookupLOConnectionsToPolygon
 921                         (POLYGONLIST_ENTRY (layer, *position), group))
 922                       return (true);
 923                 }
 924               else
 925                 {
 926                   /* try all new pads */
 927                   layer -= max_copper_layer;
 928                   if (layer > 1)
 929                     {
 930                       Message (_("bad layer number %d max_copper_layer=%d in find.c\n"),
 931                                layer, max_copper_layer);
 932                       return false;
 933                     }
 934                   position = &padposition[layer];
 935                   for (; *position < PadList[layer].Number; (*position)++)
 936                     if (LookupLOConnectionsToPad
 937                         (PADLIST_ENTRY (layer, *position), group))
 938                       return (true);
 939                 }
 940             }
 941         }
 942
 943       /* check if all lists are done; Later for-loops
 944        * may have changed the prior lists
 945        */
 946       done = !AndRats || ratposition >= RatList.Number;
 947       done = done && padposition[0] >= PadList[0].Number &&
 948                      padposition[1] >= PadList[1].Number;
 949       for (layer = 0; layer < max_copper_layer; layer++)
 950         done = done &&
 951                lineposition[layer] >= LineList[layer].Number &&
 952                arcposition[layer]  >= ArcList[layer].Number &&
 953                polyposition[layer] >= PolygonList[layer].Number;
 954     }
 955   while (!done);
 956   return (false);
 957 }
 958
 959 static int
 960 pv_pv_callback (const BoxType * b, void *cl)
 961 {
 962   PinType *pin = (PinType *) b;
 963   struct pv_info *i = (struct pv_info *) cl;
 964
 965   if (!TEST_FLAG (TheFlag, pin) && PV_TOUCH_PV (&i->pv, pin))
 966     {
 967       if (TEST_FLAG (HOLEFLAG, pin) || TEST_FLAG (HOLEFLAG, &i->pv))
 968         {
 969           SET_FLAG (WARNFLAG, pin);
 970           Settings.RatWarn = true;
 971           if (pin->Element)
 972             Message (_("WARNING: Hole too close to pin.\n"));
 973           else
 974             Message (_("WARNING: Hole too close to via.\n"));
 975         }
 976       else if (ADD_PV_TO_LIST (pin))
 977         longjmp (i->env, 1);
 978     }
 979   return 0;
 980 }
 981
 982 /* ---------------------------------------------------------------------------
 983  * searches for new PVs that are connected to PVs on the list
 984  */
 985 static bool
 986 LookupPVConnectionsToPVList (void)
 987 {
 988   Cardinal save_place;
 989   struct pv_info info;
 990
 991
 992   /* loop over all PVs on list */
 993   save_place = PVList.Location;
 994   while (PVList.Location < PVList.Number)
 995     {
 996       /* get pointer to data */
 997       info.pv = *(PVLIST_ENTRY (PVList.Location));
 998       EXPAND_BOUNDS (&info.pv);
 999       if (setjmp (info.env) == 0)
1000         r_search (PCB->Data->via_tree, (BoxType *) & info.pv, NULL,
1001                   pv_pv_callback, &info);
1002       else
1003         return true;
1004       if (setjmp (info.env) == 0)
1005         r_search (PCB->Data->pin_tree, (BoxType *) & info.pv, NULL,
1006                   pv_pv_callback, &info);
1007       else
1008         return true;
1009       PVList.Location++;
1010     }
1011   PVList.Location = save_place;
1012   return (false);
1013 }
1014
1015 struct lo_info
1016 {
1017   Cardinal layer;
1018   LineType line;
1019   PadType pad;
1020   ArcType arc;
1021   PolygonType polygon;
1022   RatType rat;
1023   jmp_buf env;
1024 };
1025
1026 static int
1027 pv_line_callback (const BoxType * b, void *cl)
1028 {
1029   PinType *pv = (PinType *) b;
1030   struct lo_info *i = (struct lo_info *) cl;
1031
1032   if (!TEST_FLAG (TheFlag, pv) && PinLineIntersect (pv, &i->line))
1033     {
1034       if (TEST_FLAG (HOLEFLAG, pv))
1035         {
1036           SET_FLAG (WARNFLAG, pv);
1037           Settings.RatWarn = true;
1038           Message (_("WARNING: Hole too close to line.\n"));
1039         }
1040       else if (ADD_PV_TO_LIST (pv))
1041         longjmp (i->env, 1);
1042     }
1043   return 0;
1044 }
1045
1046 static int
1047 pv_pad_callback (const BoxType * b, void *cl)
1048 {
1049   PinType *pv = (PinType *) b;
1050   struct lo_info *i = (struct lo_info *) cl;
1051
1052   if (!TEST_FLAG (TheFlag, pv) && IS_PV_ON_PAD (pv, &i->pad))
1053     {
1054       if (TEST_FLAG (HOLEFLAG, pv))
1055         {
1056           SET_FLAG (WARNFLAG, pv);
1057           Settings.RatWarn = true;
1058           Message (_("WARNING: Hole too close to pad.\n"));
1059         }
1060       else if (ADD_PV_TO_LIST (pv))
1061         longjmp (i->env, 1);
1062     }
1063   return 0;
1064 }
1065
1066 static int
1067 pv_arc_callback (const BoxType * b, void *cl)
1068 {
1069   PinType *pv = (PinType *) b;
1070   struct lo_info *i = (struct lo_info *) cl;
1071
1072   if (!TEST_FLAG (TheFlag, pv) && IS_PV_ON_ARC (pv, &i->arc))
1073     {
1074       if (TEST_FLAG (HOLEFLAG, pv))
1075         {
1076           SET_FLAG (WARNFLAG, pv);
1077           Settings.RatWarn = true;
1078           Message (_("WARNING: Hole touches arc.\n"));
1079         }
1080       else if (ADD_PV_TO_LIST (pv))
1081         longjmp (i->env, 1);
1082     }
1083   return 0;
1084 }
1085
1086 static int
1087 pv_poly_callback (const BoxType * b, void *cl)
1088 {
1089   PinType *pv = (PinType *) b;
1090   struct lo_info *i = (struct lo_info *) cl;
1091
1092   /* note that holes in polygons are ok, so they don't generate warnings. */
1093   if (!TEST_FLAG (TheFlag, pv) && !TEST_FLAG (HOLEFLAG, pv) &&
1094                                   (TEST_THERM (i->layer, pv) ||
1095                                    !TEST_FLAG (CLEARPOLYFLAG, &i->polygon) ||
1096                                    !pv->Clearance))
1097     {
1098       if (TEST_FLAG (SQUAREFLAG, pv))
1099         {
1100           Coord x1, x2, y1, y2;
1101           x1 = pv->X - (PIN_SIZE (pv) + 1 + Bloat) / 2;
1102           x2 = pv->X + (PIN_SIZE (pv) + 1 + Bloat) / 2;
1103           y1 = pv->Y - (PIN_SIZE (pv) + 1 + Bloat) / 2;
1104           y2 = pv->Y + (PIN_SIZE (pv) + 1 + Bloat) / 2;
1105           if (IsRectangleInPolygon (x1, y1, x2, y2, &i->polygon)
1106               && ADD_PV_TO_LIST (pv))
1107             longjmp (i->env, 1);
1108         }
1109       else if (TEST_FLAG (OCTAGONFLAG, pv))
1110         {
1111           POLYAREA *oct = OctagonPoly (pv->X, pv->Y, PIN_SIZE (pv) / 2);
1112           if (isects (oct, &i->polygon, true) && ADD_PV_TO_LIST (pv))
1113             longjmp (i->env, 1);
1114         }
1115       else
1116         {
1117           if (IsPointInPolygon
1118               (pv->X, pv->Y, PIN_SIZE (pv) * 0.5 + Bloat, &i->polygon)
1119               && ADD_PV_TO_LIST (pv))
1120             longjmp (i->env, 1);
1121         }
1122     }
1123   return 0;
1124 }
1125
1126 static int
1127 pv_rat_callback (const BoxType * b, void *cl)
1128 {
1129   PinType *pv = (PinType *) b;
1130   struct lo_info *i = (struct lo_info *) cl;
1131
1132   /* rats can't cause DRC so there is no early exit */
1133   if (!TEST_FLAG (TheFlag, pv) && IS_PV_ON_RAT (pv, &i->rat))
1134     ADD_PV_TO_LIST (pv);
1135   return 0;
1136 }
1137
1138 /* ---------------------------------------------------------------------------
1139  * searches for new PVs that are connected to NEW LOs on the list
1140  * This routine updates the position counter of the lists too.
1141  */
1142 static bool
1143 LookupPVConnectionsToLOList (bool AndRats)
1144 {
1145   Cardinal layer;
1146   struct lo_info info;
1147
1148   /* loop over all layers */
1149   for (layer = 0; layer < max_copper_layer; layer++)
1150     {
1151       if (LAYER_PTR (layer)->no_drc)
1152                        continue;
1153       /* do nothing if there are no PV's */
1154       if (TotalP + TotalV == 0)
1155         {
1156           LineList[layer].Location = LineList[layer].Number;
1157           ArcList[layer].Location = ArcList[layer].Number;
1158           PolygonList[layer].Location = PolygonList[layer].Number;
1159           continue;
1160         }
1161
1162       /* check all lines */
1163       while (LineList[layer].Location < LineList[layer].Number)
1164         {
1165           info.line = *(LINELIST_ENTRY (layer, LineList[layer].Location));
1166           EXPAND_BOUNDS (&info.line);
1167           if (setjmp (info.env) == 0)
1168             r_search (PCB->Data->via_tree, (BoxType *) & info.line, NULL,
1169                       pv_line_callback, &info);
1170           else
1171             return true;
1172           if (setjmp (info.env) == 0)
1173             r_search (PCB->Data->pin_tree, (BoxType *) & info.line, NULL,
1174                       pv_line_callback, &info);
1175           else
1176             return true;
1177           LineList[layer].Location++;
1178         }
1179
1180       /* check all arcs */
1181       while (ArcList[layer].Location < ArcList[layer].Number)
1182         {
1183           info.arc = *(ARCLIST_ENTRY (layer, ArcList[layer].Location));
1184           EXPAND_BOUNDS (&info.arc);
1185           if (setjmp (info.env) == 0)
1186             r_search (PCB->Data->via_tree, (BoxType *) & info.arc, NULL,
1187                       pv_arc_callback, &info);
1188           else
1189             return true;
1190           if (setjmp (info.env) == 0)
1191             r_search (PCB->Data->pin_tree, (BoxType *) & info.arc, NULL,
1192                       pv_arc_callback, &info);
1193           else
1194             return true;
1195           ArcList[layer].Location++;
1196         }
1197
1198       /* now all polygons */
1199       info.layer = layer;
1200       while (PolygonList[layer].Location < PolygonList[layer].Number)
1201         {
1202           info.polygon =
1203             *(POLYGONLIST_ENTRY (layer, PolygonList[layer].Location));
1204           EXPAND_BOUNDS (&info.polygon);
1205           if (setjmp (info.env) == 0)
1206             r_search (PCB->Data->via_tree, (BoxType *) & info.polygon, NULL,
1207                       pv_poly_callback, &info);
1208           else
1209             return true;
1210           if (setjmp (info.env) == 0)
1211             r_search (PCB->Data->pin_tree, (BoxType *) & info.polygon, NULL,
1212                       pv_poly_callback, &info);
1213           else
1214             return true;
1215           PolygonList[layer].Location++;
1216         }
1217     }
1218
1219   /* loop over all pad-layers */
1220   for (layer = 0; layer < 2; layer++)
1221     {
1222       /* do nothing if there are no PV's */
1223       if (TotalP + TotalV == 0)
1224         {
1225           PadList[layer].Location = PadList[layer].Number;
1226           continue;
1227         }
1228
1229       /* check all pads; for a detailed description see
1230        * the handling of lines in this subroutine
1231        */
1232       while (PadList[layer].Location < PadList[layer].Number)
1233         {
1234           info.pad = *(PADLIST_ENTRY (layer, PadList[layer].Location));
1235           EXPAND_BOUNDS (&info.pad);
1236           if (setjmp (info.env) == 0)
1237             r_search (PCB->Data->via_tree, (BoxType *) & info.pad, NULL,
1238                       pv_pad_callback, &info);
1239           else
1240             return true;
1241           if (setjmp (info.env) == 0)
1242             r_search (PCB->Data->pin_tree, (BoxType *) & info.pad, NULL,
1243                       pv_pad_callback, &info);
1244           else
1245             return true;
1246           PadList[layer].Location++;
1247         }
1248     }
1249
1250   /* do nothing if there are no PV's */
1251   if (TotalP + TotalV == 0)
1252     RatList.Location = RatList.Number;
1253
1254   /* check all rat-lines */
1255   if (AndRats)
1256     {
1257       while (RatList.Location < RatList.Number)
1258         {
1259           info.rat = *(RATLIST_ENTRY (RatList.Location));
1260           r_search_pt (PCB->Data->via_tree, & info.rat.Point1, 1, NULL,
1261                     pv_rat_callback, &info);
1262           r_search_pt (PCB->Data->via_tree, & info.rat.Point2, 1, NULL,
1263                     pv_rat_callback, &info);
1264           r_search_pt (PCB->Data->pin_tree, & info.rat.Point1, 1, NULL,
1265                     pv_rat_callback, &info);
1266           r_search_pt (PCB->Data->pin_tree, & info.rat.Point2, 1, NULL,
1267                     pv_rat_callback, &info);
1268
1269           RatList.Location++;
1270         }
1271     }
1272   return (false);
1273 }
1274
1275 int
1276 pv_touch_callback (const BoxType * b, void *cl)
1277 {
1278   PinType *pin = (PinType *) b;
1279   struct lo_info *i = (struct lo_info *) cl;
1280
1281   if (!TEST_FLAG (TheFlag, pin) && PinLineIntersect (pin, &i->line))
1282     longjmp (i->env, 1);
1283   return 0;
1284 }
1285
1286 /* reduce arc start angle and delta to 0..360 */
1287 static void
1288 normalize_angles (Angle *sa, Angle *d)
1289 {
1290   if (*d < 0)
1291     {
1292       *sa += *d;
1293       *d = - *d;
1294     }
1295   if (*d > 360) /* full circle */
1296     *d = 360;
1297   *sa = NormalizeAngle (*sa);
1298 }
1299
1300 static int
1301 radius_crosses_arc (double x, double y, ArcType *arc)
1302 {
1303   double alpha = atan2 (y - arc->Y, -x + arc->X) * RAD_TO_DEG;
1304   Angle sa = arc->StartAngle, d = arc->Delta;
1305
1306   normalize_angles (&sa, &d);
1307   if (alpha < 0)
1308     alpha += 360;
1309   if (sa <= alpha)
1310     return (sa + d) >= alpha;
1311   return (sa + d - 360) >= alpha;
1312 }
1313
1314 static void
1315 get_arc_ends (Coord *box, ArcType *arc)
1316 {
1317   box[0] = arc->X - arc->Width  * cos (M180 * arc->StartAngle);
1318   box[1] = arc->Y + arc->Height * sin (M180 * arc->StartAngle);
1319   box[2] = arc->X - arc->Width  * cos (M180 * (arc->StartAngle + arc->Delta));
1320   box[3] = arc->Y + arc->Height * sin (M180 * (arc->StartAngle + arc->Delta));
1321 }
1322 /* ---------------------------------------------------------------------------
1323  * check if two arcs intersect
1324  * first we check for circle intersections,
1325  * then find the actual points of intersection
1326  * and test them to see if they are on arcs
1327  *
1328  * consider a, the distance from the center of arc 1
1329  * to the point perpendicular to the intersecting points.
1330  *
1331  *  a = (r1^2 - r2^2 + l^2)/(2l)
1332  *
1333  * the perpendicular distance to the point of intersection
1334  * is then
1335  *
1336  * d = sqrt(r1^2 - a^2)
1337  *
1338  * the points of intersection would then be
1339  *
1340  * x = X1 + a/l dx +- d/l dy
1341  * y = Y1 + a/l dy -+ d/l dx
1342  *
1343  * where dx = X2 - X1 and dy = Y2 - Y1
1344  *
1345  *
1346  */
1347 static bool
1348 ArcArcIntersect (ArcType *Arc1, ArcType *Arc2)
1349 {
1350   double x, y, dx, dy, r1, r2, a, d, l, t, t1, t2, dl;
1351   Coord pdx, pdy;
1352   Coord box[8];
1353
1354   t  = 0.5 * Arc1->Thickness + Bloat;
1355   t2 = 0.5 * Arc2->Thickness;
1356   t1 = t2 + Bloat;
1357
1358   /* too thin arc */
1359   if (t < 0 || t1 < 0)
1360     return false;
1361
1362   /* try the end points first */
1363   get_arc_ends (&box[0], Arc1);
1364   get_arc_ends (&box[4], Arc2);
1365   if (IsPointOnArc (box[0], box[1], t, Arc2)
1366       || IsPointOnArc (box[2], box[3], t, Arc2)
1367       || IsPointOnArc (box[4], box[5], t, Arc1)
1368       || IsPointOnArc (box[6], box[7], t, Arc1))
1369     return true;
1370
1371   pdx = Arc2->X - Arc1->X;
1372   pdy = Arc2->Y - Arc1->Y;
1373   dl = Distance (Arc1->X, Arc1->Y, Arc2->X, Arc2->Y);
1374   /* concentric arcs, simpler intersection conditions */
1375   if (dl < 0.5)
1376     {
1377       if ((Arc1->Width - t >= Arc2->Width - t2
1378            && Arc1->Width - t <= Arc2->Width + t2)
1379           || (Arc1->Width + t >= Arc2->Width - t2
1380               && Arc1->Width + t <= Arc2->Width + t2))
1381         {
1382           Angle sa1 = Arc1->StartAngle, d1 = Arc1->Delta;
1383           Angle sa2 = Arc2->StartAngle, d2 = Arc2->Delta;
1384           /* NB the endpoints have already been checked,
1385              so we just compare the angles */
1386
1387           normalize_angles (&sa1, &d1);
1388           normalize_angles (&sa2, &d2);
1389           /* sa1 == sa2 was caught when checking endpoints */
1390           if (sa1 > sa2)
1391             if (sa1 < sa2 + d2 || sa1 + d1 - 360 > sa2)
1392               return true;
1393           if (sa2 > sa1)
1394             if (sa2 < sa1 + d1 || sa2 + d2 - 360 > sa1)
1395               return true;
1396         }
1397       return false;
1398     }
1399   r1 = Arc1->Width;
1400   r2 = Arc2->Width;
1401   /* arcs centerlines are too far or too near */
1402   if (dl > r1 + r2 || dl + r1 < r2 || dl + r2 < r1)
1403     {
1404       /* check the nearest to the other arc's center point */
1405       dx = pdx * r1 / dl;
1406       dy = pdy * r1 / dl;
1407       if (dl + r1 < r2) /* Arc1 inside Arc2 */
1408         {
1409           dx = - dx;
1410           dy = - dy;
1411         }
1412
1413       if (radius_crosses_arc (Arc1->X + dx, Arc1->Y + dy, Arc1)
1414           && IsPointOnArc (Arc1->X + dx, Arc1->Y + dy, t, Arc2))
1415         return true;
1416
1417       dx = - pdx * r2 / dl;
1418       dy = - pdy * r2 / dl;
1419       if (dl + r2 < r1) /* Arc2 inside Arc1 */
1420         {
1421           dx = - dx;
1422           dy = - dy;
1423         }
1424
1425       if (radius_crosses_arc (Arc2->X + dx, Arc2->Y + dy, Arc2)
1426           && IsPointOnArc (Arc2->X + dx, Arc2->Y + dy, t1, Arc1))
1427         return true;
1428       return false;
1429     }
1430
1431   l = dl * dl;
1432   r1 *= r1;
1433   r2 *= r2;
1434   a = 0.5 * (r1 - r2 + l) / l;
1435   r1 = r1 / l;
1436   d = r1 - a * a;
1437   /* the circles are too far apart to touch or probably just touch:
1438      check the nearest point */
1439   if (d < 0)
1440     d = 0;
1441   else
1442     d = sqrt (d);
1443   x = Arc1->X + a * pdx;
1444   y = Arc1->Y + a * pdy;
1445   dx = d * pdx;
1446   dy = d * pdy;
1447   if (radius_crosses_arc (x + dy, y - dx, Arc1)
1448       && IsPointOnArc (x + dy, y - dx, t, Arc2))
1449     return true;
1450   if (radius_crosses_arc (x + dy, y - dx, Arc2)
1451       && IsPointOnArc (x + dy, y - dx, t1, Arc1))
1452     return true;
1453
1454   if (radius_crosses_arc (x - dy, y + dx, Arc1)
1455       && IsPointOnArc (x - dy, y + dx, t, Arc2))
1456     return true;
1457   if (radius_crosses_arc (x - dy, y + dx, Arc2)
1458       && IsPointOnArc (x - dy, y + dx, t1, Arc1))
1459     return true;
1460   return false;
1461 }
1462
1463 /* ---------------------------------------------------------------------------
1464  * Tests if point is same as line end point
1465  */
1466 static bool
1467 IsRatPointOnLineEnd (PointType *Point, LineType *Line)
1468 {
1469   if ((Point->X == Line->Point1.X
1470        && Point->Y == Line->Point1.Y)
1471       || (Point->X == Line->Point2.X && Point->Y == Line->Point2.Y))
1472     return (true);
1473   return (false);
1474 }
1475
1476 static void
1477 form_slanted_rectangle (PointType p[4], LineType *l)
1478 /* writes vertices of a squared line */
1479 {
1480    double dwx = 0, dwy = 0;
1481    if (l->Point1.Y == l->Point2.Y)
1482      dwx = l->Thickness / 2.0;
1483    else if (l->Point1.X == l->Point2.X)
1484      dwy = l->Thickness / 2.0;
1485    else
1486      {
1487        Coord dX = l->Point2.X - l->Point1.X;
1488        Coord dY = l->Point2.Y - l->Point1.Y;
1489        double r = Distance (l->Point1.X, l->Point1.Y, l->Point2.X, l->Point2.Y);
1490        dwx = l->Thickness / 2.0 / r * dX;
1491        dwy = l->Thickness / 2.0 / r * dY;
1492      }
1493     p[0].X = l->Point1.X - dwx + dwy; p[0].Y = l->Point1.Y - dwy - dwx;
1494     p[1].X = l->Point1.X - dwx - dwy; p[1].Y = l->Point1.Y - dwy + dwx;
1495     p[2].X = l->Point2.X + dwx - dwy; p[2].Y = l->Point2.Y + dwy + dwx;
1496     p[3].X = l->Point2.X + dwx + dwy; p[3].Y = l->Point2.Y + dwy - dwx;
1497 }
1498 /* ---------------------------------------------------------------------------
1499  * checks if two lines intersect
1500  * from news FAQ:
1501  *
1502  *  Let A,B,C,D be 2-space position vectors.  Then the directed line
1503  *  segments AB & CD are given by:
1504  *
1505  *      AB=A+r(B-A), r in [0,1]
1506  *      CD=C+s(D-C), s in [0,1]
1507  *
1508  *  If AB & CD intersect, then
1509  *
1510  *      A+r(B-A)=C+s(D-C), or
1511  *
1512  *      XA+r(XB-XA)=XC+s(XD-XC)
1513  *      YA+r(YB-YA)=YC+s(YD-YC)  for some r,s in [0,1]
1514  *
1515  *  Solving the above for r and s yields
1516  *
1517  *          (YA-YC)(XD-XC)-(XA-XC)(YD-YC)
1518  *      r = -----------------------------  (eqn 1)
1519  *          (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
1520  *
1521  *          (YA-YC)(XB-XA)-(XA-XC)(YB-YA)
1522  *      s = -----------------------------  (eqn 2)
1523  *          (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
1524  *
1525  *  Let I be the position vector of the intersection point, then
1526  *
1527  *      I=A+r(B-A) or
1528  *
1529  *      XI=XA+r(XB-XA)
1530  *      YI=YA+r(YB-YA)
1531  *
1532  *  By examining the values of r & s, you can also determine some
1533  *  other limiting conditions:
1534  *
1535  *      If 0<=r<=1 & 0<=s<=1, intersection exists
1536  *          r<0 or r>1 or s<0 or s>1 line segments do not intersect
1537  *
1538  *      If the denominator in eqn 1 is zero, AB & CD are parallel
1539  *      If the numerator in eqn 1 is also zero, AB & CD are coincident
1540  *
1541  *  If the intersection point of the 2 lines are needed (lines in this
1542  *  context mean infinite lines) regardless whether the two line
1543  *  segments intersect, then
1544  *
1545  *      If r>1, I is located on extension of AB
1546  *      If r<0, I is located on extension of BA
1547  *      If s>1, I is located on extension of CD
1548  *      If s<0, I is located on extension of DC
1549  *
1550  *  Also note that the denominators of eqn 1 & 2 are identical.
1551  *
1552  */
1553 bool
1554 LineLineIntersect (LineType *Line1, LineType *Line2)
1555 {
1556   double s, r;
1557   double line1_dx, line1_dy, line2_dx, line2_dy,
1558          point1_dx, point1_dy;
1559   if (TEST_FLAG (SQUAREFLAG, Line1))/* pretty reckless recursion */
1560     {
1561       PointType p[4];
1562       form_slanted_rectangle (p, Line1);
1563       return IsLineInQuadrangle (p, Line2);
1564     }
1565   /* here come only round Line1 because IsLineInQuadrangle()
1566      calls LineLineIntersect() with first argument rounded*/
1567   if (TEST_FLAG (SQUAREFLAG, Line2))
1568     {
1569       PointType p[4];
1570       form_slanted_rectangle (p, Line2);
1571       return IsLineInQuadrangle (p, Line1);
1572     }
1573   /* now all lines are round */
1574
1575   /* Check endpoints: this provides a quick exit, catches
1576    *  cases where the "real" lines don't intersect but the
1577    *  thick lines touch, and ensures that the dx/dy business
1578    *  below does not cause a divide-by-zero. */
1579   if (IsPointInPad (Line2->Point1.X, Line2->Point1.Y,
1580                     MAX (Line2->Thickness / 2 + Bloat, 0),
1581                     (PadType *) Line1)
1582        || IsPointInPad (Line2->Point2.X, Line2->Point2.Y,
1583                         MAX (Line2->Thickness / 2 + Bloat, 0),
1584                         (PadType *) Line1)
1585        || IsPointInPad (Line1->Point1.X, Line1->Point1.Y,
1586                         MAX (Line1->Thickness / 2 + Bloat, 0),
1587                         (PadType *) Line2)
1588        || IsPointInPad (Line1->Point2.X, Line1->Point2.Y,
1589                         MAX (Line1->Thickness / 2 + Bloat, 0),
1590                         (PadType *) Line2))
1591     return true;
1592
1593   /* setup some constants */
1594   line1_dx = Line1->Point2.X - Line1->Point1.X;
1595   line1_dy = Line1->Point2.Y - Line1->Point1.Y;
1596   line2_dx = Line2->Point2.X - Line2->Point1.X;
1597   line2_dy = Line2->Point2.Y - Line2->Point1.Y;
1598   point1_dx = Line1->Point1.X - Line2->Point1.X;
1599   point1_dy = Line1->Point1.Y - Line2->Point1.Y;
1600
1601   /* If either line is a point, we have failed already, since the
1602    *   endpoint check above will have caught an "intersection". */
1603   if ((line1_dx == 0 && line1_dy == 0)
1604       || (line2_dx == 0 && line2_dy == 0))
1605     return false;
1606
1607   /* set s to cross product of Line1 and the line
1608    *   Line1.Point1--Line2.Point1 (as vectors) */
1609   s = point1_dy * line1_dx - point1_dx * line1_dy;
1610
1611   /* set r to cross product of both lines (as vectors) */
1612   r = line1_dx * line2_dy - line1_dy * line2_dx;
1613
1614   /* No cross product means parallel lines, or maybe Line2 is
1615    *  zero-length. In either case, since we did a bounding-box
1616    *  check before getting here, the above IsPointInPad() checks
1617    *  will have caught any intersections. */
1618   if (r == 0.0)
1619     return false;
1620
1621   s /= r;
1622   r = (point1_dy * line2_dx - point1_dx * line2_dy) / r;
1623
1624   /* intersection is at least on AB */
1625   if (r >= 0.0 && r <= 1.0)
1626     return (s >= 0.0 && s <= 1.0);
1627
1628   /* intersection is at least on CD */
1629   /* [removed this case since it always returns false --asp] */
1630   return false;
1631 }
1632
1633 /*---------------------------------------------------
1634  *
1635  * Check for line intersection with an arc
1636  *
1637  * Mostly this is like the circle/line intersection
1638  * found in IsPointOnLine (search.c) see the detailed
1639  * discussion for the basics there.
1640  *
1641  * Since this is only an arc, not a full circle we need
1642  * to find the actual points of intersection with the
1643  * circle, and see if they are on the arc.
1644  *
1645  * To do this, we translate along the line from the point Q
1646  * plus or minus a distance delta = sqrt(Radius^2 - d^2)
1647  * but it's handy to normalize with respect to l, the line
1648  * length so a single projection is done (e.g. we don't first
1649  * find the point Q
1650  *
1651  * The projection is now of the form
1652  *
1653  *      Px = X1 + (r +- r2)(X2 - X1)
1654  *      Py = Y1 + (r +- r2)(Y2 - Y1)
1655  *
1656  * Where r2 sqrt(Radius^2 l^2 - d^2)/l^2
1657  * note that this is the variable d, not the symbol d described in IsPointOnLine
1658  * (variable d = symbol d * l)
1659  *
1660  * The end points are hell so they are checked individually
1661  */
1662 bool
1663 LineArcIntersect (LineType *Line, ArcType *Arc)
1664 {
1665   double dx, dy, dx1, dy1, l, d, r, r2, Radius;
1666   BoxType *box;
1667
1668   dx = Line->Point2.X - Line->Point1.X;
1669   dy = Line->Point2.Y - Line->Point1.Y;
1670   dx1 = Line->Point1.X - Arc->X;
1671   dy1 = Line->Point1.Y - Arc->Y;
1672   l = dx * dx + dy * dy;
1673   d = dx * dy1 - dy * dx1;
1674   d *= d;
1675
1676   /* use the larger diameter circle first */
1677   Radius =
1678     Arc->Width + MAX (0.5 * (Arc->Thickness + Line->Thickness) + Bloat, 0.0);
1679   Radius *= Radius;
1680   r2 = Radius * l - d;
1681   /* projection doesn't even intersect circle when r2 < 0 */
1682   if (r2 < 0)
1683     return (false);
1684   /* check the ends of the line in case the projected point */
1685   /* of intersection is beyond the line end */
1686   if (IsPointOnArc
1687       (Line->Point1.X, Line->Point1.Y,
1688        MAX (0.5 * Line->Thickness + Bloat, 0.0), Arc))
1689     return (true);
1690   if (IsPointOnArc
1691       (Line->Point2.X, Line->Point2.Y,
1692        MAX (0.5 * Line->Thickness + Bloat, 0.0), Arc))
1693     return (true);
1694   if (l == 0.0)
1695     return (false);
1696   r2 = sqrt (r2);
1697   Radius = -(dx * dx1 + dy * dy1);
1698   r = (Radius + r2) / l;
1699   if (r >= 0 && r <= 1
1700       && IsPointOnArc (Line->Point1.X + r * dx,
1701                        Line->Point1.Y + r * dy,
1702                        MAX (0.5 * Line->Thickness + Bloat, 0.0), Arc))
1703     return (true);
1704   r = (Radius - r2) / l;
1705   if (r >= 0 && r <= 1
1706       && IsPointOnArc (Line->Point1.X + r * dx,
1707                        Line->Point1.Y + r * dy,
1708                        MAX (0.5 * Line->Thickness + Bloat, 0.0), Arc))
1709     return (true);
1710   /* check arc end points */
1711   box = GetArcEnds (Arc);
1712   if (IsPointInPad (box->X1, box->Y1, Arc->Thickness * 0.5 + Bloat, (PadType *)Line))
1713     return true;
1714   if (IsPointInPad (box->X2, box->Y2, Arc->Thickness * 0.5 + Bloat, (PadType *)Line))
1715     return true;
1716   return false;
1717 }
1718
1719 static int
1720 LOCtoArcLine_callback (const BoxType * b, void *cl)
1721 {
1722   LineType *line = (LineType *) b;
1723   struct lo_info *i = (struct lo_info *) cl;
1724
1725   if (!TEST_FLAG (TheFlag, line) && LineArcIntersect (line, &i->arc))
1726     {
1727       if (ADD_LINE_TO_LIST (i->layer, line))
1728         longjmp (i->env, 1);
1729     }
1730   return 0;
1731 }
1732
1733 static int
1734 LOCtoArcArc_callback (const BoxType * b, void *cl)
1735 {
1736   ArcType *arc = (ArcType *) b;
1737   struct lo_info *i = (struct lo_info *) cl;
1738
1739   if (!arc->Thickness)
1740     return 0;
1741   if (!TEST_FLAG (TheFlag, arc) && ArcArcIntersect (&i->arc, arc))
1742     {
1743       if (ADD_ARC_TO_LIST (i->layer, arc))
1744         longjmp (i->env, 1);
1745     }
1746   return 0;
1747 }
1748
1749 static int
1750 LOCtoArcPad_callback (const BoxType * b, void *cl)
1751 {
1752   PadType *pad = (PadType *) b;
1753   struct lo_info *i = (struct lo_info *) cl;
1754
1755   if (!TEST_FLAG (TheFlag, pad) && i->layer ==
1756       (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER)
1757       && ArcPadIntersect (&i->arc, pad) && ADD_PAD_TO_LIST (i->layer, pad))
1758     longjmp (i->env, 1);
1759   return 0;
1760 }
1761
1762 /* ---------------------------------------------------------------------------
1763  * searches all LOs that are connected to the given arc on the given
1764  * layergroup. All found connections are added to the list
1765  *
1766  * the notation that is used is:
1767  * Xij means Xj at arc i
1768  */
1769 static bool
1770 LookupLOConnectionsToArc (ArcType *Arc, Cardinal LayerGroup)
1771 {
1772   Cardinal entry;
1773   struct lo_info info;
1774
1775   info.arc = *Arc;
1776   EXPAND_BOUNDS (&info.arc);
1777   /* loop over all layers of the group */
1778   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
1779     {
1780       Cardinal layer;
1781       GList *i;
1782
1783       layer = PCB->LayerGroups.Entries[LayerGroup][entry];
1784
1785       /* handle normal layers */
1786       if (layer < max_copper_layer)
1787         {
1788           info.layer = layer;
1789           /* add arcs */
1790           if (setjmp (info.env) == 0)
1791             r_search (LAYER_PTR (layer)->line_tree, &info.arc.BoundingBox,
1792                       NULL, LOCtoArcLine_callback, &info);
1793           else
1794             return true;
1795
1796           if (setjmp (info.env) == 0)
1797             r_search (LAYER_PTR (layer)->arc_tree, &info.arc.BoundingBox,
1798                       NULL, LOCtoArcArc_callback, &info);
1799           else
1800             return true;
1801
1802           /* now check all polygons */
1803           for (i = PCB->Data->Layer[layer].Polygon;
1804                i != NULL; i = g_list_next (i))
1805             {
1806               PolygonType *polygon = i->data;
1807               if (!TEST_FLAG (TheFlag, polygon) && IsArcInPolygon (Arc, polygon)
1808                   && ADD_POLYGON_TO_LIST (layer, polygon))
1809                 return true;
1810             }
1811         }
1812       else
1813         {
1814           info.layer = layer - max_copper_layer;
1815           if (setjmp (info.env) == 0)
1816             r_search (PCB->Data->pad_tree, &info.arc.BoundingBox, NULL,
1817                       LOCtoArcPad_callback, &info);
1818           else
1819             return true;
1820         }
1821     }
1822   return (false);
1823 }
1824
1825 static int
1826 LOCtoLineLine_callback (const BoxType * b, void *cl)
1827 {
1828   LineType *line = (LineType *) b;
1829   struct lo_info *i = (struct lo_info *) cl;
1830
1831   if (!TEST_FLAG (TheFlag, line) && LineLineIntersect (&i->line, line))
1832     {
1833       if (ADD_LINE_TO_LIST (i->layer, line))
1834         longjmp (i->env, 1);
1835     }
1836   return 0;
1837 }
1838
1839 static int
1840 LOCtoLineArc_callback (const BoxType * b, void *cl)
1841 {
1842   ArcType *arc = (ArcType *) b;
1843   struct lo_info *i = (struct lo_info *) cl;
1844
1845   if (!arc->Thickness)
1846     return 0;
1847   if (!TEST_FLAG (TheFlag, arc) && LineArcIntersect (&i->line, arc))
1848     {
1849       if (ADD_ARC_TO_LIST (i->layer, arc))
1850         longjmp (i->env, 1);
1851     }
1852   return 0;
1853 }
1854
1855 static int
1856 LOCtoLineRat_callback (const BoxType * b, void *cl)
1857 {
1858   RatType *rat = (RatType *) b;
1859   struct lo_info *i = (struct lo_info *) cl;
1860
1861   if (!TEST_FLAG (TheFlag, rat))
1862     {
1863       if ((rat->group1 == i->layer)
1864           && IsRatPointOnLineEnd (&rat->Point1, &i->line))
1865         {
1866           if (ADD_RAT_TO_LIST (rat))
1867             longjmp (i->env, 1);
1868         }
1869       else if ((rat->group2 == i->layer)
1870                && IsRatPointOnLineEnd (&rat->Point2, &i->line))
1871         {
1872           if (ADD_RAT_TO_LIST (rat))
1873             longjmp (i->env, 1);
1874         }
1875     }
1876   return 0;
1877 }
1878
1879 static int
1880 LOCtoLinePad_callback (const BoxType * b, void *cl)
1881 {
1882   PadType *pad = (PadType *) b;
1883   struct lo_info *i = (struct lo_info *) cl;
1884
1885   if (!TEST_FLAG (TheFlag, pad) && i->layer ==
1886       (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER)
1887       && LinePadIntersect (&i->line, pad) && ADD_PAD_TO_LIST (i->layer, pad))
1888     longjmp (i->env, 1);
1889   return 0;
1890 }
1891
1892 /* ---------------------------------------------------------------------------
1893  * searches all LOs that are connected to the given line on the given
1894  * layergroup. All found connections are added to the list
1895  *
1896  * the notation that is used is:
1897  * Xij means Xj at line i
1898  */
1899 static bool
1900 LookupLOConnectionsToLine (LineType *Line, Cardinal LayerGroup,
1901                            bool PolysTo)
1902 {
1903   Cardinal entry;
1904   struct lo_info info;
1905
1906   info.line = *Line;
1907   info.layer = LayerGroup;
1908   EXPAND_BOUNDS (&info.line)
1909   /* add the new rat lines */
1910   if (setjmp (info.env) == 0)
1911     r_search (PCB->Data->rat_tree, &info.line.BoundingBox, NULL,
1912               LOCtoLineRat_callback, &info);
1913   else
1914     return true;
1915
1916   /* loop over all layers of the group */
1917   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
1918     {
1919       Cardinal layer;
1920
1921       layer = PCB->LayerGroups.Entries[LayerGroup][entry];
1922
1923       /* handle normal layers */
1924       if (layer < max_copper_layer)
1925         {
1926           info.layer = layer;
1927           /* add lines */
1928           if (setjmp (info.env) == 0)
1929             r_search (LAYER_PTR (layer)->line_tree, (BoxType *) & info.line,
1930                       NULL, LOCtoLineLine_callback, &info);
1931           else
1932             return true;
1933           /* add arcs */
1934           if (setjmp (info.env) == 0)
1935             r_search (LAYER_PTR (layer)->arc_tree, (BoxType *) & info.line,
1936                       NULL, LOCtoLineArc_callback, &info);
1937           else
1938             return true;
1939           /* now check all polygons */
1940           if (PolysTo)
1941             {
1942               GList *i;
1943               for (i = PCB->Data->Layer[layer].Polygon;
1944                    i != NULL; i = g_list_next (i))
1945                 {
1946                   PolygonType *polygon = i->data;
1947                   if (!TEST_FLAG
1948                       (TheFlag, polygon) && IsLineInPolygon (Line, polygon)
1949                       && ADD_POLYGON_TO_LIST (layer, polygon))
1950                     return true;
1951                 }
1952             }
1953         }
1954       else
1955         {
1956           /* handle special 'pad' layers */
1957           info.layer = layer - max_copper_layer;
1958           if (setjmp (info.env) == 0)
1959             r_search (PCB->Data->pad_tree, &info.line.BoundingBox, NULL,
1960                       LOCtoLinePad_callback, &info);
1961           else
1962             return true;
1963         }
1964     }
1965   return (false);
1966 }
1967
1968 struct rat_info
1969 {
1970   Cardinal layer;
1971   PointType *Point;
1972   jmp_buf env;
1973 };
1974
1975 static int
1976 LOCtoRat_callback (const BoxType * b, void *cl)
1977 {
1978   LineType *line = (LineType *) b;
1979   struct rat_info *i = (struct rat_info *) cl;
1980
1981   if (!TEST_FLAG (TheFlag, line) &&
1982       ((line->Point1.X == i->Point->X &&
1983         line->Point1.Y == i->Point->Y) ||
1984        (line->Point2.X == i->Point->X && line->Point2.Y == i->Point->Y)))
1985     {
1986       if (ADD_LINE_TO_LIST (i->layer, line))
1987         longjmp (i->env, 1);
1988     }
1989   return 0;
1990 }
1991 static int
1992 PolygonToRat_callback (const BoxType * b, void *cl)
1993 {
1994   PolygonType *polygon = (PolygonType *) b;
1995   struct rat_info *i = (struct rat_info *) cl;
1996
1997   if (!TEST_FLAG (TheFlag, polygon) && polygon->Clipped &&
1998       (i->Point->X == polygon->Clipped->contours->head.point[0]) &&
1999       (i->Point->Y == polygon->Clipped->contours->head.point[1]))
2000     {
2001       if (ADD_POLYGON_TO_LIST (i->layer, polygon))
2002         longjmp (i->env, 1);
2003     }
2004   return 0;
2005 }
2006
2007 static int
2008 LOCtoPad_callback (const BoxType * b, void *cl)
2009 {
2010   PadType *pad = (PadType *) b;
2011   struct rat_info *i = (struct rat_info *) cl;
2012
2013   if (!TEST_FLAG (TheFlag, pad) && i->layer ==
2014         (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER) &&
2015       ((pad->Point1.X == i->Point->X && pad->Point1.Y == i->Point->Y) ||
2016        (pad->Point2.X == i->Point->X && pad->Point2.Y == i->Point->Y) ||
2017        ((pad->Point1.X + pad->Point2.X) / 2 == i->Point->X &&
2018         (pad->Point1.Y + pad->Point2.Y) / 2 == i->Point->Y)) &&
2019       ADD_PAD_TO_LIST (i->layer, pad))
2020     longjmp (i->env, 1);
2021   return 0;
2022 }
2023
2024 /* ---------------------------------------------------------------------------
2025  * searches all LOs that are connected to the given rat-line on the given
2026  * layergroup. All found connections are added to the list
2027  *
2028  * the notation that is used is:
2029  * Xij means Xj at line i
2030  */
2031 static bool
2032 LookupLOConnectionsToRatEnd (PointType *Point, Cardinal LayerGroup)
2033 {
2034   Cardinal entry;
2035   struct rat_info info;
2036
2037   info.Point = Point;
2038   /* loop over all layers of this group */
2039   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2040     {
2041       Cardinal layer;
2042
2043       layer = PCB->LayerGroups.Entries[LayerGroup][entry];
2044       /* handle normal layers
2045          rats don't ever touch
2046          arcs by definition
2047        */
2048
2049       if (layer < max_copper_layer)
2050         {
2051           info.layer = layer;
2052           if (setjmp (info.env) == 0)
2053             r_search_pt (LAYER_PTR (layer)->line_tree, Point, 1, NULL,
2054                       LOCtoRat_callback, &info);
2055           else
2056             return true;
2057           if (setjmp (info.env) == 0)
2058             r_search_pt (LAYER_PTR (layer)->polygon_tree, Point, 1,
2059                       NULL, PolygonToRat_callback, &info);
2060         }
2061       else
2062         {
2063           /* handle special 'pad' layers */
2064           info.layer = layer - max_copper_layer;
2065           if (setjmp (info.env) == 0)
2066             r_search_pt (PCB->Data->pad_tree, Point, 1, NULL,
2067                       LOCtoPad_callback, &info);
2068           else
2069             return true;
2070         }
2071     }
2072   return (false);
2073 }
2074
2075 static int
2076 LOCtoPadLine_callback (const BoxType * b, void *cl)
2077 {
2078   LineType *line = (LineType *) b;
2079   struct lo_info *i = (struct lo_info *) cl;
2080
2081   if (!TEST_FLAG (TheFlag, line) && LinePadIntersect (line, &i->pad))
2082     {
2083       if (ADD_LINE_TO_LIST (i->layer, line))
2084         longjmp (i->env, 1);
2085     }
2086   return 0;
2087 }
2088
2089 static int
2090 LOCtoPadArc_callback (const BoxType * b, void *cl)
2091 {
2092   ArcType *arc = (ArcType *) b;
2093   struct lo_info *i = (struct lo_info *) cl;
2094
2095   if (!arc->Thickness)
2096     return 0;
2097   if (!TEST_FLAG (TheFlag, arc) && ArcPadIntersect (arc, &i->pad))
2098     {
2099       if (ADD_ARC_TO_LIST (i->layer, arc))
2100         longjmp (i->env, 1);
2101     }
2102   return 0;
2103 }
2104
2105 static int
2106 LOCtoPadPoly_callback (const BoxType * b, void *cl)
2107 {
2108   PolygonType *polygon = (PolygonType *) b;
2109   struct lo_info *i = (struct lo_info *) cl;
2110
2111
2112   if (!TEST_FLAG (TheFlag, polygon) &&
2113       (!TEST_FLAG (CLEARPOLYFLAG, polygon) || !i->pad.Clearance))
2114     {
2115       if (IsPadInPolygon (&i->pad, polygon) &&
2116           ADD_POLYGON_TO_LIST (i->layer, polygon))
2117         longjmp (i->env, 1);
2118     }
2119   return 0;
2120 }
2121
2122 static int
2123 LOCtoPadRat_callback (const BoxType * b, void *cl)
2124 {
2125   RatType *rat = (RatType *) b;
2126   struct lo_info *i = (struct lo_info *) cl;
2127
2128   if (!TEST_FLAG (TheFlag, rat))
2129     {
2130       if (rat->group1 == i->layer &&
2131           ((rat->Point1.X == i->pad.Point1.X && rat->Point1.Y == i->pad.Point1.Y) ||
2132            (rat->Point1.X == i->pad.Point2.X && rat->Point1.Y == i->pad.Point2.Y) ||
2133            (rat->Point1.X == (i->pad.Point1.X + i->pad.Point2.X) / 2 &&
2134             rat->Point1.Y == (i->pad.Point1.Y + i->pad.Point2.Y) / 2)))
2135         {
2136           if (ADD_RAT_TO_LIST (rat))
2137             longjmp (i->env, 1);
2138         }
2139       else if (rat->group2 == i->layer &&
2140                ((rat->Point2.X == i->pad.Point1.X && rat->Point2.Y == i->pad.Point1.Y) ||
2141                 (rat->Point2.X == i->pad.Point2.X && rat->Point2.Y == i->pad.Point2.Y) ||
2142                 (rat->Point2.X == (i->pad.Point1.X + i->pad.Point2.X) / 2 &&
2143                  rat->Point2.Y == (i->pad.Point1.Y + i->pad.Point2.Y) / 2)))
2144         {
2145           if (ADD_RAT_TO_LIST (rat))
2146             longjmp (i->env, 1);
2147         }
2148     }
2149   return 0;
2150 }
2151
2152 static int
2153 LOCtoPadPad_callback (const BoxType * b, void *cl)
2154 {
2155   PadType *pad = (PadType *) b;
2156   struct lo_info *i = (struct lo_info *) cl;
2157
2158   if (!TEST_FLAG (TheFlag, pad) && i->layer ==
2159       (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER)
2160       && PadPadIntersect (pad, &i->pad) && ADD_PAD_TO_LIST (i->layer, pad))
2161     longjmp (i->env, 1);
2162   return 0;
2163 }
2164
2165 /* ---------------------------------------------------------------------------
2166  * searches all LOs that are connected to the given pad on the given
2167  * layergroup. All found connections are added to the list
2168  */
2169 static bool
2170 LookupLOConnectionsToPad (PadType *Pad, Cardinal LayerGroup)
2171 {
2172   Cardinal entry;
2173   struct lo_info info;
2174
2175   if (!TEST_FLAG (SQUAREFLAG, Pad))
2176     return (LookupLOConnectionsToLine ((LineType *) Pad, LayerGroup, false));
2177
2178   info.pad = *Pad;
2179   EXPAND_BOUNDS (&info.pad);
2180   /* add the new rat lines */
2181   info.layer = LayerGroup;
2182   if (setjmp (info.env) == 0)
2183     r_search (PCB->Data->rat_tree, &info.pad.BoundingBox, NULL,
2184               LOCtoPadRat_callback, &info);
2185   else
2186     return true;
2187
2188   /* loop over all layers of the group */
2189   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2190     {
2191       Cardinal layer;
2192
2193       layer = PCB->LayerGroups.Entries[LayerGroup][entry];
2194       /* handle normal layers */
2195       if (layer < max_copper_layer)
2196         {
2197           info.layer = layer;
2198           /* add lines */
2199           if (setjmp (info.env) == 0)
2200             r_search (LAYER_PTR (layer)->line_tree, &info.pad.BoundingBox,
2201                       NULL, LOCtoPadLine_callback, &info);
2202           else
2203             return true;
2204           /* add arcs */
2205           if (setjmp (info.env) == 0)
2206             r_search (LAYER_PTR (layer)->arc_tree, &info.pad.BoundingBox,
2207                       NULL, LOCtoPadArc_callback, &info);
2208           else
2209             return true;
2210           /* add polygons */
2211           if (setjmp (info.env) == 0)
2212             r_search (LAYER_PTR (layer)->polygon_tree, &info.pad.BoundingBox,
2213                       NULL, LOCtoPadPoly_callback, &info);
2214           else
2215             return true;
2216         }
2217       else
2218         {
2219           /* handle special 'pad' layers */
2220           info.layer = layer - max_copper_layer;
2221           if (setjmp (info.env) == 0)
2222             r_search (PCB->Data->pad_tree, (BoxType *) & info.pad, NULL,
2223                       LOCtoPadPad_callback, &info);
2224           else
2225             return true;
2226         }
2227
2228     }
2229   return (false);
2230 }
2231
2232 static int
2233 LOCtoPolyLine_callback (const BoxType * b, void *cl)
2234 {
2235   LineType *line = (LineType *) b;
2236   struct lo_info *i = (struct lo_info *) cl;
2237
2238   if (!TEST_FLAG (TheFlag, line) && IsLineInPolygon (line, &i->polygon))
2239     {
2240       if (ADD_LINE_TO_LIST (i->layer, line))
2241         longjmp (i->env, 1);
2242     }
2243   return 0;
2244 }
2245
2246 static int
2247 LOCtoPolyArc_callback (const BoxType * b, void *cl)
2248 {
2249   ArcType *arc = (ArcType *) b;
2250   struct lo_info *i = (struct lo_info *) cl;
2251
2252   if (!arc->Thickness)
2253     return 0;
2254   if (!TEST_FLAG (TheFlag, arc) && IsArcInPolygon (arc, &i->polygon))
2255     {
2256       if (ADD_ARC_TO_LIST (i->layer, arc))
2257         longjmp (i->env, 1);
2258     }
2259   return 0;
2260 }
2261
2262 static int
2263 LOCtoPolyPad_callback (const BoxType * b, void *cl)
2264 {
2265   PadType *pad = (PadType *) b;
2266   struct lo_info *i = (struct lo_info *) cl;
2267
2268   if (!TEST_FLAG (TheFlag, pad) && i->layer ==
2269       (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER)
2270       && IsPadInPolygon (pad, &i->polygon))
2271     {
2272       if (ADD_PAD_TO_LIST (i->layer, pad))
2273         longjmp (i->env, 1);
2274     }
2275   return 0;
2276 }
2277
2278 static int
2279 LOCtoPolyRat_callback (const BoxType * b, void *cl)
2280 {
2281   RatType *rat = (RatType *) b;
2282   struct lo_info *i = (struct lo_info *) cl;
2283
2284   if (!TEST_FLAG (TheFlag, rat))
2285     {
2286       if ((rat->Point1.X == (i->polygon.Clipped->contours->head.point[0]) &&
2287            rat->Point1.Y == (i->polygon.Clipped->contours->head.point[1]) &&
2288            rat->group1 == i->layer) ||
2289           (rat->Point2.X == (i->polygon.Clipped->contours->head.point[0]) &&
2290            rat->Point2.Y == (i->polygon.Clipped->contours->head.point[1]) &&
2291            rat->group2 == i->layer))
2292         if (ADD_RAT_TO_LIST (rat))
2293           longjmp (i->env, 1);
2294     }
2295   return 0;
2296 }
2297
2298
2299 /* ---------------------------------------------------------------------------
2300  * looks up LOs that are connected to the given polygon
2301  * on the given layergroup. All found connections are added to the list
2302  */
2303 static bool
2304 LookupLOConnectionsToPolygon (PolygonType *Polygon, Cardinal LayerGroup)
2305 {
2306   Cardinal entry;
2307   struct lo_info info;
2308
2309   if (!Polygon->Clipped)
2310     return false;
2311   info.polygon = *Polygon;
2312   EXPAND_BOUNDS (&info.polygon);
2313   info.layer = LayerGroup;
2314   /* check rats */
2315   if (setjmp (info.env) == 0)
2316     r_search (PCB->Data->rat_tree, (BoxType *) & info.polygon, NULL,
2317               LOCtoPolyRat_callback, &info);
2318   else
2319     return true;
2320 /* loop over all layers of the group */
2321   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2322     {
2323       Cardinal layer;
2324
2325       layer = PCB->LayerGroups.Entries[LayerGroup][entry];
2326
2327       /* handle normal layers */
2328       if (layer < max_copper_layer)
2329         {
2330           GList *i;
2331
2332           /* check all polygons */
2333           for (i = PCB->Data->Layer[layer].Polygon;
2334                i != NULL; i = g_list_next (i))
2335             {
2336               PolygonType *polygon = i->data;
2337               if (!TEST_FLAG (TheFlag, polygon)
2338                   && IsPolygonInPolygon (polygon, Polygon)
2339                   && ADD_POLYGON_TO_LIST (layer, polygon))
2340                 return true;
2341             }
2342
2343           info.layer = layer;
2344           /* check all lines */
2345           if (setjmp (info.env) == 0)
2346             r_search (LAYER_PTR (layer)->line_tree,
2347                       (BoxType *) & info.polygon, NULL,
2348                       LOCtoPolyLine_callback, &info);
2349           else
2350             return true;
2351           /* check all arcs */
2352           if (setjmp (info.env) == 0)
2353             r_search (LAYER_PTR (layer)->arc_tree, (BoxType *) & info.polygon,
2354                       NULL, LOCtoPolyArc_callback, &info);
2355           else
2356             return true;
2357         }
2358       else
2359         {
2360           info.layer = layer - max_copper_layer;
2361           if (setjmp (info.env) == 0)
2362             r_search (PCB->Data->pad_tree, (BoxType *) & info.polygon,
2363                       NULL, LOCtoPolyPad_callback, &info);
2364           else
2365             return true;
2366         }
2367     }
2368   return (false);
2369 }
2370
2371 /* ---------------------------------------------------------------------------
2372  * checks if an arc has a connection to a polygon
2373  *
2374  * - first check if the arc can intersect with the polygon by
2375  *   evaluating the bounding boxes
2376  * - check the two end points of the arc. If none of them matches
2377  * - check all segments of the polygon against the arc.
2378  */
2379 static bool
2380 IsArcInPolygon (ArcType *Arc, PolygonType *Polygon)
2381 {
2382   BoxType *Box = (BoxType *) Arc;
2383
2384   /* arcs with clearance never touch polys */
2385   if (TEST_FLAG (CLEARPOLYFLAG, Polygon) && TEST_FLAG (CLEARLINEFLAG, Arc))
2386     return false;
2387   if (!Polygon->Clipped)
2388     return false;
2389   if (Box->X1 <= Polygon->Clipped->contours->xmax + Bloat
2390       && Box->X2 >= Polygon->Clipped->contours->xmin - Bloat
2391       && Box->Y1 <= Polygon->Clipped->contours->ymax + Bloat
2392       && Box->Y2 >= Polygon->Clipped->contours->ymin - Bloat)
2393     {
2394       POLYAREA *ap;
2395
2396       if (!(ap = ArcPoly (Arc, Arc->Thickness + Bloat)))
2397         return false;           /* error */
2398       return isects (ap, Polygon, true);
2399     }
2400   return false;
2401 }
2402
2403 /* ---------------------------------------------------------------------------
2404  * checks if a line has a connection to a polygon
2405  *
2406  * - first check if the line can intersect with the polygon by
2407  *   evaluating the bounding boxes
2408  * - check the two end points of the line. If none of them matches
2409  * - check all segments of the polygon against the line.
2410  */
2411 static bool
2412 IsLineInPolygon (LineType *Line, PolygonType *Polygon)
2413 {
2414   BoxType *Box = (BoxType *) Line;
2415   POLYAREA *lp;
2416
2417   /* lines with clearance never touch polygons */
2418   if (TEST_FLAG (CLEARPOLYFLAG, Polygon) && TEST_FLAG (CLEARLINEFLAG, Line))
2419     return false;
2420   if (!Polygon->Clipped)
2421     return false;
2422   if (TEST_FLAG(SQUAREFLAG,Line)&&(Line->Point1.X==Line->Point2.X||Line->Point1.Y==Line->Point2.Y))
2423      {
2424        Coord wid = (Line->Thickness + Bloat + 1) / 2;
2425        Coord x1, x2, y1, y2;
2426
2427        x1 = MIN (Line->Point1.X, Line->Point2.X) - wid;
2428        y1 = MIN (Line->Point1.Y, Line->Point2.Y) - wid;
2429        x2 = MAX (Line->Point1.X, Line->Point2.X) + wid;
2430        y2 = MAX (Line->Point1.Y, Line->Point2.Y) + wid;
2431        return IsRectangleInPolygon (x1, y1, x2, y2, Polygon);
2432      }
2433   if (Box->X1 <= Polygon->Clipped->contours->xmax + Bloat
2434       && Box->X2 >= Polygon->Clipped->contours->xmin - Bloat
2435       && Box->Y1 <= Polygon->Clipped->contours->ymax + Bloat
2436       && Box->Y2 >= Polygon->Clipped->contours->ymin - Bloat)
2437     {
2438       if (!(lp = LinePoly (Line, Line->Thickness + Bloat)))
2439         return FALSE;           /* error */
2440       return isects (lp, Polygon, true);
2441     }
2442   return false;
2443 }
2444
2445 /* ---------------------------------------------------------------------------
2446  * checks if a pad connects to a non-clearing polygon
2447  *
2448  * The polygon is assumed to already have been proven non-clearing
2449  */
2450 static bool
2451 IsPadInPolygon (PadType *pad, PolygonType *polygon)
2452 {
2453     return IsLineInPolygon ((LineType *) pad, polygon);
2454 }
2455
2456 /* ---------------------------------------------------------------------------
2457  * checks if a polygon has a connection to a second one
2458  *
2459  * First check all points out of P1 against P2 and vice versa.
2460  * If both fail check all lines of P1 against the ones of P2
2461  */
2462 static bool
2463 IsPolygonInPolygon (PolygonType *P1, PolygonType *P2)
2464 {
2465   if (!P1->Clipped || !P2->Clipped)
2466     return false;
2467   assert (P1->Clipped->contours);
2468   assert (P2->Clipped->contours);
2469
2470   /* first check if both bounding boxes intersect. If not, return quickly */
2471   if (P1->Clipped->contours->xmin - Bloat > P2->Clipped->contours->xmax ||
2472       P1->Clipped->contours->xmax + Bloat < P2->Clipped->contours->xmin ||
2473       P1->Clipped->contours->ymin - Bloat > P2->Clipped->contours->ymax ||
2474       P1->Clipped->contours->ymax + Bloat < P2->Clipped->contours->ymin)
2475     return false;
2476
2477   /* first check un-bloated case */
2478   if (isects (P1->Clipped, P2, false))
2479     return TRUE;
2480
2481   /* now the difficult case of bloated */
2482   if (Bloat > 0)
2483     {
2484       PLINE *c;
2485       for (c = P1->Clipped->contours; c; c = c->next)
2486         {
2487           LineType line;
2488           VNODE *v = &c->head;
2489           if (c->xmin - Bloat <= P2->Clipped->contours->xmax &&
2490               c->xmax + Bloat >= P2->Clipped->contours->xmin &&
2491               c->ymin - Bloat <= P2->Clipped->contours->ymax &&
2492               c->ymax + Bloat >= P2->Clipped->contours->ymin)
2493             {
2494
2495               line.Point1.X = v->point[0];
2496               line.Point1.Y = v->point[1];
2497               line.Thickness = 2 * Bloat;
2498               line.Clearance = 0;
2499               line.Flags = NoFlags ();
2500               for (v = v->next; v != &c->head; v = v->next)
2501                 {
2502                   line.Point2.X = v->point[0];
2503                   line.Point2.Y = v->point[1];
2504                   SetLineBoundingBox (&line);
2505                   if (IsLineInPolygon (&line, P2))
2506                     return (true);
2507                   line.Point1.X = line.Point2.X;
2508                   line.Point1.Y = line.Point2.Y;
2509                 }
2510             }
2511         }
2512     }
2513
2514   return (false);
2515 }
2516
2517 /* ---------------------------------------------------------------------------
2518  * writes the several names of an element to a file
2519  */
2520 static void
2521 PrintElementNameList (ElementType *Element, FILE * FP)
2522 {
2523   static DynamicStringType cname, pname, vname;
2524
2525   CreateQuotedString (&cname, (char *)EMPTY (DESCRIPTION_NAME (Element)));
2526   CreateQuotedString (&pname, (char *)EMPTY (NAMEONPCB_NAME (Element)));
2527   CreateQuotedString (&vname, (char *)EMPTY (VALUE_NAME (Element)));
2528   fprintf (FP, "(%s %s %s)\n", cname.Data, pname.Data, vname.Data);
2529 }
2530
2531 /* ---------------------------------------------------------------------------
2532  * writes the several names of an element to a file
2533  */
2534 static void
2535 PrintConnectionElementName (ElementType *Element, FILE * FP)
2536 {
2537   fputs ("Element", FP);
2538   PrintElementNameList (Element, FP);
2539   fputs ("{\n", FP);
2540 }
2541
2542 /* ---------------------------------------------------------------------------
2543  * prints one {pin,pad,via}/element entry of connection lists
2544  */
2545 static void
2546 PrintConnectionListEntry (char *ObjName, ElementType *Element,
2547                           bool FirstOne, FILE * FP)
2548 {
2549   static DynamicStringType oname;
2550
2551   CreateQuotedString (&oname, ObjName);
2552   if (FirstOne)
2553     fprintf (FP, "\t%s\n\t{\n", oname.Data);
2554   else
2555     {
2556       fprintf (FP, "\t\t%s ", oname.Data);
2557       if (Element)
2558         PrintElementNameList (Element, FP);
2559       else
2560         fputs ("(__VIA__)\n", FP);
2561     }
2562 }
2563
2564 /* ---------------------------------------------------------------------------
2565  * prints all found connections of a pads to file FP
2566  * the connections are stacked in 'PadList'
2567  */
2568 static void
2569 PrintPadConnections (Cardinal Layer, FILE * FP, bool IsFirst)
2570 {
2571   Cardinal i;
2572   PadType *ptr;
2573
2574   if (!PadList[Layer].Number)
2575     return;
2576
2577   /* the starting pad */
2578   if (IsFirst)
2579     {
2580       ptr = PADLIST_ENTRY (Layer, 0);
2581       if (ptr != NULL)
2582         PrintConnectionListEntry ((char *)UNKNOWN (ptr->Name), NULL, true, FP);
2583       else
2584         printf ("Skipping NULL ptr in 1st part of PrintPadConnections\n");
2585     }
2586
2587   /* we maybe have to start with i=1 if we are handling the
2588    * starting-pad itself
2589    */
2590   for (i = IsFirst ? 1 : 0; i < PadList[Layer].Number; i++)
2591     {
2592       ptr = PADLIST_ENTRY (Layer, i);
2593       if (ptr != NULL)
2594         PrintConnectionListEntry ((char *)EMPTY (ptr->Name), (ElementType *)ptr->Element, false, FP);
2595       else
2596         printf ("Skipping NULL ptr in 2nd part of PrintPadConnections\n");
2597     }
2598 }
2599
2600 /* ---------------------------------------------------------------------------
2601  * prints all found connections of a pin to file FP
2602  * the connections are stacked in 'PVList'
2603  */
2604 static void
2605 PrintPinConnections (FILE * FP, bool IsFirst)
2606 {
2607   Cardinal i;
2608   PinType *pv;
2609
2610   if (!PVList.Number)
2611     return;
2612
2613   if (IsFirst)
2614     {
2615       /* the starting pin */
2616       pv = PVLIST_ENTRY (0);
2617       PrintConnectionListEntry ((char *)EMPTY (pv->Name), NULL, true, FP);
2618     }
2619
2620   /* we maybe have to start with i=1 if we are handling the
2621    * starting-pin itself
2622    */
2623   for (i = IsFirst ? 1 : 0; i < PVList.Number; i++)
2624     {
2625       /* get the elements name or assume that its a via */
2626       pv = PVLIST_ENTRY (i);
2627       PrintConnectionListEntry ((char *)EMPTY (pv->Name), (ElementType *)pv->Element, false, FP);
2628     }
2629 }
2630
2631 /* ---------------------------------------------------------------------------
2632  * checks if all lists of new objects are handled
2633  */
2634 static bool
2635 ListsEmpty (bool AndRats)
2636 {
2637   bool empty;
2638   int i;
2639
2640   empty = (PVList.Location >= PVList.Number);
2641   if (AndRats)
2642     empty = empty && (RatList.Location >= RatList.Number);
2643   for (i = 0; i < max_copper_layer && empty; i++)
2644     if (!LAYER_PTR (i)->no_drc)
2645       empty = empty && LineList[i].Location >= LineList[i].Number
2646         && ArcList[i].Location >= ArcList[i].Number
2647         && PolygonList[i].Location >= PolygonList[i].Number;
2648   return (empty);
2649 }
2650
2651 static void
2652 reassign_no_drc_flags (void)
2653 {
2654   int layer;
2655
2656   for (layer = 0; layer < max_copper_layer; layer++)
2657     {
2658       LayerType *l = LAYER_PTR (layer);
2659       l->no_drc = AttributeGet (l, "PCB::skip-drc") != NULL;
2660     }
2661 }
2662
2663
2664
2665
2666 /* ---------------------------------------------------------------------------
2667  * loops till no more connections are found
2668  */
2669 static bool
2670 DoIt (bool AndRats, bool AndDraw)
2671 {
2672   bool newone = false;
2673   reassign_no_drc_flags ();
2674   do
2675     {
2676       /* lookup connections; these are the steps (2) to (4)
2677        * from the description
2678        */
2679       newone = LookupPVConnectionsToPVList () ||
2680                LookupLOConnectionsToPVList (AndRats) ||
2681                LookupLOConnectionsToLOList (AndRats) ||
2682                LookupPVConnectionsToLOList (AndRats);
2683       if (AndDraw)
2684         DrawNewConnections ();
2685     }
2686   while (!newone && !ListsEmpty (AndRats));
2687   if (AndDraw)
2688     Draw ();
2689   return (newone);
2690 }
2691
2692 /* ---------------------------------------------------------------------------
2693  * prints all unused pins of an element to file FP
2694  */
2695 static bool
2696 PrintAndSelectUnusedPinsAndPadsOfElement (ElementType *Element, FILE * FP)
2697 {
2698   bool first = true;
2699   Cardinal number;
2700   static DynamicStringType oname;
2701
2702   /* check all pins in element */
2703
2704   PIN_LOOP (Element);
2705   {
2706     if (!TEST_FLAG (HOLEFLAG, pin))
2707       {
2708         /* pin might have bee checked before, add to list if not */
2709         if (!TEST_FLAG (TheFlag, pin) && FP)
2710           {
2711             int i;
2712             if (ADD_PV_TO_LIST (pin))
2713               return true;
2714             DoIt (true, true);
2715             number = PadList[COMPONENT_LAYER].Number
2716               + PadList[SOLDER_LAYER].Number + PVList.Number;
2717             /* the pin has no connection if it's the only
2718              * list entry; don't count vias
2719              */
2720             for (i = 0; i < PVList.Number; i++)
2721               if (!PVLIST_ENTRY (i)->Element)
2722                 number--;
2723             if (number == 1)
2724               {
2725                 /* output of element name if not already done */
2726                 if (first)
2727                   {
2728                     PrintConnectionElementName (Element, FP);
2729                     first = false;
2730                   }
2731
2732                 /* write name to list and draw selected object */
2733                 CreateQuotedString (&oname, (char *)EMPTY (pin->Name));
2734                 fprintf (FP, "\t%s\n", oname.Data);
2735                 SET_FLAG (SELECTEDFLAG, pin);
2736                 DrawPin (pin);
2737               }
2738
2739             /* reset found objects for the next pin */
2740             if (PrepareNextLoop (FP))
2741               return (true);
2742           }
2743       }
2744   }
2745   END_LOOP;
2746
2747   /* check all pads in element */
2748   PAD_LOOP (Element);
2749   {
2750     /* lookup pad in list */
2751     /* pad might has bee checked before, add to list if not */
2752     if (!TEST_FLAG (TheFlag, pad) && FP)
2753       {
2754         int i;
2755         if (ADD_PAD_TO_LIST (TEST_FLAG (ONSOLDERFLAG, pad)
2756                              ? SOLDER_LAYER : COMPONENT_LAYER, pad))
2757           return true;
2758         DoIt (true, true);
2759         number = PadList[COMPONENT_LAYER].Number
2760           + PadList[SOLDER_LAYER].Number + PVList.Number;
2761         /* the pin has no connection if it's the only
2762          * list entry; don't count vias
2763          */
2764         for (i = 0; i < PVList.Number; i++)
2765           if (!PVLIST_ENTRY (i)->Element)
2766             number--;
2767         if (number == 1)
2768           {
2769             /* output of element name if not already done */
2770             if (first)
2771               {
2772                 PrintConnectionElementName (Element, FP);
2773                 first = false;
2774               }
2775
2776             /* write name to list and draw selected object */
2777             CreateQuotedString (&oname, (char *)EMPTY (pad->Name));
2778             fprintf (FP, "\t%s\n", oname.Data);
2779             SET_FLAG (SELECTEDFLAG, pad);
2780             DrawPad (pad);
2781           }
2782
2783         /* reset found objects for the next pin */
2784         if (PrepareNextLoop (FP))
2785           return (true);
2786       }
2787   }
2788   END_LOOP;
2789
2790   /* print separator if element has unused pins or pads */
2791   if (!first)
2792     {
2793       fputs ("}\n\n", FP);
2794       SEPARATE (FP);
2795     }
2796   return (false);
2797 }
2798
2799 /* ---------------------------------------------------------------------------
2800  * resets some flags for looking up the next pin/pad
2801  */
2802 static bool
2803 PrepareNextLoop (FILE * FP)
2804 {
2805   Cardinal layer;
2806
2807   /* reset found LOs for the next pin */
2808   for (layer = 0; layer < max_copper_layer; layer++)
2809     {
2810       LineList[layer].Location = LineList[layer].Number = 0;
2811       ArcList[layer].Location = ArcList[layer].Number = 0;
2812       PolygonList[layer].Location = PolygonList[layer].Number = 0;
2813     }
2814
2815   /* reset found pads */
2816   for (layer = 0; layer < 2; layer++)
2817     PadList[layer].Location = PadList[layer].Number = 0;
2818
2819   /* reset PVs */
2820   PVList.Number = PVList.Location = 0;
2821   RatList.Number = RatList.Location = 0;
2822
2823   return (false);
2824 }
2825
2826 /* ---------------------------------------------------------------------------
2827  * finds all connections to the pins of the passed element.
2828  * The result is written to file FP
2829  * Returns true if operation was aborted
2830  */
2831 static bool
2832 PrintElementConnections (ElementType *Element, FILE * FP, bool AndDraw)
2833 {
2834   PrintConnectionElementName (Element, FP);
2835
2836   /* check all pins in element */
2837   PIN_LOOP (Element);
2838   {
2839     /* pin might have been checked before, add to list if not */
2840     if (TEST_FLAG (TheFlag, pin))
2841       {
2842         PrintConnectionListEntry ((char *)EMPTY (pin->Name), NULL, true, FP);
2843         fputs ("\t\t__CHECKED_BEFORE__\n\t}\n", FP);
2844         continue;
2845       }
2846     if (ADD_PV_TO_LIST (pin))
2847       return true;
2848     DoIt (true, AndDraw);
2849     /* printout all found connections */
2850     PrintPinConnections (FP, true);
2851     PrintPadConnections (COMPONENT_LAYER, FP, false);
2852     PrintPadConnections (SOLDER_LAYER, FP, false);
2853     fputs ("\t}\n", FP);
2854     if (PrepareNextLoop (FP))
2855       return (true);
2856   }
2857   END_LOOP;
2858
2859   /* check all pads in element */
2860   PAD_LOOP (Element);
2861   {
2862     Cardinal layer;
2863     /* pad might have been checked before, add to list if not */
2864     if (TEST_FLAG (TheFlag, pad))
2865       {
2866         PrintConnectionListEntry ((char *)EMPTY (pad->Name), NULL, true, FP);
2867         fputs ("\t\t__CHECKED_BEFORE__\n\t}\n", FP);
2868         continue;
2869       }
2870     layer = TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER;
2871     if (ADD_PAD_TO_LIST (layer, pad))
2872       return true;
2873     DoIt (true, AndDraw);
2874     /* print all found connections */
2875     PrintPadConnections (layer, FP, true);
2876     PrintPadConnections (layer ==
2877                          (COMPONENT_LAYER ? SOLDER_LAYER : COMPONENT_LAYER),
2878                          FP, false);
2879     PrintPinConnections (FP, false);
2880     fputs ("\t}\n", FP);
2881     if (PrepareNextLoop (FP))
2882       return (true);
2883   }
2884   END_LOOP;
2885   fputs ("}\n\n", FP);
2886   return (false);
2887 }
2888
2889 /* ---------------------------------------------------------------------------
2890  * draws all new connections which have been found since the
2891  * routine was called the last time
2892  */
2893 static void
2894 DrawNewConnections (void)
2895 {
2896   int i;
2897   Cardinal position;
2898
2899   /* decrement 'i' to keep layerstack order */
2900   for (i = max_copper_layer - 1; i != -1; i--)
2901     {
2902       Cardinal layer = LayerStack[i];
2903
2904       if (PCB->Data->Layer[layer].On)
2905         {
2906           /* draw all new lines */
2907           position = LineList[layer].DrawLocation;
2908           for (; position < LineList[layer].Number; position++)
2909             DrawLine (LAYER_PTR (layer), LINELIST_ENTRY (layer, position));
2910           LineList[layer].DrawLocation = LineList[layer].Number;
2911
2912           /* draw all new arcs */
2913           position = ArcList[layer].DrawLocation;
2914           for (; position < ArcList[layer].Number; position++)
2915             DrawArc (LAYER_PTR (layer), ARCLIST_ENTRY (layer, position));
2916           ArcList[layer].DrawLocation = ArcList[layer].Number;
2917
2918           /* draw all new polygons */
2919           position = PolygonList[layer].DrawLocation;
2920           for (; position < PolygonList[layer].Number; position++)
2921             DrawPolygon (LAYER_PTR (layer), POLYGONLIST_ENTRY (layer, position));
2922           PolygonList[layer].DrawLocation = PolygonList[layer].Number;
2923         }
2924     }
2925
2926   /* draw all new pads */
2927   if (PCB->PinOn)
2928     for (i = 0; i < 2; i++)
2929       {
2930         position = PadList[i].DrawLocation;
2931
2932         for (; position < PadList[i].Number; position++)
2933           DrawPad (PADLIST_ENTRY (i, position));
2934         PadList[i].DrawLocation = PadList[i].Number;
2935       }
2936
2937   /* draw all new PVs; 'PVList' holds a list of pointers to the
2938    * sorted array pointers to PV data
2939    */
2940   while (PVList.DrawLocation < PVList.Number)
2941     {
2942       PinType *pv = PVLIST_ENTRY (PVList.DrawLocation);
2943
2944       if (TEST_FLAG (PINFLAG, pv))
2945         {
2946           if (PCB->PinOn)
2947             DrawPin (pv);
2948         }
2949       else if (PCB->ViaOn)
2950         DrawVia (pv);
2951       PVList.DrawLocation++;
2952     }
2953   /* draw the new rat-lines */
2954   if (PCB->RatOn)
2955     {
2956       position = RatList.DrawLocation;
2957       for (; position < RatList.Number; position++)
2958         DrawRat (RATLIST_ENTRY (position));
2959       RatList.DrawLocation = RatList.Number;
2960     }
2961 }
2962
2963 /* ---------------------------------------------------------------------------
2964  * find all connections to pins within one element
2965  */
2966 void
2967 LookupElementConnections (ElementType *Element, FILE * FP)
2968 {
2969   /* reset all currently marked connections */
2970   User = true;
2971   TheFlag = FOUNDFLAG;
2972   ResetConnections (true, FOUNDFLAG);
2973   InitConnectionLookup ();
2974   PrintElementConnections (Element, FP, true);
2975   SetChangedFlag (true);
2976   if (Settings.RingBellWhenFinished)
2977     gui->beep ();
2978   FreeConnectionLookupMemory ();
2979   IncrementUndoSerialNumber ();
2980   User = false;
2981   Draw ();
2982 }
2983
2984 /* ---------------------------------------------------------------------------
2985  * find all connections to pins of all element
2986  */
2987 void
2988 LookupConnectionsToAllElements (FILE * FP)
2989 {
2990   /* reset all currently marked connections */
2991   User = false;
2992   TheFlag = FOUNDFLAG;
2993   ResetConnections (false, FOUNDFLAG);
2994   InitConnectionLookup ();
2995
2996   ELEMENT_LOOP (PCB->Data);
2997   {
2998     /* break if abort dialog returned true */
2999     if (PrintElementConnections (element, FP, false))
3000       break;
3001     SEPARATE (FP);
3002     if (Settings.ResetAfterElement && n != 1)
3003       ResetConnections (false, FOUNDFLAG);
3004   }
3005   END_LOOP;
3006   if (Settings.RingBellWhenFinished)
3007     gui->beep ();
3008   ResetConnections (false, FOUNDFLAG);
3009   FreeConnectionLookupMemory ();
3010   Redraw ();
3011 }
3012
3013 /*---------------------------------------------------------------------------
3014  * add the starting object to the list of found objects
3015  */
3016 static bool
3017 ListStart (int type, void *ptr1, void *ptr2, void *ptr3)
3018 {
3019   DumpList ();
3020   switch (type)
3021     {
3022     case PIN_TYPE:
3023     case VIA_TYPE:
3024       {
3025         if (ADD_PV_TO_LIST ((PinType *) ptr2))
3026           return true;
3027         break;
3028       }
3029
3030     case RATLINE_TYPE:
3031       {
3032         if (ADD_RAT_TO_LIST ((RatType *) ptr1))
3033           return true;
3034         break;
3035       }
3036
3037     case LINE_TYPE:
3038       {
3039         int layer = GetLayerNumber (PCB->Data,
3040                                     (LayerType *) ptr1);
3041
3042         if (ADD_LINE_TO_LIST (layer, (LineType *) ptr2))
3043           return true;
3044         break;
3045       }
3046
3047     case ARC_TYPE:
3048       {
3049         int layer = GetLayerNumber (PCB->Data,
3050                                     (LayerType *) ptr1);
3051
3052         if (ADD_ARC_TO_LIST (layer, (ArcType *) ptr2))
3053           return true;
3054         break;
3055       }
3056
3057     case POLYGON_TYPE:
3058       {
3059         int layer = GetLayerNumber (PCB->Data,
3060                                     (LayerType *) ptr1);
3061
3062         if (ADD_POLYGON_TO_LIST (layer, (PolygonType *) ptr2))
3063           return true;
3064         break;
3065       }
3066
3067     case PAD_TYPE:
3068       {
3069         PadType *pad = (PadType *) ptr2;
3070         if (ADD_PAD_TO_LIST
3071             (TEST_FLAG
3072              (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER, pad))
3073           return true;
3074         break;
3075       }
3076     }
3077   return (false);
3078 }
3079
3080
3081 /* ---------------------------------------------------------------------------
3082  * looks up all connections from the object at the given coordinates
3083  * the TheFlag (normally 'FOUNDFLAG') is set for all objects found
3084  * the objects are re-drawn if AndDraw is true
3085  * also the action is marked as undoable if AndDraw is true
3086  */
3087 void
3088 LookupConnection (Coord X, Coord Y, bool AndDraw, Coord Range, int which_flag,
3089                   bool AndRats)
3090 {
3091   void *ptr1, *ptr2, *ptr3;
3092   char *name;
3093   int type;
3094
3095   /* check if there are any pins or pads at that position */
3096
3097         reassign_no_drc_flags ();
3098
3099   type
3100     = SearchObjectByLocation (LOOKUP_FIRST, &ptr1, &ptr2, &ptr3, X, Y, Range);
3101   if (type == NO_TYPE)
3102     {
3103       type = SearchObjectByLocation (
3104         LOOKUP_MORE & ~(AndRats ? RATLINE_TYPE : 0),
3105         &ptr1, &ptr2, &ptr3, X, Y, Range);
3106       if (type == NO_TYPE)
3107         return;
3108       if (type & SILK_TYPE)
3109         {
3110           int laynum = GetLayerNumber (PCB->Data,
3111                                        (LayerType *) ptr1);
3112
3113           /* don't mess with non-conducting objects! */
3114           if (laynum >= max_copper_layer || ((LayerType *)ptr1)->no_drc)
3115             return;
3116         }
3117     }
3118
3119   name = ConnectionName (type, ptr1, ptr2);
3120   hid_actionl ("NetlistShow", name, NULL);
3121
3122   TheFlag = which_flag;
3123   User = AndDraw;
3124   InitConnectionLookup ();
3125
3126   /* now add the object to the appropriate list and start scanning
3127    * This is step (1) from the description
3128    */
3129   ListStart (type, ptr1, ptr2, ptr3);
3130   DoIt (AndRats, AndDraw);
3131   if (User)
3132     IncrementUndoSerialNumber ();
3133   User = false;
3134
3135   /* we are done */
3136   if (AndDraw)
3137     Draw ();
3138   if (AndDraw && Settings.RingBellWhenFinished)
3139     gui->beep ();
3140   FreeConnectionLookupMemory ();
3141 }
3142
3143 /* ---------------------------------------------------------------------------
3144  * find connections for rats nesting
3145  * assumes InitConnectionLookup() has already been done
3146  */
3147 void
3148 RatFindHook (int type, void *ptr1, void *ptr2, void *ptr3,
3149              bool undo, int flag, bool AndRats)
3150 {
3151   User = undo;
3152   TheFlag = flag;
3153   DumpList ();
3154   ListStart (type, ptr1, ptr2, ptr3);
3155   DoIt (AndRats, false);
3156   User = false;
3157 }
3158
3159 /* ---------------------------------------------------------------------------
3160  * find all unused pins of all element
3161  */
3162 void
3163 LookupUnusedPins (FILE * FP)
3164 {
3165   /* reset all currently marked connections */
3166   User = true;
3167   TheFlag = FOUNDFLAG;
3168   ResetConnections (true, FOUNDFLAG);
3169   InitConnectionLookup ();
3170
3171   ELEMENT_LOOP (PCB->Data);
3172   {
3173     /* break if abort dialog returned true;
3174      * passing NULL as filedescriptor discards the normal output
3175      */
3176     if (PrintAndSelectUnusedPinsAndPadsOfElement (element, FP))
3177       break;
3178   }
3179   END_LOOP;
3180
3181   if (Settings.RingBellWhenFinished)
3182     gui->beep ();
3183   FreeConnectionLookupMemory ();
3184   IncrementUndoSerialNumber ();
3185   User = false;
3186   Draw ();
3187 }
3188
3189 /* ---------------------------------------------------------------------------
3190  * resets all used flags of pins and vias
3191  */
3192 bool
3193 ResetFoundPinsViasAndPads (bool AndDraw, int flag)
3194 {
3195   bool change = false;
3196
3197   VIA_LOOP (PCB->Data);
3198   {
3199     if (TEST_FLAG (flag, via))
3200       {
3201         if (AndDraw)
3202           AddObjectToFlagUndoList (VIA_TYPE, via, via, via);
3203         CLEAR_FLAG (flag, via);
3204         if (AndDraw)
3205           DrawVia (via);
3206         change = true;
3207       }
3208   }
3209   END_LOOP;
3210   ELEMENT_LOOP (PCB->Data);
3211   {
3212     PIN_LOOP (element);
3213     {
3214       if (TEST_FLAG (flag, pin))
3215         {
3216           if (AndDraw)
3217             AddObjectToFlagUndoList (PIN_TYPE, element, pin, pin);
3218           CLEAR_FLAG (flag, pin);
3219           if (AndDraw)
3220             DrawPin (pin);
3221           change = true;
3222         }
3223     }
3224     END_LOOP;
3225     PAD_LOOP (element);
3226     {
3227       if (TEST_FLAG (flag, pad))
3228         {
3229           if (AndDraw)
3230             AddObjectToFlagUndoList (PAD_TYPE, element, pad, pad);
3231           CLEAR_FLAG (flag, pad);
3232           if (AndDraw)
3233             DrawPad (pad);
3234           change = true;
3235         }
3236     }
3237     END_LOOP;
3238   }
3239   END_LOOP;
3240   if (change)
3241     SetChangedFlag (true);
3242   return change;
3243 }
3244
3245 /* ---------------------------------------------------------------------------
3246  * resets all used flags of LOs
3247  */
3248 bool
3249 ResetFoundLinesAndPolygons (bool AndDraw, int flag)
3250 {
3251   bool change = false;
3252
3253   RAT_LOOP (PCB->Data);
3254   {
3255     if (TEST_FLAG (flag, line))
3256       {
3257         if (AndDraw)
3258           AddObjectToFlagUndoList (RATLINE_TYPE, line, line, line);
3259         CLEAR_FLAG (flag, line);
3260         if (AndDraw)
3261           DrawRat (line);
3262         change = true;
3263       }
3264   }
3265   END_LOOP;
3266   COPPERLINE_LOOP (PCB->Data);
3267   {
3268     if (TEST_FLAG (flag, line))
3269       {
3270         if (AndDraw)
3271           AddObjectToFlagUndoList (LINE_TYPE, layer, line, line);
3272         CLEAR_FLAG (flag, line);
3273         if (AndDraw)
3274           DrawLine (layer, line);
3275         change = true;
3276       }
3277   }
3278   ENDALL_LOOP;
3279   COPPERARC_LOOP (PCB->Data);
3280   {
3281     if (TEST_FLAG (flag, arc))
3282       {
3283         if (AndDraw)
3284           AddObjectToFlagUndoList (ARC_TYPE, layer, arc, arc);
3285         CLEAR_FLAG (flag, arc);
3286         if (AndDraw)
3287           DrawArc (layer, arc);
3288         change = true;
3289       }
3290   }
3291   ENDALL_LOOP;
3292   COPPERPOLYGON_LOOP (PCB->Data);
3293   {
3294     if (TEST_FLAG (flag, polygon))
3295       {
3296         if (AndDraw)
3297           AddObjectToFlagUndoList (POLYGON_TYPE, layer, polygon, polygon);
3298         CLEAR_FLAG (flag, polygon);
3299         if (AndDraw)
3300           DrawPolygon (layer, polygon);
3301         change = true;
3302       }
3303   }
3304   ENDALL_LOOP;
3305   if (change)
3306     SetChangedFlag (true);
3307   return change;
3308 }
3309
3310 /* ---------------------------------------------------------------------------
3311  * resets all found connections
3312  */
3313 bool
3314 ResetConnections (bool AndDraw, int flag)
3315 {
3316   bool change = false;
3317
3318   change = ResetFoundPinsViasAndPads  (AndDraw, flag) || change;
3319   change = ResetFoundLinesAndPolygons (AndDraw, flag) || change;
3320
3321   return change;
3322 }
3323
3324 /*----------------------------------------------------------------------------
3325  * Dumps the list contents
3326  */
3327 static void
3328 DumpList (void)
3329 {
3330   Cardinal i;
3331
3332   for (i = 0; i < 2; i++)
3333     {
3334       PadList[i].Number = 0;
3335       PadList[i].Location = 0;
3336       PadList[i].DrawLocation = 0;
3337     }
3338
3339   PVList.Number = 0;
3340   PVList.Location = 0;
3341
3342   for (i = 0; i < max_copper_layer; i++)
3343     {
3344       LineList[i].Location = 0;
3345       LineList[i].DrawLocation = 0;
3346       LineList[i].Number = 0;
3347       ArcList[i].Location = 0;
3348       ArcList[i].DrawLocation = 0;
3349       ArcList[i].Number = 0;
3350       PolygonList[i].Location = 0;
3351       PolygonList[i].DrawLocation = 0;
3352       PolygonList[i].Number = 0;
3353     }
3354   RatList.Number = 0;
3355   RatList.Location = 0;
3356   RatList.DrawLocation = 0;
3357 }
3358
3359 /*-----------------------------------------------------------------------------
3360  * Check for DRC violations on a single net starting from the pad or pin
3361  * sees if the connectivity changes when everything is bloated, or shrunk
3362  */
3363 static bool
3364 DRCFind (int What, void *ptr1, void *ptr2, void *ptr3)
3365 {
3366   Coord x, y;
3367   int object_count;
3368   long int *object_id_list;
3369   int *object_type_list;
3370   DrcViolationType *violation;
3371
3372   if (PCB->Shrink != 0)
3373     {
3374       Bloat = -PCB->Shrink;
3375       TheFlag = DRCFLAG | SELECTEDFLAG;
3376       ListStart (What, ptr1, ptr2, ptr3);
3377       DoIt (true, false);
3378       /* ok now the shrunk net has the SELECTEDFLAG set */
3379       DumpList ();
3380       TheFlag = FOUNDFLAG;
3381       ListStart (What, ptr1, ptr2, ptr3);
3382       Bloat = 0;
3383       drc = true;               /* abort the search if we find anything not already found */
3384       if (DoIt (true, false))
3385         {
3386           DumpList ();
3387           /* make the flag changes undoable */
3388           TheFlag = FOUNDFLAG | SELECTEDFLAG;
3389           ResetConnections (false, TheFlag);
3390           User = true;
3391           drc = false;
3392           Bloat = -PCB->Shrink;
3393           TheFlag = SELECTEDFLAG;
3394           ListStart (What, ptr1, ptr2, ptr3);
3395           DoIt (true, true);
3396           DumpList ();
3397           ListStart (What, ptr1, ptr2, ptr3);
3398           TheFlag = FOUNDFLAG;
3399           Bloat = 0;
3400           drc = true;
3401           DoIt (true, true);
3402           DumpList ();
3403           User = false;
3404           drc = false;
3405           drcerr_count++;
3406           LocateError (&x, &y);
3407           BuildObjectList (&object_count, &object_id_list, &object_type_list);
3408           violation = pcb_drc_violation_new (_("Potential for broken trace"),
3409                                              _("Insufficient overlap between objects can lead to broken tracks\n"
3410                                                "due to registration errors with old wheel style photo-plotters."),
3411                                              x, y,
3412                                              0,     /* ANGLE OF ERROR UNKNOWN */
3413                                              FALSE, /* MEASUREMENT OF ERROR UNKNOWN */
3414                                              0,     /* MAGNITUDE OF ERROR UNKNOWN */
3415                                              PCB->Shrink,
3416                                              object_count,
3417                                              object_id_list,
3418                                              object_type_list);
3419           append_drc_violation (violation);
3420           pcb_drc_violation_free (violation);
3421           free (object_id_list);
3422           free (object_type_list);
3423
3424           if (!throw_drc_dialog())
3425             return (true);
3426           IncrementUndoSerialNumber ();
3427           Undo (true);
3428         }
3429       DumpList ();
3430     }
3431   /* now check the bloated condition */
3432   drc = false;
3433   ResetConnections (false, TheFlag);
3434   TheFlag = FOUNDFLAG;
3435   ListStart (What, ptr1, ptr2, ptr3);
3436   Bloat = PCB->Bloat;
3437   drc = true;
3438   while (DoIt (true, false))
3439     {
3440       DumpList ();
3441       /* make the flag changes undoable */
3442       TheFlag = FOUNDFLAG | SELECTEDFLAG;
3443       ResetConnections (false, TheFlag);
3444       User = true;
3445       drc = false;
3446       Bloat = 0;
3447       TheFlag = SELECTEDFLAG;
3448       ListStart (What, ptr1, ptr2, ptr3);
3449       DoIt (true, true);
3450       DumpList ();
3451       TheFlag = FOUNDFLAG;
3452       ListStart (What, ptr1, ptr2, ptr3);
3453       Bloat = PCB->Bloat;
3454       drc = true;
3455       DoIt (true, true);
3456       DumpList ();
3457       drcerr_count++;
3458       LocateError (&x, &y);
3459       BuildObjectList (&object_count, &object_id_list, &object_type_list);
3460       violation = pcb_drc_violation_new (_("Copper areas too close"),
3461                                          _("Circuits that are too close may bridge during imaging, etching,\n"
3462                                            "plating, or soldering processes resulting in a direct short."),
3463                                          x, y,
3464                                          0,     /* ANGLE OF ERROR UNKNOWN */
3465                                          FALSE, /* MEASUREMENT OF ERROR UNKNOWN */
3466                                          0,     /* MAGNITUDE OF ERROR UNKNOWN */
3467                                          PCB->Bloat,
3468                                          object_count,
3469                                          object_id_list,
3470                                          object_type_list);
3471       append_drc_violation (violation);
3472       pcb_drc_violation_free (violation);
3473       free (object_id_list);
3474       free (object_type_list);
3475       User = false;
3476       drc = false;
3477       if (!throw_drc_dialog())
3478         return (true);
3479       IncrementUndoSerialNumber ();
3480       Undo (true);
3481       /* highlight the rest of the encroaching net so it's not reported again */
3482       TheFlag |= SELECTEDFLAG;
3483       Bloat = 0;
3484       ListStart (thing_type, thing_ptr1, thing_ptr2, thing_ptr3);
3485       DoIt (true, true);
3486       DumpList ();
3487       drc = true;
3488       Bloat = PCB->Bloat;
3489       ListStart (What, ptr1, ptr2, ptr3);
3490     }
3491   drc = false;
3492   DumpList ();
3493   TheFlag = FOUNDFLAG | SELECTEDFLAG;
3494   ResetConnections (false, TheFlag);
3495   return (false);
3496 }
3497
3498 /* DRC clearance callback */
3499
3500 static int
3501 drc_callback (DataType *data, LayerType *layer, PolygonType *polygon,
3502               int type, void *ptr1, void *ptr2)
3503 {
3504   char *message;
3505   Coord x, y;
3506   int object_count;
3507   long int *object_id_list;
3508   int *object_type_list;
3509   DrcViolationType *violation;
3510
3511   LineType *line = (LineType *) ptr2;
3512   ArcType *arc = (ArcType *) ptr2;
3513   PinType *pin = (PinType *) ptr2;
3514   PadType *pad = (PadType *) ptr2;
3515
3516   thing_type = type;
3517   thing_ptr1 = ptr1;
3518   thing_ptr2 = ptr2;
3519   thing_ptr3 = ptr2;
3520   switch (type)
3521     {
3522     case LINE_TYPE:
3523       if (line->Clearance < 2 * PCB->Bloat)
3524         {
3525           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3526           SET_FLAG (TheFlag, line);
3527           message = _("Line with insufficient clearance inside polygon\n");
3528           goto doIsBad;
3529         }
3530       break;
3531     case ARC_TYPE:
3532       if (arc->Clearance < 2 * PCB->Bloat)
3533         {
3534           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3535           SET_FLAG (TheFlag, arc);
3536           message = _("Arc with insufficient clearance inside polygon\n");
3537           goto doIsBad;
3538         }
3539       break;
3540     case PAD_TYPE:
3541       if (pad->Clearance && pad->Clearance < 2 * PCB->Bloat)
3542         if (IsPadInPolygon(pad,polygon))
3543           {
3544             AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3545             SET_FLAG (TheFlag, pad);
3546             message = _("Pad with insufficient clearance inside polygon\n");
3547             goto doIsBad;
3548           }
3549       break;
3550     case PIN_TYPE:
3551       if (pin->Clearance && pin->Clearance < 2 * PCB->Bloat)
3552         {
3553           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3554           SET_FLAG (TheFlag, pin);
3555           message = _("Pin with insufficient clearance inside polygon\n");
3556           goto doIsBad;
3557         }
3558       break;
3559     case VIA_TYPE:
3560       if (pin->Clearance && pin->Clearance < 2 * PCB->Bloat)
3561         {
3562           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3563           SET_FLAG (TheFlag, pin);
3564           message = _("Via with insufficient clearance inside polygon\n");
3565           goto doIsBad;
3566         }
3567       break;
3568     default:
3569       Message ("hace: Bad Plow object in callback\n");
3570     }
3571   return 0;
3572
3573 doIsBad:
3574   AddObjectToFlagUndoList (POLYGON_TYPE, layer, polygon, polygon);
3575   SET_FLAG (FOUNDFLAG, polygon);
3576   DrawPolygon (layer, polygon);
3577   DrawObject (type, ptr1, ptr2);
3578   drcerr_count++;
3579   LocateError (&x, &y);
3580   BuildObjectList (&object_count, &object_id_list, &object_type_list);
3581   violation = pcb_drc_violation_new (message,
3582                                      _("Circuits that are too close may bridge during imaging, etching,\n"
3583                                        "plating, or soldering processes resulting in a direct short."),
3584                                      x, y,
3585                                      0,     /* ANGLE OF ERROR UNKNOWN */
3586                                      FALSE, /* MEASUREMENT OF ERROR UNKNOWN */
3587                                      0,     /* MAGNITUDE OF ERROR UNKNOWN */
3588                                      PCB->Bloat,
3589                                      object_count,
3590                                      object_id_list,
3591                                      object_type_list);
3592   append_drc_violation (violation);
3593   pcb_drc_violation_free (violation);
3594   free (object_id_list);
3595   free (object_type_list);
3596   if (!throw_drc_dialog())
3597     {
3598       IsBad = true;
3599       return 1;
3600     }
3601   IncrementUndoSerialNumber ();
3602   Undo (true);
3603   return 0;
3604 }
3605
3606 /*-----------------------------------------------------------------------------
3607  * Check for DRC violations
3608  * see if the connectivity changes when everything is bloated, or shrunk
3609  */
3610 int
3611 DRCAll (void)
3612 {
3613   Coord x, y;
3614   int object_count;
3615   long int *object_id_list;
3616   int *object_type_list;
3617   DrcViolationType *violation;
3618   int tmpcnt;
3619   int nopastecnt = 0;
3620
3621   reset_drc_dialog_message();
3622
3623   IsBad = false;
3624   drcerr_count = 0;
3625   SaveStackAndVisibility ();
3626   ResetStackAndVisibility ();
3627   hid_action ("LayersChanged");
3628   InitConnectionLookup ();
3629
3630   TheFlag = FOUNDFLAG | DRCFLAG | SELECTEDFLAG;
3631
3632   if (ResetConnections (true, TheFlag))
3633     {
3634       IncrementUndoSerialNumber ();
3635       Draw ();
3636     }
3637
3638   User = false;
3639
3640   ELEMENT_LOOP (PCB->Data);
3641   {
3642     PIN_LOOP (element);
3643     {
3644       if (!TEST_FLAG (DRCFLAG, pin)
3645           && DRCFind (PIN_TYPE, (void *) element, (void *) pin, (void *) pin))
3646         {
3647           IsBad = true;
3648           break;
3649         }
3650     }
3651     END_LOOP;
3652     if (IsBad)
3653       break;
3654     PAD_LOOP (element);
3655     {
3656
3657       /* count up how many pads have no solderpaste openings */
3658       if (TEST_FLAG (NOPASTEFLAG, pad))
3659         nopastecnt++;
3660
3661       if (!TEST_FLAG (DRCFLAG, pad)
3662           && DRCFind (PAD_TYPE, (void *) element, (void *) pad, (void *) pad))
3663         {
3664           IsBad = true;
3665           break;
3666         }
3667     }
3668     END_LOOP;
3669     if (IsBad)
3670       break;
3671   }
3672   END_LOOP;
3673   if (!IsBad)
3674     VIA_LOOP (PCB->Data);
3675   {
3676     if (!TEST_FLAG (DRCFLAG, via)
3677         && DRCFind (VIA_TYPE, (void *) via, (void *) via, (void *) via))
3678       {
3679         IsBad = true;
3680         break;
3681       }
3682   }
3683   END_LOOP;
3684
3685   TheFlag = (IsBad) ? DRCFLAG : (FOUNDFLAG | DRCFLAG | SELECTEDFLAG);
3686   ResetConnections (false, TheFlag);
3687   TheFlag = SELECTEDFLAG;
3688   /* check minimum widths and polygon clearances */
3689   if (!IsBad)
3690     {
3691       COPPERLINE_LOOP (PCB->Data);
3692       {
3693         /* check line clearances in polygons */
3694         PlowsPolygon (PCB->Data, LINE_TYPE, layer, line, drc_callback);
3695         if (IsBad)
3696           break;
3697         if (line->Thickness < PCB->minWid)
3698           {
3699             AddObjectToFlagUndoList (LINE_TYPE, layer, line, line);
3700             SET_FLAG (TheFlag, line);
3701             DrawLine (layer, line);
3702             drcerr_count++;
3703             SetThing (LINE_TYPE, layer, line, line);
3704             LocateError (&x, &y);
3705             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3706             violation = pcb_drc_violation_new (_("Line width is too thin"),
3707                                                _("Process specifications dictate a minimum feature-width\n"
3708                                                  "that can reliably be reproduced"),
3709                                                x, y,
3710                                                0,    /* ANGLE OF ERROR UNKNOWN */
3711                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3712                                                line->Thickness,
3713                                                PCB->minWid,
3714                                                object_count,
3715                                                object_id_list,
3716                                                object_type_list);
3717             append_drc_violation (violation);
3718             pcb_drc_violation_free (violation);
3719             free (object_id_list);
3720             free (object_type_list);
3721             if (!throw_drc_dialog())
3722               {
3723                 IsBad = true;
3724                 break;
3725               }
3726             IncrementUndoSerialNumber ();
3727             Undo (false);
3728           }
3729       }
3730       ENDALL_LOOP;
3731     }
3732   if (!IsBad)
3733     {
3734       COPPERARC_LOOP (PCB->Data);
3735       {
3736         PlowsPolygon (PCB->Data, ARC_TYPE, layer, arc, drc_callback);
3737         if (IsBad)
3738           break;
3739         if (arc->Thickness < PCB->minWid)
3740           {
3741             AddObjectToFlagUndoList (ARC_TYPE, layer, arc, arc);
3742             SET_FLAG (TheFlag, arc);
3743             DrawArc (layer, arc);
3744             drcerr_count++;
3745             SetThing (ARC_TYPE, layer, arc, arc);
3746             LocateError (&x, &y);
3747             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3748             violation = pcb_drc_violation_new (_("Arc width is too thin"),
3749                                                _("Process specifications dictate a minimum feature-width\n"
3750                                                  "that can reliably be reproduced"),
3751                                                x, y,
3752                                                0,    /* ANGLE OF ERROR UNKNOWN */
3753                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3754                                                arc->Thickness,
3755                                                PCB->minWid,
3756                                                object_count,
3757                                                object_id_list,
3758                                                object_type_list);
3759             append_drc_violation (violation);
3760             pcb_drc_violation_free (violation);
3761             free (object_id_list);
3762             free (object_type_list);
3763             if (!throw_drc_dialog())
3764               {
3765                 IsBad = true;
3766                 break;
3767               }
3768             IncrementUndoSerialNumber ();
3769             Undo (false);
3770           }
3771       }
3772       ENDALL_LOOP;
3773     }
3774   if (!IsBad)
3775     {
3776       ALLPIN_LOOP (PCB->Data);
3777       {
3778         PlowsPolygon (PCB->Data, PIN_TYPE, element, pin, drc_callback);
3779         if (IsBad)
3780           break;
3781         if (!TEST_FLAG (HOLEFLAG, pin) &&
3782             pin->Thickness - pin->DrillingHole < 2 * PCB->minRing)
3783           {
3784             AddObjectToFlagUndoList (PIN_TYPE, element, pin, pin);
3785             SET_FLAG (TheFlag, pin);
3786             DrawPin (pin);
3787             drcerr_count++;
3788             SetThing (PIN_TYPE, element, pin, pin);
3789             LocateError (&x, &y);
3790             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3791             violation = pcb_drc_violation_new (_("Pin annular ring too small"),
3792                                                _("Annular rings that are too small may erode during etching,\n"
3793                                                  "resulting in a broken connection"),
3794                                                x, y,
3795                                                0,    /* ANGLE OF ERROR UNKNOWN */
3796                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3797                                                (pin->Thickness - pin->DrillingHole) / 2,
3798                                                PCB->minRing,
3799                                                object_count,
3800                                                object_id_list,
3801                                                object_type_list);
3802             append_drc_violation (violation);
3803             pcb_drc_violation_free (violation);
3804             free (object_id_list);
3805             free (object_type_list);
3806             if (!throw_drc_dialog())
3807               {
3808                 IsBad = true;
3809                 break;
3810               }
3811             IncrementUndoSerialNumber ();
3812             Undo (false);
3813           }
3814         if (pin->DrillingHole < PCB->minDrill)
3815           {
3816             AddObjectToFlagUndoList (PIN_TYPE, element, pin, pin);
3817             SET_FLAG (TheFlag, pin);
3818             DrawPin (pin);
3819             drcerr_count++;
3820             SetThing (PIN_TYPE, element, pin, pin);
3821             LocateError (&x, &y);
3822             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3823             violation = pcb_drc_violation_new (_("Pin drill size is too small"),
3824                                                _("Process rules dictate the minimum drill size which can be used"),
3825                                                x, y,
3826                                                0,    /* ANGLE OF ERROR UNKNOWN */
3827                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3828                                                pin->DrillingHole,
3829                                                PCB->minDrill,
3830                                                object_count,
3831                                                object_id_list,
3832                                                object_type_list);
3833             append_drc_violation (violation);
3834             pcb_drc_violation_free (violation);
3835             free (object_id_list);
3836             free (object_type_list);
3837             if (!throw_drc_dialog())
3838               {
3839                 IsBad = true;
3840                 break;
3841               }
3842             IncrementUndoSerialNumber ();
3843             Undo (false);
3844           }
3845       }
3846       ENDALL_LOOP;
3847     }
3848   if (!IsBad)
3849     {
3850       ALLPAD_LOOP (PCB->Data);
3851       {
3852         PlowsPolygon (PCB->Data, PAD_TYPE, element, pad, drc_callback);
3853         if (IsBad)
3854           break;
3855         if (pad->Thickness < PCB->minWid)
3856           {
3857             AddObjectToFlagUndoList (PAD_TYPE, element, pad, pad);
3858             SET_FLAG (TheFlag, pad);
3859             DrawPad (pad);
3860             drcerr_count++;
3861             SetThing (PAD_TYPE, element, pad, pad);
3862             LocateError (&x, &y);
3863             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3864             violation = pcb_drc_violation_new (_("Pad is too thin"),
3865                                                _("Pads which are too thin may erode during etching,\n"
3866                                                   "resulting in a broken or unreliable connection"),
3867                                                x, y,
3868                                                0,    /* ANGLE OF ERROR UNKNOWN */
3869                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3870                                                pad->Thickness,
3871                                                PCB->minWid,
3872                                                object_count,
3873                                                object_id_list,
3874                                                object_type_list);
3875             append_drc_violation (violation);
3876             pcb_drc_violation_free (violation);
3877             free (object_id_list);
3878             free (object_type_list);
3879             if (!throw_drc_dialog())
3880               {
3881                 IsBad = true;
3882                 break;
3883               }
3884             IncrementUndoSerialNumber ();
3885             Undo (false);
3886           }
3887       }
3888       ENDALL_LOOP;
3889     }
3890   if (!IsBad)
3891     {
3892       VIA_LOOP (PCB->Data);
3893       {
3894         PlowsPolygon (PCB->Data, VIA_TYPE, via, via, drc_callback);
3895         if (IsBad)
3896           break;
3897         if (!TEST_FLAG (HOLEFLAG, via) &&
3898             via->Thickness - via->DrillingHole < 2 * PCB->minRing)
3899           {
3900             AddObjectToFlagUndoList (VIA_TYPE, via, via, via);
3901             SET_FLAG (TheFlag, via);
3902             DrawVia (via);
3903             drcerr_count++;
3904             SetThing (VIA_TYPE, via, via, via);
3905             LocateError (&x, &y);
3906             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3907             violation = pcb_drc_violation_new (_("Via annular ring too small"),
3908                                                _("Annular rings that are too small may erode during etching,\n"
3909                                                  "resulting in a broken connection"),
3910                                                x, y,
3911                                                0,    /* ANGLE OF ERROR UNKNOWN */
3912                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3913                                                (via->Thickness - via->DrillingHole) / 2,
3914                                                PCB->minRing,
3915                                                object_count,
3916                                                object_id_list,
3917                                                object_type_list);
3918             append_drc_violation (violation);
3919             pcb_drc_violation_free (violation);
3920             free (object_id_list);
3921             free (object_type_list);
3922             if (!throw_drc_dialog())
3923               {
3924                 IsBad = true;
3925                 break;
3926               }
3927             IncrementUndoSerialNumber ();
3928             Undo (false);
3929           }
3930         if (via->DrillingHole < PCB->minDrill)
3931           {
3932             AddObjectToFlagUndoList (VIA_TYPE, via, via, via);
3933             SET_FLAG (TheFlag, via);
3934             DrawVia (via);
3935             drcerr_count++;
3936             SetThing (VIA_TYPE, via, via, via);
3937             LocateError (&x, &y);
3938             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3939             violation = pcb_drc_violation_new (_("Via drill size is too small"),
3940                                                _("Process rules dictate the minimum drill size which can be used"),
3941                                                x, y,
3942                                                0,    /* ANGLE OF ERROR UNKNOWN */
3943                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3944                                                via->DrillingHole,
3945                                                PCB->minDrill,
3946                                                object_count,
3947                                                object_id_list,
3948                                                object_type_list);
3949             append_drc_violation (violation);
3950             pcb_drc_violation_free (violation);
3951             free (object_id_list);
3952             free (object_type_list);
3953             if (!throw_drc_dialog())
3954               {
3955                 IsBad = true;
3956                 break;
3957               }
3958             IncrementUndoSerialNumber ();
3959             Undo (false);
3960           }
3961       }
3962       END_LOOP;
3963     }
3964
3965   FreeConnectionLookupMemory ();
3966   TheFlag = FOUNDFLAG;
3967   Bloat = 0;
3968
3969   /* check silkscreen minimum widths outside of elements */
3970   /* XXX - need to check text and polygons too! */
3971   TheFlag = SELECTEDFLAG;
3972   if (!IsBad)
3973     {
3974       SILKLINE_LOOP (PCB->Data);
3975       {
3976         if (line->Thickness < PCB->minSlk)
3977           {
3978             SET_FLAG (TheFlag, line);
3979             DrawLine (layer, line);
3980             drcerr_count++;
3981             SetThing (LINE_TYPE, layer, line, line);
3982             LocateError (&x, &y);
3983             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3984             violation = pcb_drc_violation_new (_("Silk line is too thin"),
3985                                                _("Process specifications dictate a minimum silkscreen feature-width\n"
3986                                                  "that can reliably be reproduced"),
3987                                                x, y,
3988                                                0,    /* ANGLE OF ERROR UNKNOWN */
3989                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3990                                                line->Thickness,
3991                                                PCB->minSlk,
3992                                                object_count,
3993                                                object_id_list,
3994                                                object_type_list);
3995             append_drc_violation (violation);
3996             pcb_drc_violation_free (violation);
3997             free (object_id_list);
3998             free (object_type_list);
3999             if (!throw_drc_dialog())
4000               {
4001                 IsBad = true;
4002                 break;
4003               }
4004           }
4005       }
4006       ENDALL_LOOP;
4007     }
4008
4009   /* check silkscreen minimum widths inside of elements */
4010   /* XXX - need to check text and polygons too! */
4011   TheFlag = SELECTEDFLAG;
4012   if (!IsBad)
4013     {
4014       ELEMENT_LOOP (PCB->Data);
4015       {
4016         tmpcnt = 0;
4017         ELEMENTLINE_LOOP (element);
4018         {
4019           if (line->Thickness < PCB->minSlk)
4020             tmpcnt++;
4021         }
4022         END_LOOP;
4023         if (tmpcnt > 0)
4024           {
4025             char *title;
4026             char *name;
4027             char *buffer;
4028             int buflen;
4029
4030             SET_FLAG (TheFlag, element);
4031             DrawElement (element);
4032             drcerr_count++;
4033             SetThing (ELEMENT_TYPE, element, element, element);
4034             LocateError (&x, &y);
4035             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4036
4037             title = _("Element %s has %i silk lines which are too thin");
4038             name = (char *)UNKNOWN (NAMEONPCB_NAME (element));
4039
4040             /* -4 is for the %s and %i place-holders */
4041             /* +11 is the max printed length for a 32 bit integer */
4042             /* +1 is for the \0 termination */
4043             buflen = strlen (title) - 4 + strlen (name) + 11 + 1;
4044             buffer = (char *)malloc (buflen);
4045             snprintf (buffer, buflen, title, name, tmpcnt);
4046
4047             violation = pcb_drc_violation_new (buffer,
4048                                                _("Process specifications dictate a minimum silkscreen\n"
4049                                                "feature-width that can reliably be reproduced"),
4050                                                x, y,
4051                                                0,    /* ANGLE OF ERROR UNKNOWN */
4052                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4053                                                0,    /* MINIMUM OFFENDING WIDTH UNKNOWN */
4054                                                PCB->minSlk,
4055                                                object_count,
4056                                                object_id_list,
4057                                                object_type_list);
4058             free (buffer);
4059             append_drc_violation (violation);
4060             pcb_drc_violation_free (violation);
4061             free (object_id_list);
4062             free (object_type_list);
4063             if (!throw_drc_dialog())
4064               {
4065                 IsBad = true;
4066                 break;
4067               }
4068           }
4069       }
4070       END_LOOP;
4071     }
4072
4073
4074   if (IsBad)
4075     {
4076       IncrementUndoSerialNumber ();
4077     }
4078
4079
4080   RestoreStackAndVisibility ();
4081   hid_action ("LayersChanged");
4082   gui->invalidate_all ();
4083
4084   if (nopastecnt > 0)
4085     {
4086       Message (_("Warning:  %d pad%s the nopaste flag set.\n"),
4087                nopastecnt,
4088                nopastecnt > 1 ? "s have" : " has");
4089     }
4090   return IsBad ? -drcerr_count : drcerr_count;
4091 }
4092
4093 /*----------------------------------------------------------------------------
4094  * Locate the coordinatates of offending item (thing)
4095  */
4096 static void
4097 LocateError (Coord *x, Coord *y)
4098 {
4099   switch (thing_type)
4100     {
4101     case LINE_TYPE:
4102       {
4103         LineType *line = (LineType *) thing_ptr3;
4104         *x = (line->Point1.X + line->Point2.X) / 2;
4105         *y = (line->Point1.Y + line->Point2.Y) / 2;
4106         break;
4107       }
4108     case ARC_TYPE:
4109       {
4110         ArcType *arc = (ArcType *) thing_ptr3;
4111         *x = arc->X;
4112         *y = arc->Y;
4113         break;
4114       }
4115     case POLYGON_TYPE:
4116       {
4117         PolygonType *polygon = (PolygonType *) thing_ptr3;
4118         *x =
4119           (polygon->Clipped->contours->xmin +
4120            polygon->Clipped->contours->xmax) / 2;
4121         *y =
4122           (polygon->Clipped->contours->ymin +
4123            polygon->Clipped->contours->ymax) / 2;
4124         break;
4125       }
4126     case PIN_TYPE:
4127     case VIA_TYPE:
4128       {
4129         PinType *pin = (PinType *) thing_ptr3;
4130         *x = pin->X;
4131         *y = pin->Y;
4132         break;
4133       }
4134     case PAD_TYPE:
4135       {
4136         PadType *pad = (PadType *) thing_ptr3;
4137         *x = (pad->Point1.X + pad->Point2.X) / 2;
4138         *y = (pad->Point1.Y + pad->Point2.Y) / 2;
4139         break;
4140       }
4141     case ELEMENT_TYPE:
4142       {
4143         ElementType *element = (ElementType *) thing_ptr3;
4144         *x = element->MarkX;
4145         *y = element->MarkY;
4146         break;
4147       }
4148     default:
4149       return;
4150     }
4151 }
4152
4153
4154 /*----------------------------------------------------------------------------
4155  * Build a list of the of offending items by ID. (Currently just "thing")
4156  */
4157 static void
4158 BuildObjectList (int *object_count, long int **object_id_list, int **object_type_list)
4159 {
4160   *object_count = 0;
4161   *object_id_list = NULL;
4162   *object_type_list = NULL;
4163
4164   switch (thing_type)
4165     {
4166     case LINE_TYPE:
4167     case ARC_TYPE:
4168     case POLYGON_TYPE:
4169     case PIN_TYPE:
4170     case VIA_TYPE:
4171     case PAD_TYPE:
4172     case ELEMENT_TYPE:
4173     case RATLINE_TYPE:
4174       *object_count = 1;
4175       *object_id_list = (long int *)malloc (sizeof (long int));
4176       *object_type_list = (int *)malloc (sizeof (int));
4177       **object_id_list = ((AnyObjectType *)thing_ptr3)->ID;
4178       **object_type_list = thing_type;
4179       return;
4180
4181     default:
4182       fprintf (stderr,
4183                _("Internal error in BuildObjectList: unknown object type %i\n"),
4184                thing_type);
4185     }
4186 }
4187
4188
4189 /*----------------------------------------------------------------------------
4190  * center the display to show the offending item (thing)
4191  */
4192 static void
4193 GotoError (void)
4194 {
4195   Coord X, Y;
4196
4197   LocateError (&X, &Y);
4198
4199   switch (thing_type)
4200     {
4201     case LINE_TYPE:
4202     case ARC_TYPE:
4203     case POLYGON_TYPE:
4204       ChangeGroupVisibility (
4205           GetLayerNumber (PCB->Data, (LayerType *) thing_ptr1),
4206           true, true);
4207     }
4208   CenterDisplay (X, Y);
4209 }
4210
4211 void
4212 InitConnectionLookup (void)
4213 {
4214   InitComponentLookup ();
4215   InitLayoutLookup ();
4216 }
4217
4218 void
4219 FreeConnectionLookupMemory (void)
4220 {
4221   FreeComponentLookupMemory ();
4222   FreeLayoutLookupMemory ();
4223 }