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) && !TEST_FLAG (CLEARPOLYFLAG, polygon))
2291     {
2292       if (IsPadInPolygon (&i->pad, polygon) &&
2293           ADD_POLYGON_TO_LIST (i->layer, polygon))
2294         longjmp (i->env, 1);
2295     }
2296   return 0;
2297 }
2298
2299 static int
2300 LOCtoPadRat_callback (const BoxType * b, void *cl)
2301 {
2302   RatTypePtr rat = (RatTypePtr) b;
2303   struct lo_info *i = (struct lo_info *) cl;
2304
2305   if (!TEST_FLAG (TheFlag, rat))
2306     {
2307       if (rat->group1 == i->layer &&
2308           ((rat->Point1.X == i->pad.Point1.X
2309             && rat->Point1.Y == i->pad.Point1.Y)
2310            || (rat->Point1.X == i->pad.Point2.X
2311                && rat->Point1.Y == i->pad.Point2.Y)))
2312         {
2313           if (ADD_RAT_TO_LIST (rat))
2314             longjmp (i->env, 1);
2315         }
2316       else if (rat->group2 == i->layer &&
2317                ((rat->Point2.X == i->pad.Point1.X
2318                  && rat->Point2.Y == i->pad.Point1.Y)
2319                 || (rat->Point2.X == i->pad.Point2.X
2320                     && rat->Point2.Y == i->pad.Point2.Y)))
2321         {
2322           if (ADD_RAT_TO_LIST (rat))
2323             longjmp (i->env, 1);
2324         }
2325     }
2326   return 0;
2327 }
2328
2329 static int
2330 LOCtoPadPad_callback (const BoxType * b, void *cl)
2331 {
2332   PadTypePtr pad = (PadTypePtr) b;
2333   struct lo_info *i = (struct lo_info *) cl;
2334
2335   if (!TEST_FLAG (TheFlag, pad) && i->layer ==
2336       (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER)
2337       && PadPadIntersect (pad, &i->pad) && ADD_PAD_TO_LIST (i->layer, pad))
2338     longjmp (i->env, 1);
2339   return 0;
2340 }
2341
2342 /* ---------------------------------------------------------------------------
2343  * searches all LOs that are connected to the given pad on the given
2344  * layergroup. All found connections are added to the list
2345  */
2346 static Boolean
2347 LookupLOConnectionsToPad (PadTypePtr Pad, Cardinal LayerGroup)
2348 {
2349   Cardinal entry;
2350   struct lo_info info;
2351
2352   if (!TEST_FLAG (SQUAREFLAG, Pad))
2353     return (LookupLOConnectionsToLine ((LineTypePtr) Pad, LayerGroup, False));
2354
2355   info.pad = *Pad;
2356   EXPAND_BOUNDS (&info.pad);
2357   /* add the new rat lines */
2358   info.layer = LayerGroup;
2359   if (setjmp (info.env) == 0)
2360     r_search (PCB->Data->rat_tree, &info.pad.BoundingBox, NULL,
2361               LOCtoPadRat_callback, &info);
2362   else
2363     return True;
2364
2365   /* loop over all layers of the group */
2366   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2367     {
2368       Cardinal layer;
2369
2370       layer = PCB->LayerGroups.Entries[LayerGroup][entry];
2371       /* handle normal layers */
2372       if (layer < max_layer)
2373         {
2374           info.layer = layer;
2375           /* add lines */
2376           if (setjmp (info.env) == 0)
2377             r_search (LAYER_PTR (layer)->line_tree, &info.pad.BoundingBox,
2378                       NULL, LOCtoPadLine_callback, &info);
2379           else
2380             return True;
2381           /* add arcs */
2382           if (setjmp (info.env) == 0)
2383             r_search (LAYER_PTR (layer)->arc_tree, &info.pad.BoundingBox,
2384                       NULL, LOCtoPadArc_callback, &info);
2385           else
2386             return True;
2387           /* add polygons */
2388           if (setjmp (info.env) == 0)
2389             r_search (LAYER_PTR (layer)->polygon_tree, &info.pad.BoundingBox,
2390                       NULL, LOCtoPadPoly_callback, &info);
2391           else
2392             return True;
2393         }
2394       else
2395         {
2396           /* handle special 'pad' layers */
2397           info.layer = layer - max_layer;
2398           if (setjmp (info.env) == 0)
2399             r_search (PCB->Data->pad_tree, (BoxType *) & info.pad, NULL,
2400                       LOCtoPadPad_callback, &info);
2401           else
2402             return True;
2403         }
2404
2405     }
2406   return (False);
2407 }
2408
2409 static int
2410 LOCtoPolyLine_callback (const BoxType * b, void *cl)
2411 {
2412   LineTypePtr line = (LineTypePtr) b;
2413   struct lo_info *i = (struct lo_info *) cl;
2414
2415   if (!TEST_FLAG (TheFlag, line) && IsLineInPolygon (line, &i->polygon))
2416     {
2417       if (ADD_LINE_TO_LIST (i->layer, line))
2418         longjmp (i->env, 1);
2419     }
2420   return 0;
2421 }
2422
2423 static int
2424 LOCtoPolyArc_callback (const BoxType * b, void *cl)
2425 {
2426   ArcTypePtr arc = (ArcTypePtr) b;
2427   struct lo_info *i = (struct lo_info *) cl;
2428
2429   if (!arc->Thickness)
2430     return 0;
2431   if (!TEST_FLAG (TheFlag, arc) && IsArcInPolygon (arc, &i->polygon))
2432     {
2433       if (ADD_ARC_TO_LIST (i->layer, arc))
2434         longjmp (i->env, 1);
2435     }
2436   return 0;
2437 }
2438
2439 static int
2440 LOCtoPolyPad_callback (const BoxType * b, void *cl)
2441 {
2442   PadTypePtr pad = (PadTypePtr) b;
2443   struct lo_info *i = (struct lo_info *) cl;
2444
2445   if (!TEST_FLAG (TheFlag, pad) && i->layer ==
2446       (TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER)
2447       && IsPadInPolygon (pad, &i->polygon))
2448     {
2449       if (ADD_PAD_TO_LIST (i->layer, pad))
2450         longjmp (i->env, 1);
2451     }
2452   return 0;
2453 }
2454
2455 static int
2456 LOCtoPolyRat_callback (const BoxType * b, void *cl)
2457 {
2458   RatTypePtr rat = (RatTypePtr) b;
2459   struct lo_info *i = (struct lo_info *) cl;
2460
2461   if (!TEST_FLAG (TheFlag, rat))
2462     {
2463       if ((rat->Point1.X == (i->polygon.Clipped->contours->head.point[0]) &&
2464            rat->Point1.Y == (i->polygon.Clipped->contours->head.point[1]) &&
2465            rat->group1 == i->layer) ||
2466           (rat->Point2.X == (i->polygon.Clipped->contours->head.point[0]) &&
2467            rat->Point2.Y == (i->polygon.Clipped->contours->head.point[1]) &&
2468            rat->group2 == i->layer))
2469         if (ADD_RAT_TO_LIST (rat))
2470           longjmp (i->env, 1);
2471     }
2472   return 0;
2473 }
2474
2475
2476 /* ---------------------------------------------------------------------------
2477  * looks up LOs that are connected to the given polygon
2478  * on the given layergroup. All found connections are added to the list
2479  */
2480 static Boolean
2481 LookupLOConnectionsToPolygon (PolygonTypePtr Polygon, Cardinal LayerGroup)
2482 {
2483   Cardinal entry;
2484   struct lo_info info;
2485
2486   if (!Polygon->Clipped)
2487     return False;
2488   info.polygon = *Polygon;
2489   EXPAND_BOUNDS (&info.polygon);
2490   info.layer = LayerGroup;
2491   /* check rats */
2492   if (setjmp (info.env) == 0)
2493     r_search (PCB->Data->rat_tree, (BoxType *) & info.polygon, NULL,
2494               LOCtoPolyRat_callback, &info);
2495   else
2496     return True;
2497 /* loop over all layers of the group */
2498   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2499     {
2500       Cardinal layer, i;
2501
2502       layer = PCB->LayerGroups.Entries[LayerGroup][entry];
2503
2504       /* handle normal layers */
2505       if (layer < max_layer)
2506         {
2507           PolygonTypePtr polygon;
2508
2509           /* check all polygons */
2510
2511           polygon = PCB->Data->Layer[layer].Polygon;
2512           for (i = 0; i < PCB->Data->Layer[layer].PolygonN; i++, polygon++)
2513             if (!TEST_FLAG (TheFlag, polygon)
2514                 && IsPolygonInPolygon (polygon, Polygon)
2515                 && ADD_POLYGON_TO_LIST (layer, polygon))
2516               return True;
2517
2518           info.layer = layer;
2519           /* check all lines */
2520           if (setjmp (info.env) == 0)
2521             r_search (LAYER_PTR (layer)->line_tree,
2522                       (BoxType *) & info.polygon, NULL,
2523                       LOCtoPolyLine_callback, &info);
2524           else
2525             return True;
2526           /* check all arcs */
2527           if (setjmp (info.env) == 0)
2528             r_search (LAYER_PTR (layer)->arc_tree, (BoxType *) & info.polygon,
2529                       NULL, LOCtoPolyArc_callback, &info);
2530           else
2531             return True;
2532         }
2533       else
2534         {
2535           if (!TEST_FLAG (CLEARPOLYFLAG, Polygon))
2536             {
2537               info.layer = layer - max_layer;
2538               if (setjmp (info.env) == 0)
2539                 r_search (PCB->Data->pad_tree, (BoxType *) & info.polygon,
2540                           NULL, LOCtoPolyPad_callback, &info);
2541               else
2542                 return True;
2543             }
2544         }
2545     }
2546   return (False);
2547 }
2548
2549 /* ---------------------------------------------------------------------------
2550  * checks if an arc has a connection to a polygon
2551  *
2552  * - first check if the arc can intersect with the polygon by
2553  *   evaluating the bounding boxes
2554  * - check the two end points of the arc. If none of them matches
2555  * - check all segments of the polygon against the arc.
2556  */
2557 Boolean
2558 IsArcInPolygon (ArcTypePtr Arc, PolygonTypePtr Polygon)
2559 {
2560   BoxTypePtr Box = (BoxType *) Arc;
2561
2562   /* arcs with clearance never touch polys */
2563   if (TEST_FLAG (CLEARPOLYFLAG, Polygon) && TEST_FLAG (CLEARLINEFLAG, Arc))
2564     return False;
2565   if (!Polygon->Clipped)
2566     return False;
2567   if (Box->X1 <= Polygon->Clipped->contours->xmax + Bloat
2568       && Box->X2 >= Polygon->Clipped->contours->xmin - Bloat
2569       && Box->Y1 <= Polygon->Clipped->contours->ymax + Bloat
2570       && Box->Y2 >= Polygon->Clipped->contours->ymin - Bloat)
2571     {
2572       POLYAREA *ap;
2573
2574       if (!(ap = ArcPoly (Arc, Arc->Thickness + Bloat)))
2575         return False;           /* error */
2576       return isects (ap, Polygon, True);
2577     }
2578   return False;
2579 }
2580
2581 /* ---------------------------------------------------------------------------
2582  * checks if a line has a connection to a polygon
2583  *
2584  * - first check if the line can intersect with the polygon by
2585  *   evaluating the bounding boxes
2586  * - check the two end points of the line. If none of them matches
2587  * - check all segments of the polygon against the line.
2588  */
2589 Boolean
2590 IsLineInPolygon (LineTypePtr Line, PolygonTypePtr Polygon)
2591 {
2592   BoxTypePtr Box = (BoxType *) Line;
2593   POLYAREA *lp;
2594
2595   /* lines with clearance never touch polygons */
2596   if (TEST_FLAG (CLEARPOLYFLAG, Polygon) && TEST_FLAG (CLEARLINEFLAG, Line))
2597     return False;
2598   if (!Polygon->Clipped)
2599     return False;
2600   if (TEST_FLAG(SQUAREFLAG,Line)&&(Line->Point1.X==Line->Point2.X||Line->Point1.Y==Line->Point2.Y))
2601      {
2602        BDimension wid = (Line->Thickness + Bloat + 1) / 2;
2603        LocationType x1, x2, y1, y2;
2604
2605        x1 = MIN (Line->Point1.X, Line->Point2.X) - wid;
2606        y1 = MIN (Line->Point1.Y, Line->Point2.Y) - wid;
2607        x2 = MAX (Line->Point1.X, Line->Point2.X) + wid;
2608        y2 = MAX (Line->Point1.Y, Line->Point2.Y) + wid;
2609        return IsRectangleInPolygon (x1, y1, x2, y2, Polygon);
2610      }
2611   if (Box->X1 <= Polygon->Clipped->contours->xmax + Bloat
2612       && Box->X2 >= Polygon->Clipped->contours->xmin - Bloat
2613       && Box->Y1 <= Polygon->Clipped->contours->ymax + Bloat
2614       && Box->Y2 >= Polygon->Clipped->contours->ymin - Bloat)
2615     {
2616       if (!(lp = LinePoly (Line, Line->Thickness + Bloat)))
2617         return FALSE;           /* error */
2618       return isects (lp, Polygon, True);
2619     }
2620   return False;
2621 }
2622
2623 /* ---------------------------------------------------------------------------
2624  * checks if a pad connects to a non-clearing polygon
2625  *
2626  * The polygon is assumed to already have been proven non-clearing
2627  */
2628 Boolean
2629 IsPadInPolygon (PadTypePtr pad, PolygonTypePtr polygon)
2630 {
2631     return IsLineInPolygon ((LineTypePtr) pad, polygon);
2632 }
2633
2634 /* ---------------------------------------------------------------------------
2635  * checks if a polygon has a connection to a second one
2636  *
2637  * First check all points out of P1 against P2 and vice versa.
2638  * If both fail check all lines of P1 against the ones of P2
2639  */
2640 Boolean
2641 IsPolygonInPolygon (PolygonTypePtr P1, PolygonTypePtr P2)
2642 {
2643   if (!P1->Clipped || !P2->Clipped)
2644     return False;
2645   assert (P1->Clipped->contours);
2646   assert (P2->Clipped->contours);
2647
2648   /* first check if both bounding boxes intersect. If not, return quickly */
2649   if (P1->Clipped->contours->xmin - Bloat > P2->Clipped->contours->xmax ||
2650       P1->Clipped->contours->xmax + Bloat < P2->Clipped->contours->xmin ||
2651       P1->Clipped->contours->ymin - Bloat > P2->Clipped->contours->ymax ||
2652       P1->Clipped->contours->ymax + Bloat < P2->Clipped->contours->ymin)
2653     return False;
2654
2655   /* first check un-bloated case */
2656   if (isects (P1->Clipped, P2, False))
2657     return TRUE;
2658
2659   /* now the difficult case of bloated */
2660   if (Bloat > 0)
2661     {
2662       PLINE *c;
2663       for (c = P1->Clipped->contours; c; c = c->next)
2664         {
2665           LineType line;
2666           VNODE *v = &c->head;
2667           if (c->xmin - Bloat <= P2->Clipped->contours->xmax &&
2668               c->xmax + Bloat >= P2->Clipped->contours->xmin &&
2669               c->ymin - Bloat <= P2->Clipped->contours->ymax &&
2670               c->ymax + Bloat >= P2->Clipped->contours->ymin)
2671             {
2672
2673               line.Point1.X = v->point[0];
2674               line.Point1.Y = v->point[1];
2675               line.Thickness = 2 * Bloat;
2676               line.Clearance = 0;
2677               line.Flags = NoFlags ();
2678               for (v = v->next; v != &c->head; v = v->next)
2679                 {
2680                   line.Point2.X = v->point[0];
2681                   line.Point2.Y = v->point[1];
2682                   SetLineBoundingBox (&line);
2683                   if (IsLineInPolygon (&line, P2))
2684                     return (True);
2685                   line.Point1.X = line.Point2.X;
2686                   line.Point1.Y = line.Point2.Y;
2687                 }
2688             }
2689         }
2690     }
2691
2692   return (False);
2693 }
2694
2695 /* ---------------------------------------------------------------------------
2696  * writes the several names of an element to a file
2697  */
2698 static void
2699 PrintElementNameList (ElementTypePtr Element, FILE * FP)
2700 {
2701   static DynamicStringType cname, pname, vname;
2702
2703   CreateQuotedString (&cname, EMPTY (DESCRIPTION_NAME (Element)));
2704   CreateQuotedString (&pname, EMPTY (NAMEONPCB_NAME (Element)));
2705   CreateQuotedString (&vname, EMPTY (VALUE_NAME (Element)));
2706   fprintf (FP, "(%s %s %s)\n", cname.Data, pname.Data, vname.Data);
2707 }
2708
2709 /* ---------------------------------------------------------------------------
2710  * writes the several names of an element to a file
2711  */
2712 static void
2713 PrintConnectionElementName (ElementTypePtr Element, FILE * FP)
2714 {
2715   fputs ("Element", FP);
2716   PrintElementNameList (Element, FP);
2717   fputs ("{\n", FP);
2718 }
2719
2720 /* ---------------------------------------------------------------------------
2721  * prints one {pin,pad,via}/element entry of connection lists
2722  */
2723 static void
2724 PrintConnectionListEntry (char *ObjName, ElementTypePtr Element,
2725                           Boolean FirstOne, FILE * FP)
2726 {
2727   static DynamicStringType oname;
2728
2729   CreateQuotedString (&oname, ObjName);
2730   if (FirstOne)
2731     fprintf (FP, "\t%s\n\t{\n", oname.Data);
2732   else
2733     {
2734       fprintf (FP, "\t\t%s ", oname.Data);
2735       if (Element)
2736         PrintElementNameList (Element, FP);
2737       else
2738         fputs ("(__VIA__)\n", FP);
2739     }
2740 }
2741
2742 /* ---------------------------------------------------------------------------
2743  * prints all found connections of a pads to file FP
2744  * the connections are stacked in 'PadList'
2745  */
2746 static void
2747 PrintPadConnections (Cardinal Layer, FILE * FP, Boolean IsFirst)
2748 {
2749   Cardinal i;
2750   PadTypePtr ptr;
2751
2752   if (!PadList[Layer].Number)
2753     return;
2754
2755   /* the starting pad */
2756   if (IsFirst)
2757     {
2758       ptr = PADLIST_ENTRY (Layer, 0);
2759       if (ptr != NULL)
2760         PrintConnectionListEntry (UNKNOWN (ptr->Name), NULL, True, FP);
2761       else
2762         printf ("Skipping NULL ptr in 1st part of PrintPadConnections\n");
2763     }
2764
2765   /* we maybe have to start with i=1 if we are handling the
2766    * starting-pad itself
2767    */
2768   for (i = IsFirst ? 1 : 0; i < PadList[Layer].Number; i++)
2769     {
2770       ptr = PADLIST_ENTRY (Layer, i);
2771       if (ptr != NULL)
2772         PrintConnectionListEntry (EMPTY (ptr->Name), ptr->Element, False, FP);
2773       else
2774         printf ("Skipping NULL ptr in 2nd part of PrintPadConnections\n");
2775     }
2776 }
2777
2778 /* ---------------------------------------------------------------------------
2779  * prints all found connections of a pin to file FP
2780  * the connections are stacked in 'PVList'
2781  */
2782 static void
2783 PrintPinConnections (FILE * FP, Boolean IsFirst)
2784 {
2785   Cardinal i;
2786   PinTypePtr pv;
2787
2788   if (!PVList.Number)
2789     return;
2790
2791   if (IsFirst)
2792     {
2793       /* the starting pin */
2794       pv = PVLIST_ENTRY (0);
2795       PrintConnectionListEntry (EMPTY (pv->Name), NULL, True, FP);
2796     }
2797
2798   /* we maybe have to start with i=1 if we are handling the
2799    * starting-pin itself
2800    */
2801   for (i = IsFirst ? 1 : 0; i < PVList.Number; i++)
2802     {
2803       /* get the elements name or assume that its a via */
2804       pv = PVLIST_ENTRY (i);
2805       PrintConnectionListEntry (EMPTY (pv->Name), pv->Element, False, FP);
2806     }
2807 }
2808
2809 /* ---------------------------------------------------------------------------
2810  * checks if all lists of new objects are handled
2811  */
2812 static Boolean
2813 ListsEmpty (Boolean AndRats)
2814 {
2815   Boolean empty;
2816   int i;
2817
2818   empty = (PVList.Location >= PVList.Number);
2819   if (AndRats)
2820     empty = empty && (RatList.Location >= RatList.Number);
2821   for (i = 0; i < max_layer && empty; i++)
2822     empty = empty && LineList[i].Location >= LineList[i].Number
2823       && ArcList[i].Location >= ArcList[i].Number
2824       && PolygonList[i].Location >= PolygonList[i].Number;
2825   return (empty);
2826 }
2827
2828 /* ---------------------------------------------------------------------------
2829  * loops till no more connections are found
2830  */
2831 static Boolean
2832 DoIt (Boolean AndRats, Boolean AndDraw)
2833 {
2834   Boolean new = False;
2835   do
2836     {
2837       /* lookup connections; these are the steps (2) to (4)
2838        * from the description
2839        */
2840       new = LookupPVConnectionsToPVList ();
2841       if (!new)
2842         new = LookupLOConnectionsToPVList (AndRats);
2843       if (!new)
2844         new = LookupLOConnectionsToLOList (AndRats);
2845       if (!new)
2846         new = LookupPVConnectionsToLOList (AndRats);
2847       if (AndDraw)
2848         DrawNewConnections ();
2849     }
2850   while (!new && !ListsEmpty (AndRats));
2851   if (AndDraw)
2852     Draw ();
2853   return (new);
2854 }
2855
2856 /* returns True if nothing un-found touches the passed line
2857  * returns False if it would touch something not yet found
2858  * doesn't include rat-lines in the search
2859  */
2860
2861 Boolean
2862 lineClear (LineTypePtr line, Cardinal group)
2863 {
2864   if (LOTouchesLine (line, group))
2865     return (False);
2866   if (PVTouchesLine (line))
2867     return (False);
2868   return (True);
2869 }
2870
2871 /* ---------------------------------------------------------------------------
2872  * prints all unused pins of an element to file FP
2873  */
2874 static Boolean
2875 PrintAndSelectUnusedPinsAndPadsOfElement (ElementTypePtr Element, FILE * FP)
2876 {
2877   Boolean first = True;
2878   Cardinal number;
2879   static DynamicStringType oname;
2880
2881   /* check all pins in element */
2882
2883   PIN_LOOP (Element);
2884   {
2885     if (!TEST_FLAG (HOLEFLAG, pin))
2886       {
2887         /* pin might have bee checked before, add to list if not */
2888         if (!TEST_FLAG (TheFlag, pin) && FP)
2889           {
2890             int i;
2891             if (ADD_PV_TO_LIST (pin))
2892               return True;
2893             DoIt (True, True);
2894             number = PadList[COMPONENT_LAYER].Number
2895               + PadList[SOLDER_LAYER].Number + PVList.Number;
2896             /* the pin has no connection if it's the only
2897              * list entry; don't count vias
2898              */
2899             for (i = 0; i < PVList.Number; i++)
2900               if (!PVLIST_ENTRY (i)->Element)
2901                 number--;
2902             if (number == 1)
2903               {
2904                 /* output of element name if not already done */
2905                 if (first)
2906                   {
2907                     PrintConnectionElementName (Element, FP);
2908                     first = False;
2909                   }
2910
2911                 /* write name to list and draw selected object */
2912                 CreateQuotedString (&oname, EMPTY (pin->Name));
2913                 fprintf (FP, "\t%s\n", oname.Data);
2914                 SET_FLAG (SELECTEDFLAG, pin);
2915                 DrawPin (pin, 0);
2916               }
2917
2918             /* reset found objects for the next pin */
2919             if (PrepareNextLoop (FP))
2920               return (True);
2921           }
2922       }
2923   }
2924   END_LOOP;
2925
2926   /* check all pads in element */
2927   PAD_LOOP (Element);
2928   {
2929     /* lookup pad in list */
2930     /* pad might has bee checked before, add to list if not */
2931     if (!TEST_FLAG (TheFlag, pad) && FP)
2932       {
2933         int i;
2934         if (ADD_PAD_TO_LIST (TEST_FLAG (ONSOLDERFLAG, pad)
2935                              ? SOLDER_LAYER : COMPONENT_LAYER, pad))
2936           return True;
2937         DoIt (True, True);
2938         number = PadList[COMPONENT_LAYER].Number
2939           + PadList[SOLDER_LAYER].Number + PVList.Number;
2940         /* the pin has no connection if it's the only
2941          * list entry; don't count vias
2942          */
2943         for (i = 0; i < PVList.Number; i++)
2944           if (!PVLIST_ENTRY (i)->Element)
2945             number--;
2946         if (number == 1)
2947           {
2948             /* output of element name if not already done */
2949             if (first)
2950               {
2951                 PrintConnectionElementName (Element, FP);
2952                 first = False;
2953               }
2954
2955             /* write name to list and draw selected object */
2956             CreateQuotedString (&oname, EMPTY (pad->Name));
2957             fprintf (FP, "\t%s\n", oname.Data);
2958             SET_FLAG (SELECTEDFLAG, pad);
2959             DrawPad (pad, 0);
2960           }
2961
2962         /* reset found objects for the next pin */
2963         if (PrepareNextLoop (FP))
2964           return (True);
2965       }
2966   }
2967   END_LOOP;
2968
2969   /* print separator if element has unused pins or pads */
2970   if (!first)
2971     {
2972       fputs ("}\n\n", FP);
2973       SEPARATE (FP);
2974     }
2975   return (False);
2976 }
2977
2978 /* ---------------------------------------------------------------------------
2979  * resets some flags for looking up the next pin/pad
2980  */
2981 static Boolean
2982 PrepareNextLoop (FILE * FP)
2983 {
2984   Cardinal layer;
2985
2986   /* reset found LOs for the next pin */
2987   for (layer = 0; layer < max_layer; layer++)
2988     {
2989       LineList[layer].Location = LineList[layer].Number = 0;
2990       ArcList[layer].Location = ArcList[layer].Number = 0;
2991       PolygonList[layer].Location = PolygonList[layer].Number = 0;
2992     }
2993
2994   /* reset found pads */
2995   for (layer = 0; layer < 2; layer++)
2996     PadList[layer].Location = PadList[layer].Number = 0;
2997
2998   /* reset PVs */
2999   PVList.Number = PVList.Location = 0;
3000   RatList.Number = RatList.Location = 0;
3001
3002   return (False);
3003 }
3004
3005 /* ---------------------------------------------------------------------------
3006  * finds all connections to the pins of the passed element.
3007  * The result is written to file FP
3008  * Returns True if operation was aborted
3009  */
3010 static Boolean
3011 PrintElementConnections (ElementTypePtr Element, FILE * FP, Boolean AndDraw)
3012 {
3013   PrintConnectionElementName (Element, FP);
3014
3015   /* check all pins in element */
3016   PIN_LOOP (Element);
3017   {
3018     /* pin might have been checked before, add to list if not */
3019     if (TEST_FLAG (TheFlag, pin))
3020       {
3021         PrintConnectionListEntry (EMPTY (pin->Name), NULL, True, FP);
3022         fputs ("\t\t__CHECKED_BEFORE__\n\t}\n", FP);
3023         continue;
3024       }
3025     if (ADD_PV_TO_LIST (pin))
3026       return True;
3027     DoIt (True, AndDraw);
3028     /* printout all found connections */
3029     PrintPinConnections (FP, True);
3030     PrintPadConnections (COMPONENT_LAYER, FP, False);
3031     PrintPadConnections (SOLDER_LAYER, FP, False);
3032     fputs ("\t}\n", FP);
3033     if (PrepareNextLoop (FP))
3034       return (True);
3035   }
3036   END_LOOP;
3037
3038   /* check all pads in element */
3039   PAD_LOOP (Element);
3040   {
3041     Cardinal layer;
3042     /* pad might have been checked before, add to list if not */
3043     if (TEST_FLAG (TheFlag, pad))
3044       {
3045         PrintConnectionListEntry (EMPTY (pad->Name), NULL, True, FP);
3046         fputs ("\t\t__CHECKED_BEFORE__\n\t}\n", FP);
3047         continue;
3048       }
3049     layer = TEST_FLAG (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER;
3050     if (ADD_PAD_TO_LIST (layer, pad))
3051       return True;
3052     DoIt (True, AndDraw);
3053     /* print all found connections */
3054     PrintPadConnections (layer, FP, True);
3055     PrintPadConnections (layer ==
3056                          (COMPONENT_LAYER ? SOLDER_LAYER : COMPONENT_LAYER),
3057                          FP, False);
3058     PrintPinConnections (FP, False);
3059     fputs ("\t}\n", FP);
3060     if (PrepareNextLoop (FP))
3061       return (True);
3062   }
3063   END_LOOP;
3064   fputs ("}\n\n", FP);
3065   return (False);
3066 }
3067
3068 /* ---------------------------------------------------------------------------
3069  * draws all new connections which have been found since the
3070  * routine was called the last time
3071  */
3072 static void
3073 DrawNewConnections (void)
3074 {
3075   int i;
3076   Cardinal position;
3077
3078   /* decrement 'i' to keep layerstack order */
3079   for (i = max_layer - 1; i != -1; i--)
3080     {
3081       Cardinal layer = LayerStack[i];
3082
3083       if (PCB->Data->Layer[layer].On)
3084         {
3085           /* draw all new lines */
3086           position = LineList[layer].DrawLocation;
3087           for (; position < LineList[layer].Number; position++)
3088             DrawLine (LAYER_PTR (layer), LINELIST_ENTRY (layer, position), 0);
3089           LineList[layer].DrawLocation = LineList[layer].Number;
3090
3091           /* draw all new arcs */
3092           position = ArcList[layer].DrawLocation;
3093           for (; position < ArcList[layer].Number; position++)
3094             DrawArc (LAYER_PTR (layer), ARCLIST_ENTRY (layer, position), 0);
3095           ArcList[layer].DrawLocation = ArcList[layer].Number;
3096
3097           /* draw all new polygons */
3098           position = PolygonList[layer].DrawLocation;
3099           for (; position < PolygonList[layer].Number; position++)
3100             DrawPolygon
3101               (LAYER_PTR (layer), POLYGONLIST_ENTRY (layer, position), 0);
3102           PolygonList[layer].DrawLocation = PolygonList[layer].Number;
3103         }
3104     }
3105
3106   /* draw all new pads */
3107   if (PCB->PinOn)
3108     for (i = 0; i < 2; i++)
3109       {
3110         position = PadList[i].DrawLocation;
3111
3112         for (; position < PadList[i].Number; position++)
3113           DrawPad (PADLIST_ENTRY (i, position), 0);
3114         PadList[i].DrawLocation = PadList[i].Number;
3115       }
3116
3117   /* draw all new PVs; 'PVList' holds a list of pointers to the
3118    * sorted array pointers to PV data
3119    */
3120   while (PVList.DrawLocation < PVList.Number)
3121     {
3122       PinTypePtr pv = PVLIST_ENTRY (PVList.DrawLocation);
3123
3124       if (TEST_FLAG (PINFLAG, pv))
3125         {
3126           if (PCB->PinOn)
3127             DrawPin (pv, 0);
3128         }
3129       else if (PCB->ViaOn)
3130         DrawVia (pv, 0);
3131       PVList.DrawLocation++;
3132     }
3133   /* draw the new rat-lines */
3134   if (PCB->RatOn)
3135     {
3136       position = RatList.DrawLocation;
3137       for (; position < RatList.Number; position++)
3138         DrawRat (RATLIST_ENTRY (position), 0);
3139       RatList.DrawLocation = RatList.Number;
3140     }
3141 }
3142
3143 /* ---------------------------------------------------------------------------
3144  * find all connections to pins within one element
3145  */
3146 void
3147 LookupElementConnections (ElementTypePtr Element, FILE * FP)
3148 {
3149   /* reset all currently marked connections */
3150   User = True;
3151   TheFlag = FOUNDFLAG;
3152   ResetConnections (True);
3153   InitConnectionLookup ();
3154   PrintElementConnections (Element, FP, True);
3155   SetChangedFlag (True);
3156   if (Settings.RingBellWhenFinished)
3157     gui->beep ();
3158   FreeConnectionLookupMemory ();
3159   IncrementUndoSerialNumber ();
3160   User = False;
3161   Draw ();
3162 }
3163
3164 /* ---------------------------------------------------------------------------
3165  * find all connections to pins of all element
3166  */
3167 void
3168 LookupConnectionsToAllElements (FILE * FP)
3169 {
3170   /* reset all currently marked connections */
3171   User = False;
3172   TheFlag = FOUNDFLAG;
3173   ResetConnections (False);
3174   InitConnectionLookup ();
3175
3176   ELEMENT_LOOP (PCB->Data);
3177   {
3178     /* break if abort dialog returned True */
3179     if (PrintElementConnections (element, FP, False))
3180       break;
3181     SEPARATE (FP);
3182     if (Settings.ResetAfterElement && n != 1)
3183       ResetConnections (False);
3184   }
3185   END_LOOP;
3186   if (Settings.RingBellWhenFinished)
3187     gui->beep ();
3188   ResetConnections (False);
3189   FreeConnectionLookupMemory ();
3190   ClearAndRedrawOutput ();
3191 }
3192
3193 /*---------------------------------------------------------------------------
3194  * add the starting object to the list of found objects
3195  */
3196 static Boolean
3197 ListStart (int type, void *ptr1, void *ptr2, void *ptr3)
3198 {
3199   DumpList ();
3200   switch (type)
3201     {
3202     case PIN_TYPE:
3203     case VIA_TYPE:
3204       {
3205         if (ADD_PV_TO_LIST ((PinTypePtr) ptr2))
3206           return True;
3207         break;
3208       }
3209
3210     case RATLINE_TYPE:
3211       {
3212         if (ADD_RAT_TO_LIST ((RatTypePtr) ptr1))
3213           return True;
3214         break;
3215       }
3216
3217     case LINE_TYPE:
3218       {
3219         int layer = GetLayerNumber (PCB->Data,
3220                                     (LayerTypePtr) ptr1);
3221
3222         if (ADD_LINE_TO_LIST (layer, (LineTypePtr) ptr2))
3223           return True;
3224         break;
3225       }
3226
3227     case ARC_TYPE:
3228       {
3229         int layer = GetLayerNumber (PCB->Data,
3230                                     (LayerTypePtr) ptr1);
3231
3232         if (ADD_ARC_TO_LIST (layer, (ArcTypePtr) ptr2))
3233           return True;
3234         break;
3235       }
3236
3237     case POLYGON_TYPE:
3238       {
3239         int layer = GetLayerNumber (PCB->Data,
3240                                     (LayerTypePtr) ptr1);
3241
3242         if (ADD_POLYGON_TO_LIST (layer, (PolygonTypePtr) ptr2))
3243           return True;
3244         break;
3245       }
3246
3247     case PAD_TYPE:
3248       {
3249         PadTypePtr pad = (PadTypePtr) ptr2;
3250         if (ADD_PAD_TO_LIST
3251             (TEST_FLAG
3252              (ONSOLDERFLAG, pad) ? SOLDER_LAYER : COMPONENT_LAYER, pad))
3253           return True;
3254         break;
3255       }
3256     }
3257   return (False);
3258 }
3259
3260
3261 /* ---------------------------------------------------------------------------
3262  * looks up all connections from the object at the given coordinates
3263  * the TheFlag (normally 'FOUNDFLAG') is set for all objects found
3264  * the objects are re-drawn if AndDraw is true
3265  * also the action is marked as undoable if AndDraw is true
3266  */
3267 void
3268 LookupConnection (LocationType X, LocationType Y, Boolean AndDraw,
3269                   BDimension Range, int which_flag)
3270 {
3271   void *ptr1, *ptr2, *ptr3;
3272   char *name;
3273   int type;
3274
3275   /* check if there are any pins or pads at that position */
3276
3277
3278   type
3279     = SearchObjectByLocation (LOOKUP_FIRST, &ptr1, &ptr2, &ptr3, X, Y, Range);
3280   if (type == NO_TYPE)
3281     {
3282       type
3283         =
3284         SearchObjectByLocation
3285         (LOOKUP_MORE, &ptr1, &ptr2, &ptr3, X, Y, Range);
3286       if (type == NO_TYPE)
3287         return;
3288       if (type & SILK_TYPE)
3289         {
3290           int laynum = GetLayerNumber (PCB->Data,
3291                                        (LayerTypePtr) ptr1);
3292
3293           /* don't mess with silk objects! */
3294           if (laynum >= max_layer)
3295             return;
3296         }
3297     }
3298   else
3299     {
3300       name = ConnectionName (type, ptr1, ptr2);
3301       hid_actionl ("NetlistShow", name, NULL);
3302     }
3303
3304   TheFlag = which_flag;
3305   User = AndDraw;
3306   InitConnectionLookup ();
3307
3308   /* now add the object to the appropriate list and start scanning
3309    * This is step (1) from the description
3310    */
3311   ListStart (type, ptr1, ptr2, ptr3);
3312   DoIt (True, AndDraw);
3313   if (User)
3314     IncrementUndoSerialNumber ();
3315   User = False;
3316
3317   /* we are done */
3318   if (AndDraw)
3319     Draw ();
3320   if (AndDraw && Settings.RingBellWhenFinished)
3321     gui->beep ();
3322   FreeConnectionLookupMemory ();
3323 }
3324
3325 /* ---------------------------------------------------------------------------
3326  * find connections for rats nesting
3327  * assumes InitConnectionLookup() has already been done
3328  */
3329 void
3330   RatFindHook
3331   (int type, void *ptr1, void *ptr2, void *ptr3, Boolean undo,
3332    Boolean AndRats)
3333 {
3334   User = undo;
3335   DumpList ();
3336   ListStart (type, ptr1, ptr2, ptr3);
3337   DoIt (AndRats, False);
3338   User = False;
3339 }
3340
3341 /* ---------------------------------------------------------------------------
3342  * find all unused pins of all element
3343  */
3344 void
3345 LookupUnusedPins (FILE * FP)
3346 {
3347   /* reset all currently marked connections */
3348   User = True;
3349   SaveUndoSerialNumber ();
3350   ResetConnections (True);
3351   RestoreUndoSerialNumber ();
3352   InitConnectionLookup ();
3353
3354   ELEMENT_LOOP (PCB->Data);
3355   {
3356     /* break if abort dialog returned True;
3357      * passing NULL as filedescriptor discards the normal output
3358      */
3359     if (PrintAndSelectUnusedPinsAndPadsOfElement (element, FP))
3360       break;
3361   }
3362   END_LOOP;
3363
3364   if (Settings.RingBellWhenFinished)
3365     gui->beep ();
3366   FreeConnectionLookupMemory ();
3367   IncrementUndoSerialNumber ();
3368   User = False;
3369   Draw ();
3370 }
3371
3372 /* ---------------------------------------------------------------------------
3373  * resets all used flags of pins and vias
3374  */
3375 void
3376 ResetFoundPinsViasAndPads (Boolean AndDraw)
3377 {
3378   Boolean change = False;
3379
3380
3381   VIA_LOOP (PCB->Data);
3382   {
3383     if (TEST_FLAG (TheFlag, via))
3384       {
3385         if (AndDraw)
3386           AddObjectToFlagUndoList (VIA_TYPE, via, via, via);
3387         CLEAR_FLAG (TheFlag, via);
3388         if (AndDraw)
3389           DrawVia (via, 0);
3390         change = True;
3391       }
3392   }
3393   END_LOOP;
3394   ELEMENT_LOOP (PCB->Data);
3395   {
3396     PIN_LOOP (element);
3397     {
3398       if (TEST_FLAG (TheFlag, pin))
3399         {
3400           if (AndDraw)
3401             AddObjectToFlagUndoList (PIN_TYPE, element, pin, pin);
3402           CLEAR_FLAG (TheFlag, pin);
3403           if (AndDraw)
3404             DrawPin (pin, 0);
3405           change = True;
3406         }
3407     }
3408     END_LOOP;
3409     PAD_LOOP (element);
3410     {
3411       if (TEST_FLAG (TheFlag, pad))
3412         {
3413           if (AndDraw)
3414             AddObjectToFlagUndoList (PAD_TYPE, element, pad, pad);
3415           CLEAR_FLAG (TheFlag, pad);
3416           if (AndDraw)
3417             DrawPad (pad, 0);
3418           change = True;
3419         }
3420     }
3421     END_LOOP;
3422   }
3423   END_LOOP;
3424   if (change)
3425     {
3426       SetChangedFlag (True);
3427       if (AndDraw)
3428         {
3429           IncrementUndoSerialNumber ();
3430           Draw ();
3431         }
3432     }
3433 }
3434
3435 /* ---------------------------------------------------------------------------
3436  * resets all used flags of LOs
3437  */
3438 void
3439 ResetFoundLinesAndPolygons (Boolean AndDraw)
3440 {
3441   Boolean change = False;
3442
3443
3444   RAT_LOOP (PCB->Data);
3445   {
3446     if (TEST_FLAG (TheFlag, line))
3447       {
3448         if (AndDraw)
3449           AddObjectToFlagUndoList (RATLINE_TYPE, line, line, line);
3450         CLEAR_FLAG (TheFlag, line);
3451         if (AndDraw)
3452           DrawRat (line, 0);
3453         change = True;
3454       }
3455   }
3456   END_LOOP;
3457   COPPERLINE_LOOP (PCB->Data);
3458   {
3459     if (TEST_FLAG (TheFlag, line))
3460       {
3461         if (AndDraw)
3462           AddObjectToFlagUndoList (LINE_TYPE, layer, line, line);
3463         CLEAR_FLAG (TheFlag, line);
3464         if (AndDraw)
3465           DrawLine (layer, line, 0);
3466         change = True;
3467       }
3468   }
3469   ENDALL_LOOP;
3470   COPPERARC_LOOP (PCB->Data);
3471   {
3472     if (TEST_FLAG (TheFlag, arc))
3473       {
3474         if (AndDraw)
3475           AddObjectToFlagUndoList (ARC_TYPE, layer, arc, arc);
3476         CLEAR_FLAG (TheFlag, arc);
3477         if (AndDraw)
3478           DrawArc (layer, arc, 0);
3479         change = True;
3480       }
3481   }
3482   ENDALL_LOOP;
3483   COPPERPOLYGON_LOOP (PCB->Data);
3484   {
3485     if (TEST_FLAG (TheFlag, polygon))
3486       {
3487         if (AndDraw)
3488           AddObjectToFlagUndoList (POLYGON_TYPE, layer, polygon, polygon);
3489         CLEAR_FLAG (TheFlag, polygon);
3490         if (AndDraw)
3491           DrawPolygon (layer, polygon, 0);
3492         change = True;
3493       }
3494   }
3495   ENDALL_LOOP;
3496   if (change)
3497     {
3498       SetChangedFlag (True);
3499       if (AndDraw)
3500         {
3501           IncrementUndoSerialNumber ();
3502           Draw ();
3503         }
3504     }
3505 }
3506
3507 /* ---------------------------------------------------------------------------
3508  * resets all found connections
3509  */
3510 static void
3511 ResetConnections (Boolean AndDraw)
3512 {
3513   if (AndDraw)
3514     SaveUndoSerialNumber ();
3515   ResetFoundPinsViasAndPads (AndDraw);
3516   if (AndDraw)
3517     RestoreUndoSerialNumber ();
3518   ResetFoundLinesAndPolygons (AndDraw);
3519 }
3520
3521 /*----------------------------------------------------------------------------
3522  * Dumps the list contents
3523  */
3524 static void
3525 DumpList (void)
3526 {
3527   Cardinal i;
3528
3529   for (i = 0; i < 2; i++)
3530     {
3531       PadList[i].Number = 0;
3532       PadList[i].Location = 0;
3533       PadList[i].DrawLocation = 0;
3534     }
3535
3536   PVList.Number = 0;
3537   PVList.Location = 0;
3538
3539   for (i = 0; i < max_layer; i++)
3540     {
3541       LineList[i].Location = 0;
3542       LineList[i].DrawLocation = 0;
3543       LineList[i].Number = 0;
3544       ArcList[i].Location = 0;
3545       ArcList[i].DrawLocation = 0;
3546       ArcList[i].Number = 0;
3547       PolygonList[i].Location = 0;
3548       PolygonList[i].DrawLocation = 0;
3549       PolygonList[i].Number = 0;
3550     }
3551   RatList.Number = 0;
3552   RatList.Location = 0;
3553   RatList.DrawLocation = 0;
3554 }
3555
3556 /*-----------------------------------------------------------------------------
3557  * Check for DRC violations on a single net starting from the pad or pin
3558  * sees if the connectivity changes when everything is bloated, or shrunk
3559  */
3560 static Boolean
3561 DRCFind (int What, void *ptr1, void *ptr2, void *ptr3)
3562 {
3563   LocationType x, y;
3564   int object_count;
3565   long int *object_id_list;
3566   int *object_type_list;
3567   DrcViolationType *violation;
3568
3569   if (PCB->Shrink != 0)
3570     {
3571       Bloat = -PCB->Shrink;
3572       fBloat = (float) -PCB->Shrink;
3573       TheFlag = DRCFLAG | SELECTEDFLAG;
3574       ListStart (What, ptr1, ptr2, ptr3);
3575       DoIt (True, False);
3576       /* ok now the shrunk net has the SELECTEDFLAG set */
3577       DumpList ();
3578       TheFlag = FOUNDFLAG;
3579       ListStart (What, ptr1, ptr2, ptr3);
3580       Bloat = 0;
3581       fBloat = 0.0;
3582       drc = True;               /* abort the search if we find anything not already found */
3583       if (DoIt (True, False))
3584         {
3585           DumpList ();
3586           /* make the flag changes undoable */
3587           TheFlag = FOUNDFLAG | SELECTEDFLAG;
3588           ResetConnections (False);
3589           User = True;
3590           drc = False;
3591           Bloat = -PCB->Shrink;
3592           fBloat = (float) -PCB->Shrink;
3593           TheFlag = SELECTEDFLAG;
3594           RestoreUndoSerialNumber ();
3595           ListStart (What, ptr1, ptr2, ptr3);
3596           DoIt (True, True);
3597           DumpList ();
3598           ListStart (What, ptr1, ptr2, ptr3);
3599           TheFlag = FOUNDFLAG;
3600           Bloat = 0;
3601           fBloat = 0.0;
3602           drc = True;
3603           DoIt (True, True);
3604           DumpList ();
3605           User = False;
3606           drc = False;
3607           drcerr_count++;
3608           LocateError (&x, &y);
3609           BuildObjectList (&object_count, &object_id_list, &object_type_list);
3610           violation = pcb_drc_violation_new (_("Potential for broken trace"),
3611                                              _("Insufficient overlap between objects can lead to broken tracks\n"
3612                                                "due to registration errors with old wheel style photo-plotters."),
3613                                              x, y,
3614                                              0,     /* ANGLE OF ERROR UNKNOWN */
3615                                              FALSE, /* MEASUREMENT OF ERROR UNKNOWN */
3616                                              0,     /* MAGNITUDE OF ERROR UNKNOWN */
3617                                              LENGTH_TO_HUMAN(PCB->Shrink),
3618                                              LENGTH_DIGITS,
3619                                              LENGTH_UNITS_STRING,
3620                                              object_count,
3621                                              object_id_list,
3622                                              object_type_list);
3623           append_drc_violation (violation);
3624           pcb_drc_violation_free (violation);
3625           free (object_id_list);
3626           free (object_type_list);
3627
3628           if (!throw_drc_dialog())
3629             return (True);
3630           IncrementUndoSerialNumber ();
3631           Undo (True);
3632         }
3633       DumpList ();
3634     }
3635   /* now check the bloated condition */
3636   drc = False;
3637   ResetConnections (False);
3638   TheFlag = FOUNDFLAG;
3639   ListStart (What, ptr1, ptr2, ptr3);
3640   Bloat = PCB->Bloat;
3641   fBloat = (float) PCB->Bloat;
3642   drc = True;
3643   while (DoIt (True, False))
3644     {
3645       DumpList ();
3646       /* make the flag changes undoable */
3647       TheFlag = FOUNDFLAG | SELECTEDFLAG;
3648       ResetConnections (False);
3649       User = True;
3650       drc = False;
3651       Bloat = 0;
3652       fBloat = 0.0;
3653       RestoreUndoSerialNumber ();
3654       TheFlag = SELECTEDFLAG;
3655       ListStart (What, ptr1, ptr2, ptr3);
3656       DoIt (True, True);
3657       DumpList ();
3658       TheFlag = FOUNDFLAG;
3659       ListStart (What, ptr1, ptr2, ptr3);
3660       Bloat = PCB->Bloat;
3661       fBloat = (float) PCB->Bloat;
3662       drc = True;
3663       DoIt (True, True);
3664       DumpList ();
3665       drcerr_count++;
3666       LocateError (&x, &y);
3667       BuildObjectList (&object_count, &object_id_list, &object_type_list);
3668       violation = pcb_drc_violation_new (_("Copper areas too close"),
3669                                          _("Circuits that are too close may bridge during imaging, etching,\n"
3670                                            "plating, or soldering processes resulting in a direct short."),
3671                                          x, y,
3672                                          0,     /* ANGLE OF ERROR UNKNOWN */
3673                                          FALSE, /* MEASUREMENT OF ERROR UNKNOWN */
3674                                          0,     /* MAGNITUDE OF ERROR UNKNOWN */
3675                                          LENGTH_TO_HUMAN(PCB->Bloat),
3676                                          LENGTH_DIGITS,
3677                                          LENGTH_UNITS_STRING,
3678                                          object_count,
3679                                          object_id_list,
3680                                          object_type_list);
3681       append_drc_violation (violation);
3682       pcb_drc_violation_free (violation);
3683       free (object_id_list);
3684       free (object_type_list);
3685       User = False;
3686       drc = False;
3687       if (!throw_drc_dialog())
3688         return (True);
3689       IncrementUndoSerialNumber ();
3690       Undo (True);
3691       /* highlight the rest of the encroaching net so it's not reported again */
3692       TheFlag |= SELECTEDFLAG;
3693       Bloat = 0;
3694       fBloat = 0.0;
3695       ListStart (thing_type, thing_ptr1, thing_ptr2, thing_ptr3);
3696       DoIt (True, True);
3697       DumpList ();
3698       drc = True;
3699       Bloat = PCB->Bloat;
3700       fBloat = (float) PCB->Bloat;
3701       ListStart (What, ptr1, ptr2, ptr3);
3702     }
3703   drc = False;
3704   DumpList ();
3705   TheFlag = FOUNDFLAG | SELECTEDFLAG;
3706   ResetConnections (False);
3707   return (False);
3708 }
3709
3710 /*----------------------------------------------------------------------------
3711  * set up a temporary flag to use
3712  */
3713 void
3714 SaveFindFlag (int NewFlag)
3715 {
3716   OldFlag = TheFlag;
3717   TheFlag = NewFlag;
3718 }
3719
3720 /*----------------------------------------------------------------------------
3721  * restore flag
3722  */
3723 void
3724 RestoreFindFlag (void)
3725 {
3726   TheFlag = OldFlag;
3727 }
3728
3729 /* DRC clearance callback */
3730
3731 static int
3732 drc_callback (DataTypePtr data, LayerTypePtr layer, PolygonTypePtr polygon,
3733               int type, void *ptr1, void *ptr2)
3734 {
3735   char *message;
3736   LocationType x, y;
3737   int object_count;
3738   long int *object_id_list;
3739   int *object_type_list;
3740   DrcViolationType *violation;
3741
3742   LineTypePtr line = (LineTypePtr) ptr2;
3743   ArcTypePtr arc = (ArcTypePtr) ptr2;
3744   PinTypePtr pin = (PinTypePtr) ptr2;
3745   PadTypePtr pad = (PadTypePtr) ptr2;
3746
3747   thing_type = type;
3748   thing_ptr1 = ptr1;
3749   thing_ptr2 = ptr2;
3750   thing_ptr3 = ptr2;
3751   switch (type)
3752     {
3753     case LINE_TYPE:
3754       if (line->Clearance < 2 * PCB->Bloat)
3755         {
3756           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3757           SET_FLAG (TheFlag, line);
3758           message = _("Line with insufficient clearance inside polygon\n");
3759           goto doIsBad;
3760         }
3761       break;
3762     case ARC_TYPE:
3763       if (arc->Clearance < 2 * PCB->Bloat)
3764         {
3765           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3766           SET_FLAG (TheFlag, arc);
3767           message = _("Arc with insufficient clearance inside polygon\n");
3768           goto doIsBad;
3769         }
3770       break;
3771     case PAD_TYPE:
3772       if (pad->Clearance < 2 * PCB->Bloat)
3773         if (IsPadInPolygon(pad,polygon))
3774           {
3775             AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3776             SET_FLAG (TheFlag, pad);
3777             message = _("Pad with insufficient clearance inside polygon\n");
3778             goto doIsBad;
3779           }
3780       break;
3781     case PIN_TYPE:
3782       if (pin->Clearance < 2 * PCB->Bloat)
3783         {
3784           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3785           SET_FLAG (TheFlag, pin);
3786           message = _("Pin with insufficient clearance inside polygon\n");
3787           goto doIsBad;
3788         }
3789       break;
3790     case VIA_TYPE:
3791       if (pin->Clearance && pin->Clearance < 2 * PCB->Bloat)
3792         {
3793           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3794           SET_FLAG (TheFlag, pin);
3795           message = _("Via with insufficient clearance inside polygon\n");
3796           goto doIsBad;
3797         }
3798       break;
3799     default:
3800       Message ("hace: Bad Plow object in callback\n");
3801     }
3802   return 0;
3803
3804 doIsBad:
3805   AddObjectToFlagUndoList (POLYGON_TYPE, layer, polygon, polygon);
3806   SET_FLAG (FOUNDFLAG, polygon);
3807   DrawPolygon (layer, polygon, 0);
3808   DrawObject (type, ptr1, ptr2, 0);
3809   drcerr_count++;
3810   LocateError (&x, &y);
3811   BuildObjectList (&object_count, &object_id_list, &object_type_list);
3812   violation = pcb_drc_violation_new (message,
3813                                      _("Circuits that are too close may bridge during imaging, etching,\n"
3814                                        "plating, or soldering processes resulting in a direct short."),
3815                                      x, y,
3816                                      0,     /* ANGLE OF ERROR UNKNOWN */
3817                                      FALSE, /* MEASUREMENT OF ERROR UNKNOWN */
3818                                      0,     /* MAGNITUDE OF ERROR UNKNOWN */
3819                                      LENGTH_TO_HUMAN(PCB->Bloat),
3820                                      LENGTH_DIGITS,
3821                                      LENGTH_UNITS_STRING,
3822                                      object_count,
3823                                      object_id_list,
3824                                      object_type_list);
3825   append_drc_violation (violation);
3826   pcb_drc_violation_free (violation);
3827   free (object_id_list);
3828   free (object_type_list);
3829   if (!throw_drc_dialog())
3830     {
3831       IsBad = True;
3832       return 1;
3833     }
3834   IncrementUndoSerialNumber ();
3835   Undo (True);
3836   return 0;
3837 }
3838
3839 /*-----------------------------------------------------------------------------
3840  * Check for DRC violations
3841  * see if the connectivity changes when everything is bloated, or shrunk
3842  */
3843 int
3844 DRCAll (void)
3845 {
3846   LocationType x, y;
3847   int object_count;
3848   long int *object_id_list;
3849   int *object_type_list;
3850   DrcViolationType *violation;
3851   int tmpcnt;
3852   int nopastecnt = 0;
3853
3854   reset_drc_dialog_message();
3855
3856   IsBad = False;
3857   drcerr_count = 0;
3858   SaveStackAndVisibility ();
3859   ResetStackAndVisibility ();
3860   hid_action ("LayersChanged");
3861   InitConnectionLookup ();
3862
3863   TheFlag = FOUNDFLAG | DRCFLAG | SELECTEDFLAG;
3864
3865   ResetConnections (True);
3866
3867   User = False;
3868
3869   ELEMENT_LOOP (PCB->Data);
3870   {
3871     PIN_LOOP (element);
3872     {
3873       if (!TEST_FLAG (DRCFLAG, pin)
3874           && DRCFind (PIN_TYPE, (void *) element, (void *) pin, (void *) pin))
3875         {
3876           IsBad = True;
3877           break;
3878         }
3879     }
3880     END_LOOP;
3881     if (IsBad)
3882       break;
3883     PAD_LOOP (element);
3884     {
3885
3886       /* count up how many pads have no solderpaste openings */
3887       if (TEST_FLAG (NOPASTEFLAG, pad))
3888         nopastecnt++;
3889
3890       if (!TEST_FLAG (DRCFLAG, pad)
3891           && DRCFind (PAD_TYPE, (void *) element, (void *) pad, (void *) pad))
3892         {
3893           IsBad = True;
3894           break;
3895         }
3896     }
3897     END_LOOP;
3898     if (IsBad)
3899       break;
3900   }
3901   END_LOOP;
3902   if (!IsBad)
3903     VIA_LOOP (PCB->Data);
3904   {
3905     if (!TEST_FLAG (DRCFLAG, via)
3906         && DRCFind (VIA_TYPE, (void *) via, (void *) via, (void *) via))
3907       {
3908         IsBad = True;
3909         break;
3910       }
3911   }
3912   END_LOOP;
3913
3914   TheFlag = (IsBad) ? DRCFLAG : (FOUNDFLAG | DRCFLAG | SELECTEDFLAG);
3915   ResetConnections (False);
3916   TheFlag = SELECTEDFLAG;
3917   /* check minimum widths and polygon clearances */
3918   if (!IsBad)
3919     {
3920       COPPERLINE_LOOP (PCB->Data);
3921       {
3922         /* check line clearances in polygons */
3923         PlowsPolygon (PCB->Data, LINE_TYPE, layer, line, drc_callback);
3924         if (IsBad)
3925           break;
3926         if (line->Thickness < PCB->minWid)
3927           {
3928             AddObjectToFlagUndoList (LINE_TYPE, layer, line, line);
3929             SET_FLAG (TheFlag, line);
3930             DrawLine (layer, line, 0);
3931             drcerr_count++;
3932             SetThing (LINE_TYPE, layer, line, line);
3933             LocateError (&x, &y);
3934             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3935             violation = pcb_drc_violation_new (_("Line width is too thin"),
3936                                                _("Process specifications dictate a minimum feature-width\n"
3937                                                  "that can reliably be reproduced"),
3938                                                x, y,
3939                                                0,    /* ANGLE OF ERROR UNKNOWN */
3940                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3941                                                LENGTH_TO_HUMAN(line->Thickness),
3942                                                LENGTH_TO_HUMAN(PCB->minWid),
3943                                                LENGTH_DIGITS,
3944                                                LENGTH_UNITS_STRING,
3945                                                object_count,
3946                                                object_id_list,
3947                                                object_type_list);
3948             append_drc_violation (violation);
3949             pcb_drc_violation_free (violation);
3950             free (object_id_list);
3951             free (object_type_list);
3952             if (!throw_drc_dialog())
3953               {
3954                 IsBad = True;
3955                 break;
3956               }
3957             IncrementUndoSerialNumber ();
3958             Undo (False);
3959           }
3960       }
3961       ENDALL_LOOP;
3962     }
3963   if (!IsBad)
3964     {
3965       COPPERARC_LOOP (PCB->Data);
3966       {
3967         PlowsPolygon (PCB->Data, ARC_TYPE, layer, arc, drc_callback);
3968         if (IsBad)
3969           break;
3970         if (arc->Thickness < PCB->minWid)
3971           {
3972             AddObjectToFlagUndoList (ARC_TYPE, layer, arc, arc);
3973             SET_FLAG (TheFlag, arc);
3974             DrawArc (layer, arc, 0);
3975             drcerr_count++;
3976             SetThing (ARC_TYPE, layer, arc, arc);
3977             LocateError (&x, &y);
3978             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3979             violation = pcb_drc_violation_new (_("Arc width is too thin"),
3980                                                _("Process specifications dictate a minimum feature-width\n"
3981                                                  "that can reliably be reproduced"),
3982                                                x, y,
3983                                                0,    /* ANGLE OF ERROR UNKNOWN */
3984                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3985                                                LENGTH_TO_HUMAN(arc->Thickness),
3986                                                LENGTH_TO_HUMAN(PCB->minWid),
3987                                                LENGTH_DIGITS,
3988                                                LENGTH_UNITS_STRING,
3989                                                object_count,
3990                                                object_id_list,
3991                                                object_type_list);
3992             append_drc_violation (violation);
3993             pcb_drc_violation_free (violation);
3994             free (object_id_list);
3995             free (object_type_list);
3996             if (!throw_drc_dialog())
3997               {
3998                 IsBad = True;
3999                 break;
4000               }
4001             IncrementUndoSerialNumber ();
4002             Undo (False);
4003           }
4004       }
4005       ENDALL_LOOP;
4006     }
4007   if (!IsBad)
4008     {
4009       ALLPIN_LOOP (PCB->Data);
4010       {
4011         PlowsPolygon (PCB->Data, PIN_TYPE, element, pin, drc_callback);
4012         if (IsBad)
4013           break;
4014         if (!TEST_FLAG (HOLEFLAG, pin) &&
4015             pin->Thickness - pin->DrillingHole < 2 * PCB->minRing)
4016           {
4017             AddObjectToFlagUndoList (PIN_TYPE, element, pin, pin);
4018             SET_FLAG (TheFlag, pin);
4019             DrawPin (pin, 0);
4020             drcerr_count++;
4021             SetThing (PIN_TYPE, element, pin, pin);
4022             LocateError (&x, &y);
4023             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4024             violation = pcb_drc_violation_new (_("Pin annular ring too small"),
4025                                                _("Annular rings that are too small may erode during etching,\n"
4026                                                  "resulting in a broken connection"),
4027                                                x, y,
4028                                                0,    /* ANGLE OF ERROR UNKNOWN */
4029                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4030                                                LENGTH_TO_HUMAN((pin->Thickness - pin->DrillingHole) / 2),
4031                                                LENGTH_TO_HUMAN(PCB->minRing),
4032                                                LENGTH_DIGITS,
4033                                                LENGTH_UNITS_STRING,
4034                                                object_count,
4035                                                object_id_list,
4036                                                object_type_list);
4037             append_drc_violation (violation);
4038             pcb_drc_violation_free (violation);
4039             free (object_id_list);
4040             free (object_type_list);
4041             if (!throw_drc_dialog())
4042               {
4043                 IsBad = True;
4044                 break;
4045               }
4046             IncrementUndoSerialNumber ();
4047             Undo (False);
4048           }
4049         if (pin->DrillingHole < PCB->minDrill)
4050           {
4051             AddObjectToFlagUndoList (PIN_TYPE, element, pin, pin);
4052             SET_FLAG (TheFlag, pin);
4053             DrawPin (pin, 0);
4054             drcerr_count++;
4055             SetThing (PIN_TYPE, element, pin, pin);
4056             LocateError (&x, &y);
4057             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4058             violation = pcb_drc_violation_new (_("Pin drill size is too small"),
4059                                                _("Process rules dictate the minimum drill size which can be used"),
4060                                                x, y,
4061                                                0,    /* ANGLE OF ERROR UNKNOWN */
4062                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4063                                                LENGTH_TO_HUMAN(pin->DrillingHole),
4064                                                LENGTH_TO_HUMAN(PCB->minDrill),
4065                                                LENGTH_DIGITS,
4066                                                LENGTH_UNITS_STRING,
4067                                                object_count,
4068                                                object_id_list,
4069                                                object_type_list);
4070             append_drc_violation (violation);
4071             pcb_drc_violation_free (violation);
4072             free (object_id_list);
4073             free (object_type_list);
4074             if (!throw_drc_dialog())
4075               {
4076                 IsBad = True;
4077                 break;
4078               }
4079             IncrementUndoSerialNumber ();
4080             Undo (False);
4081           }
4082       }
4083       ENDALL_LOOP;
4084     }
4085   if (!IsBad)
4086     {
4087       ALLPAD_LOOP (PCB->Data);
4088       {
4089         PlowsPolygon (PCB->Data, PAD_TYPE, element, pad, drc_callback);
4090         if (IsBad)
4091           break;
4092         if (pad->Thickness < PCB->minWid)
4093           {
4094             AddObjectToFlagUndoList (PAD_TYPE, element, pad, pad);
4095             SET_FLAG (TheFlag, pad);
4096             DrawPad (pad, 0);
4097             drcerr_count++;
4098             SetThing (PAD_TYPE, element, pad, pad);
4099             LocateError (&x, &y);
4100             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4101             violation = pcb_drc_violation_new (_("Pad is too thin"),
4102                                                _("Pads which are too thin may erode during etching,\n"
4103                                                   "resulting in a broken or unreliable connection"),
4104                                                x, y,
4105                                                0,    /* ANGLE OF ERROR UNKNOWN */
4106                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4107                                                LENGTH_TO_HUMAN(pad->Thickness),
4108                                                LENGTH_TO_HUMAN(PCB->minWid),
4109                                                LENGTH_DIGITS,
4110                                                LENGTH_UNITS_STRING,
4111                                                object_count,
4112                                                object_id_list,
4113                                                object_type_list);
4114             append_drc_violation (violation);
4115             pcb_drc_violation_free (violation);
4116             free (object_id_list);
4117             free (object_type_list);
4118             if (!throw_drc_dialog())
4119               {
4120                 IsBad = True;
4121                 break;
4122               }
4123             IncrementUndoSerialNumber ();
4124             Undo (False);
4125           }
4126       }
4127       ENDALL_LOOP;
4128     }
4129   if (!IsBad)
4130     {
4131       VIA_LOOP (PCB->Data);
4132       {
4133         PlowsPolygon (PCB->Data, VIA_TYPE, via, via, drc_callback);
4134         if (IsBad)
4135           break;
4136         if (!TEST_FLAG (HOLEFLAG, via) &&
4137             via->Thickness - via->DrillingHole < 2 * PCB->minRing)
4138           {
4139             AddObjectToFlagUndoList (VIA_TYPE, via, via, via);
4140             SET_FLAG (TheFlag, via);
4141             DrawVia (via, 0);
4142             drcerr_count++;
4143             SetThing (VIA_TYPE, via, via, via);
4144             LocateError (&x, &y);
4145             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4146             violation = pcb_drc_violation_new (_("Via annular ring too small"),
4147                                                _("Annular rings that are too small may erode during etching,\n"
4148                                                  "resulting in a broken connection"),
4149                                                x, y,
4150                                                0,    /* ANGLE OF ERROR UNKNOWN */
4151                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4152                                                LENGTH_TO_HUMAN((via->Thickness - via->DrillingHole) / 2),
4153                                                LENGTH_TO_HUMAN(PCB->minRing),
4154                                                LENGTH_DIGITS,
4155                                                LENGTH_UNITS_STRING,
4156                                                object_count,
4157                                                object_id_list,
4158                                                object_type_list);
4159             append_drc_violation (violation);
4160             pcb_drc_violation_free (violation);
4161             free (object_id_list);
4162             free (object_type_list);
4163             if (!throw_drc_dialog())
4164               {
4165                 IsBad = True;
4166                 break;
4167               }
4168             IncrementUndoSerialNumber ();
4169             Undo (False);
4170           }
4171         if (via->DrillingHole < PCB->minDrill)
4172           {
4173             AddObjectToFlagUndoList (VIA_TYPE, via, via, via);
4174             SET_FLAG (TheFlag, via);
4175             DrawVia (via, 0);
4176             drcerr_count++;
4177             SetThing (VIA_TYPE, via, via, via);
4178             LocateError (&x, &y);
4179             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4180             violation = pcb_drc_violation_new (_("Via drill size is too small"),
4181                                                _("Process rules dictate the minimum drill size which can be used"),
4182                                                x, y,
4183                                                0,    /* ANGLE OF ERROR UNKNOWN */
4184                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4185                                                LENGTH_TO_HUMAN(via->DrillingHole),
4186                                                LENGTH_TO_HUMAN(PCB->minDrill),
4187                                                LENGTH_DIGITS,
4188                                                LENGTH_UNITS_STRING,
4189                                                object_count,
4190                                                object_id_list,
4191                                                object_type_list);
4192             append_drc_violation (violation);
4193             pcb_drc_violation_free (violation);
4194             free (object_id_list);
4195             free (object_type_list);
4196             if (!throw_drc_dialog())
4197               {
4198                 IsBad = True;
4199                 break;
4200               }
4201             IncrementUndoSerialNumber ();
4202             Undo (False);
4203           }
4204       }
4205       END_LOOP;
4206     }
4207
4208   FreeConnectionLookupMemory ();
4209   TheFlag = FOUNDFLAG;
4210   Bloat = 0;
4211   fBloat = 0.0;
4212
4213   /* check silkscreen minimum widths outside of elements */
4214   /* XXX - need to check text and polygons too! */
4215   TheFlag = SELECTEDFLAG;
4216   if (!IsBad)
4217     {
4218       SILKLINE_LOOP (PCB->Data);
4219       {
4220         if (line->Thickness < PCB->minSlk)
4221           {
4222             SET_FLAG (TheFlag, line);
4223             DrawLine (layer, line, 0);
4224             drcerr_count++;
4225             SetThing (LINE_TYPE, layer, line, line);
4226             LocateError (&x, &y);
4227             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4228             violation = pcb_drc_violation_new (_("Silk line is too thin"),
4229                                                _("Process specifications dictate a minimum silkscreen feature-width\n"
4230                                                  "that can reliably be reproduced"),
4231                                                x, y,
4232                                                0,    /* ANGLE OF ERROR UNKNOWN */
4233                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4234                                                LENGTH_TO_HUMAN(line->Thickness),
4235                                                LENGTH_TO_HUMAN(PCB->minSlk),
4236                                                LENGTH_DIGITS,
4237                                                LENGTH_UNITS_STRING,
4238                                                object_count,
4239                                                object_id_list,
4240                                                object_type_list);
4241             append_drc_violation (violation);
4242             pcb_drc_violation_free (violation);
4243             free (object_id_list);
4244             free (object_type_list);
4245             if (!throw_drc_dialog())
4246               {
4247                 IsBad = True;
4248                 break;
4249               }
4250           }
4251       }
4252       ENDALL_LOOP;
4253     }
4254
4255   /* check silkscreen minimum widths inside of elements */
4256   /* XXX - need to check text and polygons too! */
4257   TheFlag = SELECTEDFLAG;
4258   if (!IsBad)
4259     {
4260       ELEMENT_LOOP (PCB->Data);
4261       {
4262         tmpcnt = 0;
4263         ELEMENTLINE_LOOP (element);
4264         {
4265           if (line->Thickness < PCB->minSlk)
4266             tmpcnt++;
4267         }
4268         END_LOOP;
4269         if (tmpcnt > 0)
4270           {
4271             char *title;
4272             char *name;
4273             char *buffer;
4274             int buflen;
4275
4276             SET_FLAG (TheFlag, element);
4277             DrawElement (element, 0);
4278             drcerr_count++;
4279             SetThing (ELEMENT_TYPE, element, element, element);
4280             LocateError (&x, &y);
4281             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4282
4283             title = _("Element %s has %i silk lines which are too thin");
4284             name = UNKNOWN (NAMEONPCB_NAME (element));
4285
4286             /* -4 is for the %s and %i place-holders */
4287             /* +11 is the max printed length for a 32 bit integer */
4288             /* +1 is for the \0 termination */
4289             buflen = strlen (title) - 4 + strlen (name) + 11 + 1;
4290             buffer = malloc (buflen);
4291             snprintf (buffer, buflen, title, name, tmpcnt);
4292
4293             violation = pcb_drc_violation_new (buffer,
4294                                                _("Process specifications dictate a minimum silkscreen\n"
4295                                                "feature-width that can reliably be reproduced"),
4296                                                x, y,
4297                                                0,    /* ANGLE OF ERROR UNKNOWN */
4298                                                0,    /* MINIMUM OFFENDING WIDTH UNKNOWN */
4299                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4300                                                LENGTH_TO_HUMAN(PCB->minSlk),
4301                                                LENGTH_DIGITS,
4302                                                LENGTH_UNITS_STRING,
4303                                                object_count,
4304                                                object_id_list,
4305                                                object_type_list);
4306             free (buffer);
4307             append_drc_violation (violation);
4308             pcb_drc_violation_free (violation);
4309             free (object_id_list);
4310             free (object_type_list);
4311             if (!throw_drc_dialog())
4312               {
4313                 IsBad = True;
4314                 break;
4315               }
4316           }
4317       }
4318       END_LOOP;
4319     }
4320
4321
4322   if (IsBad)
4323     {
4324       IncrementUndoSerialNumber ();
4325     }
4326
4327
4328   RestoreStackAndVisibility ();
4329   hid_action ("LayersChanged");
4330   gui->invalidate_all ();
4331
4332   if (nopastecnt > 0)
4333     {
4334       Message (_("Warning:  %d pad%s the nopaste flag set.\n"),
4335                nopastecnt,
4336                nopastecnt > 1 ? "s have" : " has");
4337     }
4338   return IsBad ? -drcerr_count : drcerr_count;
4339 }
4340
4341 /*----------------------------------------------------------------------------
4342  * Locate the coordinatates of offending item (thing)
4343  */
4344 static void
4345 LocateError (LocationType *x, LocationType *y)
4346 {
4347   switch (thing_type)
4348     {
4349     case LINE_TYPE:
4350       {
4351         LineTypePtr line = (LineTypePtr) thing_ptr3;
4352         *x = (line->Point1.X + line->Point2.X) / 2;
4353         *y = (line->Point1.Y + line->Point2.Y) / 2;
4354         break;
4355       }
4356     case ARC_TYPE:
4357       {
4358         ArcTypePtr arc = (ArcTypePtr) thing_ptr3;
4359         *x = arc->X;
4360         *y = arc->Y;
4361         break;
4362       }
4363     case POLYGON_TYPE:
4364       {
4365         PolygonTypePtr polygon = (PolygonTypePtr) thing_ptr3;
4366         *x =
4367           (polygon->Clipped->contours->xmin +
4368            polygon->Clipped->contours->xmax) / 2;
4369         *y =
4370           (polygon->Clipped->contours->ymin +
4371            polygon->Clipped->contours->ymax) / 2;
4372         break;
4373       }
4374     case PIN_TYPE:
4375     case VIA_TYPE:
4376       {
4377         PinTypePtr pin = (PinTypePtr) thing_ptr3;
4378         *x = pin->X;
4379         *y = pin->Y;
4380         break;
4381       }
4382     case PAD_TYPE:
4383       {
4384         PadTypePtr pad = (PadTypePtr) thing_ptr3;
4385         *x = (pad->Point1.X + pad->Point2.X) / 2;
4386         *y = (pad->Point1.Y + pad->Point2.Y) / 2;
4387         break;
4388       }
4389     case ELEMENT_TYPE:
4390       {
4391         ElementTypePtr element = (ElementTypePtr) thing_ptr3;
4392         *x = element->MarkX;
4393         *y = element->MarkY;
4394         break;
4395       }
4396     default:
4397       return;
4398     }
4399 }
4400
4401
4402 /*----------------------------------------------------------------------------
4403  * Build a list of the of offending items by ID. (Currently just "thing")
4404  */
4405 static void
4406 BuildObjectList (int *object_count, long int **object_id_list, int **object_type_list)
4407 {
4408   *object_count = 0;
4409   *object_id_list = NULL;
4410
4411   switch (thing_type)
4412     {
4413     case LINE_TYPE:
4414     case ARC_TYPE:
4415     case POLYGON_TYPE:
4416     case PIN_TYPE:
4417     case VIA_TYPE:
4418     case PAD_TYPE:
4419     case ELEMENT_TYPE:
4420       *object_count = 1;
4421       *object_id_list = malloc (sizeof (long int));
4422       *object_type_list = malloc (sizeof (int));
4423       **object_id_list = ((AnyObjectType *)thing_ptr3)->ID;
4424       **object_type_list = thing_type;
4425       return;
4426
4427     default:
4428       return;
4429     }
4430 }
4431
4432
4433 /*----------------------------------------------------------------------------
4434  * center the display to show the offending item (thing)
4435  */
4436 static void
4437 GotoError (void)
4438 {
4439   LocationType X, Y;
4440
4441   LocateError (&X, &Y);
4442
4443   switch (thing_type)
4444     {
4445     case LINE_TYPE:
4446     case ARC_TYPE:
4447     case POLYGON_TYPE:
4448       ChangeGroupVisibility (GetLayerNumber
4449                              (PCB->Data, (LayerTypePtr) thing_ptr1), True,
4450                              True);
4451     }
4452   CenterDisplay (X, Y, False);
4453 }
4454
4455 void
4456 InitConnectionLookup (void)
4457 {
4458   InitComponentLookup ();
4459   InitLayoutLookup ();
4460 }
4461
4462 void
4463 FreeConnectionLookupMemory (void)
4464 {
4465   FreeComponentLookupMemory ();
4466   FreeLayoutLookupMemory ();
4467 }