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