src/search.c

   1 /* $Id$ */
   2
   3 /*
   4  *                            COPYRIGHT
   5  *
   6  *  PCB, interactive printed circuit board design
   7  *  Copyright (C) 1994,1995,1996 Thomas Nau
   8  *
   9  *  This program is free software; you can redistribute it and/or modify
  10  *  it under the terms of the GNU General Public License as published by
  11  *  the Free Software Foundation; either version 2 of the License, or
  12  *  (at your option) any later version.
  13  *
  14  *  This program is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  *  GNU General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU General Public License
  20  *  along with this program; if not, write to the Free Software
  21  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  22  *
  23  *  Contact addresses for paper mail and Email:
  24  *  Thomas Nau, Schlehenweg 15, 88471 Baustetten, Germany
  25  *  Thomas.Nau@rz.uni-ulm.de
  26  *
  27  */
  28
  29
  30 /* search routines
  31  * some of the functions use dummy parameters
  32  */
  33
  34 #ifdef HAVE_CONFIG_H
  35 #include "config.h"
  36 #endif
  37
  38 #include <math.h>
  39 #include <setjmp.h>
  40
  41 #include "global.h"
  42
  43 #include "box.h"
  44 #include "data.h"
  45 #include "draw.h"
  46 #include "error.h"
  47 #include "find.h"
  48 #include "misc.h"
  49 #include "polygon.h"
  50 #include "rtree.h"
  51 #include "search.h"
  52
  53 #ifdef HAVE_LIBDMALLOC
  54 #include <dmalloc.h>
  55 #endif
  56
  57 RCSID ("$Id$");
  58
  59
  60 /* ---------------------------------------------------------------------------
  61  * some local identifiers
  62  */
  63 static double PosX, PosY;               /* search position for subroutines */
  64 static Coord SearchRadius;
  65 static BoxType SearchBox;
  66 static LayerTypePtr SearchLayer;
  67
  68 /* ---------------------------------------------------------------------------
  69  * some local prototypes.  The first parameter includes LOCKED_TYPE if we
  70  * want to include locked types in the search.
  71  */
  72 static bool SearchLineByLocation (int, LayerTypePtr *, LineTypePtr *,
  73                                      LineTypePtr *);
  74 static bool SearchArcByLocation (int, LayerTypePtr *, ArcTypePtr *,
  75                                     ArcTypePtr *);
  76 static bool SearchRatLineByLocation (int, RatTypePtr *, RatTypePtr *,
  77                                         RatTypePtr *);
  78 static bool SearchTextByLocation (int, LayerTypePtr *, TextTypePtr *,
  79                                      TextTypePtr *);
  80 static bool SearchPolygonByLocation (int, LayerTypePtr *, PolygonTypePtr *,
  81                                         PolygonTypePtr *);
  82 static bool SearchPinByLocation (int, ElementTypePtr *, PinTypePtr *,
  83                                     PinTypePtr *);
  84 static bool SearchPadByLocation (int, ElementTypePtr *, PadTypePtr *,
  85                                     PadTypePtr *, bool);
  86 static bool SearchViaByLocation (int, PinTypePtr *, PinTypePtr *,
  87                                     PinTypePtr *);
  88 static bool SearchElementNameByLocation (int, ElementTypePtr *,
  89                                             TextTypePtr *, TextTypePtr *,
  90                                             bool);
  91 static bool SearchLinePointByLocation (int, LayerTypePtr *, LineTypePtr *,
  92                                           PointTypePtr *);
  93 static bool SearchPointByLocation (int, LayerTypePtr *, PolygonTypePtr *,
  94                                       PointTypePtr *);
  95 static bool SearchElementByLocation (int, ElementTypePtr *,
  96                                         ElementTypePtr *, ElementTypePtr *,
  97                                         bool);
  98
  99 /* ---------------------------------------------------------------------------
 100  * searches a via
 101  */
 102 struct ans_info
 103 {
 104   void **ptr1, **ptr2, **ptr3;
 105   bool BackToo;
 106   double area;
 107   jmp_buf env;
 108   int locked;                   /* This will be zero or LOCKFLAG */
 109 };
 110
 111 static int
 112 pinorvia_callback (const BoxType * box, void *cl)
 113 {
 114   struct ans_info *i = (struct ans_info *) cl;
 115   PinTypePtr pin = (PinTypePtr) box;
 116   AnyObjectType *ptr1 = pin->Element ? pin->Element : pin;
 117
 118   if (TEST_FLAG (i->locked, ptr1))
 119     return 0;
 120
 121   if (!IsPointOnPin (PosX, PosY, SearchRadius, pin))
 122     return 0;
 123   *i->ptr1 = ptr1;
 124   *i->ptr2 = *i->ptr3 = pin;
 125   longjmp (i->env, 1);
 126   return 1;                     /* never reached */
 127 }
 128
 129 static bool
 130 SearchViaByLocation (int locked, PinTypePtr * Via, PinTypePtr * Dummy1,
 131                      PinTypePtr * Dummy2)
 132 {
 133   struct ans_info info;
 134
 135   /* search only if via-layer is visible */
 136   if (!PCB->ViaOn)
 137     return false;
 138
 139   info.ptr1 = (void **) Via;
 140   info.ptr2 = (void **) Dummy1;
 141   info.ptr3 = (void **) Dummy2;
 142   info.locked = (locked & LOCKED_TYPE) ? 0 : LOCKFLAG;
 143
 144   if (setjmp (info.env) == 0)
 145     {
 146       r_search (PCB->Data->via_tree, &SearchBox, NULL, pinorvia_callback,
 147                 &info);
 148       return false;
 149     }
 150   return true;
 151 }
 152
 153 /* ---------------------------------------------------------------------------
 154  * searches a pin
 155  * starts with the newest element
 156  */
 157 static bool
 158 SearchPinByLocation (int locked, ElementTypePtr * Element, PinTypePtr * Pin,
 159                      PinTypePtr * Dummy)
 160 {
 161   struct ans_info info;
 162
 163   /* search only if pin-layer is visible */
 164   if (!PCB->PinOn)
 165     return false;
 166   info.ptr1 = (void **) Element;
 167   info.ptr2 = (void **) Pin;
 168   info.ptr3 = (void **) Dummy;
 169   info.locked = (locked & LOCKED_TYPE) ? 0 : LOCKFLAG;
 170
 171   if (setjmp (info.env) == 0)
 172     r_search (PCB->Data->pin_tree, &SearchBox, NULL, pinorvia_callback,
 173               &info);
 174   else
 175     return true;
 176   return false;
 177 }
 178
 179 static int
 180 pad_callback (const BoxType * b, void *cl)
 181 {
 182   PadTypePtr pad = (PadTypePtr) b;
 183   struct ans_info *i = (struct ans_info *) cl;
 184   AnyObjectType *ptr1 = pad->Element;
 185
 186   if (TEST_FLAG (i->locked, ptr1))
 187     return 0;
 188
 189   if (FRONT (pad) || i->BackToo)
 190     {
 191       if (IsPointInPad (PosX, PosY, SearchRadius, pad))
 192             {
 193               *i->ptr1 = ptr1;
 194               *i->ptr2 = *i->ptr3 = pad;
 195               longjmp (i->env, 1);
 196             }
 197         }
 198   return 0;
 199 }
 200
 201 /* ---------------------------------------------------------------------------
 202  * searches a pad
 203  * starts with the newest element
 204  */
 205 static bool
 206 SearchPadByLocation (int locked, ElementTypePtr * Element, PadTypePtr * Pad,
 207                      PadTypePtr * Dummy, bool BackToo)
 208 {
 209   struct ans_info info;
 210
 211   /* search only if pin-layer is visible */
 212   if (!PCB->PinOn)
 213     return (false);
 214   info.ptr1 = (void **) Element;
 215   info.ptr2 = (void **) Pad;
 216   info.ptr3 = (void **) Dummy;
 217   info.locked = (locked & LOCKED_TYPE) ? 0 : LOCKFLAG;
 218   info.BackToo = (BackToo && PCB->InvisibleObjectsOn);
 219   if (setjmp (info.env) == 0)
 220     r_search (PCB->Data->pad_tree, &SearchBox, NULL, pad_callback, &info);
 221   else
 222     return true;
 223   return false;
 224 }
 225
 226 /* ---------------------------------------------------------------------------
 227  * searches ordinary line on the SearchLayer
 228  */
 229
 230 struct line_info
 231 {
 232   LineTypePtr *Line;
 233   PointTypePtr *Point;
 234   double least;
 235   jmp_buf env;
 236   int locked;
 237 };
 238
 239 static int
 240 line_callback (const BoxType * box, void *cl)
 241 {
 242   struct line_info *i = (struct line_info *) cl;
 243   LineTypePtr l = (LineTypePtr) box;
 244
 245   if (TEST_FLAG (i->locked, l))
 246     return 0;
 247
 248   if (!IsPointInPad (PosX, PosY, SearchRadius, (PadTypePtr)l))
 249     return 0;
 250   *i->Line = l;
 251   *i->Point = (PointTypePtr) l;
 252   longjmp (i->env, 1);
 253   return 1;                     /* never reached */
 254 }
 255
 256
 257 static bool
 258 SearchLineByLocation (int locked, LayerTypePtr * Layer, LineTypePtr * Line,
 259                       LineTypePtr * Dummy)
 260 {
 261   struct line_info info;
 262
 263   info.Line = Line;
 264   info.Point = (PointTypePtr *) Dummy;
 265   info.locked = (locked & LOCKED_TYPE) ? 0 : LOCKFLAG;
 266
 267   *Layer = SearchLayer;
 268   if (setjmp (info.env) == 0)
 269     {
 270       r_search (SearchLayer->line_tree, &SearchBox, NULL, line_callback,
 271                 &info);
 272       return false;
 273     }
 274   return (true);
 275 }
 276
 277 static int
 278 rat_callback (const BoxType * box, void *cl)
 279 {
 280   LineTypePtr line = (LineTypePtr) box;
 281   struct ans_info *i = (struct ans_info *) cl;
 282
 283   if (TEST_FLAG (i->locked, line))
 284     return 0;
 285
 286   if (TEST_FLAG (VIAFLAG, line) ?
 287       (Distance (line->Point1.X, line->Point1.Y, PosX, PosY) <=
 288            line->Thickness * 2 + SearchRadius) :
 289       IsPointOnLine (PosX, PosY, SearchRadius, line))
 290     {
 291       *i->ptr1 = *i->ptr2 = *i->ptr3 = line;
 292       longjmp (i->env, 1);
 293     }
 294   return 0;
 295 }
 296
 297 /* ---------------------------------------------------------------------------
 298  * searches rat lines if they are visible
 299  */
 300 static bool
 301 SearchRatLineByLocation (int locked, RatTypePtr * Line, RatTypePtr * Dummy1,
 302                          RatTypePtr * Dummy2)
 303 {
 304   struct ans_info info;
 305
 306   info.ptr1 = (void **) Line;
 307   info.ptr2 = (void **) Dummy1;
 308   info.ptr3 = (void **) Dummy2;
 309   info.locked = (locked & LOCKED_TYPE) ? 0 : LOCKFLAG;
 310
 311   if (setjmp (info.env) == 0)
 312     {
 313       r_search (PCB->Data->rat_tree, &SearchBox, NULL, rat_callback, &info);
 314       return false;
 315     }
 316   return (true);
 317 }
 318
 319 /* ---------------------------------------------------------------------------
 320  * searches arc on the SearchLayer
 321  */
 322 struct arc_info
 323 {
 324   ArcTypePtr *Arc, *Dummy;
 325   PointTypePtr *Point;
 326   double least;
 327   jmp_buf env;
 328   int locked;
 329 };
 330
 331 static int
 332 arc_callback (const BoxType * box, void *cl)
 333 {
 334   struct arc_info *i = (struct arc_info *) cl;
 335   ArcTypePtr a = (ArcTypePtr) box;
 336
 337   if (TEST_FLAG (i->locked, a))
 338     return 0;
 339
 340   if (!IsPointOnArc (PosX, PosY, SearchRadius, a))
 341     return 0;
 342   *i->Arc = a;
 343   *i->Dummy = a;
 344   longjmp (i->env, 1);
 345   return 1;                     /* never reached */
 346 }
 347
 348
 349 static bool
 350 SearchArcByLocation (int locked, LayerTypePtr * Layer, ArcTypePtr * Arc,
 351                      ArcTypePtr * Dummy)
 352 {
 353   struct arc_info info;
 354
 355   info.Arc = Arc;
 356   info.Dummy = Dummy;
 357   info.locked = (locked & LOCKED_TYPE) ? 0 : LOCKFLAG;
 358
 359   *Layer = SearchLayer;
 360   if (setjmp (info.env) == 0)
 361     {
 362       r_search (SearchLayer->arc_tree, &SearchBox, NULL, arc_callback, &info);
 363       return false;
 364     }
 365   return (true);
 366 }
 367
 368 static int
 369 text_callback (const BoxType * box, void *cl)
 370 {
 371   TextTypePtr text = (TextTypePtr) box;
 372   struct ans_info *i = (struct ans_info *) cl;
 373
 374   if (TEST_FLAG (i->locked, text))
 375     return 0;
 376
 377   if (POINT_IN_BOX (PosX, PosY, &text->BoundingBox))
 378     {
 379       *i->ptr2 = *i->ptr3 = text;
 380       longjmp (i->env, 1);
 381     }
 382   return 0;
 383 }
 384
 385 /* ---------------------------------------------------------------------------
 386  * searches text on the SearchLayer
 387  */
 388 static bool
 389 SearchTextByLocation (int locked, LayerTypePtr * Layer, TextTypePtr * Text,
 390                       TextTypePtr * Dummy)
 391 {
 392   struct ans_info info;
 393
 394   *Layer = SearchLayer;
 395   info.ptr2 = (void **) Text;
 396   info.ptr3 = (void **) Dummy;
 397   info.locked = (locked & LOCKED_TYPE) ? 0 : LOCKFLAG;
 398
 399   if (setjmp (info.env) == 0)
 400     {
 401       r_search (SearchLayer->text_tree, &SearchBox, NULL, text_callback,
 402                 &info);
 403       return false;
 404     }
 405   return (true);
 406 }
 407
 408 static int
 409 polygon_callback (const BoxType * box, void *cl)
 410 {
 411   PolygonTypePtr polygon = (PolygonTypePtr) box;
 412   struct ans_info *i = (struct ans_info *) cl;
 413
 414   if (TEST_FLAG (i->locked, polygon))
 415     return 0;
 416
 417   if (IsPointInPolygon (PosX, PosY, SearchRadius, polygon))
 418     {
 419       *i->ptr2 = *i->ptr3 = polygon;
 420       longjmp (i->env, 1);
 421     }
 422   return 0;
 423 }
 424
 425
 426 /* ---------------------------------------------------------------------------
 427  * searches a polygon on the SearchLayer
 428  */
 429 static bool
 430 SearchPolygonByLocation (int locked, LayerTypePtr * Layer,
 431                          PolygonTypePtr * Polygon, PolygonTypePtr * Dummy)
 432 {
 433   struct ans_info info;
 434
 435   *Layer = SearchLayer;
 436   info.ptr2 = (void **) Polygon;
 437   info.ptr3 = (void **) Dummy;
 438   info.locked = (locked & LOCKED_TYPE) ? 0 : LOCKFLAG;
 439
 440   if (setjmp (info.env) == 0)
 441     {
 442       r_search (SearchLayer->polygon_tree, &SearchBox, NULL, polygon_callback,
 443                 &info);
 444       return false;
 445     }
 446   return (true);
 447 }
 448
 449 static int
 450 linepoint_callback (const BoxType * b, void *cl)
 451 {
 452   LineTypePtr line = (LineTypePtr) b;
 453   struct line_info *i = (struct line_info *) cl;
 454   int ret_val = 0;
 455   double d;
 456
 457   if (TEST_FLAG (i->locked, line))
 458     return 0;
 459
 460   /* some stupid code to check both points */
 461   d = Distance (PosX, PosY, line->Point1.X, line->Point1.Y);
 462   if (d < i->least)
 463     {
 464       i->least = d;
 465       *i->Line = line;
 466       *i->Point = &line->Point1;
 467       ret_val = 1;
 468     }
 469
 470   d = Distance (PosX, PosY, line->Point2.X, line->Point2.Y);
 471   if (d < i->least)
 472     {
 473       i->least = d;
 474       *i->Line = line;
 475       *i->Point = &line->Point2;
 476       ret_val = 1;
 477     }
 478   return ret_val;
 479 }
 480
 481 /* ---------------------------------------------------------------------------
 482  * searches a line-point on all the search layer
 483  */
 484 static bool
 485 SearchLinePointByLocation (int locked, LayerTypePtr * Layer,
 486                            LineTypePtr * Line, PointTypePtr * Point)
 487 {
 488   struct line_info info;
 489   *Layer = SearchLayer;
 490   info.Line = Line;
 491   info.Point = Point;
 492   *Point = NULL;
 493   info.least = MAX_LINE_POINT_DISTANCE + SearchRadius;
 494   info.locked = (locked & LOCKED_TYPE) ? 0 : LOCKFLAG;
 495   if (r_search
 496       (SearchLayer->line_tree, &SearchBox, NULL, linepoint_callback, &info))
 497     return true;
 498   return false;
 499 }
 500
 501 static int
 502 arcpoint_callback (const BoxType * b, void *cl)
 503 {
 504   ArcTypePtr arc = (ArcTypePtr) b;
 505   struct arc_info *i = (struct arc_info *) cl;
 506   int ret_val = 0;
 507   double d;
 508
 509   if (TEST_FLAG (i->locked, arc))
 510     return 0;
 511
 512   d = Distance (PosX, PosY, arc->Point1.X, arc->Point1.Y);
 513   if (d < i->least)
 514     {
 515       i->least = d;
 516       *i->Arc = arc;
 517       *i->Point = &arc->Point1;
 518       ret_val = 1;
 519     }
 520
 521   d = Distance (PosX, PosY, arc->Point2.X, arc->Point2.Y);
 522   if (d < i->least)
 523     {
 524       i->least = d;
 525       *i->Arc = arc;
 526       *i->Point = &arc->Point2;
 527       ret_val = 1;
 528     }
 529   return ret_val;
 530 }
 531
 532 /* ---------------------------------------------------------------------------
 533  * searches an arc-point on all the search layer
 534  */
 535 static bool
 536 SearchArcPointByLocation (int locked, LayerType **Layer,
 537                           ArcType **arc, PointType **Point)
 538 {
 539   struct arc_info info;
 540   *Layer = SearchLayer;
 541   info.Arc = arc;
 542   info.Point = Point;
 543   *Point = NULL;
 544   info.least = MAX_ARC_POINT_DISTANCE + SearchRadius;
 545   info.locked = (locked & LOCKED_TYPE) ? 0 : LOCKFLAG;
 546   if (r_search
 547       (SearchLayer->arc_tree, &SearchBox, NULL, arcpoint_callback, &info))
 548     return true;
 549   return false;
 550 }
 551 /* ---------------------------------------------------------------------------
 552  * searches a polygon-point on all layers that are switched on
 553  * in layerstack order
 554  */
 555 static bool
 556 SearchPointByLocation (int locked, LayerTypePtr * Layer,
 557                        PolygonTypePtr * Polygon, PointTypePtr * Point)
 558 {
 559   double d, least;
 560   bool found = false;
 561
 562   least = SearchRadius + MAX_POLYGON_POINT_DISTANCE;
 563   *Layer = SearchLayer;
 564   POLYGON_LOOP (*Layer);
 565   {
 566     POLYGONPOINT_LOOP (polygon);
 567     {
 568       d = Distance (point->X, point->Y, PosX, PosY);
 569       if (d < least)
 570         {
 571           least = d;
 572           *Polygon = polygon;
 573           *Point = point;
 574           found = true;
 575         }
 576     }
 577     END_LOOP;
 578   }
 579   END_LOOP;
 580   if (found)
 581     return (true);
 582   return (false);
 583 }
 584
 585 static int
 586 name_callback (const BoxType * box, void *cl)
 587 {
 588   TextTypePtr text = (TextTypePtr) box;
 589   struct ans_info *i = (struct ans_info *) cl;
 590   ElementTypePtr element = (ElementTypePtr) text->Element;
 591   double newarea;
 592
 593   if (TEST_FLAG (i->locked, text))
 594     return 0;
 595
 596   if ((FRONT (element) || i->BackToo) && !TEST_FLAG (HIDENAMEFLAG, element) &&
 597       POINT_IN_BOX (PosX, PosY, &text->BoundingBox))
 598     {
 599       /* use the text with the smallest bounding box */
 600       newarea = (text->BoundingBox.X2 - text->BoundingBox.X1) *
 601         (double) (text->BoundingBox.Y2 - text->BoundingBox.Y1);
 602       if (newarea < i->area)
 603         {
 604           i->area = newarea;
 605           *i->ptr1 = element;
 606           *i->ptr2 = *i->ptr3 = text;
 607         }
 608       return 1;
 609     }
 610   return 0;
 611 }
 612
 613 /* ---------------------------------------------------------------------------
 614  * searches the name of an element
 615  * the search starts with the last element and goes back to the beginning
 616  */
 617 static bool
 618 SearchElementNameByLocation (int locked, ElementTypePtr * Element,
 619                              TextTypePtr * Text, TextTypePtr * Dummy,
 620                              bool BackToo)
 621 {
 622   struct ans_info info;
 623
 624   /* package layer have to be switched on */
 625   if (PCB->ElementOn)
 626     {
 627       info.ptr1 = (void **) Element;
 628       info.ptr2 = (void **) Text;
 629       info.ptr3 = (void **) Dummy;
 630       info.area = SQUARE (MAX_COORD);
 631       info.BackToo = (BackToo && PCB->InvisibleObjectsOn);
 632       info.locked = (locked & LOCKED_TYPE) ? 0 : LOCKFLAG;
 633       if (r_search (PCB->Data->name_tree[NAME_INDEX (PCB)], &SearchBox, NULL,
 634                     name_callback, &info))
 635         return true;
 636     }
 637   return (false);
 638 }
 639
 640 static int
 641 element_callback (const BoxType * box, void *cl)
 642 {
 643   ElementTypePtr element = (ElementTypePtr) box;
 644   struct ans_info *i = (struct ans_info *) cl;
 645   double newarea;
 646
 647   if (TEST_FLAG (i->locked, element))
 648     return 0;
 649
 650   if ((FRONT (element) || i->BackToo) &&
 651       POINT_IN_BOX (PosX, PosY, &element->VBox))
 652     {
 653       /* use the element with the smallest bounding box */
 654       newarea = (element->VBox.X2 - element->VBox.X1) *
 655         (double) (element->VBox.Y2 - element->VBox.Y1);
 656       if (newarea < i->area)
 657         {
 658           i->area = newarea;
 659           *i->ptr1 = *i->ptr2 = *i->ptr3 = element;
 660           return 1;
 661         }
 662     }
 663   return 0;
 664 }
 665
 666 /* ---------------------------------------------------------------------------
 667  * searches an element
 668  * the search starts with the last element and goes back to the beginning
 669  * if more than one element matches, the smallest one is taken
 670  */
 671 static bool
 672 SearchElementByLocation (int locked,
 673                          ElementTypePtr * Element,
 674                          ElementTypePtr * Dummy1, ElementTypePtr * Dummy2,
 675                          bool BackToo)
 676 {
 677   struct ans_info info;
 678
 679   /* Both package layers have to be switched on */
 680   if (PCB->ElementOn && PCB->PinOn)
 681     {
 682       info.ptr1 = (void **) Element;
 683       info.ptr2 = (void **) Dummy1;
 684       info.ptr3 = (void **) Dummy2;
 685       info.area = SQUARE (MAX_COORD);
 686       info.BackToo = (BackToo && PCB->InvisibleObjectsOn);
 687       info.locked = (locked & LOCKED_TYPE) ? 0 : LOCKFLAG;
 688       if (r_search
 689           (PCB->Data->element_tree, &SearchBox, NULL, element_callback,
 690            &info))
 691         return true;
 692     }
 693   return false;
 694 }
 695
 696 /* ---------------------------------------------------------------------------
 697  * checks if a point is on a pin
 698  */
 699 bool
 700 IsPointOnPin (Coord X, Coord Y, Coord Radius, PinTypePtr pin)
 701 {
 702   Coord t = PIN_SIZE (pin) / 2;
 703   if (TEST_FLAG (SQUAREFLAG, pin))
 704     {
 705       BoxType b;
 706
 707       b.X1 = pin->X - t;
 708       b.X2 = pin->X + t;
 709       b.Y1 = pin->Y - t;
 710       b.Y2 = pin->Y + t;
 711       if (IsPointInBox (X, Y, &b, Radius))
 712         return true;
 713     }
 714   else if (Distance (pin->X, pin->Y, X, Y) <= Radius + t)
 715     return true;
 716   return false;
 717 }
 718
 719 /* ---------------------------------------------------------------------------
 720  * checks if a rat-line end is on a PV
 721  */
 722 bool
 723 IsPointOnLineEnd (Coord X, Coord Y, RatTypePtr Line)
 724 {
 725   if (((X == Line->Point1.X) && (Y == Line->Point1.Y)) ||
 726       ((X == Line->Point2.X) && (Y == Line->Point2.Y)))
 727     return (true);
 728   return (false);
 729 }
 730
 731 /* ---------------------------------------------------------------------------
 732  * checks if a line intersects with a PV
 733  *
 734  * let the point be (X,Y) and the line (X1,Y1)(X2,Y2)
 735  * the length of the line is
 736  *
 737  *   L = ((X2-X1)^2 + (Y2-Y1)^2)^0.5
 738  *
 739  * let Q be the point of perpendicular projection of (X,Y) onto the line
 740  *
 741  *   QX = X1 + D1*(X2-X1) / L
 742  *   QY = Y1 + D1*(Y2-Y1) / L
 743  *
 744  * with (from vector geometry)
 745  *
 746  *        (Y1-Y)(Y1-Y2)+(X1-X)(X1-X2)
 747  *   D1 = ---------------------------
 748  *                     L
 749  *
 750  *   D1 < 0   Q is on backward extension of the line
 751  *   D1 > L   Q is on forward extension of the line
 752  *   else     Q is on the line
 753  *
 754  * the signed distance from (X,Y) to Q is
 755  *
 756  *        (Y2-Y1)(X-X1)-(X2-X1)(Y-Y1)
 757  *   D2 = ----------------------------
 758  *                     L
 759  *
 760  * Finally, D1 and D2 are orthogonal, so we can sum them easily
 761  * by pythagorean theorem.
 762  */
 763 bool
 764 IsPointOnLine (Coord X, Coord Y, Coord Radius, LineTypePtr Line)
 765 {
 766   double D1, D2, L;
 767
 768   /* Get length of segment */
 769   L = Distance (Line->Point1.X, Line->Point1.Y, Line->Point2.X, Line->Point2.Y);
 770   if (L < 0.1)
 771     return Distance (X, Y, Line->Point1.X, Line->Point1.Y) < Radius + Line->Thickness / 2;
 772
 773   /* Get distance from (X1, Y1) to Q (on the line) */
 774   D1 = ((double) (Y - Line->Point1.Y) * (Line->Point2.Y - Line->Point1.Y)
 775         + (double) (X - Line->Point1.X) * (Line->Point2.X - Line->Point1.X)) / L;
 776   /* Translate this into distance to Q from segment */
 777   if (D1 < 0)       D1 = -D1;
 778   else if (D1 > L)  D1 -= L;
 779   else              D1 = 0;
 780   /* Get distance from (X, Y) to Q */
 781   D2 = ((double) (X - Line->Point1.X) * (Line->Point2.Y - Line->Point1.Y)
 782         - (double) (Y - Line->Point1.Y) * (Line->Point2.X - Line->Point1.X)) / L;
 783   /* Total distance is then the pythagorean sum of these */
 784   return sqrt (D1*D1 + D2*D2) <= Radius + Line->Thickness / 2;
 785 }
 786
 787 /* ---------------------------------------------------------------------------
 788  * checks if a line crosses a rectangle
 789  */
 790 bool
 791 IsLineInRectangle (Coord X1, Coord Y1, Coord X2, Coord Y2, LineTypePtr Line)
 792 {
 793   LineType line;
 794
 795   /* first, see if point 1 is inside the rectangle */
 796   /* in case the whole line is inside the rectangle */
 797   if (X1 < Line->Point1.X && X2 > Line->Point1.X &&
 798       Y1 < Line->Point1.Y && Y2 > Line->Point1.Y)
 799     return (true);
 800   /* construct a set of dummy lines and check each of them */
 801   line.Thickness = 0;
 802   line.Flags = NoFlags ();
 803
 804   /* upper-left to upper-right corner */
 805   line.Point1.Y = line.Point2.Y = Y1;
 806   line.Point1.X = X1;
 807   line.Point2.X = X2;
 808   if (LineLineIntersect (&line, Line))
 809     return (true);
 810
 811   /* upper-right to lower-right corner */
 812   line.Point1.X = X2;
 813   line.Point1.Y = Y1;
 814   line.Point2.Y = Y2;
 815   if (LineLineIntersect (&line, Line))
 816     return (true);
 817
 818   /* lower-right to lower-left corner */
 819   line.Point1.Y = Y2;
 820   line.Point1.X = X1;
 821   line.Point2.X = X2;
 822   if (LineLineIntersect (&line, Line))
 823     return (true);
 824
 825   /* lower-left to upper-left corner */
 826   line.Point2.X = X1;
 827   line.Point1.Y = Y1;
 828   line.Point2.Y = Y2;
 829   if (LineLineIntersect (&line, Line))
 830     return (true);
 831
 832   return (false);
 833 }
 834
 835 static int /*checks if a point (of null radius) is in a slanted rectangle*/
 836 IsPointInQuadrangle(PointType p[4], PointTypePtr l)
 837 {
 838   Coord dx, dy, x, y;
 839   double prod0, prod1;
 840
 841   dx = p[1].X - p[0].X;
 842   dy = p[1].Y - p[0].Y;
 843   x = l->X - p[0].X;
 844   y = l->Y - p[0].Y;
 845   prod0 = (double) x * dx + (double) y * dy;
 846   x = l->X - p[1].X;
 847   y = l->Y - p[1].Y;
 848   prod1 = (double) x * dx + (double) y * dy;
 849   if (prod0 * prod1 <= 0)
 850     {
 851       dx = p[1].X - p[2].X;
 852       dy = p[1].Y - p[2].Y;
 853       prod0 = (double) x * dx + (double) y * dy;
 854       x = l->X - p[2].X;
 855       y = l->Y - p[2].Y;
 856       prod1 = (double) x * dx + (double) y * dy;
 857       if (prod0 * prod1 <= 0)
 858         return true;
 859     }
 860   return false;
 861 }
 862 /* ---------------------------------------------------------------------------
 863  * checks if a line crosses a quadrangle: almost copied from IsLineInRectangle()
 864  * Note: actually this quadrangle is a slanted rectangle
 865  */
 866 bool
 867 IsLineInQuadrangle (PointType p[4], LineTypePtr Line)
 868 {
 869   LineType line;
 870
 871   /* first, see if point 1 is inside the rectangle */
 872   /* in case the whole line is inside the rectangle */
 873   if (IsPointInQuadrangle(p,&(Line->Point1)))
 874     return true;
 875   if (IsPointInQuadrangle(p,&(Line->Point2)))
 876     return true;
 877   /* construct a set of dummy lines and check each of them */
 878   line.Thickness = 0;
 879   line.Flags = NoFlags ();
 880
 881   /* upper-left to upper-right corner */
 882   line.Point1.X = p[0].X; line.Point1.Y = p[0].Y;
 883   line.Point2.X = p[1].X; line.Point2.Y = p[1].Y;
 884   if (LineLineIntersect (&line, Line))
 885     return (true);
 886
 887   /* upper-right to lower-right corner */
 888   line.Point1.X = p[2].X; line.Point1.Y = p[2].Y;
 889   if (LineLineIntersect (&line, Line))
 890     return (true);
 891
 892   /* lower-right to lower-left corner */
 893   line.Point2.X = p[3].X; line.Point2.Y = p[3].Y;
 894   if (LineLineIntersect (&line, Line))
 895     return (true);
 896
 897   /* lower-left to upper-left corner */
 898   line.Point1.X = p[0].X; line.Point1.Y = p[0].Y;
 899   if (LineLineIntersect (&line, Line))
 900     return (true);
 901
 902   return (false);
 903 }
 904 /* ---------------------------------------------------------------------------
 905  * checks if an arc crosses a square
 906  */
 907 bool
 908 IsArcInRectangle (Coord X1, Coord Y1, Coord X2, Coord Y2, ArcTypePtr Arc)
 909 {
 910   LineType line;
 911
 912   /* construct a set of dummy lines and check each of them */
 913   line.Thickness = 0;
 914   line.Flags = NoFlags ();
 915
 916   /* upper-left to upper-right corner */
 917   line.Point1.Y = line.Point2.Y = Y1;
 918   line.Point1.X = X1;
 919   line.Point2.X = X2;
 920   if (LineArcIntersect (&line, Arc))
 921     return (true);
 922
 923   /* upper-right to lower-right corner */
 924   line.Point1.X = line.Point2.X = X2;
 925   line.Point1.Y = Y1;
 926   line.Point2.Y = Y2;
 927   if (LineArcIntersect (&line, Arc))
 928     return (true);
 929
 930   /* lower-right to lower-left corner */
 931   line.Point1.Y = line.Point2.Y = Y2;
 932   line.Point1.X = X1;
 933   line.Point2.X = X2;
 934   if (LineArcIntersect (&line, Arc))
 935     return (true);
 936
 937   /* lower-left to upper-left corner */
 938   line.Point1.X = line.Point2.X = X1;
 939   line.Point1.Y = Y1;
 940   line.Point2.Y = Y2;
 941   if (LineArcIntersect (&line, Arc))
 942     return (true);
 943
 944   return (false);
 945 }
 946
 947 /* ---------------------------------------------------------------------------
 948  * Check if a circle of Radius with center at (X, Y) intersects a Pad.
 949  * Written to enable arbitrary pad directions; for rounded pads, too.
 950  */
 951 bool
 952 IsPointInPad (Coord X, Coord Y, Coord Radius, PadTypePtr Pad)
 953 {
 954   double r, Sin, Cos;
 955   Coord x;
 956   Coord t2 = (Pad->Thickness + 1) / 2, range;
 957   PadType pad = *Pad;
 958
 959   /* series of transforms saving range */
 960   /* move Point1 to the origin */
 961   X -= pad.Point1.X;
 962   Y -= pad.Point1.Y;
 963
 964   pad.Point2.X -= pad.Point1.X;
 965   pad.Point2.Y -= pad.Point1.Y;
 966   /* so, pad.Point1.X = pad.Point1.Y = 0; */
 967
 968   /* rotate round (0, 0) so that Point2 coordinates be (r, 0) */
 969   r = Distance (0, 0, pad.Point2.X, pad.Point2.Y);
 970   if (r < .1)
 971     {
 972       Cos = 1;
 973       Sin = 0;
 974     }
 975   else
 976     {
 977       Sin = pad.Point2.Y / r;
 978       Cos = pad.Point2.X / r;
 979     }
 980   x = X;
 981   X = X * Cos + Y * Sin;
 982   Y = Y * Cos - x * Sin;
 983   /* now pad.Point2.X = r; pad.Point2.Y = 0; */
 984
 985   /* take into account the ends */
 986   if (TEST_FLAG (SQUAREFLAG, Pad))
 987     {
 988       r += Pad->Thickness;
 989       X += t2;
 990     }
 991   if (Y < 0)
 992     Y = -Y;     /* range value is evident now*/
 993
 994   if (TEST_FLAG (SQUAREFLAG, Pad))
 995     {
 996       if (X <= 0)
 997         {
 998           if (Y <= t2)
 999             range = -X;
1000           else
1001             return Radius > Distance (0, t2, X, Y);
1002         }
1003       else if (X >= r)
1004         {
1005           if (Y <= t2)
1006             range = X - r;
1007           else
1008             return Radius > Distance (r, t2, X, Y);
1009         }
1010       else
1011         range = Y - t2;
1012     }
1013   else/*Rounded pad: even more simple*/
1014     {
1015       if (X <= 0)
1016         return (Radius + t2) > Distance (0, 0, X, Y);
1017       else if (X >= r)
1018         return (Radius + t2) > Distance (r, 0, X, Y);
1019       else
1020         range = Y - t2;
1021     }
1022   return range < Radius;
1023 }
1024
1025 bool
1026 IsPointInBox (Coord X, Coord Y, BoxTypePtr box, Coord Radius)
1027 {
1028   Coord width, height, range;
1029
1030   /* NB: Assumes box has point1 with numerically lower X and Y coordinates */
1031
1032   /* Compute coordinates relative to Point1 */
1033   X -= box->X1;
1034   Y -= box->Y1;
1035
1036   width =  box->X2 - box->X1;
1037   height = box->Y2 - box->Y1;
1038
1039   if (X <= 0)
1040     {
1041       if (Y < 0)
1042         return Radius > Distance (0, 0, X, Y);
1043       else if (Y > height)
1044         return Radius > Distance (0, height, X, Y);
1045       else
1046         range = -X;
1047     }
1048   else if (X >= width)
1049     {
1050       if (Y < 0)
1051         return Radius > Distance (width, 0, X, Y);
1052       else if (Y > height)
1053         return Radius > Distance (width, height, X, Y);
1054       else
1055         range = X - width;
1056     }
1057   else
1058     {
1059       if (Y < 0)
1060         range = -Y;
1061       else if (Y > height)
1062         range = Y - height;
1063       else
1064         return true;
1065     }
1066
1067   return range < Radius;
1068 }
1069
1070 /* TODO: this code is BROKEN in the case of non-circular arcs,
1071  *       and in the case that the arc thickness is greater than
1072  *       the radius.
1073  */
1074 bool
1075 IsPointOnArc (Coord X, Coord Y, Coord Radius, ArcTypePtr Arc)
1076 {
1077   /* Calculate angle of point from arc center */
1078   double p_dist = Distance (X, Y, Arc->X, Arc->Y);
1079   double p_cos = (X - Arc->X) / p_dist;
1080   Angle p_ang = acos (p_cos) * RAD_TO_DEG;
1081   Angle ang1, ang2;
1082
1083   /* Convert StartAngle, Delta into bounding angles in [0, 720) */
1084   if (Arc->Delta > 0)
1085     {
1086       ang1 = NormalizeAngle (Arc->StartAngle);
1087       ang2 = NormalizeAngle (Arc->StartAngle + Arc->Delta);
1088     }
1089   else
1090     {
1091       ang1 = NormalizeAngle (Arc->StartAngle + Arc->Delta);
1092       ang2 = NormalizeAngle (Arc->StartAngle);
1093     }
1094   if (ang1 > ang2)
1095     ang2 += 360;
1096   /* Make sure full circles aren't treated as zero-length arcs */
1097   if (Arc->Delta == 360 || Arc->Delta == -360)
1098     ang2 = ang1 + 360;
1099
1100   if (Y > Arc->Y)
1101     p_ang = -p_ang;
1102   p_ang += 180;
1103
1104   /* Check point is outside arc range, check distance from endpoints */
1105   if (ang1 >= p_ang || ang2 <= p_ang)
1106     {
1107       Coord ArcX, ArcY;
1108
1109       ArcX = Arc->X + Arc->Width *
1110               cos ((Arc->StartAngle + 180) / RAD_TO_DEG);
1111       ArcY = Arc->Y - Arc->Width *
1112               sin ((Arc->StartAngle + 180) / RAD_TO_DEG);
1113       if (Distance (X, Y, ArcX, ArcY) < Radius + Arc->Thickness / 2)
1114         return true;
1115
1116       ArcX = Arc->X + Arc->Width *
1117               cos ((Arc->StartAngle + Arc->Delta + 180) / RAD_TO_DEG);
1118       ArcY = Arc->Y - Arc->Width *
1119               sin ((Arc->StartAngle + Arc->Delta + 180) / RAD_TO_DEG);
1120       if (Distance (X, Y, ArcX, ArcY) < Radius + Arc->Thickness / 2)
1121         return true;
1122       return false;
1123     }
1124   /* If point is inside the arc range, just compare it to the arc */
1125   return fabs (Distance (X, Y, Arc->X, Arc->Y) - Arc->Width) < Radius + Arc->Thickness / 2;
1126 }
1127
1128 /* ---------------------------------------------------------------------------
1129  * searches for any kind of object or for a set of object types
1130  * the calling routine passes two pointers to allocated memory for storing
1131  * the results.
1132  * A type value is returned too which is NO_TYPE if no objects has been found.
1133  * A set of object types is passed in.
1134  * The object is located by it's position.
1135  *
1136  * The layout is checked in the following order:
1137  *   polygon-point, pin, via, line, text, elementname, polygon, element
1138  *
1139  * Note that if Type includes LOCKED_TYPE, then the search includes
1140  * locked items.  Otherwise, locked items are ignored.
1141  */
1142 int
1143 SearchObjectByLocation (unsigned Type,
1144                         void **Result1, void **Result2, void **Result3,
1145                         Coord X, Coord Y, Coord Radius)
1146 {
1147   void *r1, *r2, *r3;
1148   void **pr1 = &r1, **pr2 = &r2, **pr3 = &r3;
1149   int i;
1150   double HigherBound = 0;
1151   int HigherAvail = NO_TYPE;
1152   int locked = Type & LOCKED_TYPE;
1153   /* setup variables used by local functions */
1154   PosX = X;
1155   PosY = Y;
1156   SearchRadius = Radius;
1157   if (Radius)
1158     {
1159       SearchBox.X1 = X - Radius;
1160       SearchBox.Y1 = Y - Radius;
1161       SearchBox.X2 = X + Radius;
1162       SearchBox.Y2 = Y + Radius;
1163     }
1164   else
1165     {
1166       SearchBox = point_box (X, Y);
1167     }
1168
1169   if (TEST_FLAG (LOCKNAMESFLAG, PCB))
1170     {
1171       Type &= ~ (ELEMENTNAME_TYPE | TEXT_TYPE);
1172     }
1173   if (TEST_FLAG (HIDENAMESFLAG, PCB))
1174     {
1175       Type &= ~ELEMENTNAME_TYPE;
1176     }
1177   if (TEST_FLAG (ONLYNAMESFLAG, PCB))
1178     {
1179       Type &= (ELEMENTNAME_TYPE | TEXT_TYPE);
1180     }
1181   if (TEST_FLAG (THINDRAWFLAG, PCB) || TEST_FLAG (THINDRAWPOLYFLAG, PCB))
1182     {
1183       Type &= ~POLYGON_TYPE;
1184     }
1185
1186   if (Type & RATLINE_TYPE && PCB->RatOn &&
1187       SearchRatLineByLocation (locked,
1188                                (RatTypePtr *) Result1,
1189                                (RatTypePtr *) Result2,
1190                                (RatTypePtr *) Result3))
1191     return (RATLINE_TYPE);
1192
1193   if (Type & VIA_TYPE &&
1194       SearchViaByLocation (locked,
1195                            (PinTypePtr *) Result1,
1196                            (PinTypePtr *) Result2, (PinTypePtr *) Result3))
1197     return (VIA_TYPE);
1198
1199   if (Type & PIN_TYPE &&
1200       SearchPinByLocation (locked,
1201                            (ElementTypePtr *) pr1,
1202                            (PinTypePtr *) pr2, (PinTypePtr *) pr3))
1203     HigherAvail = PIN_TYPE;
1204
1205   if (!HigherAvail && Type & PAD_TYPE &&
1206       SearchPadByLocation (locked,
1207                            (ElementTypePtr *) pr1,
1208                            (PadTypePtr *) pr2, (PadTypePtr *) pr3, false))
1209     HigherAvail = PAD_TYPE;
1210
1211   if (!HigherAvail && Type & ELEMENTNAME_TYPE &&
1212       SearchElementNameByLocation (locked,
1213                                    (ElementTypePtr *) pr1,
1214                                    (TextTypePtr *) pr2, (TextTypePtr *) pr3,
1215                                    false))
1216     {
1217       BoxTypePtr box = &((TextTypePtr) r2)->BoundingBox;
1218       HigherBound = (double) (box->X2 - box->X1) * (double) (box->Y2 - box->Y1);
1219       HigherAvail = ELEMENTNAME_TYPE;
1220     }
1221
1222   if (!HigherAvail && Type & ELEMENT_TYPE &&
1223       SearchElementByLocation (locked,
1224                                (ElementTypePtr *) pr1,
1225                                (ElementTypePtr *) pr2,
1226                                (ElementTypePtr *) pr3, false))
1227     {
1228       BoxTypePtr box = &((ElementTypePtr) r1)->BoundingBox;
1229       HigherBound = (double) (box->X2 - box->X1) * (double) (box->Y2 - box->Y1);
1230       HigherAvail = ELEMENT_TYPE;
1231     }
1232
1233   for (i = -1; i < max_copper_layer + 1; i++)
1234     {
1235       if (i < 0)
1236         SearchLayer = &PCB->Data->SILKLAYER;
1237       else if (i < max_copper_layer)
1238         SearchLayer = LAYER_ON_STACK (i);
1239       else
1240         {
1241           SearchLayer = &PCB->Data->BACKSILKLAYER;
1242           if (!PCB->InvisibleObjectsOn)
1243             continue;
1244         }
1245       if (SearchLayer->On)
1246         {
1247           if ((HigherAvail & (PIN_TYPE | PAD_TYPE)) == 0 &&
1248               Type & POLYGONPOINT_TYPE &&
1249               SearchPointByLocation (locked,
1250                                      (LayerTypePtr *) Result1,
1251                                      (PolygonTypePtr *) Result2,
1252                                      (PointTypePtr *) Result3))
1253             return (POLYGONPOINT_TYPE);
1254
1255           if ((HigherAvail & (PIN_TYPE | PAD_TYPE)) == 0 &&
1256               Type & LINEPOINT_TYPE &&
1257               SearchLinePointByLocation (locked,
1258                                          (LayerTypePtr *) Result1,
1259                                          (LineTypePtr *) Result2,
1260                                          (PointTypePtr *) Result3))
1261             return (LINEPOINT_TYPE);
1262
1263           if ((HigherAvail & (PIN_TYPE | PAD_TYPE)) == 0 && Type & LINE_TYPE
1264               && SearchLineByLocation (locked,
1265                                        (LayerTypePtr *) Result1,
1266                                        (LineTypePtr *) Result2,
1267                                        (LineTypePtr *) Result3))
1268             return (LINE_TYPE);
1269
1270             if ((HigherAvail & (PIN_TYPE | PAD_TYPE)) == 0 &&
1271               Type & ARCPOINT_TYPE &&
1272               SearchArcPointByLocation (locked,
1273                                         (LayerTypePtr *) Result1,
1274                                         (ArcTypePtr *) Result2,
1275                                         (PointTypePtr *) Result3))
1276             return (ARCPOINT_TYPE);
1277
1278           if ((HigherAvail & (PIN_TYPE | PAD_TYPE)) == 0 && Type & ARC_TYPE &&
1279               SearchArcByLocation (locked,
1280                                    (LayerTypePtr *) Result1,
1281                                    (ArcTypePtr *) Result2,
1282                                    (ArcTypePtr *) Result3))
1283             return (ARC_TYPE);
1284
1285           if ((HigherAvail & (PIN_TYPE | PAD_TYPE)) == 0 && Type & TEXT_TYPE
1286               && SearchTextByLocation (locked,
1287                                        (LayerTypePtr *) Result1,
1288                                        (TextTypePtr *) Result2,
1289                                        (TextTypePtr *) Result3))
1290             return (TEXT_TYPE);
1291
1292           if (Type & POLYGON_TYPE &&
1293               SearchPolygonByLocation (locked,
1294                                        (LayerTypePtr *) Result1,
1295                                        (PolygonTypePtr *) Result2,
1296                                        (PolygonTypePtr *) Result3))
1297             {
1298               if (HigherAvail)
1299                 {
1300                   BoxTypePtr box =
1301                     &(*(PolygonTypePtr *) Result2)->BoundingBox;
1302                   double area =
1303                     (double) (box->X2 - box->X1) * (double) (box->X2 - box->X1);
1304                   if (HigherBound < area)
1305                     break;
1306                   else
1307                     return (POLYGON_TYPE);
1308                 }
1309               else
1310                 return (POLYGON_TYPE);
1311             }
1312         }
1313     }
1314   /* return any previously found objects */
1315   if (HigherAvail & PIN_TYPE)
1316     {
1317       *Result1 = r1;
1318       *Result2 = r2;
1319       *Result3 = r3;
1320       return (PIN_TYPE);
1321     }
1322
1323   if (HigherAvail & PAD_TYPE)
1324     {
1325       *Result1 = r1;
1326       *Result2 = r2;
1327       *Result3 = r3;
1328       return (PAD_TYPE);
1329     }
1330
1331   if (HigherAvail & ELEMENTNAME_TYPE)
1332     {
1333       *Result1 = r1;
1334       *Result2 = r2;
1335       *Result3 = r3;
1336       return (ELEMENTNAME_TYPE);
1337     }
1338
1339   if (HigherAvail & ELEMENT_TYPE)
1340     {
1341       *Result1 = r1;
1342       *Result2 = r2;
1343       *Result3 = r3;
1344       return (ELEMENT_TYPE);
1345     }
1346
1347   /* search the 'invisible objects' last */
1348   if (!PCB->InvisibleObjectsOn)
1349     return (NO_TYPE);
1350
1351   if (Type & PAD_TYPE &&
1352       SearchPadByLocation (locked,
1353                            (ElementTypePtr *) Result1,
1354                            (PadTypePtr *) Result2, (PadTypePtr *) Result3,
1355                            true))
1356     return (PAD_TYPE);
1357
1358   if (Type & ELEMENTNAME_TYPE &&
1359       SearchElementNameByLocation (locked,
1360                                    (ElementTypePtr *) Result1,
1361                                    (TextTypePtr *) Result2,
1362                                    (TextTypePtr *) Result3, true))
1363     return (ELEMENTNAME_TYPE);
1364
1365   if (Type & ELEMENT_TYPE &&
1366       SearchElementByLocation (locked,
1367                                (ElementTypePtr *) Result1,
1368                                (ElementTypePtr *) Result2,
1369                                (ElementTypePtr *) Result3, true))
1370     return (ELEMENT_TYPE);
1371
1372   return (NO_TYPE);
1373 }
1374
1375 /* ---------------------------------------------------------------------------
1376  * searches for a object by it's unique ID. It doesn't matter if
1377  * the object is visible or not. The search is performed on a PCB, a
1378  * buffer or on the remove list.
1379  * The calling routine passes two pointers to allocated memory for storing
1380  * the results.
1381  * A type value is returned too which is NO_TYPE if no objects has been found.
1382  */
1383 int
1384 SearchObjectByID (DataTypePtr Base,
1385                   void **Result1, void **Result2, void **Result3, int ID,
1386                   int type)
1387 {
1388   if (type == LINE_TYPE || type == LINEPOINT_TYPE)
1389     {
1390       ALLLINE_LOOP (Base);
1391       {
1392         if (line->ID == ID)
1393           {
1394             *Result1 = (void *) layer;
1395             *Result2 = *Result3 = (void *) line;
1396             return (LINE_TYPE);
1397           }
1398         if (line->Point1.ID == ID)
1399           {
1400             *Result1 = (void *) layer;
1401             *Result2 = (void *) line;
1402             *Result3 = (void *) &line->Point1;
1403             return (LINEPOINT_TYPE);
1404           }
1405         if (line->Point2.ID == ID)
1406           {
1407             *Result1 = (void *) layer;
1408             *Result2 = (void *) line;
1409             *Result3 = (void *) &line->Point2;
1410             return (LINEPOINT_TYPE);
1411           }
1412       }
1413       ENDALL_LOOP;
1414     }
1415   if (type == ARC_TYPE)
1416     {
1417       ALLARC_LOOP (Base);
1418       {
1419         if (arc->ID == ID)
1420           {
1421             *Result1 = (void *) layer;
1422             *Result2 = *Result3 = (void *) arc;
1423             return (ARC_TYPE);
1424           }
1425       }
1426       ENDALL_LOOP;
1427     }
1428
1429   if (type == TEXT_TYPE)
1430     {
1431       ALLTEXT_LOOP (Base);
1432       {
1433         if (text->ID == ID)
1434           {
1435             *Result1 = (void *) layer;
1436             *Result2 = *Result3 = (void *) text;
1437             return (TEXT_TYPE);
1438           }
1439       }
1440       ENDALL_LOOP;
1441     }
1442
1443   if (type == POLYGON_TYPE || type == POLYGONPOINT_TYPE)
1444     {
1445       ALLPOLYGON_LOOP (Base);
1446       {
1447         if (polygon->ID == ID)
1448           {
1449             *Result1 = (void *) layer;
1450             *Result2 = *Result3 = (void *) polygon;
1451             return (POLYGON_TYPE);
1452           }
1453         if (type == POLYGONPOINT_TYPE)
1454           POLYGONPOINT_LOOP (polygon);
1455         {
1456           if (point->ID == ID)
1457             {
1458               *Result1 = (void *) layer;
1459               *Result2 = (void *) polygon;
1460               *Result3 = (void *) point;
1461               return (POLYGONPOINT_TYPE);
1462             }
1463         }
1464         END_LOOP;
1465       }
1466       ENDALL_LOOP;
1467     }
1468   if (type == VIA_TYPE)
1469     {
1470       VIA_LOOP (Base);
1471       {
1472         if (via->ID == ID)
1473           {
1474             *Result1 = *Result2 = *Result3 = (void *) via;
1475             return (VIA_TYPE);
1476           }
1477       }
1478       END_LOOP;
1479     }
1480
1481   if (type == RATLINE_TYPE || type == LINEPOINT_TYPE)
1482     {
1483       RAT_LOOP (Base);
1484       {
1485         if (line->ID == ID)
1486           {
1487             *Result1 = *Result2 = *Result3 = (void *) line;
1488             return (RATLINE_TYPE);
1489           }
1490         if (line->Point1.ID == ID)
1491           {
1492             *Result1 = (void *) NULL;
1493             *Result2 = (void *) line;
1494             *Result3 = (void *) &line->Point1;
1495             return (LINEPOINT_TYPE);
1496           }
1497         if (line->Point2.ID == ID)
1498           {
1499             *Result1 = (void *) NULL;
1500             *Result2 = (void *) line;
1501             *Result3 = (void *) &line->Point2;
1502             return (LINEPOINT_TYPE);
1503           }
1504       }
1505       END_LOOP;
1506     }
1507
1508   if (type == ELEMENT_TYPE || type == PAD_TYPE || type == PIN_TYPE
1509       || type == ELEMENTLINE_TYPE || type == ELEMENTNAME_TYPE
1510       || type == ELEMENTARC_TYPE)
1511     /* check pins and elementnames too */
1512     ELEMENT_LOOP (Base);
1513   {
1514     if (element->ID == ID)
1515       {
1516         *Result1 = *Result2 = *Result3 = (void *) element;
1517         return (ELEMENT_TYPE);
1518       }
1519     if (type == ELEMENTLINE_TYPE)
1520       ELEMENTLINE_LOOP (element);
1521     {
1522       if (line->ID == ID)
1523         {
1524           *Result1 = (void *) element;
1525           *Result2 = *Result3 = (void *) line;
1526           return (ELEMENTLINE_TYPE);
1527         }
1528     }
1529     END_LOOP;
1530     if (type == ELEMENTARC_TYPE)
1531       ARC_LOOP (element);
1532     {
1533       if (arc->ID == ID)
1534         {
1535           *Result1 = (void *) element;
1536           *Result2 = *Result3 = (void *) arc;
1537           return (ELEMENTARC_TYPE);
1538         }
1539     }
1540     END_LOOP;
1541     if (type == ELEMENTNAME_TYPE)
1542       ELEMENTTEXT_LOOP (element);
1543     {
1544       if (text->ID == ID)
1545         {
1546           *Result1 = (void *) element;
1547           *Result2 = *Result3 = (void *) text;
1548           return (ELEMENTNAME_TYPE);
1549         }
1550     }
1551     END_LOOP;
1552     if (type == PIN_TYPE)
1553       PIN_LOOP (element);
1554     {
1555       if (pin->ID == ID)
1556         {
1557           *Result1 = (void *) element;
1558           *Result2 = *Result3 = (void *) pin;
1559           return (PIN_TYPE);
1560         }
1561     }
1562     END_LOOP;
1563     if (type == PAD_TYPE)
1564       PAD_LOOP (element);
1565     {
1566       if (pad->ID == ID)
1567         {
1568           *Result1 = (void *) element;
1569           *Result2 = *Result3 = (void *) pad;
1570           return (PAD_TYPE);
1571         }
1572     }
1573     END_LOOP;
1574   }
1575   END_LOOP;
1576
1577   Message ("hace: Internal error, search for ID %d failed\n", ID);
1578   return (NO_TYPE);
1579 }
1580
1581 /* ---------------------------------------------------------------------------
1582  * searches for an element by its board name.
1583  * The function returns a pointer to the element, NULL if not found
1584  */
1585 ElementTypePtr
1586 SearchElementByName (DataTypePtr Base, char *Name)
1587 {
1588   ElementTypePtr result = NULL;
1589
1590   ELEMENT_LOOP (Base);
1591   {
1592     if (element->Name[1].TextString &&
1593         NSTRCMP (element->Name[1].TextString, Name) == 0)
1594       {
1595         result = element;
1596         return (result);
1597       }
1598   }
1599   END_LOOP;
1600   return result;
1601 }
1602
1603 /* ---------------------------------------------------------------------------
1604  * searches the cursor position for the type
1605  */
1606 int
1607 SearchScreen (Coord X, Coord Y, int Type, void **Result1,
1608               void **Result2, void **Result3)
1609 {
1610   int ans;
1611
1612   ans = SearchObjectByLocation (Type, Result1, Result2, Result3,
1613                                 X, Y, SLOP * pixel_slop);
1614   return (ans);
1615 }
1616
1617 /* ---------------------------------------------------------------------------
1618  * searches the cursor position for the type
1619  */
1620 int
1621 SearchScreenGridSlop (Coord X, Coord Y, int Type, void **Result1,
1622               void **Result2, void **Result3)
1623 {
1624   int ans;
1625
1626   ans = SearchObjectByLocation (Type, Result1, Result2, Result3,
1627                                 X, Y, PCB->Grid / 2);
1628   return (ans);
1629 }