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 Boolean User = False;    /* user action causing this */
 314 static Boolean drc = False;     /* whether to stop if finding something not found */
 315 static Boolean 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 Boolean LookupLOConnectionsToPVList (Boolean);
 325 static Boolean LookupLOConnectionsToLOList (Boolean);
 326 static Boolean LookupPVConnectionsToLOList (Boolean);
 327 static Boolean LookupPVConnectionsToPVList (void);
 328 static Boolean LookupLOConnectionsToLine (LineTypePtr, Cardinal, Boolean);
 329 static Boolean LookupLOConnectionsToPad (PadTypePtr, Cardinal);
 330 static Boolean LookupLOConnectionsToPolygon (PolygonTypePtr, Cardinal);
 331 static Boolean LookupLOConnectionsToArc (ArcTypePtr, Cardinal);
 332 static Boolean LookupLOConnectionsToRatEnd (PointTypePtr, Cardinal);
 333 static Boolean IsRatPointOnLineEnd (PointTypePtr, LineTypePtr);
 334 static Boolean ArcArcIntersect (ArcTypePtr, ArcTypePtr);
 335 static Boolean PrepareNextLoop (FILE *);
 336 static Boolean PrintElementConnections (ElementTypePtr, FILE *, Boolean);
 337 static Boolean ListsEmpty (Boolean);
 338 static Boolean DoIt (Boolean, Boolean);
 339 static void PrintElementNameList (ElementTypePtr, FILE *);
 340 static void PrintConnectionElementName (ElementTypePtr, FILE *);
 341 static void PrintConnectionListEntry (char *, ElementTypePtr,
 342                                       Boolean, FILE *);
 343 static void PrintPadConnections (Cardinal, FILE *, Boolean);
 344 static void PrintPinConnections (FILE *, Boolean);
 345 static Boolean PrintAndSelectUnusedPinsAndPadsOfElement (ElementTypePtr,
 346                                                          FILE *);
 347 static void DrawNewConnections (void);
 348 static void ResetConnections (Boolean);
 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 Boolean DRCFind (int, void *, void *, void *);
 354 static Boolean ListStart (int, void *, void *, void *);
 355 static Boolean LOTouchesLine (LineTypePtr Line, Cardinal LayerGroup);
 356 static Boolean PVTouchesLine (LineTypePtr line);
 357 static Boolean 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 Boolean
 364 LinePadIntersect (LineTypePtr Line, PadTypePtr Pad)
 365 {
 366   return LineLineIntersect ((Line), (LineTypePtr)Pad);
 367 }
 368
 369 Boolean
 370 ArcPadIntersect (ArcTypePtr Arc, PadTypePtr Pad)
 371 {
 372   return LineArcIntersect ((LineTypePtr) (Pad), (Arc));
 373 }
 374
 375 static Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 531 PadPadIntersect (PadTypePtr p1, PadTypePtr p2)
 532 {
 533   return LinePadIntersect ((LineTypePtr) p1, p2);
 534 }
 535
 536 static inline Boolean
 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 Boolean
 807 LookupLOConnectionsToPVList (Boolean 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 Boolean
 867 LookupLOConnectionsToLOList (Boolean AndRats)
 868 {
 869   Boolean 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 Boolean
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 Boolean
1168 LookupPVConnectionsToLOList (Boolean 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 Boolean
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 /* ---------------------------------------------------------------------------
1331  * check if two arcs intersect
1332  * first we check for circle intersections,
1333  * then find the actual points of intersection
1334  * and test them to see if they are on both arcs
1335  *
1336  * consider a, the distance from the center of arc 1
1337  * to the point perpendicular to the intersecting points.
1338  *
1339  *  a = (r1^2 - r2^2 + l^2)/(2l)
1340  *
1341  * the perpendicular distance to the point of intersection
1342  * is then
1343  *
1344  * d = sqrt(r1^2 - a^2)
1345  *
1346  * the points of intersection would then be
1347  *
1348  * x = X1 + a/l dx +- d/l dy
1349  * y = Y1 + a/l dy -+ d/l dx
1350  *
1351  * where dx = X2 - X1 and dy = Y2 - Y1
1352  *
1353  *
1354  */
1355 static Boolean
1356 ArcArcIntersect (ArcTypePtr Arc1, ArcTypePtr Arc2)
1357 {
1358   register float x, y, dx, dy, r1, r2, a, d, l, t, t2;
1359   register LocationType pdx, pdy;
1360   BoxTypePtr box;
1361   BoxType box1, box2;
1362
1363   pdx = Arc2->X - Arc1->X;
1364   pdy = Arc2->Y - Arc1->Y;
1365   l = pdx * pdx + pdy * pdy;
1366   t = MAX (0.5 * Arc1->Thickness + fBloat, 0.0);
1367   t2 = 0.5 * Arc2->Thickness;
1368   /* concentric arcs, simpler intersection conditions */
1369   if (l == 0.0)
1370     {
1371       if ((Arc1->Width - t >= Arc2->Width - t2
1372            && Arc1->Width - t <=
1373            Arc2->Width + t2)
1374           || (Arc1->Width + t >=
1375               Arc2->Width - t2 && Arc1->Width + t <= Arc2->Width + t2))
1376         {
1377           if ((Arc2->BoundingBox.X1 +
1378                MAX (Arc2->Thickness + Bloat,
1379                     0) >= Arc1->BoundingBox.X1
1380                && Arc2->BoundingBox.X1 <=
1381                Arc1->BoundingBox.X2
1382                && Arc2->BoundingBox.Y1 +
1383                MAX (Arc2->Thickness + Bloat,
1384                     0) >= Arc1->BoundingBox.Y1
1385                && Arc2->BoundingBox.Y1 <=
1386                Arc1->BoundingBox.Y2)
1387               || (Arc2->BoundingBox.X2 +
1388                   MAX (Arc2->Thickness +
1389                        Bloat,
1390                        0) >=
1391                   Arc1->BoundingBox.X1
1392                   && Arc2->BoundingBox.X2 <=
1393                   Arc1->BoundingBox.X2
1394                   && Arc2->BoundingBox.Y2 +
1395                   MAX (Arc2->Thickness +
1396                        Bloat,
1397                        0) >=
1398                   Arc1->BoundingBox.Y1
1399                   && Arc2->BoundingBox.Y2 <= Arc1->BoundingBox.Y2))
1400             return (True);
1401         }
1402       return (False);
1403     }
1404   r1 = Arc1->Width + t;
1405   r1 *= r1;
1406   r2 = Arc2->Width + t2;
1407   r2 *= r2;
1408   a = 0.5 * (r1 - r2 + l) / l;
1409   r1 = r1 / l;
1410   /* add a tiny positive number for round-off problems */
1411   d = r1 - a * a + 1e-5;
1412   /* the circles are too far apart to touch */
1413   if (d < 0)
1414     return (False);
1415   d = sqrt (d);
1416   x = Arc1->X + a * pdx;
1417   y = Arc1->Y + a * pdy;
1418   dx = d * pdx;
1419   dy = d * pdy;
1420   if (x + dy >= Arc1->BoundingBox.X1
1421       && x + dy <= Arc1->BoundingBox.X2
1422       && y - dx >= Arc1->BoundingBox.Y1
1423       && y - dx <= Arc1->BoundingBox.Y2
1424       && x + dy >= Arc2->BoundingBox.X1
1425       && x + dy <= Arc2->BoundingBox.X2
1426       && y - dx >= Arc2->BoundingBox.Y1 && y - dx <= Arc2->BoundingBox.Y2)
1427     return (True);
1428
1429   if (x - dy >= Arc1->BoundingBox.X1
1430       && x - dy <= Arc1->BoundingBox.X2
1431       && y + dx >= Arc1->BoundingBox.Y1
1432       && y + dx <= Arc1->BoundingBox.Y2
1433       && x - dy >= Arc2->BoundingBox.X1
1434       && x - dy <= Arc2->BoundingBox.X2
1435       && y + dx >= Arc2->BoundingBox.Y1 && y + dx <= Arc2->BoundingBox.Y2)
1436     return (True);
1437
1438   /* try the end points in case the ends don't actually pierce the outer radii */
1439   box = GetArcEnds (Arc1);
1440   box1 = *box;
1441   box = GetArcEnds (Arc2);
1442   box2 = *box;
1443   if (IsPointOnArc
1444       ((float) box1.X1, (float) box1.Y1, t,
1445        Arc2) || IsPointOnArc ((float) box1.X2, (float) box1.Y2, t, Arc2))
1446     return (True);
1447
1448   if (IsPointOnArc
1449       ((float) box2.X1, (float) box2.Y1,
1450        MAX (t2 + fBloat, 0.0), Arc1)
1451       || IsPointOnArc ((float) box2.X2,
1452                        (float) box2.Y2, MAX (t2 + fBloat, 0.0), Arc1))
1453     return (True);
1454   return (False);
1455 }
1456
1457 /* ---------------------------------------------------------------------------
1458  * Tests if point is same as line end point
1459  */
1460 static Boolean
1461 IsRatPointOnLineEnd (PointTypePtr Point, LineTypePtr Line)
1462 {
1463   if ((Point->X == Line->Point1.X
1464        && Point->Y == Line->Point1.Y)
1465       || (Point->X == Line->Point2.X && Point->Y == Line->Point2.Y))
1466     return (True);
1467   return (False);
1468 }
1469
1470 static void
1471 form_slanted_rectangle(PointType p[4],LineTypePtr l)
1472 /* writes vertices of a squared line */
1473 {
1474    int dX= l->Point2.X - l->Point1.X, dY = l->Point2.Y - l->Point1.Y,
1475      w = l->Thickness;
1476    double dwx, dwy;
1477    if (dY == 0)
1478      {
1479        dwx = w / 2; dwy = 0;
1480      }
1481     else if (dX == 0)
1482      {
1483        dwx = 0; dwy = w / 2;
1484      }
1485     else
1486      {double r = sqrt (dX * (double) dX + dY * (double) dY) * 2;
1487        dwx = w / r * dX; dwy =  w / r * dY;
1488      }
1489     p[0].X = l->Point1.X - dwx + dwy; p[0].Y = l->Point1.Y - dwy - dwx;
1490     p[1].X = l->Point1.X - dwx - dwy; p[1].Y = l->Point1.Y - dwy + dwx;
1491     p[2].X = l->Point2.X + dwx - dwy; p[2].Y = l->Point2.Y + dwy + dwx;
1492     p[3].X = l->Point2.X + dwx + dwy; p[3].Y = l->Point2.Y + dwy - dwx;
1493 }
1494 /* ---------------------------------------------------------------------------
1495  * checks if two lines intersect
1496  * from news FAQ:
1497  *
1498  *  Let A,B,C,D be 2-space position vectors.  Then the directed line
1499  *  segments AB & CD are given by:
1500  *
1501  *      AB=A+r(B-A), r in [0,1]
1502  *      CD=C+s(D-C), s in [0,1]
1503  *
1504  *  If AB & CD intersect, then
1505  *
1506  *      A+r(B-A)=C+s(D-C), or
1507  *
1508  *      XA+r(XB-XA)=XC+s(XD-XC)
1509  *      YA+r(YB-YA)=YC+s(YD-YC)  for some r,s in [0,1]
1510  *
1511  *  Solving the above for r and s yields
1512  *
1513  *          (YA-YC)(XD-XC)-(XA-XC)(YD-YC)
1514  *      r = -----------------------------  (eqn 1)
1515  *          (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
1516  *
1517  *          (YA-YC)(XB-XA)-(XA-XC)(YB-YA)
1518  *      s = -----------------------------  (eqn 2)
1519  *          (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
1520  *
1521  *  Let I be the position vector of the intersection point, then
1522  *
1523  *      I=A+r(B-A) or
1524  *
1525  *      XI=XA+r(XB-XA)
1526  *      YI=YA+r(YB-YA)
1527  *
1528  *  By examining the values of r & s, you can also determine some
1529  *  other limiting conditions:
1530  *
1531  *      If 0<=r<=1 & 0<=s<=1, intersection exists
1532  *          r<0 or r>1 or s<0 or s>1 line segments do not intersect
1533  *
1534  *      If the denominator in eqn 1 is zero, AB & CD are parallel
1535  *      If the numerator in eqn 1 is also zero, AB & CD are coincident
1536  *
1537  *  If the intersection point of the 2 lines are needed (lines in this
1538  *  context mean infinite lines) regardless whether the two line
1539  *  segments intersect, then
1540  *
1541  *      If r>1, I is located on extension of AB
1542  *      If r<0, I is located on extension of BA
1543  *      If s>1, I is located on extension of CD
1544  *      If s<0, I is located on extension of DC
1545  *
1546  *  Also note that the denominators of eqn 1 & 2 are identical.
1547  *
1548  */
1549 Boolean
1550 LineLineIntersect (LineTypePtr Line1, LineTypePtr Line2)
1551 {
1552   register float dx, dy, dx1, dy1, s, r;
1553   if (TEST_FLAG (SQUAREFLAG, Line1))/* pretty reckless recursion */
1554     {
1555       PointType p[4];form_slanted_rectangle(p,Line1);
1556       return IsLineInQuadrangle(p,Line2);
1557     }
1558   /* here come only round Line1 because IsLineInQuadrangle()
1559      calls LineLineIntersect() with first argument rounded*/
1560   if (TEST_FLAG (SQUAREFLAG, Line2))
1561     {
1562       PointType p[4];form_slanted_rectangle(p,Line2);
1563       return IsLineInQuadrangle(p,Line1);
1564     }
1565   /* now all lines are round */
1566
1567 #if 0
1568   if (Line1->BoundingBox.X1 - Bloat > Line2->BoundBoxing.X2
1569       || Line1->BoundingBox.X2 + Bloat < Line2->BoundingBox.X1
1570       || Line1->BoundingBox.Y1 - Bloat < Line2->BoundingBox.Y2
1571       || Line1->BoundingBox.Y2 + Bloat < Line2->BoundingBox.Y1)
1572     return False;
1573 #endif
1574
1575   /* setup some constants */
1576   dx = (float) (Line1->Point2.X - Line1->Point1.X);
1577   dy = (float) (Line1->Point2.Y - Line1->Point1.Y);
1578   dx1 = (float) (Line1->Point1.X - Line2->Point1.X);
1579   dy1 = (float) (Line1->Point1.Y - Line2->Point1.Y);
1580   s = dy1 * dx - dx1 * dy;
1581
1582   r =
1583     dx * (float) (Line2->Point2.Y -
1584                   Line2->Point1.Y) -
1585     dy * (float) (Line2->Point2.X - Line2->Point1.X);
1586
1587   /* handle parallel lines */
1588   if (r == 0.0)
1589     {
1590       /* at least one of the two end points of one segment
1591        * has to have a minimum distance to the other segment
1592        *
1593        * a first quick check is to see if the distance between
1594        * the two lines is less then their half total thickness
1595        */
1596       register float distance;
1597
1598       /* perhaps line 1 is really just a point */
1599       if ((dx == 0) && (dy == 0))
1600         return IsPointInPad
1601                 (Line1->Point1.X,
1602                  Line1->Point1.Y,
1603                  MAX (Line1->Thickness / 2 +
1604                       Bloat, 0),
1605                  (PadTypePtr) Line2);
1606       s = s * s / (dx * dx + dy * dy);
1607
1608
1609       distance =
1610         MAX ((float) 0.5 *
1611              (Line1->Thickness + Line2->Thickness) + fBloat, 0.0);
1612       distance *= distance;
1613       if (s > distance)
1614         return (False);
1615       if (IsPointInPad (Line2->Point1.
1616                                X,
1617                                Line2->Point1.
1618                                Y,
1619                                MAX (Line2->
1620                                     Thickness
1621                                     / 2 +
1622                                     Bloat, 0),
1623                                (PadTypePtr)
1624                                Line1)
1625            || IsPointInPad (Line2->
1626                                   Point2.X,
1627                                   Line2->
1628                                   Point2.Y,
1629                                   MAX (Line2->
1630                                        Thickness
1631                                        / 2 + Bloat, 0), (PadTypePtr) Line1))
1632         return (True);
1633       return ((IsPointInPad (Line1->Point1.
1634                                X,
1635                                Line1->Point1.
1636                                Y,
1637                                MAX (Line1->
1638                                     Thickness
1639                                     / 2 +
1640                                     Bloat, 0),
1641                                (PadTypePtr)
1642                                Line2)
1643            || IsPointInPad (Line1->
1644                                   Point2.X,
1645                                   Line1->
1646                                   Point2.Y,
1647                                   MAX (Line1->
1648                                        Thickness
1649                                        / 2 + Bloat, 0), (PadTypePtr) Line2)));
1650     }
1651   else
1652     {
1653       s /= r;
1654       r =
1655         (dy1 *
1656          (float) (Line2->Point2.X -
1657                   Line2->Point1.X) -
1658          dx1 * (float) (Line2->Point2.Y - Line2->Point1.Y)) / r;
1659
1660       /* intersection is at least on AB */
1661       if (r >= 0.0 && r <= 1.0)
1662         {
1663           if (s >= 0.0 && s <= 1.0)
1664             return (True);
1665
1666           /* intersection on AB and extension of CD */
1667           return (s < 0.0 ?
1668                   IsPointInPad
1669                   (Line2->Point1.X,
1670                    Line2->Point1.Y,
1671                    MAX (0.5 *
1672                         Line2->Thickness +
1673                         fBloat, 0.0),
1674                    (PadTypePtr)Line1) :
1675                   IsPointInPad
1676                   (Line2->Point2.X,
1677                    Line2->Point2.Y,
1678                    MAX (0.5 * Line2->Thickness + fBloat, 0.0), (PadTypePtr)Line1));
1679         }
1680
1681       /* intersection is at least on CD */
1682       if (s >= 0.0 && s <= 1.0)
1683         {
1684           /* intersection on CD and extension of AB */
1685           return (r < 0.0 ?
1686                   IsPointInPad
1687                   (Line1->Point1.X,
1688                    Line1->Point1.Y,
1689                    MAX (Line1->Thickness /
1690                         2.0 + fBloat, 0.0),
1691                    (PadTypePtr)Line2) :
1692                   IsPointInPad
1693                   (Line1->Point2.X,
1694                    Line1->Point2.Y,
1695                    MAX (Line1->Thickness / 2.0 + fBloat, 0.0), (PadTypePtr)Line2));
1696         }
1697
1698       /* no intersection of zero-width lines but maybe of thick lines;
1699        * Must check each end point to exclude intersection
1700        */
1701       if (IsPointInPad (Line1->Point1.X, Line1->Point1.Y,
1702                          Line1->Thickness / 2.0 + fBloat, (PadTypePtr)Line2))
1703         return True;
1704       if (IsPointInPad (Line1->Point2.X, Line1->Point2.Y,
1705                          Line1->Thickness / 2.0 + fBloat, (PadTypePtr)Line2))
1706         return True;
1707       if (IsPointInPad (Line2->Point1.X, Line2->Point1.Y,
1708                          Line2->Thickness / 2.0 + fBloat, (PadTypePtr)Line1))
1709         return True;
1710       return IsPointInPad (Line2->Point2.X, Line2->Point2.Y,
1711                             Line2->Thickness / 2.0 + fBloat, (PadTypePtr)Line1);
1712     }
1713 }
1714
1715 /*---------------------------------------------------
1716  *
1717  * Check for line intersection with an arc
1718  *
1719  * Mostly this is like the circle/line intersection
1720  * found in IsPointOnLine (search.c) see the detailed
1721  * discussion for the basics there.
1722  *
1723  * Since this is only an arc, not a full circle we need
1724  * to find the actual points of intersection with the
1725  * circle, and see if they are on the arc.
1726  *
1727  * To do this, we translate along the line from the point Q
1728  * plus or minus a distance delta = sqrt(Radius^2 - d^2)
1729  * but it's handy to normalize with respect to l, the line
1730  * length so a single projection is done (e.g. we don't first
1731  * find the point Q
1732  *
1733  * The projection is now of the form
1734  *
1735  *      Px = X1 + (r +- r2)(X2 - X1)
1736  *      Py = Y1 + (r +- r2)(Y2 - Y1)
1737  *
1738  * Where r2 sqrt(Radius^2 l^2 - d^2)/l^2
1739  * note that this is the variable d, not the symbol d described in IsPointOnLine
1740  * (variable d = symbol d * l)
1741  *
1742  * The end points are hell so they are checked individually
1743  */
1744 Boolean
1745 LineArcIntersect (LineTypePtr Line, ArcTypePtr Arc)
1746 {
1747   register float dx, dy, dx1, dy1, l, d, r, r2, Radius;
1748   BoxTypePtr box;
1749
1750   dx = (float) (Line->Point2.X - Line->Point1.X);
1751   dy = (float) (Line->Point2.Y - Line->Point1.Y);
1752   dx1 = (float) (Line->Point1.X - Arc->X);
1753   dy1 = (float) (Line->Point1.Y - Arc->Y);
1754   l = dx * dx + dy * dy;
1755   d = dx * dy1 - dy * dx1;
1756   d *= d;
1757
1758   /* use the larger diameter circle first */
1759   Radius =
1760     Arc->Width + MAX (0.5 * (Arc->Thickness + Line->Thickness) + fBloat, 0.0);
1761   Radius *= Radius;
1762   r2 = Radius * l - d;
1763   /* projection doesn't even intersect circle when r2 < 0 */
1764   if (r2 < 0)
1765     return (False);
1766   /* check the ends of the line in case the projected point */
1767   /* of intersection is beyond the line end */
1768   if (IsPointOnArc
1769       (Line->Point1.X, Line->Point1.Y,
1770        MAX (0.5 * Line->Thickness + fBloat, 0.0), Arc))
1771     return (True);
1772   if (IsPointOnArc
1773       (Line->Point2.X, Line->Point2.Y,
1774        MAX (0.5 * Line->Thickness + fBloat, 0.0), Arc))
1775     return (True);
1776   if (l == 0.0)
1777     return (False);
1778   r2 = sqrt (r2);
1779   Radius = -(dx * dx1 + dy * dy1);
1780   r = (Radius + r2) / l;
1781   if (r >= 0 && r <= 1
1782       && IsPointOnArc (Line->Point1.X + r * dx,
1783                        Line->Point1.Y + r * dy,
1784                        MAX (0.5 * Line->Thickness + fBloat, 0.0), Arc))
1785     return (True);
1786   r = (Radius - r2) / l;
1787   if (r >= 0 && r <= 1
1788       && IsPointOnArc (Line->Point1.X + r * dx,
1789                        Line->Point1.Y + r * dy,
1790                        MAX (0.5 * Line->Thickness + fBloat, 0.0), Arc))
1791     return (True);
1792   /* check arc end points */
1793   box = GetArcEnds (Arc);
1794   if (IsPointInPad (box->X1, box->Y1, Arc->Thickness * 0.5 + fBloat, (PadTypePtr)Line))
1795     return True;
1796   if (IsPointInPad (box->X2, box->Y2, Arc->Thickness * 0.5 + fBloat, (PadTypePtr)Line))
1797     return True;
1798   return False;
1799 }
1800
1801 static int
1802 LOCtoArcLine_callback (const BoxType * b, void *cl)
1803 {
1804   LineTypePtr line = (LineTypePtr) b;
1805   struct lo_info *i = (struct lo_info *) cl;
1806
1807   if (!TEST_FLAG (TheFlag, line) && LineArcIntersect (line, &i->arc))
1808     {
1809       if (ADD_LINE_TO_LIST (i->layer, line))
1810         longjmp (i->env, 1);
1811     }
1812   return 0;
1813 }
1814
1815 static int
1816 LOCtoArcArc_callback (const BoxType * b, void *cl)
1817 {
1818   ArcTypePtr arc = (ArcTypePtr) b;
1819   struct lo_info *i = (struct lo_info *) cl;
1820
1821   if (!arc->Thickness)
1822     return 0;
1823   if (!TEST_FLAG (TheFlag, arc) && ArcArcIntersect (&i->arc, arc))
1824     {
1825       if (ADD_ARC_TO_LIST (i->layer, arc))
1826         longjmp (i->env, 1);
1827     }
1828   return 0;
1829 }
1830
1831 static int
1832 LOCtoArcPad_callback (const BoxType * b, void *cl)
1833 {
1834   PadTypePtr pad = (PadTypePtr) b;
1835   struct lo_info *i = (struct lo_info *) cl;
1836
1837   if (!TEST_FLAG (TheFlag, pad) && i->layer ==
1838       (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER)
1839       && ArcPadIntersect (&i->arc, pad) && ADD_PAD_TO_LIST (i->layer, pad))
1840     longjmp (i->env, 1);
1841   return 0;
1842 }
1843
1844 /* ---------------------------------------------------------------------------
1845  * searches all LOs that are connected to the given arc on the given
1846  * layergroup. All found connections are added to the list
1847  *
1848  * the notation that is used is:
1849  * Xij means Xj at arc i
1850  */
1851 static Boolean
1852 LookupLOConnectionsToArc (ArcTypePtr Arc, Cardinal LayerGroup)
1853 {
1854   Cardinal entry;
1855   LocationType xlow, xhigh;
1856   struct lo_info info;
1857
1858   /* the maximum possible distance */
1859   xlow = Arc->BoundingBox.X1 - MAX (MAX_PADSIZE, MAX_LINESIZE) / 2;
1860   xhigh = Arc->BoundingBox.X2 + MAX (MAX_PADSIZE, MAX_LINESIZE) / 2;
1861
1862   info.arc = *Arc;
1863   EXPAND_BOUNDS (&info.arc);
1864   /* loop over all layers of the group */
1865   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
1866     {
1867       Cardinal layer, i;
1868
1869       layer = PCB->LayerGroups.Entries[LayerGroup][entry];
1870
1871       /* handle normal layers */
1872       if (layer < max_layer)
1873         {
1874           PolygonTypePtr polygon;
1875
1876           info.layer = layer;
1877           /* add arcs */
1878           if (setjmp (info.env) == 0)
1879             r_search (LAYER_PTR (layer)->line_tree, &info.arc.BoundingBox,
1880                       NULL, LOCtoArcLine_callback, &info);
1881           else
1882             return True;
1883
1884           if (setjmp (info.env) == 0)
1885             r_search (LAYER_PTR (layer)->arc_tree, &info.arc.BoundingBox,
1886                       NULL, LOCtoArcArc_callback, &info);
1887           else
1888             return True;
1889
1890           /* now check all polygons */
1891           i = 0;
1892           polygon = PCB->Data->Layer[layer].Polygon;
1893           for (; i < PCB->Data->Layer[layer].PolygonN; i++, polygon++)
1894             if (!TEST_FLAG (TheFlag, polygon) && IsArcInPolygon (Arc, polygon)
1895                 && ADD_POLYGON_TO_LIST (layer, polygon))
1896               return True;
1897         }
1898       else
1899         {
1900           info.layer = layer - max_layer;
1901           if (setjmp (info.env) == 0)
1902             r_search (PCB->Data->pad_tree, &info.arc.BoundingBox, NULL,
1903                       LOCtoArcPad_callback, &info);
1904           else
1905             return True;
1906         }
1907     }
1908   return (False);
1909 }
1910
1911 static int
1912 LOCtoLineLine_callback (const BoxType * b, void *cl)
1913 {
1914   LineTypePtr line = (LineTypePtr) b;
1915   struct lo_info *i = (struct lo_info *) cl;
1916
1917   if (!TEST_FLAG (TheFlag, line) && LineLineIntersect (&i->line, line))
1918     {
1919       if (ADD_LINE_TO_LIST (i->layer, line))
1920         longjmp (i->env, 1);
1921     }
1922   return 0;
1923 }
1924
1925 static int
1926 LOCtoLineArc_callback (const BoxType * b, void *cl)
1927 {
1928   ArcTypePtr arc = (ArcTypePtr) b;
1929   struct lo_info *i = (struct lo_info *) cl;
1930
1931   if (!arc->Thickness)
1932     return 0;
1933   if (!TEST_FLAG (TheFlag, arc) && LineArcIntersect (&i->line, arc))
1934     {
1935       if (ADD_ARC_TO_LIST (i->layer, arc))
1936         longjmp (i->env, 1);
1937     }
1938   return 0;
1939 }
1940
1941 static int
1942 LOCtoLineRat_callback (const BoxType * b, void *cl)
1943 {
1944   RatTypePtr rat = (RatTypePtr) b;
1945   struct lo_info *i = (struct lo_info *) cl;
1946
1947   if (!TEST_FLAG (TheFlag, rat))
1948     {
1949       if ((rat->group1 == i->layer)
1950           && IsRatPointOnLineEnd (&rat->Point1, &i->line))
1951         {
1952           if (ADD_RAT_TO_LIST (rat))
1953             longjmp (i->env, 1);
1954         }
1955       else if ((rat->group2 == i->layer)
1956                && IsRatPointOnLineEnd (&rat->Point2, &i->line))
1957         {
1958           if (ADD_RAT_TO_LIST (rat))
1959             longjmp (i->env, 1);
1960         }
1961     }
1962   return 0;
1963 }
1964
1965 static int
1966 LOCtoLinePad_callback (const BoxType * b, void *cl)
1967 {
1968   PadTypePtr pad = (PadTypePtr) b;
1969   struct lo_info *i = (struct lo_info *) cl;
1970
1971   if (!TEST_FLAG (TheFlag, pad) && i->layer ==
1972       (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER)
1973       && LinePadIntersect (&i->line, pad) && ADD_PAD_TO_LIST (i->layer, pad))
1974     longjmp (i->env, 1);
1975   return 0;
1976 }
1977
1978 /* ---------------------------------------------------------------------------
1979  * searches all LOs that are connected to the given line on the given
1980  * layergroup. All found connections are added to the list
1981  *
1982  * the notation that is used is:
1983  * Xij means Xj at line i
1984  */
1985 static Boolean
1986 LookupLOConnectionsToLine (LineTypePtr Line, Cardinal LayerGroup,
1987                            Boolean PolysTo)
1988 {
1989   Cardinal entry;
1990   struct lo_info info;
1991
1992   info.line = *Line;
1993   info.layer = LayerGroup;
1994   EXPAND_BOUNDS (&info.line)
1995   /* add the new rat lines */
1996   if (setjmp (info.env) == 0)
1997     r_search (PCB->Data->rat_tree, &info.line.BoundingBox, NULL,
1998               LOCtoLineRat_callback, &info);
1999   else
2000     return True;
2001
2002   /* loop over all layers of the group */
2003   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2004     {
2005       Cardinal layer;
2006
2007       layer = PCB->LayerGroups.Entries[LayerGroup][entry];
2008
2009       /* handle normal layers */
2010       if (layer < max_layer)
2011         {
2012           PolygonTypePtr polygon;
2013
2014           info.layer = layer;
2015           /* add lines */
2016           if (setjmp (info.env) == 0)
2017             r_search (LAYER_PTR (layer)->line_tree, (BoxType *) & info.line,
2018                       NULL, LOCtoLineLine_callback, &info);
2019           else
2020             return True;
2021           /* add arcs */
2022           if (setjmp (info.env) == 0)
2023             r_search (LAYER_PTR (layer)->arc_tree, (BoxType *) & info.line,
2024                       NULL, LOCtoLineArc_callback, &info);
2025           else
2026             return True;
2027           /* now check all polygons */
2028           if (PolysTo)
2029             {
2030               Cardinal i = 0;
2031               polygon = PCB->Data->Layer[layer].Polygon;
2032               for (; i < PCB->Data->Layer[layer].PolygonN; i++, polygon++)
2033                 if (!TEST_FLAG
2034                     (TheFlag, polygon) && IsLineInPolygon (Line, polygon)
2035                     && ADD_POLYGON_TO_LIST (layer, polygon))
2036                   return True;
2037             }
2038         }
2039       else
2040         {
2041           /* handle special 'pad' layers */
2042           info.layer = layer - max_layer;
2043           if (setjmp (info.env) == 0)
2044             r_search (PCB->Data->pad_tree, &info.line.BoundingBox, NULL,
2045                       LOCtoLinePad_callback, &info);
2046           else
2047             return True;
2048         }
2049     }
2050   return (False);
2051 }
2052
2053 static int
2054 LOT_Linecallback (const BoxType * b, void *cl)
2055 {
2056   LineTypePtr line = (LineTypePtr) b;
2057   struct lo_info *i = (struct lo_info *) cl;
2058
2059   if (!TEST_FLAG (TheFlag, line) && LineLineIntersect (&i->line, line))
2060     longjmp (i->env, 1);
2061   return 0;
2062 }
2063
2064 static int
2065 LOT_Arccallback (const BoxType * b, void *cl)
2066 {
2067   ArcTypePtr arc = (ArcTypePtr) b;
2068   struct lo_info *i = (struct lo_info *) cl;
2069
2070   if (!arc->Thickness)
2071     return 0;
2072   if (!TEST_FLAG (TheFlag, arc) && LineArcIntersect (&i->line, arc))
2073     longjmp (i->env, 1);
2074   return 0;
2075 }
2076
2077 static int
2078 LOT_Padcallback (const BoxType * b, void *cl)
2079 {
2080   PadTypePtr pad = (PadTypePtr) b;
2081   struct lo_info *i = (struct lo_info *) cl;
2082
2083   if (!TEST_FLAG (TheFlag, pad) && i->layer ==
2084       (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER)
2085       && LinePadIntersect (&i->line, pad))
2086     longjmp (i->env, 1);
2087   return 0;
2088 }
2089
2090 static Boolean
2091 LOTouchesLine (LineTypePtr Line, Cardinal LayerGroup)
2092 {
2093   Cardinal entry;
2094   Cardinal i;
2095   struct lo_info info;
2096
2097
2098   /* the maximum possible distance */
2099
2100   info.line = *Line;
2101   EXPAND_BOUNDS (&info.line);
2102
2103   /* loop over all layers of the group */
2104   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2105     {
2106       Cardinal layer = PCB->LayerGroups.Entries[LayerGroup][entry];
2107
2108       /* handle normal layers */
2109       if (layer < max_layer)
2110         {
2111           PolygonTypePtr polygon;
2112
2113           /* find the first line that touches coordinates */
2114
2115           if (setjmp (info.env) == 0)
2116             r_search (LAYER_PTR (layer)->line_tree, (BoxType *) & info.line,
2117                       NULL, LOT_Linecallback, &info);
2118           else
2119             return (True);
2120           if (setjmp (info.env) == 0)
2121             r_search (LAYER_PTR (layer)->arc_tree, (BoxType *) & info.line,
2122                       NULL, LOT_Arccallback, &info);
2123           else
2124             return (True);
2125
2126           /* now check all polygons */
2127           i = 0;
2128           polygon = PCB->Data->Layer[layer].Polygon;
2129           for (; i < PCB->Data->Layer[layer].PolygonN; i++, polygon++)
2130             if (!TEST_FLAG (TheFlag, polygon)
2131                 && IsLineInPolygon (Line, polygon))
2132               return (True);
2133         }
2134       else
2135         {
2136           /* handle special 'pad' layers */
2137           info.layer = layer - max_layer;
2138           if (setjmp (info.env) == 0)
2139             r_search (PCB->Data->pad_tree, &info.line.BoundingBox, NULL,
2140                       LOT_Padcallback, &info);
2141           else
2142             return True;
2143         }
2144     }
2145   return (False);
2146 }
2147
2148 struct rat_info
2149 {
2150   Cardinal layer;
2151   PointTypePtr Point;
2152   jmp_buf env;
2153 };
2154
2155 static int
2156 LOCtoRat_callback (const BoxType * b, void *cl)
2157 {
2158   LineTypePtr line = (LineTypePtr) b;
2159   struct rat_info *i = (struct rat_info *) cl;
2160
2161   if (!TEST_FLAG (TheFlag, line) &&
2162       ((line->Point1.X == i->Point->X &&
2163         line->Point1.Y == i->Point->Y) ||
2164        (line->Point2.X == i->Point->X && line->Point2.Y == i->Point->Y)))
2165     {
2166       if (ADD_LINE_TO_LIST (i->layer, line))
2167         longjmp (i->env, 1);
2168     }
2169   return 0;
2170 }
2171 static int
2172 PolygonToRat_callback (const BoxType * b, void *cl)
2173 {
2174   PolygonTypePtr polygon = (PolygonTypePtr) b;
2175   struct rat_info *i = (struct rat_info *) cl;
2176
2177   if (!TEST_FLAG (TheFlag, polygon) && polygon->Clipped &&
2178       (i->Point->X == polygon->Clipped->contours->head.point[0]) &&
2179       (i->Point->Y == polygon->Clipped->contours->head.point[1]))
2180     {
2181       if (ADD_POLYGON_TO_LIST (i->layer, polygon))
2182         longjmp (i->env, 1);
2183     }
2184   return 0;
2185 }
2186
2187 static int
2188 LOCtoPad_callback (const BoxType * b, void *cl)
2189 {
2190   PadTypePtr pad = (PadTypePtr) b;
2191   struct rat_info *i = (struct rat_info *) cl;
2192
2193   if (!TEST_FLAG (TheFlag, pad) && i->layer ==
2194       (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER)
2195       && (((pad->Point1.X == i->Point->X && pad->Point1.Y == i->Point->Y)) ||
2196           ((pad->Point2.X == i->Point->X && pad->Point2.Y == i->Point->Y)))
2197       && ADD_PAD_TO_LIST (i->layer, pad))
2198     longjmp (i->env, 1);
2199   return 0;
2200 }
2201
2202 /* ---------------------------------------------------------------------------
2203  * searches all LOs that are connected to the given rat-line on the given
2204  * layergroup. All found connections are added to the list
2205  *
2206  * the notation that is used is:
2207  * Xij means Xj at line i
2208  */
2209 static Boolean
2210 LookupLOConnectionsToRatEnd (PointTypePtr Point, Cardinal LayerGroup)
2211 {
2212   Cardinal entry;
2213   struct rat_info info;
2214
2215   info.Point = Point;
2216   /* loop over all layers of this group */
2217   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2218     {
2219       Cardinal layer;
2220
2221       layer = PCB->LayerGroups.Entries[LayerGroup][entry];
2222       /* handle normal layers
2223          rats don't ever touch
2224          arcs by definition
2225        */
2226
2227       if (layer < max_layer)
2228         {
2229           info.layer = layer;
2230           if (setjmp (info.env) == 0)
2231             r_search_pt (LAYER_PTR (layer)->line_tree, Point, 1, NULL,
2232                       LOCtoRat_callback, &info);
2233           else
2234             return True;
2235           if (setjmp (info.env) == 0)
2236             r_search_pt (LAYER_PTR (layer)->polygon_tree, Point, 1,
2237                       NULL, PolygonToRat_callback, &info);
2238         }
2239       else
2240         {
2241           /* handle special 'pad' layers */
2242           info.layer = layer - max_layer;
2243           if (setjmp (info.env) == 0)
2244             r_search_pt (PCB->Data->pad_tree, Point, 1, NULL,
2245                       LOCtoPad_callback, &info);
2246           else
2247             return True;
2248         }
2249     }
2250   return (False);
2251 }
2252
2253 static int
2254 LOCtoPadLine_callback (const BoxType * b, void *cl)
2255 {
2256   LineTypePtr line = (LineTypePtr) b;
2257   struct lo_info *i = (struct lo_info *) cl;
2258
2259   if (!TEST_FLAG (TheFlag, line) && LinePadIntersect (line, &i->pad))
2260     {
2261       if (ADD_LINE_TO_LIST (i->layer, line))
2262         longjmp (i->env, 1);
2263     }
2264   return 0;
2265 }
2266
2267 static int
2268 LOCtoPadArc_callback (const BoxType * b, void *cl)
2269 {
2270   ArcTypePtr arc = (ArcTypePtr) b;
2271   struct lo_info *i = (struct lo_info *) cl;
2272
2273   if (!arc->Thickness)
2274     return 0;
2275   if (!TEST_FLAG (TheFlag, arc) && ArcPadIntersect (arc, &i->pad))
2276     {
2277       if (ADD_ARC_TO_LIST (i->layer, arc))
2278         longjmp (i->env, 1);
2279     }
2280   return 0;
2281 }
2282
2283 static int
2284 LOCtoPadPoly_callback (const BoxType * b, void *cl)
2285 {
2286   PolygonTypePtr polygon = (PolygonTypePtr) b;
2287   struct lo_info *i = (struct lo_info *) cl;
2288
2289
2290   if (!TEST_FLAG (TheFlag, polygon) &&
2291       (!TEST_FLAG (CLEARPOLYFLAG, polygon) || !i->pad.Clearance))
2292     {
2293       if (IsPadInPolygon (&i->pad, polygon) &&
2294           ADD_POLYGON_TO_LIST (i->layer, polygon))
2295         longjmp (i->env, 1);
2296     }
2297   return 0;
2298 }
2299
2300 static int
2301 LOCtoPadRat_callback (const BoxType * b, void *cl)
2302 {
2303   RatTypePtr rat = (RatTypePtr) b;
2304   struct lo_info *i = (struct lo_info *) cl;
2305
2306   if (!TEST_FLAG (TheFlag, rat))
2307     {
2308       if (rat->group1 == i->layer &&
2309           ((rat->Point1.X == i->pad.Point1.X
2310             && rat->Point1.Y == i->pad.Point1.Y)
2311            || (rat->Point1.X == i->pad.Point2.X
2312                && rat->Point1.Y == i->pad.Point2.Y)))
2313         {
2314           if (ADD_RAT_TO_LIST (rat))
2315             longjmp (i->env, 1);
2316         }
2317       else if (rat->group2 == i->layer &&
2318                ((rat->Point2.X == i->pad.Point1.X
2319                  && rat->Point2.Y == i->pad.Point1.Y)
2320                 || (rat->Point2.X == i->pad.Point2.X
2321                     && rat->Point2.Y == i->pad.Point2.Y)))
2322         {
2323           if (ADD_RAT_TO_LIST (rat))
2324             longjmp (i->env, 1);
2325         }
2326     }
2327   return 0;
2328 }
2329
2330 static int
2331 LOCtoPadPad_callback (const BoxType * b, void *cl)
2332 {
2333   PadTypePtr pad = (PadTypePtr) b;
2334   struct lo_info *i = (struct lo_info *) cl;
2335
2336   if (!TEST_FLAG (TheFlag, pad) && i->layer ==
2337       (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER)
2338       && PadPadIntersect (pad, &i->pad) && ADD_PAD_TO_LIST (i->layer, pad))
2339     longjmp (i->env, 1);
2340   return 0;
2341 }
2342
2343 /* ---------------------------------------------------------------------------
2344  * searches all LOs that are connected to the given pad on the given
2345  * layergroup. All found connections are added to the list
2346  */
2347 static Boolean
2348 LookupLOConnectionsToPad (PadTypePtr Pad, Cardinal LayerGroup)
2349 {
2350   Cardinal entry;
2351   struct lo_info info;
2352
2353   if (!TEST_FLAG (SQUAREFLAG, Pad))
2354     return (LookupLOConnectionsToLine ((LineTypePtr) Pad, LayerGroup, False));
2355
2356   info.pad = *Pad;
2357   EXPAND_BOUNDS (&info.pad);
2358   /* add the new rat lines */
2359   info.layer = LayerGroup;
2360   if (setjmp (info.env) == 0)
2361     r_search (PCB->Data->rat_tree, &info.pad.BoundingBox, NULL,
2362               LOCtoPadRat_callback, &info);
2363   else
2364     return True;
2365
2366   /* loop over all layers of the group */
2367   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2368     {
2369       Cardinal layer;
2370
2371       layer = PCB->LayerGroups.Entries[LayerGroup][entry];
2372       /* handle normal layers */
2373       if (layer < max_layer)
2374         {
2375           info.layer = layer;
2376           /* add lines */
2377           if (setjmp (info.env) == 0)
2378             r_search (LAYER_PTR (layer)->line_tree, &info.pad.BoundingBox,
2379                       NULL, LOCtoPadLine_callback, &info);
2380           else
2381             return True;
2382           /* add arcs */
2383           if (setjmp (info.env) == 0)
2384             r_search (LAYER_PTR (layer)->arc_tree, &info.pad.BoundingBox,
2385                       NULL, LOCtoPadArc_callback, &info);
2386           else
2387             return True;
2388           /* add polygons */
2389           if (setjmp (info.env) == 0)
2390             r_search (LAYER_PTR (layer)->polygon_tree, &info.pad.BoundingBox,
2391                       NULL, LOCtoPadPoly_callback, &info);
2392           else
2393             return True;
2394         }
2395       else
2396         {
2397           /* handle special 'pad' layers */
2398           info.layer = layer - max_layer;
2399           if (setjmp (info.env) == 0)
2400             r_search (PCB->Data->pad_tree, (BoxType *) & info.pad, NULL,
2401                       LOCtoPadPad_callback, &info);
2402           else
2403             return True;
2404         }
2405
2406     }
2407   return (False);
2408 }
2409
2410 static int
2411 LOCtoPolyLine_callback (const BoxType * b, void *cl)
2412 {
2413   LineTypePtr line = (LineTypePtr) b;
2414   struct lo_info *i = (struct lo_info *) cl;
2415
2416   if (!TEST_FLAG (TheFlag, line) && IsLineInPolygon (line, &i->polygon))
2417     {
2418       if (ADD_LINE_TO_LIST (i->layer, line))
2419         longjmp (i->env, 1);
2420     }
2421   return 0;
2422 }
2423
2424 static int
2425 LOCtoPolyArc_callback (const BoxType * b, void *cl)
2426 {
2427   ArcTypePtr arc = (ArcTypePtr) b;
2428   struct lo_info *i = (struct lo_info *) cl;
2429
2430   if (!arc->Thickness)
2431     return 0;
2432   if (!TEST_FLAG (TheFlag, arc) && IsArcInPolygon (arc, &i->polygon))
2433     {
2434       if (ADD_ARC_TO_LIST (i->layer, arc))
2435         longjmp (i->env, 1);
2436     }
2437   return 0;
2438 }
2439
2440 static int
2441 LOCtoPolyPad_callback (const BoxType * b, void *cl)
2442 {
2443   PadTypePtr pad = (PadTypePtr) b;
2444   struct lo_info *i = (struct lo_info *) cl;
2445
2446   if (!TEST_FLAG (TheFlag, pad) && i->layer ==
2447       (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER)
2448       && IsPadInPolygon (pad, &i->polygon))
2449     {
2450       if (ADD_PAD_TO_LIST (i->layer, pad))
2451         longjmp (i->env, 1);
2452     }
2453   return 0;
2454 }
2455
2456 static int
2457 LOCtoPolyRat_callback (const BoxType * b, void *cl)
2458 {
2459   RatTypePtr rat = (RatTypePtr) b;
2460   struct lo_info *i = (struct lo_info *) cl;
2461
2462   if (!TEST_FLAG (TheFlag, rat))
2463     {
2464       if ((rat->Point1.X == (i->polygon.Clipped->contours->head.point[0]) &&
2465            rat->Point1.Y == (i->polygon.Clipped->contours->head.point[1]) &&
2466            rat->group1 == i->layer) ||
2467           (rat->Point2.X == (i->polygon.Clipped->contours->head.point[0]) &&
2468            rat->Point2.Y == (i->polygon.Clipped->contours->head.point[1]) &&
2469            rat->group2 == i->layer))
2470         if (ADD_RAT_TO_LIST (rat))
2471           longjmp (i->env, 1);
2472     }
2473   return 0;
2474 }
2475
2476
2477 /* ---------------------------------------------------------------------------
2478  * looks up LOs that are connected to the given polygon
2479  * on the given layergroup. All found connections are added to the list
2480  */
2481 static Boolean
2482 LookupLOConnectionsToPolygon (PolygonTypePtr Polygon, Cardinal LayerGroup)
2483 {
2484   Cardinal entry;
2485   struct lo_info info;
2486
2487   if (!Polygon->Clipped)
2488     return False;
2489   info.polygon = *Polygon;
2490   EXPAND_BOUNDS (&info.polygon);
2491   info.layer = LayerGroup;
2492   /* check rats */
2493   if (setjmp (info.env) == 0)
2494     r_search (PCB->Data->rat_tree, (BoxType *) & info.polygon, NULL,
2495               LOCtoPolyRat_callback, &info);
2496   else
2497     return True;
2498 /* loop over all layers of the group */
2499   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2500     {
2501       Cardinal layer, i;
2502
2503       layer = PCB->LayerGroups.Entries[LayerGroup][entry];
2504
2505       /* handle normal layers */
2506       if (layer < max_layer)
2507         {
2508           PolygonTypePtr polygon;
2509
2510           /* check all polygons */
2511
2512           polygon = PCB->Data->Layer[layer].Polygon;
2513           for (i = 0; i < PCB->Data->Layer[layer].PolygonN; i++, polygon++)
2514             if (!TEST_FLAG (TheFlag, polygon)
2515                 && IsPolygonInPolygon (polygon, Polygon)
2516                 && ADD_POLYGON_TO_LIST (layer, polygon))
2517               return True;
2518
2519           info.layer = layer;
2520           /* check all lines */
2521           if (setjmp (info.env) == 0)
2522             r_search (LAYER_PTR (layer)->line_tree,
2523                       (BoxType *) & info.polygon, NULL,
2524                       LOCtoPolyLine_callback, &info);
2525           else
2526             return True;
2527           /* check all arcs */
2528           if (setjmp (info.env) == 0)
2529             r_search (LAYER_PTR (layer)->arc_tree, (BoxType *) & info.polygon,
2530                       NULL, LOCtoPolyArc_callback, &info);
2531           else
2532             return True;
2533         }
2534       else
2535         {
2536           info.layer = layer - max_layer;
2537           if (setjmp (info.env) == 0)
2538             r_search (PCB->Data->pad_tree, (BoxType *) & info.polygon,
2539                       NULL, LOCtoPolyPad_callback, &info);
2540           else
2541             return True;
2542         }
2543     }
2544   return (False);
2545 }
2546
2547 /* ---------------------------------------------------------------------------
2548  * checks if an arc has a connection to a polygon
2549  *
2550  * - first check if the arc can intersect with the polygon by
2551  *   evaluating the bounding boxes
2552  * - check the two end points of the arc. If none of them matches
2553  * - check all segments of the polygon against the arc.
2554  */
2555 Boolean
2556 IsArcInPolygon (ArcTypePtr Arc, PolygonTypePtr Polygon)
2557 {
2558   BoxTypePtr Box = (BoxType *) Arc;
2559
2560   /* arcs with clearance never touch polys */
2561   if (TEST_FLAG (CLEARPOLYFLAG, Polygon) && TEST_FLAG (CLEARLINEFLAG, Arc))
2562     return False;
2563   if (!Polygon->Clipped)
2564     return False;
2565   if (Box->X1 <= Polygon->Clipped->contours->xmax + Bloat
2566       && Box->X2 >= Polygon->Clipped->contours->xmin - Bloat
2567       && Box->Y1 <= Polygon->Clipped->contours->ymax + Bloat
2568       && Box->Y2 >= Polygon->Clipped->contours->ymin - Bloat)
2569     {
2570       POLYAREA *ap;
2571
2572       if (!(ap = ArcPoly (Arc, Arc->Thickness + Bloat)))
2573         return False;           /* error */
2574       return isects (ap, Polygon, True);
2575     }
2576   return False;
2577 }
2578
2579 /* ---------------------------------------------------------------------------
2580  * checks if a line has a connection to a polygon
2581  *
2582  * - first check if the line can intersect with the polygon by
2583  *   evaluating the bounding boxes
2584  * - check the two end points of the line. If none of them matches
2585  * - check all segments of the polygon against the line.
2586  */
2587 Boolean
2588 IsLineInPolygon (LineTypePtr Line, PolygonTypePtr Polygon)
2589 {
2590   BoxTypePtr Box = (BoxType *) Line;
2591   POLYAREA *lp;
2592
2593   /* lines with clearance never touch polygons */
2594   if (TEST_FLAG (CLEARPOLYFLAG, Polygon) && TEST_FLAG (CLEARLINEFLAG, Line))
2595     return False;
2596   if (!Polygon->Clipped)
2597     return False;
2598   if (TEST_FLAG(SQUAREFLAG,Line)&&(Line->Point1.X==Line->Point2.X||Line->Point1.Y==Line->Point2.Y))
2599      {
2600        BDimension wid = (Line->Thickness + Bloat + 1) / 2;
2601        LocationType x1, x2, y1, y2;
2602
2603        x1 = MIN (Line->Point1.X, Line->Point2.X) - wid;
2604        y1 = MIN (Line->Point1.Y, Line->Point2.Y) - wid;
2605        x2 = MAX (Line->Point1.X, Line->Point2.X) + wid;
2606        y2 = MAX (Line->Point1.Y, Line->Point2.Y) + wid;
2607        return IsRectangleInPolygon (x1, y1, x2, y2, Polygon);
2608      }
2609   if (Box->X1 <= Polygon->Clipped->contours->xmax + Bloat
2610       && Box->X2 >= Polygon->Clipped->contours->xmin - Bloat
2611       && Box->Y1 <= Polygon->Clipped->contours->ymax + Bloat
2612       && Box->Y2 >= Polygon->Clipped->contours->ymin - Bloat)
2613     {
2614       if (!(lp = LinePoly (Line, Line->Thickness + Bloat)))
2615         return FALSE;           /* error */
2616       return isects (lp, Polygon, True);
2617     }
2618   return False;
2619 }
2620
2621 /* ---------------------------------------------------------------------------
2622  * checks if a pad connects to a non-clearing polygon
2623  *
2624  * The polygon is assumed to already have been proven non-clearing
2625  */
2626 Boolean
2627 IsPadInPolygon (PadTypePtr pad, PolygonTypePtr polygon)
2628 {
2629     return IsLineInPolygon ((LineTypePtr) pad, polygon);
2630 }
2631
2632 /* ---------------------------------------------------------------------------
2633  * checks if a polygon has a connection to a second one
2634  *
2635  * First check all points out of P1 against P2 and vice versa.
2636  * If both fail check all lines of P1 against the ones of P2
2637  */
2638 Boolean
2639 IsPolygonInPolygon (PolygonTypePtr P1, PolygonTypePtr P2)
2640 {
2641   if (!P1->Clipped || !P2->Clipped)
2642     return False;
2643   assert (P1->Clipped->contours);
2644   assert (P2->Clipped->contours);
2645
2646   /* first check if both bounding boxes intersect. If not, return quickly */
2647   if (P1->Clipped->contours->xmin - Bloat > P2->Clipped->contours->xmax ||
2648       P1->Clipped->contours->xmax + Bloat < P2->Clipped->contours->xmin ||
2649       P1->Clipped->contours->ymin - Bloat > P2->Clipped->contours->ymax ||
2650       P1->Clipped->contours->ymax + Bloat < P2->Clipped->contours->ymin)
2651     return False;
2652
2653   /* first check un-bloated case */
2654   if (isects (P1->Clipped, P2, False))
2655     return TRUE;
2656
2657   /* now the difficult case of bloated */
2658   if (Bloat > 0)
2659     {
2660       PLINE *c;
2661       for (c = P1->Clipped->contours; c; c = c->next)
2662         {
2663           LineType line;
2664           VNODE *v = &c->head;
2665           if (c->xmin - Bloat <= P2->Clipped->contours->xmax &&
2666               c->xmax + Bloat >= P2->Clipped->contours->xmin &&
2667               c->ymin - Bloat <= P2->Clipped->contours->ymax &&
2668               c->ymax + Bloat >= P2->Clipped->contours->ymin)
2669             {
2670
2671               line.Point1.X = v->point[0];
2672               line.Point1.Y = v->point[1];
2673               line.Thickness = 2 * Bloat;
2674               line.Clearance = 0;
2675               line.Flags = NoFlags ();
2676               for (v = v->next; v != &c->head; v = v->next)
2677                 {
2678                   line.Point2.X = v->point[0];
2679                   line.Point2.Y = v->point[1];
2680                   SetLineBoundingBox (&line);
2681                   if (IsLineInPolygon (&line, P2))
2682                     return (True);
2683                   line.Point1.X = line.Point2.X;
2684                   line.Point1.Y = line.Point2.Y;
2685                 }
2686             }
2687         }
2688     }
2689
2690   return (False);
2691 }
2692
2693 /* ---------------------------------------------------------------------------
2694  * writes the several names of an element to a file
2695  */
2696 static void
2697 PrintElementNameList (ElementTypePtr Element, FILE * FP)
2698 {
2699   static DynamicStringType cname, pname, vname;
2700
2701   CreateQuotedString (&cname, EMPTY (DESCRIPTION_NAME (Element)));
2702   CreateQuotedString (&pname, EMPTY (NAMEONPCB_NAME (Element)));
2703   CreateQuotedString (&vname, EMPTY (VALUE_NAME (Element)));
2704   fprintf (FP, "(%s %s %s)\n", cname.Data, pname.Data, vname.Data);
2705 }
2706
2707 /* ---------------------------------------------------------------------------
2708  * writes the several names of an element to a file
2709  */
2710 static void
2711 PrintConnectionElementName (ElementTypePtr Element, FILE * FP)
2712 {
2713   fputs ("Element", FP);
2714   PrintElementNameList (Element, FP);
2715   fputs ("{\n", FP);
2716 }
2717
2718 /* ---------------------------------------------------------------------------
2719  * prints one {pin,pad,via}/element entry of connection lists
2720  */
2721 static void
2722 PrintConnectionListEntry (char *ObjName, ElementTypePtr Element,
2723                           Boolean FirstOne, FILE * FP)
2724 {
2725   static DynamicStringType oname;
2726
2727   CreateQuotedString (&oname, ObjName);
2728   if (FirstOne)
2729     fprintf (FP, "\t%s\n\t{\n", oname.Data);
2730   else
2731     {
2732       fprintf (FP, "\t\t%s ", oname.Data);
2733       if (Element)
2734         PrintElementNameList (Element, FP);
2735       else
2736         fputs ("(__VIA__)\n", FP);
2737     }
2738 }
2739
2740 /* ---------------------------------------------------------------------------
2741  * prints all found connections of a pads to file FP
2742  * the connections are stacked in 'PadList'
2743  */
2744 static void
2745 PrintPadConnections (Cardinal Layer, FILE * FP, Boolean IsFirst)
2746 {
2747   Cardinal i;
2748   PadTypePtr ptr;
2749
2750   if (!PadList[Layer].Number)
2751     return;
2752
2753   /* the starting pad */
2754   if (IsFirst)
2755     {
2756       ptr = PADLIST_ENTRY (Layer, 0);
2757       if (ptr != NULL)
2758         PrintConnectionListEntry (UNKNOWN (ptr->Name), NULL, True, FP);
2759       else
2760         printf ("Skipping NULL ptr in 1st part of PrintPadConnections\n");
2761     }
2762
2763   /* we maybe have to start with i=1 if we are handling the
2764    * starting-pad itself
2765    */
2766   for (i = IsFirst ? 1 : 0; i < PadList[Layer].Number; i++)
2767     {
2768       ptr = PADLIST_ENTRY (Layer, i);
2769       if (ptr != NULL)
2770         PrintConnectionListEntry (EMPTY (ptr->Name), ptr->Element, False, FP);
2771       else
2772         printf ("Skipping NULL ptr in 2nd part of PrintPadConnections\n");
2773     }
2774 }
2775
2776 /* ---------------------------------------------------------------------------
2777  * prints all found connections of a pin to file FP
2778  * the connections are stacked in 'PVList'
2779  */
2780 static void
2781 PrintPinConnections (FILE * FP, Boolean IsFirst)
2782 {
2783   Cardinal i;
2784   PinTypePtr pv;
2785
2786   if (!PVList.Number)
2787     return;
2788
2789   if (IsFirst)
2790     {
2791       /* the starting pin */
2792       pv = PVLIST_ENTRY (0);
2793       PrintConnectionListEntry (EMPTY (pv->Name), NULL, True, FP);
2794     }
2795
2796   /* we maybe have to start with i=1 if we are handling the
2797    * starting-pin itself
2798    */
2799   for (i = IsFirst ? 1 : 0; i < PVList.Number; i++)
2800     {
2801       /* get the elements name or assume that its a via */
2802       pv = PVLIST_ENTRY (i);
2803       PrintConnectionListEntry (EMPTY (pv->Name), pv->Element, False, FP);
2804     }
2805 }
2806
2807 /* ---------------------------------------------------------------------------
2808  * checks if all lists of new objects are handled
2809  */
2810 static Boolean
2811 ListsEmpty (Boolean AndRats)
2812 {
2813   Boolean empty;
2814   int i;
2815
2816   empty = (PVList.Location >= PVList.Number);
2817   if (AndRats)
2818     empty = empty && (RatList.Location >= RatList.Number);
2819   for (i = 0; i < max_layer && empty; i++)
2820     empty = empty && LineList[i].Location >= LineList[i].Number
2821       && ArcList[i].Location >= ArcList[i].Number
2822       && PolygonList[i].Location >= PolygonList[i].Number;
2823   return (empty);
2824 }
2825
2826 /* ---------------------------------------------------------------------------
2827  * loops till no more connections are found
2828  */
2829 static Boolean
2830 DoIt (Boolean AndRats, Boolean AndDraw)
2831 {
2832   Boolean new = False;
2833   do
2834     {
2835       /* lookup connections; these are the steps (2) to (4)
2836        * from the description
2837        */
2838       new = LookupPVConnectionsToPVList ();
2839       if (!new)
2840         new = LookupLOConnectionsToPVList (AndRats);
2841       if (!new)
2842         new = LookupLOConnectionsToLOList (AndRats);
2843       if (!new)
2844         new = LookupPVConnectionsToLOList (AndRats);
2845       if (AndDraw)
2846         DrawNewConnections ();
2847     }
2848   while (!new && !ListsEmpty (AndRats));
2849   if (AndDraw)
2850     Draw ();
2851   return (new);
2852 }
2853
2854 /* returns True if nothing un-found touches the passed line
2855  * returns False if it would touch something not yet found
2856  * doesn't include rat-lines in the search
2857  */
2858
2859 Boolean
2860 lineClear (LineTypePtr line, Cardinal group)
2861 {
2862   if (LOTouchesLine (line, group))
2863     return (False);
2864   if (PVTouchesLine (line))
2865     return (False);
2866   return (True);
2867 }
2868
2869 /* ---------------------------------------------------------------------------
2870  * prints all unused pins of an element to file FP
2871  */
2872 static Boolean
2873 PrintAndSelectUnusedPinsAndPadsOfElement (ElementTypePtr Element, FILE * FP)
2874 {
2875   Boolean first = True;
2876   Cardinal number;
2877   static DynamicStringType oname;
2878
2879   /* check all pins in element */
2880
2881   PIN_LOOP (Element);
2882   {
2883     if (!TEST_FLAG (HOLEFLAG, pin))
2884       {
2885         /* pin might have bee checked before, add to list if not */
2886         if (!TEST_FLAG (TheFlag, pin) && FP)
2887           {
2888             int i;
2889             if (ADD_PV_TO_LIST (pin))
2890               return True;
2891             DoIt (True, True);
2892             number = PadList[COMPONENT_LAYER].Number
2893               + PadList[SOLDER_LAYER].Number + PVList.Number;
2894             /* the pin has no connection if it's the only
2895              * list entry; don't count vias
2896              */
2897             for (i = 0; i < PVList.Number; i++)
2898               if (!PVLIST_ENTRY (i)->Element)
2899                 number--;
2900             if (number == 1)
2901               {
2902                 /* output of element name if not already done */
2903                 if (first)
2904                   {
2905                     PrintConnectionElementName (Element, FP);
2906                     first = False;
2907                   }
2908
2909                 /* write name to list and draw selected object */
2910                 CreateQuotedString (&oname, EMPTY (pin->Name));
2911                 fprintf (FP, "\t%s\n", oname.Data);
2912                 SET_FLAG (SELECTEDFLAG, pin);
2913                 DrawPin (pin, 0);
2914               }
2915
2916             /* reset found objects for the next pin */
2917             if (PrepareNextLoop (FP))
2918               return (True);
2919           }
2920       }
2921   }
2922   END_LOOP;
2923
2924   /* check all pads in element */
2925   PAD_LOOP (Element);
2926   {
2927     /* lookup pad in list */
2928     /* pad might has bee checked before, add to list if not */
2929     if (!TEST_FLAG (TheFlag, pad) && FP)
2930       {
2931         int i;
2932         if (ADD_PAD_TO_LIST (TEST_FLAG (ONSOLDERFLAG, pad)
2933                              ? SOLDER_LAYER : COMPONENT_LAYER, pad))
2934           return True;
2935         DoIt (True, True);
2936         number = PadList[COMPONENT_LAYER].Number
2937           + PadList[SOLDER_LAYER].Number + PVList.Number;
2938         /* the pin has no connection if it's the only
2939          * list entry; don't count vias
2940          */
2941         for (i = 0; i < PVList.Number; i++)
2942           if (!PVLIST_ENTRY (i)->Element)
2943             number--;
2944         if (number == 1)
2945           {
2946             /* output of element name if not already done */
2947             if (first)
2948               {
2949                 PrintConnectionElementName (Element, FP);
2950                 first = False;
2951               }
2952
2953             /* write name to list and draw selected object */
2954             CreateQuotedString (&oname, EMPTY (pad->Name));
2955             fprintf (FP, "\t%s\n", oname.Data);
2956             SET_FLAG (SELECTEDFLAG, pad);
2957             DrawPad (pad, 0);
2958           }
2959
2960         /* reset found objects for the next pin */
2961         if (PrepareNextLoop (FP))
2962           return (True);
2963       }
2964   }
2965   END_LOOP;
2966
2967   /* print separator if element has unused pins or pads */
2968   if (!first)
2969     {
2970       fputs ("}\n\n", FP);
2971       SEPARATE (FP);
2972     }
2973   return (False);
2974 }
2975
2976 /* ---------------------------------------------------------------------------
2977  * resets some flags for looking up the next pin/pad
2978  */
2979 static Boolean
2980 PrepareNextLoop (FILE * FP)
2981 {
2982   Cardinal layer;
2983
2984   /* reset found LOs for the next pin */
2985   for (layer = 0; layer < max_layer; layer++)
2986     {
2987       LineList[layer].Location = LineList[layer].Number = 0;
2988       ArcList[layer].Location = ArcList[layer].Number = 0;
2989       PolygonList[layer].Location = PolygonList[layer].Number = 0;
2990     }
2991
2992   /* reset found pads */
2993   for (layer = 0; layer < 2; layer++)
2994     PadList[layer].Location = PadList[layer].Number = 0;
2995
2996   /* reset PVs */
2997   PVList.Number = PVList.Location = 0;
2998   RatList.Number = RatList.Location = 0;
2999
3000   return (False);
3001 }
3002
3003 /* ---------------------------------------------------------------------------
3004  * finds all connections to the pins of the passed element.
3005  * The result is written to file FP
3006  * Returns True if operation was aborted
3007  */
3008 static Boolean
3009 PrintElementConnections (ElementTypePtr Element, FILE * FP, Boolean AndDraw)
3010 {
3011   PrintConnectionElementName (Element, FP);
3012
3013   /* check all pins in element */
3014   PIN_LOOP (Element);
3015   {
3016     /* pin might have been checked before, add to list if not */
3017     if (TEST_FLAG (TheFlag, pin))
3018       {
3019         PrintConnectionListEntry (EMPTY (pin->Name), NULL, True, FP);
3020         fputs ("\t\t__CHECKED_BEFORE__\n\t}\n", FP);
3021         continue;
3022       }
3023     if (ADD_PV_TO_LIST (pin))
3024       return True;
3025     DoIt (True, AndDraw);
3026     /* printout all found connections */
3027     PrintPinConnections (FP, True);
3028     PrintPadConnections (COMPONENT_LAYER, FP, False);
3029     PrintPadConnections (SOLDER_LAYER, FP, False);
3030     fputs ("\t}\n", FP);
3031     if (PrepareNextLoop (FP))
3032       return (True);
3033   }
3034   END_LOOP;
3035
3036   /* check all pads in element */
3037   PAD_LOOP (Element);
3038   {
3039     Cardinal layer;
3040     /* pad might have been checked before, add to list if not */
3041     if (TEST_FLAG (TheFlag, pad))
3042       {
3043         PrintConnectionListEntry (EMPTY (pad->Name), NULL, True, FP);
3044         fputs ("\t\t__CHECKED_BEFORE__\n\t}\n", FP);
3045         continue;
3046       }
3047     layer = TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER;
3048     if (ADD_PAD_TO_LIST (layer, pad))
3049       return True;
3050     DoIt (True, AndDraw);
3051     /* print all found connections */
3052     PrintPadConnections (layer, FP, True);
3053     PrintPadConnections (layer ==
3054                          (COMPONENT_LAYER ? SOLDER_LAYER : COMPONENT_LAYER),
3055                          FP, False);
3056     PrintPinConnections (FP, False);
3057     fputs ("\t}\n", FP);
3058     if (PrepareNextLoop (FP))
3059       return (True);
3060   }
3061   END_LOOP;
3062   fputs ("}\n\n", FP);
3063   return (False);
3064 }
3065
3066 /* ---------------------------------------------------------------------------
3067  * draws all new connections which have been found since the
3068  * routine was called the last time
3069  */
3070 static void
3071 DrawNewConnections (void)
3072 {
3073   int i;
3074   Cardinal position;
3075
3076   /* decrement 'i' to keep layerstack order */
3077   for (i = max_layer - 1; i != -1; i--)
3078     {
3079       Cardinal layer = LayerStack[i];
3080
3081       if (PCB->Data->Layer[layer].On)
3082         {
3083           /* draw all new lines */
3084           position = LineList[layer].DrawLocation;
3085           for (; position < LineList[layer].Number; position++)
3086             DrawLine (LAYER_PTR (layer), LINELIST_ENTRY (layer, position), 0);
3087           LineList[layer].DrawLocation = LineList[layer].Number;
3088
3089           /* draw all new arcs */
3090           position = ArcList[layer].DrawLocation;
3091           for (; position < ArcList[layer].Number; position++)
3092             DrawArc (LAYER_PTR (layer), ARCLIST_ENTRY (layer, position), 0);
3093           ArcList[layer].DrawLocation = ArcList[layer].Number;
3094
3095           /* draw all new polygons */
3096           position = PolygonList[layer].DrawLocation;
3097           for (; position < PolygonList[layer].Number; position++)
3098             DrawPolygon
3099               (LAYER_PTR (layer), POLYGONLIST_ENTRY (layer, position), 0);
3100           PolygonList[layer].DrawLocation = PolygonList[layer].Number;
3101         }
3102     }
3103
3104   /* draw all new pads */
3105   if (PCB->PinOn)
3106     for (i = 0; i < 2; i++)
3107       {
3108         position = PadList[i].DrawLocation;
3109
3110         for (; position < PadList[i].Number; position++)
3111           DrawPad (PADLIST_ENTRY (i, position), 0);
3112         PadList[i].DrawLocation = PadList[i].Number;
3113       }
3114
3115   /* draw all new PVs; 'PVList' holds a list of pointers to the
3116    * sorted array pointers to PV data
3117    */
3118   while (PVList.DrawLocation < PVList.Number)
3119     {
3120       PinTypePtr pv = PVLIST_ENTRY (PVList.DrawLocation);
3121
3122       if (TEST_FLAG (PINFLAG, pv))
3123         {
3124           if (PCB->PinOn)
3125             DrawPin (pv, 0);
3126         }
3127       else if (PCB->ViaOn)
3128         DrawVia (pv, 0);
3129       PVList.DrawLocation++;
3130     }
3131   /* draw the new rat-lines */
3132   if (PCB->RatOn)
3133     {
3134       position = RatList.DrawLocation;
3135       for (; position < RatList.Number; position++)
3136         DrawRat (RATLIST_ENTRY (position), 0);
3137       RatList.DrawLocation = RatList.Number;
3138     }
3139 }
3140
3141 /* ---------------------------------------------------------------------------
3142  * find all connections to pins within one element
3143  */
3144 void
3145 LookupElementConnections (ElementTypePtr Element, FILE * FP)
3146 {
3147   /* reset all currently marked connections */
3148   User = True;
3149   TheFlag = FOUNDFLAG;
3150   ResetConnections (True);
3151   InitConnectionLookup ();
3152   PrintElementConnections (Element, FP, True);
3153   SetChangedFlag (True);
3154   if (Settings.RingBellWhenFinished)
3155     gui->beep ();
3156   FreeConnectionLookupMemory ();
3157   IncrementUndoSerialNumber ();
3158   User = False;
3159   Draw ();
3160 }
3161
3162 /* ---------------------------------------------------------------------------
3163  * find all connections to pins of all element
3164  */
3165 void
3166 LookupConnectionsToAllElements (FILE * FP)
3167 {
3168   /* reset all currently marked connections */
3169   User = False;
3170   TheFlag = FOUNDFLAG;
3171   ResetConnections (False);
3172   InitConnectionLookup ();
3173
3174   ELEMENT_LOOP (PCB->Data);
3175   {
3176     /* break if abort dialog returned True */
3177     if (PrintElementConnections (element, FP, False))
3178       break;
3179     SEPARATE (FP);
3180     if (Settings.ResetAfterElement && n != 1)
3181       ResetConnections (False);
3182   }
3183   END_LOOP;
3184   if (Settings.RingBellWhenFinished)
3185     gui->beep ();
3186   ResetConnections (False);
3187   FreeConnectionLookupMemory ();
3188   ClearAndRedrawOutput ();
3189 }
3190
3191 /*---------------------------------------------------------------------------
3192  * add the starting object to the list of found objects
3193  */
3194 static Boolean
3195 ListStart (int type, void *ptr1, void *ptr2, void *ptr3)
3196 {
3197   DumpList ();
3198   switch (type)
3199     {
3200     case PIN_TYPE:
3201     case VIA_TYPE:
3202       {
3203         if (ADD_PV_TO_LIST ((PinTypePtr) ptr2))
3204           return True;
3205         break;
3206       }
3207
3208     case RATLINE_TYPE:
3209       {
3210         if (ADD_RAT_TO_LIST ((RatTypePtr) ptr1))
3211           return True;
3212         break;
3213       }
3214
3215     case LINE_TYPE:
3216       {
3217         int layer = GetLayerNumber (PCB->Data,
3218                                     (LayerTypePtr) ptr1);
3219
3220         if (ADD_LINE_TO_LIST (layer, (LineTypePtr) ptr2))
3221           return True;
3222         break;
3223       }
3224
3225     case ARC_TYPE:
3226       {
3227         int layer = GetLayerNumber (PCB->Data,
3228                                     (LayerTypePtr) ptr1);
3229
3230         if (ADD_ARC_TO_LIST (layer, (ArcTypePtr) ptr2))
3231           return True;
3232         break;
3233       }
3234
3235     case POLYGON_TYPE:
3236       {
3237         int layer = GetLayerNumber (PCB->Data,
3238                                     (LayerTypePtr) ptr1);
3239
3240         if (ADD_POLYGON_TO_LIST (layer, (PolygonTypePtr) ptr2))
3241           return True;
3242         break;
3243       }
3244
3245     case PAD_TYPE:
3246       {
3247         PadTypePtr pad = (PadTypePtr) ptr2;
3248         if (ADD_PAD_TO_LIST
3249             (TEST_FLAG
3250              (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER, pad))
3251           return True;
3252         break;
3253       }
3254     }
3255   return (False);
3256 }
3257
3258
3259 /* ---------------------------------------------------------------------------
3260  * looks up all connections from the object at the given coordinates
3261  * the TheFlag (normally 'FOUNDFLAG') is set for all objects found
3262  * the objects are re-drawn if AndDraw is true
3263  * also the action is marked as undoable if AndDraw is true
3264  */
3265 void
3266 LookupConnection (LocationType X, LocationType Y, Boolean AndDraw,
3267                   BDimension Range, int which_flag)
3268 {
3269   void *ptr1, *ptr2, *ptr3;
3270   char *name;
3271   int type;
3272
3273   /* check if there are any pins or pads at that position */
3274
3275
3276   type
3277     = SearchObjectByLocation (LOOKUP_FIRST, &ptr1, &ptr2, &ptr3, X, Y, Range);
3278   if (type == NO_TYPE)
3279     {
3280       type
3281         =
3282         SearchObjectByLocation
3283         (LOOKUP_MORE, &ptr1, &ptr2, &ptr3, X, Y, Range);
3284       if (type == NO_TYPE)
3285         return;
3286       if (type & SILK_TYPE)
3287         {
3288           int laynum = GetLayerNumber (PCB->Data,
3289                                        (LayerTypePtr) ptr1);
3290
3291           /* don't mess with silk objects! */
3292           if (laynum >= max_layer)
3293             return;
3294         }
3295     }
3296   else
3297     {
3298       name = ConnectionName (type, ptr1, ptr2);
3299       hid_actionl ("NetlistShow", name, NULL);
3300     }
3301
3302   TheFlag = which_flag;
3303   User = AndDraw;
3304   InitConnectionLookup ();
3305
3306   /* now add the object to the appropriate list and start scanning
3307    * This is step (1) from the description
3308    */
3309   ListStart (type, ptr1, ptr2, ptr3);
3310   DoIt (True, AndDraw);
3311   if (User)
3312     IncrementUndoSerialNumber ();
3313   User = False;
3314
3315   /* we are done */
3316   if (AndDraw)
3317     Draw ();
3318   if (AndDraw && Settings.RingBellWhenFinished)
3319     gui->beep ();
3320   FreeConnectionLookupMemory ();
3321 }
3322
3323 /* ---------------------------------------------------------------------------
3324  * find connections for rats nesting
3325  * assumes InitConnectionLookup() has already been done
3326  */
3327 void
3328   RatFindHook
3329   (int type, void *ptr1, void *ptr2, void *ptr3, Boolean undo,
3330    Boolean AndRats)
3331 {
3332   User = undo;
3333   DumpList ();
3334   ListStart (type, ptr1, ptr2, ptr3);
3335   DoIt (AndRats, False);
3336   User = False;
3337 }
3338
3339 /* ---------------------------------------------------------------------------
3340  * find all unused pins of all element
3341  */
3342 void
3343 LookupUnusedPins (FILE * FP)
3344 {
3345   /* reset all currently marked connections */
3346   User = True;
3347   SaveUndoSerialNumber ();
3348   ResetConnections (True);
3349   RestoreUndoSerialNumber ();
3350   InitConnectionLookup ();
3351
3352   ELEMENT_LOOP (PCB->Data);
3353   {
3354     /* break if abort dialog returned True;
3355      * passing NULL as filedescriptor discards the normal output
3356      */
3357     if (PrintAndSelectUnusedPinsAndPadsOfElement (element, FP))
3358       break;
3359   }
3360   END_LOOP;
3361
3362   if (Settings.RingBellWhenFinished)
3363     gui->beep ();
3364   FreeConnectionLookupMemory ();
3365   IncrementUndoSerialNumber ();
3366   User = False;
3367   Draw ();
3368 }
3369
3370 /* ---------------------------------------------------------------------------
3371  * resets all used flags of pins and vias
3372  */
3373 void
3374 ResetFoundPinsViasAndPads (Boolean AndDraw)
3375 {
3376   Boolean change = False;
3377
3378
3379   VIA_LOOP (PCB->Data);
3380   {
3381     if (TEST_FLAG (TheFlag, via))
3382       {
3383         if (AndDraw)
3384           AddObjectToFlagUndoList (VIA_TYPE, via, via, via);
3385         CLEAR_FLAG (TheFlag, via);
3386         if (AndDraw)
3387           DrawVia (via, 0);
3388         change = True;
3389       }
3390   }
3391   END_LOOP;
3392   ELEMENT_LOOP (PCB->Data);
3393   {
3394     PIN_LOOP (element);
3395     {
3396       if (TEST_FLAG (TheFlag, pin))
3397         {
3398           if (AndDraw)
3399             AddObjectToFlagUndoList (PIN_TYPE, element, pin, pin);
3400           CLEAR_FLAG (TheFlag, pin);
3401           if (AndDraw)
3402             DrawPin (pin, 0);
3403           change = True;
3404         }
3405     }
3406     END_LOOP;
3407     PAD_LOOP (element);
3408     {
3409       if (TEST_FLAG (TheFlag, pad))
3410         {
3411           if (AndDraw)
3412             AddObjectToFlagUndoList (PAD_TYPE, element, pad, pad);
3413           CLEAR_FLAG (TheFlag, pad);
3414           if (AndDraw)
3415             DrawPad (pad, 0);
3416           change = True;
3417         }
3418     }
3419     END_LOOP;
3420   }
3421   END_LOOP;
3422   if (change)
3423     {
3424       SetChangedFlag (True);
3425       if (AndDraw)
3426         {
3427           IncrementUndoSerialNumber ();
3428           Draw ();
3429         }
3430     }
3431 }
3432
3433 /* ---------------------------------------------------------------------------
3434  * resets all used flags of LOs
3435  */
3436 void
3437 ResetFoundLinesAndPolygons (Boolean AndDraw)
3438 {
3439   Boolean change = False;
3440
3441
3442   RAT_LOOP (PCB->Data);
3443   {
3444     if (TEST_FLAG (TheFlag, line))
3445       {
3446         if (AndDraw)
3447           AddObjectToFlagUndoList (RATLINE_TYPE, line, line, line);
3448         CLEAR_FLAG (TheFlag, line);
3449         if (AndDraw)
3450           DrawRat (line, 0);
3451         change = True;
3452       }
3453   }
3454   END_LOOP;
3455   COPPERLINE_LOOP (PCB->Data);
3456   {
3457     if (TEST_FLAG (TheFlag, line))
3458       {
3459         if (AndDraw)
3460           AddObjectToFlagUndoList (LINE_TYPE, layer, line, line);
3461         CLEAR_FLAG (TheFlag, line);
3462         if (AndDraw)
3463           DrawLine (layer, line, 0);
3464         change = True;
3465       }
3466   }
3467   ENDALL_LOOP;
3468   COPPERARC_LOOP (PCB->Data);
3469   {
3470     if (TEST_FLAG (TheFlag, arc))
3471       {
3472         if (AndDraw)
3473           AddObjectToFlagUndoList (ARC_TYPE, layer, arc, arc);
3474         CLEAR_FLAG (TheFlag, arc);
3475         if (AndDraw)
3476           DrawArc (layer, arc, 0);
3477         change = True;
3478       }
3479   }
3480   ENDALL_LOOP;
3481   COPPERPOLYGON_LOOP (PCB->Data);
3482   {
3483     if (TEST_FLAG (TheFlag, polygon))
3484       {
3485         if (AndDraw)
3486           AddObjectToFlagUndoList (POLYGON_TYPE, layer, polygon, polygon);
3487         CLEAR_FLAG (TheFlag, polygon);
3488         if (AndDraw)
3489           DrawPolygon (layer, polygon, 0);
3490         change = True;
3491       }
3492   }
3493   ENDALL_LOOP;
3494   if (change)
3495     {
3496       SetChangedFlag (True);
3497       if (AndDraw)
3498         {
3499           IncrementUndoSerialNumber ();
3500           Draw ();
3501         }
3502     }
3503 }
3504
3505 /* ---------------------------------------------------------------------------
3506  * resets all found connections
3507  */
3508 static void
3509 ResetConnections (Boolean AndDraw)
3510 {
3511   if (AndDraw)
3512     SaveUndoSerialNumber ();
3513   ResetFoundPinsViasAndPads (AndDraw);
3514   if (AndDraw)
3515     RestoreUndoSerialNumber ();
3516   ResetFoundLinesAndPolygons (AndDraw);
3517 }
3518
3519 /*----------------------------------------------------------------------------
3520  * Dumps the list contents
3521  */
3522 static void
3523 DumpList (void)
3524 {
3525   Cardinal i;
3526
3527   for (i = 0; i < 2; i++)
3528     {
3529       PadList[i].Number = 0;
3530       PadList[i].Location = 0;
3531       PadList[i].DrawLocation = 0;
3532     }
3533
3534   PVList.Number = 0;
3535   PVList.Location = 0;
3536
3537   for (i = 0; i < max_layer; i++)
3538     {
3539       LineList[i].Location = 0;
3540       LineList[i].DrawLocation = 0;
3541       LineList[i].Number = 0;
3542       ArcList[i].Location = 0;
3543       ArcList[i].DrawLocation = 0;
3544       ArcList[i].Number = 0;
3545       PolygonList[i].Location = 0;
3546       PolygonList[i].DrawLocation = 0;
3547       PolygonList[i].Number = 0;
3548     }
3549   RatList.Number = 0;
3550   RatList.Location = 0;
3551   RatList.DrawLocation = 0;
3552 }
3553
3554 /*-----------------------------------------------------------------------------
3555  * Check for DRC violations on a single net starting from the pad or pin
3556  * sees if the connectivity changes when everything is bloated, or shrunk
3557  */
3558 static Boolean
3559 DRCFind (int What, void *ptr1, void *ptr2, void *ptr3)
3560 {
3561   LocationType x, y;
3562   int object_count;
3563   long int *object_id_list;
3564   int *object_type_list;
3565   DrcViolationType *violation;
3566
3567   if (PCB->Shrink != 0)
3568     {
3569       Bloat = -PCB->Shrink;
3570       fBloat = (float) -PCB->Shrink;
3571       TheFlag = DRCFLAG | SELECTEDFLAG;
3572       ListStart (What, ptr1, ptr2, ptr3);
3573       DoIt (True, False);
3574       /* ok now the shrunk net has the SELECTEDFLAG set */
3575       DumpList ();
3576       TheFlag = FOUNDFLAG;
3577       ListStart (What, ptr1, ptr2, ptr3);
3578       Bloat = 0;
3579       fBloat = 0.0;
3580       drc = True;               /* abort the search if we find anything not already found */
3581       if (DoIt (True, False))
3582         {
3583           DumpList ();
3584           /* make the flag changes undoable */
3585           TheFlag = FOUNDFLAG | SELECTEDFLAG;
3586           ResetConnections (False);
3587           User = True;
3588           drc = False;
3589           Bloat = -PCB->Shrink;
3590           fBloat = (float) -PCB->Shrink;
3591           TheFlag = SELECTEDFLAG;
3592           RestoreUndoSerialNumber ();
3593           ListStart (What, ptr1, ptr2, ptr3);
3594           DoIt (True, True);
3595           DumpList ();
3596           ListStart (What, ptr1, ptr2, ptr3);
3597           TheFlag = FOUNDFLAG;
3598           Bloat = 0;
3599           fBloat = 0.0;
3600           drc = True;
3601           DoIt (True, True);
3602           DumpList ();
3603           User = False;
3604           drc = False;
3605           drcerr_count++;
3606           LocateError (&x, &y);
3607           BuildObjectList (&object_count, &object_id_list, &object_type_list);
3608           violation = pcb_drc_violation_new (_("Potential for broken trace"),
3609                                              _("Insufficient overlap between objects can lead to broken tracks\n"
3610                                                "due to registration errors with old wheel style photo-plotters."),
3611                                              x, y,
3612                                              0,     /* ANGLE OF ERROR UNKNOWN */
3613                                              FALSE, /* MEASUREMENT OF ERROR UNKNOWN */
3614                                              0,     /* MAGNITUDE OF ERROR UNKNOWN */
3615                                              LENGTH_TO_HUMAN(PCB->Shrink),
3616                                              LENGTH_DIGITS,
3617                                              LENGTH_UNITS_STRING,
3618                                              object_count,
3619                                              object_id_list,
3620                                              object_type_list);
3621           append_drc_violation (violation);
3622           pcb_drc_violation_free (violation);
3623           free (object_id_list);
3624           free (object_type_list);
3625
3626           if (!throw_drc_dialog())
3627             return (True);
3628           IncrementUndoSerialNumber ();
3629           Undo (True);
3630         }
3631       DumpList ();
3632     }
3633   /* now check the bloated condition */
3634   drc = False;
3635   ResetConnections (False);
3636   TheFlag = FOUNDFLAG;
3637   ListStart (What, ptr1, ptr2, ptr3);
3638   Bloat = PCB->Bloat;
3639   fBloat = (float) PCB->Bloat;
3640   drc = True;
3641   while (DoIt (True, False))
3642     {
3643       DumpList ();
3644       /* make the flag changes undoable */
3645       TheFlag = FOUNDFLAG | SELECTEDFLAG;
3646       ResetConnections (False);
3647       User = True;
3648       drc = False;
3649       Bloat = 0;
3650       fBloat = 0.0;
3651       RestoreUndoSerialNumber ();
3652       TheFlag = SELECTEDFLAG;
3653       ListStart (What, ptr1, ptr2, ptr3);
3654       DoIt (True, True);
3655       DumpList ();
3656       TheFlag = FOUNDFLAG;
3657       ListStart (What, ptr1, ptr2, ptr3);
3658       Bloat = PCB->Bloat;
3659       fBloat = (float) PCB->Bloat;
3660       drc = True;
3661       DoIt (True, True);
3662       DumpList ();
3663       drcerr_count++;
3664       LocateError (&x, &y);
3665       BuildObjectList (&object_count, &object_id_list, &object_type_list);
3666       violation = pcb_drc_violation_new (_("Copper areas too close"),
3667                                          _("Circuits that are too close may bridge during imaging, etching,\n"
3668                                            "plating, or soldering processes resulting in a direct short."),
3669                                          x, y,
3670                                          0,     /* ANGLE OF ERROR UNKNOWN */
3671                                          FALSE, /* MEASUREMENT OF ERROR UNKNOWN */
3672                                          0,     /* MAGNITUDE OF ERROR UNKNOWN */
3673                                          LENGTH_TO_HUMAN(PCB->Bloat),
3674                                          LENGTH_DIGITS,
3675                                          LENGTH_UNITS_STRING,
3676                                          object_count,
3677                                          object_id_list,
3678                                          object_type_list);
3679       append_drc_violation (violation);
3680       pcb_drc_violation_free (violation);
3681       free (object_id_list);
3682       free (object_type_list);
3683       User = False;
3684       drc = False;
3685       if (!throw_drc_dialog())
3686         return (True);
3687       IncrementUndoSerialNumber ();
3688       Undo (True);
3689       /* highlight the rest of the encroaching net so it's not reported again */
3690       TheFlag |= SELECTEDFLAG;
3691       Bloat = 0;
3692       fBloat = 0.0;
3693       ListStart (thing_type, thing_ptr1, thing_ptr2, thing_ptr3);
3694       DoIt (True, True);
3695       DumpList ();
3696       drc = True;
3697       Bloat = PCB->Bloat;
3698       fBloat = (float) PCB->Bloat;
3699       ListStart (What, ptr1, ptr2, ptr3);
3700     }
3701   drc = False;
3702   DumpList ();
3703   TheFlag = FOUNDFLAG | SELECTEDFLAG;
3704   ResetConnections (False);
3705   return (False);
3706 }
3707
3708 /*----------------------------------------------------------------------------
3709  * set up a temporary flag to use
3710  */
3711 void
3712 SaveFindFlag (int NewFlag)
3713 {
3714   OldFlag = TheFlag;
3715   TheFlag = NewFlag;
3716 }
3717
3718 /*----------------------------------------------------------------------------
3719  * restore flag
3720  */
3721 void
3722 RestoreFindFlag (void)
3723 {
3724   TheFlag = OldFlag;
3725 }
3726
3727 /* DRC clearance callback */
3728
3729 static int
3730 drc_callback (DataTypePtr data, LayerTypePtr layer, PolygonTypePtr polygon,
3731               int type, void *ptr1, void *ptr2)
3732 {
3733   char *message;
3734   LocationType x, y;
3735   int object_count;
3736   long int *object_id_list;
3737   int *object_type_list;
3738   DrcViolationType *violation;
3739
3740   LineTypePtr line = (LineTypePtr) ptr2;
3741   ArcTypePtr arc = (ArcTypePtr) ptr2;
3742   PinTypePtr pin = (PinTypePtr) ptr2;
3743   PadTypePtr pad = (PadTypePtr) ptr2;
3744
3745   thing_type = type;
3746   thing_ptr1 = ptr1;
3747   thing_ptr2 = ptr2;
3748   thing_ptr3 = ptr2;
3749   switch (type)
3750     {
3751     case LINE_TYPE:
3752       if (line->Clearance < 2 * PCB->Bloat)
3753         {
3754           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3755           SET_FLAG (TheFlag, line);
3756           message = _("Line with insufficient clearance inside polygon\n");
3757           goto doIsBad;
3758         }
3759       break;
3760     case ARC_TYPE:
3761       if (arc->Clearance < 2 * PCB->Bloat)
3762         {
3763           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3764           SET_FLAG (TheFlag, arc);
3765           message = _("Arc with insufficient clearance inside polygon\n");
3766           goto doIsBad;
3767         }
3768       break;
3769     case PAD_TYPE:
3770       if (pad->Clearance < 2 * PCB->Bloat)
3771         if (IsPadInPolygon(pad,polygon))
3772           {
3773             AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3774             SET_FLAG (TheFlag, pad);
3775             message = _("Pad with insufficient clearance inside polygon\n");
3776             goto doIsBad;
3777           }
3778       break;
3779     case PIN_TYPE:
3780       if (pin->Clearance < 2 * PCB->Bloat)
3781         {
3782           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3783           SET_FLAG (TheFlag, pin);
3784           message = _("Pin with insufficient clearance inside polygon\n");
3785           goto doIsBad;
3786         }
3787       break;
3788     case VIA_TYPE:
3789       if (pin->Clearance && pin->Clearance < 2 * PCB->Bloat)
3790         {
3791           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3792           SET_FLAG (TheFlag, pin);
3793           message = _("Via with insufficient clearance inside polygon\n");
3794           goto doIsBad;
3795         }
3796       break;
3797     default:
3798       Message ("hace: Bad Plow object in callback\n");
3799     }
3800   return 0;
3801
3802 doIsBad:
3803   AddObjectToFlagUndoList (POLYGON_TYPE, layer, polygon, polygon);
3804   SET_FLAG (FOUNDFLAG, polygon);
3805   DrawPolygon (layer, polygon, 0);
3806   DrawObject (type, ptr1, ptr2, 0);
3807   drcerr_count++;
3808   LocateError (&x, &y);
3809   BuildObjectList (&object_count, &object_id_list, &object_type_list);
3810   violation = pcb_drc_violation_new (message,
3811                                      _("Circuits that are too close may bridge during imaging, etching,\n"
3812                                        "plating, or soldering processes resulting in a direct short."),
3813                                      x, y,
3814                                      0,     /* ANGLE OF ERROR UNKNOWN */
3815                                      FALSE, /* MEASUREMENT OF ERROR UNKNOWN */
3816                                      0,     /* MAGNITUDE OF ERROR UNKNOWN */
3817                                      LENGTH_TO_HUMAN(PCB->Bloat),
3818                                      LENGTH_DIGITS,
3819                                      LENGTH_UNITS_STRING,
3820                                      object_count,
3821                                      object_id_list,
3822                                      object_type_list);
3823   append_drc_violation (violation);
3824   pcb_drc_violation_free (violation);
3825   free (object_id_list);
3826   free (object_type_list);
3827   if (!throw_drc_dialog())
3828     {
3829       IsBad = True;
3830       return 1;
3831     }
3832   IncrementUndoSerialNumber ();
3833   Undo (True);
3834   return 0;
3835 }
3836
3837 /*-----------------------------------------------------------------------------
3838  * Check for DRC violations
3839  * see if the connectivity changes when everything is bloated, or shrunk
3840  */
3841 int
3842 DRCAll (void)
3843 {
3844   LocationType x, y;
3845   int object_count;
3846   long int *object_id_list;
3847   int *object_type_list;
3848   DrcViolationType *violation;
3849   int tmpcnt;
3850   int nopastecnt = 0;
3851
3852   reset_drc_dialog_message();
3853
3854   IsBad = False;
3855   drcerr_count = 0;
3856   SaveStackAndVisibility ();
3857   ResetStackAndVisibility ();
3858   hid_action ("LayersChanged");
3859   InitConnectionLookup ();
3860
3861   TheFlag = FOUNDFLAG | DRCFLAG | SELECTEDFLAG;
3862
3863   ResetConnections (True);
3864
3865   User = False;
3866
3867   ELEMENT_LOOP (PCB->Data);
3868   {
3869     PIN_LOOP (element);
3870     {
3871       if (!TEST_FLAG (DRCFLAG, pin)
3872           && DRCFind (PIN_TYPE, (void *) element, (void *) pin, (void *) pin))
3873         {
3874           IsBad = True;
3875           break;
3876         }
3877     }
3878     END_LOOP;
3879     if (IsBad)
3880       break;
3881     PAD_LOOP (element);
3882     {
3883
3884       /* count up how many pads have no solderpaste openings */
3885       if (TEST_FLAG (NOPASTEFLAG, pad))
3886         nopastecnt++;
3887
3888       if (!TEST_FLAG (DRCFLAG, pad)
3889           && DRCFind (PAD_TYPE, (void *) element, (void *) pad, (void *) pad))
3890         {
3891           IsBad = True;
3892           break;
3893         }
3894     }
3895     END_LOOP;
3896     if (IsBad)
3897       break;
3898   }
3899   END_LOOP;
3900   if (!IsBad)
3901     VIA_LOOP (PCB->Data);
3902   {
3903     if (!TEST_FLAG (DRCFLAG, via)
3904         && DRCFind (VIA_TYPE, (void *) via, (void *) via, (void *) via))
3905       {
3906         IsBad = True;
3907         break;
3908       }
3909   }
3910   END_LOOP;
3911
3912   TheFlag = (IsBad) ? DRCFLAG : (FOUNDFLAG | DRCFLAG | SELECTEDFLAG);
3913   ResetConnections (False);
3914   TheFlag = SELECTEDFLAG;
3915   /* check minimum widths and polygon clearances */
3916   if (!IsBad)
3917     {
3918       COPPERLINE_LOOP (PCB->Data);
3919       {
3920         /* check line clearances in polygons */
3921         PlowsPolygon (PCB->Data, LINE_TYPE, layer, line, drc_callback);
3922         if (IsBad)
3923           break;
3924         if (line->Thickness < PCB->minWid)
3925           {
3926             AddObjectToFlagUndoList (LINE_TYPE, layer, line, line);
3927             SET_FLAG (TheFlag, line);
3928             DrawLine (layer, line, 0);
3929             drcerr_count++;
3930             SetThing (LINE_TYPE, layer, line, line);
3931             LocateError (&x, &y);
3932             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3933             violation = pcb_drc_violation_new (_("Line width is too thin"),
3934                                                _("Process specifications dictate a minimum feature-width\n"
3935                                                  "that can reliably be reproduced"),
3936                                                x, y,
3937                                                0,    /* ANGLE OF ERROR UNKNOWN */
3938                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3939                                                LENGTH_TO_HUMAN(line->Thickness),
3940                                                LENGTH_TO_HUMAN(PCB->minWid),
3941                                                LENGTH_DIGITS,
3942                                                LENGTH_UNITS_STRING,
3943                                                object_count,
3944                                                object_id_list,
3945                                                object_type_list);
3946             append_drc_violation (violation);
3947             pcb_drc_violation_free (violation);
3948             free (object_id_list);
3949             free (object_type_list);
3950             if (!throw_drc_dialog())
3951               {
3952                 IsBad = True;
3953                 break;
3954               }
3955             IncrementUndoSerialNumber ();
3956             Undo (False);
3957           }
3958       }
3959       ENDALL_LOOP;
3960     }
3961   if (!IsBad)
3962     {
3963       COPPERARC_LOOP (PCB->Data);
3964       {
3965         PlowsPolygon (PCB->Data, ARC_TYPE, layer, arc, drc_callback);
3966         if (IsBad)
3967           break;
3968         if (arc->Thickness < PCB->minWid)
3969           {
3970             AddObjectToFlagUndoList (ARC_TYPE, layer, arc, arc);
3971             SET_FLAG (TheFlag, arc);
3972             DrawArc (layer, arc, 0);
3973             drcerr_count++;
3974             SetThing (ARC_TYPE, layer, arc, arc);
3975             LocateError (&x, &y);
3976             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3977             violation = pcb_drc_violation_new (_("Arc width is too thin"),
3978                                                _("Process specifications dictate a minimum feature-width\n"
3979                                                  "that can reliably be reproduced"),
3980                                                x, y,
3981                                                0,    /* ANGLE OF ERROR UNKNOWN */
3982                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3983                                                LENGTH_TO_HUMAN(arc->Thickness),
3984                                                LENGTH_TO_HUMAN(PCB->minWid),
3985                                                LENGTH_DIGITS,
3986                                                LENGTH_UNITS_STRING,
3987                                                object_count,
3988                                                object_id_list,
3989                                                object_type_list);
3990             append_drc_violation (violation);
3991             pcb_drc_violation_free (violation);
3992             free (object_id_list);
3993             free (object_type_list);
3994             if (!throw_drc_dialog())
3995               {
3996                 IsBad = True;
3997                 break;
3998               }
3999             IncrementUndoSerialNumber ();
4000             Undo (False);
4001           }
4002       }
4003       ENDALL_LOOP;
4004     }
4005   if (!IsBad)
4006     {
4007       ALLPIN_LOOP (PCB->Data);
4008       {
4009         PlowsPolygon (PCB->Data, PIN_TYPE, element, pin, drc_callback);
4010         if (IsBad)
4011           break;
4012         if (!TEST_FLAG (HOLEFLAG, pin) &&
4013             pin->Thickness - pin->DrillingHole < 2 * PCB->minRing)
4014           {
4015             AddObjectToFlagUndoList (PIN_TYPE, element, pin, pin);
4016             SET_FLAG (TheFlag, pin);
4017             DrawPin (pin, 0);
4018             drcerr_count++;
4019             SetThing (PIN_TYPE, element, pin, pin);
4020             LocateError (&x, &y);
4021             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4022             violation = pcb_drc_violation_new (_("Pin annular ring too small"),
4023                                                _("Annular rings that are too small may erode during etching,\n"
4024                                                  "resulting in a broken connection"),
4025                                                x, y,
4026                                                0,    /* ANGLE OF ERROR UNKNOWN */
4027                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4028                                                LENGTH_TO_HUMAN((pin->Thickness - pin->DrillingHole) / 2),
4029                                                LENGTH_TO_HUMAN(PCB->minRing),
4030                                                LENGTH_DIGITS,
4031                                                LENGTH_UNITS_STRING,
4032                                                object_count,
4033                                                object_id_list,
4034                                                object_type_list);
4035             append_drc_violation (violation);
4036             pcb_drc_violation_free (violation);
4037             free (object_id_list);
4038             free (object_type_list);
4039             if (!throw_drc_dialog())
4040               {
4041                 IsBad = True;
4042                 break;
4043               }
4044             IncrementUndoSerialNumber ();
4045             Undo (False);
4046           }
4047         if (pin->DrillingHole < PCB->minDrill)
4048           {
4049             AddObjectToFlagUndoList (PIN_TYPE, element, pin, pin);
4050             SET_FLAG (TheFlag, pin);
4051             DrawPin (pin, 0);
4052             drcerr_count++;
4053             SetThing (PIN_TYPE, element, pin, pin);
4054             LocateError (&x, &y);
4055             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4056             violation = pcb_drc_violation_new (_("Pin drill size is too small"),
4057                                                _("Process rules dictate the minimum drill size which can be used"),
4058                                                x, y,
4059                                                0,    /* ANGLE OF ERROR UNKNOWN */
4060                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4061                                                LENGTH_TO_HUMAN(pin->DrillingHole),
4062                                                LENGTH_TO_HUMAN(PCB->minDrill),
4063                                                LENGTH_DIGITS,
4064                                                LENGTH_UNITS_STRING,
4065                                                object_count,
4066                                                object_id_list,
4067                                                object_type_list);
4068             append_drc_violation (violation);
4069             pcb_drc_violation_free (violation);
4070             free (object_id_list);
4071             free (object_type_list);
4072             if (!throw_drc_dialog())
4073               {
4074                 IsBad = True;
4075                 break;
4076               }
4077             IncrementUndoSerialNumber ();
4078             Undo (False);
4079           }
4080       }
4081       ENDALL_LOOP;
4082     }
4083   if (!IsBad)
4084     {
4085       ALLPAD_LOOP (PCB->Data);
4086       {
4087         PlowsPolygon (PCB->Data, PAD_TYPE, element, pad, drc_callback);
4088         if (IsBad)
4089           break;
4090         if (pad->Thickness < PCB->minWid)
4091           {
4092             AddObjectToFlagUndoList (PAD_TYPE, element, pad, pad);
4093             SET_FLAG (TheFlag, pad);
4094             DrawPad (pad, 0);
4095             drcerr_count++;
4096             SetThing (PAD_TYPE, element, pad, pad);
4097             LocateError (&x, &y);
4098             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4099             violation = pcb_drc_violation_new (_("Pad is too thin"),
4100                                                _("Pads which are too thin may erode during etching,\n"
4101                                                   "resulting in a broken or unreliable connection"),
4102                                                x, y,
4103                                                0,    /* ANGLE OF ERROR UNKNOWN */
4104                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4105                                                LENGTH_TO_HUMAN(pad->Thickness),
4106                                                LENGTH_TO_HUMAN(PCB->minWid),
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       }
4125       ENDALL_LOOP;
4126     }
4127   if (!IsBad)
4128     {
4129       VIA_LOOP (PCB->Data);
4130       {
4131         PlowsPolygon (PCB->Data, VIA_TYPE, via, via, drc_callback);
4132         if (IsBad)
4133           break;
4134         if (!TEST_FLAG (HOLEFLAG, via) &&
4135             via->Thickness - via->DrillingHole < 2 * PCB->minRing)
4136           {
4137             AddObjectToFlagUndoList (VIA_TYPE, via, via, via);
4138             SET_FLAG (TheFlag, via);
4139             DrawVia (via, 0);
4140             drcerr_count++;
4141             SetThing (VIA_TYPE, via, via, via);
4142             LocateError (&x, &y);
4143             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4144             violation = pcb_drc_violation_new (_("Via annular ring too small"),
4145                                                _("Annular rings that are too small may erode during etching,\n"
4146                                                  "resulting in a broken connection"),
4147                                                x, y,
4148                                                0,    /* ANGLE OF ERROR UNKNOWN */
4149                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4150                                                LENGTH_TO_HUMAN((via->Thickness - via->DrillingHole) / 2),
4151                                                LENGTH_TO_HUMAN(PCB->minRing),
4152                                                LENGTH_DIGITS,
4153                                                LENGTH_UNITS_STRING,
4154                                                object_count,
4155                                                object_id_list,
4156                                                object_type_list);
4157             append_drc_violation (violation);
4158             pcb_drc_violation_free (violation);
4159             free (object_id_list);
4160             free (object_type_list);
4161             if (!throw_drc_dialog())
4162               {
4163                 IsBad = True;
4164                 break;
4165               }
4166             IncrementUndoSerialNumber ();
4167             Undo (False);
4168           }
4169         if (via->DrillingHole < PCB->minDrill)
4170           {
4171             AddObjectToFlagUndoList (VIA_TYPE, via, via, via);
4172             SET_FLAG (TheFlag, via);
4173             DrawVia (via, 0);
4174             drcerr_count++;
4175             SetThing (VIA_TYPE, via, via, via);
4176             LocateError (&x, &y);
4177             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4178             violation = pcb_drc_violation_new (_("Via drill size is too small"),
4179                                                _("Process rules dictate the minimum drill size which can be used"),
4180                                                x, y,
4181                                                0,    /* ANGLE OF ERROR UNKNOWN */
4182                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4183                                                LENGTH_TO_HUMAN(via->DrillingHole),
4184                                                LENGTH_TO_HUMAN(PCB->minDrill),
4185                                                LENGTH_DIGITS,
4186                                                LENGTH_UNITS_STRING,
4187                                                object_count,
4188                                                object_id_list,
4189                                                object_type_list);
4190             append_drc_violation (violation);
4191             pcb_drc_violation_free (violation);
4192             free (object_id_list);
4193             free (object_type_list);
4194             if (!throw_drc_dialog())
4195               {
4196                 IsBad = True;
4197                 break;
4198               }
4199             IncrementUndoSerialNumber ();
4200             Undo (False);
4201           }
4202       }
4203       END_LOOP;
4204     }
4205
4206   FreeConnectionLookupMemory ();
4207   TheFlag = FOUNDFLAG;
4208   Bloat = 0;
4209   fBloat = 0.0;
4210
4211   /* check silkscreen minimum widths outside of elements */
4212   /* XXX - need to check text and polygons too! */
4213   TheFlag = SELECTEDFLAG;
4214   if (!IsBad)
4215     {
4216       SILKLINE_LOOP (PCB->Data);
4217       {
4218         if (line->Thickness < PCB->minSlk)
4219           {
4220             SET_FLAG (TheFlag, line);
4221             DrawLine (layer, line, 0);
4222             drcerr_count++;
4223             SetThing (LINE_TYPE, layer, line, line);
4224             LocateError (&x, &y);
4225             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4226             violation = pcb_drc_violation_new (_("Silk line is too thin"),
4227                                                _("Process specifications dictate a minimum silkscreen feature-width\n"
4228                                                  "that can reliably be reproduced"),
4229                                                x, y,
4230                                                0,    /* ANGLE OF ERROR UNKNOWN */
4231                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4232                                                LENGTH_TO_HUMAN(line->Thickness),
4233                                                LENGTH_TO_HUMAN(PCB->minSlk),
4234                                                LENGTH_DIGITS,
4235                                                LENGTH_UNITS_STRING,
4236                                                object_count,
4237                                                object_id_list,
4238                                                object_type_list);
4239             append_drc_violation (violation);
4240             pcb_drc_violation_free (violation);
4241             free (object_id_list);
4242             free (object_type_list);
4243             if (!throw_drc_dialog())
4244               {
4245                 IsBad = True;
4246                 break;
4247               }
4248           }
4249       }
4250       ENDALL_LOOP;
4251     }
4252
4253   /* check silkscreen minimum widths inside of elements */
4254   /* XXX - need to check text and polygons too! */
4255   TheFlag = SELECTEDFLAG;
4256   if (!IsBad)
4257     {
4258       ELEMENT_LOOP (PCB->Data);
4259       {
4260         tmpcnt = 0;
4261         ELEMENTLINE_LOOP (element);
4262         {
4263           if (line->Thickness < PCB->minSlk)
4264             tmpcnt++;
4265         }
4266         END_LOOP;
4267         if (tmpcnt > 0)
4268           {
4269             char *title;
4270             char *name;
4271             char *buffer;
4272             int buflen;
4273
4274             SET_FLAG (TheFlag, element);
4275             DrawElement (element, 0);
4276             drcerr_count++;
4277             SetThing (ELEMENT_TYPE, element, element, element);
4278             LocateError (&x, &y);
4279             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4280
4281             title = _("Element %s has %i silk lines which are too thin");
4282             name = UNKNOWN (NAMEONPCB_NAME (element));
4283
4284             /* -4 is for the %s and %i place-holders */
4285             /* +11 is the max printed length for a 32 bit integer */
4286             /* +1 is for the \0 termination */
4287             buflen = strlen (title) - 4 + strlen (name) + 11 + 1;
4288             buffer = malloc (buflen);
4289             snprintf (buffer, buflen, title, name, tmpcnt);
4290
4291             violation = pcb_drc_violation_new (buffer,
4292                                                _("Process specifications dictate a minimum silkscreen\n"
4293                                                "feature-width that can reliably be reproduced"),
4294                                                x, y,
4295                                                0,    /* ANGLE OF ERROR UNKNOWN */
4296                                                0,    /* MINIMUM OFFENDING WIDTH UNKNOWN */
4297                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4298                                                LENGTH_TO_HUMAN(PCB->minSlk),
4299                                                LENGTH_DIGITS,
4300                                                LENGTH_UNITS_STRING,
4301                                                object_count,
4302                                                object_id_list,
4303                                                object_type_list);
4304             free (buffer);
4305             append_drc_violation (violation);
4306             pcb_drc_violation_free (violation);
4307             free (object_id_list);
4308             free (object_type_list);
4309             if (!throw_drc_dialog())
4310               {
4311                 IsBad = True;
4312                 break;
4313               }
4314           }
4315       }
4316       END_LOOP;
4317     }
4318
4319
4320   if (IsBad)
4321     {
4322       IncrementUndoSerialNumber ();
4323     }
4324
4325
4326   RestoreStackAndVisibility ();
4327   hid_action ("LayersChanged");
4328   gui->invalidate_all ();
4329
4330   if (nopastecnt > 0)
4331     {
4332       Message (_("Warning:  %d pad%s the nopaste flag set.\n"),
4333                nopastecnt,
4334                nopastecnt > 1 ? "s have" : " has");
4335     }
4336   return IsBad ? -drcerr_count : drcerr_count;
4337 }
4338
4339 /*----------------------------------------------------------------------------
4340  * Locate the coordinatates of offending item (thing)
4341  */
4342 static void
4343 LocateError (LocationType *x, LocationType *y)
4344 {
4345   switch (thing_type)
4346     {
4347     case LINE_TYPE:
4348       {
4349         LineTypePtr line = (LineTypePtr) thing_ptr3;
4350         *x = (line->Point1.X + line->Point2.X) / 2;
4351         *y = (line->Point1.Y + line->Point2.Y) / 2;
4352         break;
4353       }
4354     case ARC_TYPE:
4355       {
4356         ArcTypePtr arc = (ArcTypePtr) thing_ptr3;
4357         *x = arc->X;
4358         *y = arc->Y;
4359         break;
4360       }
4361     case POLYGON_TYPE:
4362       {
4363         PolygonTypePtr polygon = (PolygonTypePtr) thing_ptr3;
4364         *x =
4365           (polygon->Clipped->contours->xmin +
4366            polygon->Clipped->contours->xmax) / 2;
4367         *y =
4368           (polygon->Clipped->contours->ymin +
4369            polygon->Clipped->contours->ymax) / 2;
4370         break;
4371       }
4372     case PIN_TYPE:
4373     case VIA_TYPE:
4374       {
4375         PinTypePtr pin = (PinTypePtr) thing_ptr3;
4376         *x = pin->X;
4377         *y = pin->Y;
4378         break;
4379       }
4380     case PAD_TYPE:
4381       {
4382         PadTypePtr pad = (PadTypePtr) thing_ptr3;
4383         *x = (pad->Point1.X + pad->Point2.X) / 2;
4384         *y = (pad->Point1.Y + pad->Point2.Y) / 2;
4385         break;
4386       }
4387     case ELEMENT_TYPE:
4388       {
4389         ElementTypePtr element = (ElementTypePtr) thing_ptr3;
4390         *x = element->MarkX;
4391         *y = element->MarkY;
4392         break;
4393       }
4394     default:
4395       return;
4396     }
4397 }
4398
4399
4400 /*----------------------------------------------------------------------------
4401  * Build a list of the of offending items by ID. (Currently just "thing")
4402  */
4403 static void
4404 BuildObjectList (int *object_count, long int **object_id_list, int **object_type_list)
4405 {
4406   *object_count = 0;
4407   *object_id_list = NULL;
4408
4409   switch (thing_type)
4410     {
4411     case LINE_TYPE:
4412     case ARC_TYPE:
4413     case POLYGON_TYPE:
4414     case PIN_TYPE:
4415     case VIA_TYPE:
4416     case PAD_TYPE:
4417     case ELEMENT_TYPE:
4418       *object_count = 1;
4419       *object_id_list = malloc (sizeof (long int));
4420       *object_type_list = malloc (sizeof (int));
4421       **object_id_list = ((AnyObjectType *)thing_ptr3)->ID;
4422       **object_type_list = thing_type;
4423       return;
4424
4425     default:
4426       return;
4427     }
4428 }
4429
4430
4431 /*----------------------------------------------------------------------------
4432  * center the display to show the offending item (thing)
4433  */
4434 static void
4435 GotoError (void)
4436 {
4437   LocationType X, Y;
4438
4439   LocateError (&X, &Y);
4440
4441   switch (thing_type)
4442     {
4443     case LINE_TYPE:
4444     case ARC_TYPE:
4445     case POLYGON_TYPE:
4446       ChangeGroupVisibility (GetLayerNumber
4447                              (PCB->Data, (LayerTypePtr) thing_ptr1), True,
4448                              True);
4449     }
4450   CenterDisplay (X, Y, False);
4451 }
4452
4453 void
4454 InitConnectionLookup (void)
4455 {
4456   InitComponentLookup ();
4457   InitLayoutLookup ();
4458 }
4459
4460 void
4461 FreeConnectionLookupMemory (void)
4462 {
4463   FreeComponentLookupMemory ();
4464   FreeLayoutLookupMemory ();
4465 }