src/find.c

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