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