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 Boolean SearchLineByLocation (int, LayerTypePtr *, LineTypePtr *,
  74                                      LineTypePtr *);
  75 static Boolean SearchArcByLocation (int, LayerTypePtr *, ArcTypePtr *,
  76                                     ArcTypePtr *);
  77 static Boolean SearchRatLineByLocation (int, RatTypePtr *, RatTypePtr *,
  78                                         RatTypePtr *);
  79 static Boolean SearchTextByLocation (int, LayerTypePtr *, TextTypePtr *,
  80                                      TextTypePtr *);
  81 static Boolean SearchPolygonByLocation (int, LayerTypePtr *, PolygonTypePtr *,
  82                                         PolygonTypePtr *);
  83 static Boolean SearchPinByLocation (int, ElementTypePtr *, PinTypePtr *,
  84                                     PinTypePtr *);
  85 static Boolean SearchPadByLocation (int, ElementTypePtr *, PadTypePtr *,
  86                                     PadTypePtr *, Boolean);
  87 static Boolean SearchViaByLocation (int, PinTypePtr *, PinTypePtr *,
  88                                     PinTypePtr *);
  89 static Boolean SearchElementNameByLocation (int, ElementTypePtr *,
  90                                             TextTypePtr *, TextTypePtr *,
  91                                             Boolean);
  92 static Boolean SearchLinePointByLocation (int, LayerTypePtr *, LineTypePtr *,
  93                                           PointTypePtr *);
  94 static Boolean SearchPointByLocation (int, LayerTypePtr *, PolygonTypePtr *,
  95                                       PointTypePtr *);
  96 static Boolean SearchElementByLocation (int, ElementTypePtr *,
  97                                         ElementTypePtr *, ElementTypePtr *,
  98                                         Boolean);
  99
 100 /* ---------------------------------------------------------------------------
 101  * searches a via
 102  */
 103 struct ans_info
 104 {
 105   void **ptr1, **ptr2, **ptr3;
 106   Boolean 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 Boolean
 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 Boolean
 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 Boolean
 205 SearchPadByLocation (int locked, ElementTypePtr * Element, PadTypePtr * Pad,
 206                      PadTypePtr * Dummy, Boolean 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 505 SearchPointByLocation (int locked, LayerTypePtr * Layer,
 506                        PolygonTypePtr * Polygon, PointTypePtr * Point)
 507 {
 508   float d, least;
 509   Boolean 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 Boolean
 567 SearchElementNameByLocation (int locked, ElementTypePtr * Element,
 568                              TextTypePtr * Text, TextTypePtr * Dummy,
 569                              Boolean 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 Boolean
 621 SearchElementByLocation (int locked,
 622                          ElementTypePtr * Element,
 623                          ElementTypePtr * Dummy1, ElementTypePtr * Dummy2,
 624                          Boolean 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
 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 Boolean
1041 IsPointOnArc (float X, float Y, float Radius, ArcTypePtr Arc)
1042 {
1043
1044   register float x, y, dx, dy, r1, r2, a, d, l;
1045   register float pdx, pdy;
1046   int ang1, ang2, delta;
1047   int startAngle, arcDelta;
1048
1049   pdx = X - Arc->X;
1050   pdy = Y - Arc->Y;
1051   l = pdx * pdx + pdy * pdy;
1052   /* concentric arcs, simpler intersection conditions */
1053   if (l == 0.0)
1054     {
1055       if (Arc->Width <= Radius + 0.5 * Arc->Thickness)
1056         return (True);
1057       else
1058         return (False);
1059     }
1060   r1 = Arc->Width;
1061   r1 *= r1;
1062   r2 = Radius + 0.5 * Arc->Thickness;
1063   r2 *= r2;
1064   a = 0.5 * (r1 - r2 + l) / l;
1065   r1 = r1 / l;
1066   /* add a tiny positive number for round-off problems */
1067   d = r1 - a * a + 1e-5;
1068   /* the circles are too far apart to touch */
1069   if (d < 0)
1070     return (False);
1071   /* project the points of intersection */
1072   d = sqrt (d);
1073   x = a * pdx;
1074   y = a * pdy;
1075   dy = -d * pdx;
1076   dx = d * pdy;
1077   /* arrgh! calculate the angles, and put them in a standard range */
1078   startAngle = Arc->StartAngle;
1079   arcDelta = Arc->Delta;
1080   while (startAngle < 0)
1081     startAngle += 360;
1082   if (arcDelta < 0)
1083     {
1084       startAngle += arcDelta;
1085       arcDelta = -arcDelta;
1086       while (startAngle < 0)
1087         startAngle += 360;
1088     }
1089   ang1 = RAD_TO_DEG * atan2 ((y + dy), -(x + dx));
1090   if (ang1 < 0)
1091     ang1 += 360;
1092   ang2 = RAD_TO_DEG * atan2 ((y - dy), -(x - dx));
1093   if (ang2 < 0)
1094     ang2 += 360;
1095   delta = ang2 - ang1;
1096   if (delta > 180)
1097     delta -= 360;
1098   else if (delta < -180)
1099     delta += 360;
1100   if (delta < 0)
1101     {
1102       ang1 += delta;
1103       delta = -delta;
1104       while (ang1 < 0)
1105         ang1 += 360;
1106     }
1107   if (ang1 >= startAngle && ang1 <= startAngle + arcDelta)
1108     return (True);
1109   if (startAngle >= ang1 && startAngle <= ang1 + delta)
1110     return (True);
1111   if (startAngle + arcDelta >= 360 && ang1 <= startAngle + arcDelta - 360)
1112     return (True);
1113   if (ang1 + delta >= 360 && startAngle <= ang1 + delta - 360)
1114     return (True);
1115   return (False);
1116 }
1117
1118 /* ---------------------------------------------------------------------------
1119  * searches for any kind of object or for a set of object types
1120  * the calling routine passes two pointers to allocated memory for storing
1121  * the results.
1122  * A type value is returned too which is NO_TYPE if no objects has been found.
1123  * A set of object types is passed in.
1124  * The object is located by it's position.
1125  *
1126  * The layout is checked in the following order:
1127  *   polygon-point, pin, via, line, text, elementname, polygon, element
1128  *
1129  * Note that if Type includes LOCKED_TYPE, then the search includes
1130  * locked items.  Otherwise, locked items are ignored.
1131  */
1132 int
1133 SearchObjectByLocation (int Type,
1134                         void **Result1, void **Result2, void **Result3,
1135                         LocationType X, LocationType Y, BDimension Radius)
1136 {
1137   void *r1, *r2, *r3;
1138   void **pr1 = &r1, **pr2 = &r2, **pr3 = &r3;
1139   int i;
1140   float HigherBound = 0;
1141   int HigherAvail = NO_TYPE;
1142   int locked = Type & LOCKED_TYPE;
1143   /* setup variables used by local functions */
1144   PosX = X;
1145   PosY = Y;
1146   SearchRadius = Radius;
1147   if (Radius)
1148     {
1149       SearchBox.X1 = X - Radius;
1150       SearchBox.Y1 = Y - Radius;
1151       SearchBox.X2 = X + Radius;
1152       SearchBox.Y2 = Y + Radius;
1153     }
1154   else
1155     {
1156       SearchBox = point_box (X, Y);
1157     }
1158
1159   if (TEST_FLAG (LOCKNAMESFLAG, PCB)
1160       || TEST_FLAG (HIDENAMESFLAG, PCB))
1161     {
1162       Type &= ~ (ELEMENTNAME_TYPE | TEXT_TYPE);
1163     }
1164   if (TEST_FLAG (ONLYNAMESFLAG, PCB))
1165     {
1166       Type &= (ELEMENTNAME_TYPE | TEXT_TYPE);
1167     }
1168   if (TEST_FLAG (THINDRAWFLAG, PCB) || TEST_FLAG (THINDRAWPOLYFLAG, PCB))
1169     {
1170       Type &= ~POLYGON_TYPE;
1171     }
1172
1173   if (Type & RATLINE_TYPE && PCB->RatOn &&
1174       SearchRatLineByLocation (locked,
1175                                (RatTypePtr *) Result1,
1176                                (RatTypePtr *) Result2,
1177                                (RatTypePtr *) Result3))
1178     return (RATLINE_TYPE);
1179
1180   if (Type & VIA_TYPE &&
1181       SearchViaByLocation (locked,
1182                            (PinTypePtr *) Result1,
1183                            (PinTypePtr *) Result2, (PinTypePtr *) Result3))
1184     return (VIA_TYPE);
1185
1186   if (Type & PIN_TYPE &&
1187       SearchPinByLocation (locked,
1188                            (ElementTypePtr *) pr1,
1189                            (PinTypePtr *) pr2, (PinTypePtr *) pr3))
1190     HigherAvail = PIN_TYPE;
1191
1192   if (!HigherAvail && Type & PAD_TYPE &&
1193       SearchPadByLocation (locked,
1194                            (ElementTypePtr *) pr1,
1195                            (PadTypePtr *) pr2, (PadTypePtr *) pr3, False))
1196     HigherAvail = PAD_TYPE;
1197
1198   if (!HigherAvail && Type & ELEMENTNAME_TYPE &&
1199       SearchElementNameByLocation (locked,
1200                                    (ElementTypePtr *) pr1,
1201                                    (TextTypePtr *) pr2, (TextTypePtr *) pr3,
1202                                    False))
1203     {
1204       BoxTypePtr box = &((TextTypePtr) r2)->BoundingBox;
1205       HigherBound = (float) (box->X2 - box->X1) * (float) (box->Y2 - box->Y1);
1206       HigherAvail = ELEMENTNAME_TYPE;
1207     }
1208
1209   if (!HigherAvail && Type & ELEMENT_TYPE &&
1210       SearchElementByLocation (locked,
1211                                (ElementTypePtr *) pr1,
1212                                (ElementTypePtr *) pr2,
1213                                (ElementTypePtr *) pr3, False))
1214     {
1215       BoxTypePtr box = &((ElementTypePtr) r1)->BoundingBox;
1216       HigherBound = (float) (box->X2 - box->X1) * (float) (box->Y2 - box->Y1);
1217       HigherAvail = ELEMENT_TYPE;
1218     }
1219
1220   for (i = -1; i < max_layer + 1; i++)
1221     {
1222       if (i < 0)
1223         SearchLayer = &PCB->Data->SILKLAYER;
1224       else if (i < max_layer)
1225         SearchLayer = LAYER_ON_STACK (i);
1226       else
1227         {
1228           SearchLayer = &PCB->Data->BACKSILKLAYER;
1229           if (!PCB->InvisibleObjectsOn)
1230             continue;
1231         }
1232       if (SearchLayer->On)
1233         {
1234           if ((HigherAvail & (PIN_TYPE | PAD_TYPE)) == 0 &&
1235               Type & POLYGONPOINT_TYPE &&
1236               SearchPointByLocation (locked,
1237                                      (LayerTypePtr *) Result1,
1238                                      (PolygonTypePtr *) Result2,
1239                                      (PointTypePtr *) Result3))
1240             return (POLYGONPOINT_TYPE);
1241
1242           if ((HigherAvail & (PIN_TYPE | PAD_TYPE)) == 0 &&
1243               Type & LINEPOINT_TYPE &&
1244               SearchLinePointByLocation (locked,
1245                                          (LayerTypePtr *) Result1,
1246                                          (LineTypePtr *) Result2,
1247                                          (PointTypePtr *) Result3))
1248             return (LINEPOINT_TYPE);
1249
1250           if ((HigherAvail & (PIN_TYPE | PAD_TYPE)) == 0 && Type & LINE_TYPE
1251               && SearchLineByLocation (locked,
1252                                        (LayerTypePtr *) Result1,
1253                                        (LineTypePtr *) Result2,
1254                                        (LineTypePtr *) Result3))
1255             return (LINE_TYPE);
1256
1257           if ((HigherAvail & (PIN_TYPE | PAD_TYPE)) == 0 && Type & ARC_TYPE &&
1258               SearchArcByLocation (locked,
1259                                    (LayerTypePtr *) Result1,
1260                                    (ArcTypePtr *) Result2,
1261                                    (ArcTypePtr *) Result3))
1262             return (ARC_TYPE);
1263
1264           if ((HigherAvail & (PIN_TYPE | PAD_TYPE)) == 0 && Type & TEXT_TYPE
1265               && SearchTextByLocation (locked,
1266                                        (LayerTypePtr *) Result1,
1267                                        (TextTypePtr *) Result2,
1268                                        (TextTypePtr *) Result3))
1269             return (TEXT_TYPE);
1270
1271           if (Type & POLYGON_TYPE &&
1272               SearchPolygonByLocation (locked,
1273                                        (LayerTypePtr *) Result1,
1274                                        (PolygonTypePtr *) Result2,
1275                                        (PolygonTypePtr *) Result3))
1276             {
1277               if (HigherAvail)
1278                 {
1279                   BoxTypePtr box =
1280                     &(*(PolygonTypePtr *) Result2)->BoundingBox;
1281                   float area =
1282                     (float) (box->X2 - box->X1) * (float) (box->X2 - box->X1);
1283                   if (HigherBound < area)
1284                     break;
1285                   else
1286                     return (POLYGON_TYPE);
1287                 }
1288               else
1289                 return (POLYGON_TYPE);
1290             }
1291         }
1292     }
1293   /* return any previously found objects */
1294   if (HigherAvail & PIN_TYPE)
1295     {
1296       *Result1 = r1;
1297       *Result2 = r2;
1298       *Result3 = r3;
1299       return (PIN_TYPE);
1300     }
1301
1302   if (HigherAvail & PAD_TYPE)
1303     {
1304       *Result1 = r1;
1305       *Result2 = r2;
1306       *Result3 = r3;
1307       return (PAD_TYPE);
1308     }
1309
1310   if (HigherAvail & ELEMENTNAME_TYPE)
1311     {
1312       *Result1 = r1;
1313       *Result2 = r2;
1314       *Result3 = r3;
1315       return (ELEMENTNAME_TYPE);
1316     }
1317
1318   if (HigherAvail & ELEMENT_TYPE)
1319     {
1320       *Result1 = r1;
1321       *Result2 = r2;
1322       *Result3 = r3;
1323       return (ELEMENT_TYPE);
1324     }
1325
1326   /* search the 'invisible objects' last */
1327   if (!PCB->InvisibleObjectsOn)
1328     return (NO_TYPE);
1329
1330   if (Type & PAD_TYPE &&
1331       SearchPadByLocation (locked,
1332                            (ElementTypePtr *) Result1,
1333                            (PadTypePtr *) Result2, (PadTypePtr *) Result3,
1334                            True))
1335     return (PAD_TYPE);
1336
1337   if (Type & ELEMENTNAME_TYPE &&
1338       SearchElementNameByLocation (locked,
1339                                    (ElementTypePtr *) Result1,
1340                                    (TextTypePtr *) Result2,
1341                                    (TextTypePtr *) Result3, True))
1342     return (ELEMENTNAME_TYPE);
1343
1344   if (Type & ELEMENT_TYPE &&
1345       SearchElementByLocation (locked,
1346                                (ElementTypePtr *) Result1,
1347                                (ElementTypePtr *) Result2,
1348                                (ElementTypePtr *) Result3, True))
1349     return (ELEMENT_TYPE);
1350
1351   return (NO_TYPE);
1352 }
1353
1354 /* ---------------------------------------------------------------------------
1355  * searches for a object by it's unique ID. It doesn't matter if
1356  * the object is visible or not. The search is performed on a PCB, a
1357  * buffer or on the remove list.
1358  * The calling routine passes two pointers to allocated memory for storing
1359  * the results.
1360  * A type value is returned too which is NO_TYPE if no objects has been found.
1361  */
1362 int
1363 SearchObjectByID (DataTypePtr Base,
1364                   void **Result1, void **Result2, void **Result3, int ID,
1365                   int type)
1366 {
1367   if (type == LINE_TYPE || type == LINEPOINT_TYPE)
1368     {
1369       ALLLINE_LOOP (Base);
1370       {
1371         if (line->ID == ID)
1372           {
1373             *Result1 = (void *) layer;
1374             *Result2 = *Result3 = (void *) line;
1375             return (LINE_TYPE);
1376           }
1377         if (line->Point1.ID == ID)
1378           {
1379             *Result1 = (void *) layer;
1380             *Result2 = (void *) line;
1381             *Result3 = (void *) &line->Point1;
1382             return (LINEPOINT_TYPE);
1383           }
1384         if (line->Point2.ID == ID)
1385           {
1386             *Result1 = (void *) layer;
1387             *Result2 = (void *) line;
1388             *Result3 = (void *) &line->Point2;
1389             return (LINEPOINT_TYPE);
1390           }
1391       }
1392       ENDALL_LOOP;
1393     }
1394   if (type == ARC_TYPE)
1395     {
1396       ALLARC_LOOP (Base);
1397       {
1398         if (arc->ID == ID)
1399           {
1400             *Result1 = (void *) layer;
1401             *Result2 = *Result3 = (void *) arc;
1402             return (ARC_TYPE);
1403           }
1404       }
1405       ENDALL_LOOP;
1406     }
1407
1408   if (type == TEXT_TYPE)
1409     {
1410       ALLTEXT_LOOP (Base);
1411       {
1412         if (text->ID == ID)
1413           {
1414             *Result1 = (void *) layer;
1415             *Result2 = *Result3 = (void *) text;
1416             return (TEXT_TYPE);
1417           }
1418       }
1419       ENDALL_LOOP;
1420     }
1421
1422   if (type == POLYGON_TYPE || type == POLYGONPOINT_TYPE)
1423     {
1424       ALLPOLYGON_LOOP (Base);
1425       {
1426         if (polygon->ID == ID)
1427           {
1428             *Result1 = (void *) layer;
1429             *Result2 = *Result3 = (void *) polygon;
1430             return (POLYGON_TYPE);
1431           }
1432         if (type == POLYGONPOINT_TYPE)
1433           POLYGONPOINT_LOOP (polygon);
1434         {
1435           if (point->ID == ID)
1436             {
1437               *Result1 = (void *) layer;
1438               *Result2 = (void *) polygon;
1439               *Result3 = (void *) point;
1440               return (POLYGONPOINT_TYPE);
1441             }
1442         }
1443         END_LOOP;
1444       }
1445       ENDALL_LOOP;
1446     }
1447   if (type == VIA_TYPE)
1448     {
1449       VIA_LOOP (Base);
1450       {
1451         if (via->ID == ID)
1452           {
1453             *Result1 = *Result2 = *Result3 = (void *) via;
1454             return (VIA_TYPE);
1455           }
1456       }
1457       END_LOOP;
1458     }
1459
1460   if (type == RATLINE_TYPE || type == LINEPOINT_TYPE)
1461     {
1462       RAT_LOOP (Base);
1463       {
1464         if (line->ID == ID)
1465           {
1466             *Result1 = *Result2 = *Result3 = (void *) line;
1467             return (RATLINE_TYPE);
1468           }
1469         if (line->Point1.ID == ID)
1470           {
1471             *Result1 = (void *) NULL;
1472             *Result2 = (void *) line;
1473             *Result3 = (void *) &line->Point1;
1474             return (LINEPOINT_TYPE);
1475           }
1476         if (line->Point2.ID == ID)
1477           {
1478             *Result1 = (void *) NULL;
1479             *Result2 = (void *) line;
1480             *Result3 = (void *) &line->Point2;
1481             return (LINEPOINT_TYPE);
1482           }
1483       }
1484       END_LOOP;
1485     }
1486
1487   if (type == ELEMENT_TYPE || type == PAD_TYPE || type == PIN_TYPE
1488       || type == ELEMENTLINE_TYPE || type == ELEMENTNAME_TYPE
1489       || type == ELEMENTARC_TYPE)
1490     /* check pins and elementnames too */
1491     ELEMENT_LOOP (Base);
1492   {
1493     if (element->ID == ID)
1494       {
1495         *Result1 = *Result2 = *Result3 = (void *) element;
1496         return (ELEMENT_TYPE);
1497       }
1498     if (type == ELEMENTLINE_TYPE)
1499       ELEMENTLINE_LOOP (element);
1500     {
1501       if (line->ID == ID)
1502         {
1503           *Result1 = (void *) element;
1504           *Result2 = *Result3 = (void *) line;
1505           return (ELEMENTLINE_TYPE);
1506         }
1507     }
1508     END_LOOP;
1509     if (type == ELEMENTARC_TYPE)
1510       ARC_LOOP (element);
1511     {
1512       if (arc->ID == ID)
1513         {
1514           *Result1 = (void *) element;
1515           *Result2 = *Result3 = (void *) arc;
1516           return (ELEMENTARC_TYPE);
1517         }
1518     }
1519     END_LOOP;
1520     if (type == ELEMENTNAME_TYPE)
1521       ELEMENTTEXT_LOOP (element);
1522     {
1523       if (text->ID == ID)
1524         {
1525           *Result1 = (void *) element;
1526           *Result2 = *Result3 = (void *) text;
1527           return (ELEMENTNAME_TYPE);
1528         }
1529     }
1530     END_LOOP;
1531     if (type == PIN_TYPE)
1532       PIN_LOOP (element);
1533     {
1534       if (pin->ID == ID)
1535         {
1536           *Result1 = (void *) element;
1537           *Result2 = *Result3 = (void *) pin;
1538           return (PIN_TYPE);
1539         }
1540     }
1541     END_LOOP;
1542     if (type == PAD_TYPE)
1543       PAD_LOOP (element);
1544     {
1545       if (pad->ID == ID)
1546         {
1547           *Result1 = (void *) element;
1548           *Result2 = *Result3 = (void *) pad;
1549           return (PAD_TYPE);
1550         }
1551     }
1552     END_LOOP;
1553   }
1554   END_LOOP;
1555
1556   Message ("hace: Internal error, search for ID %d failed\n", ID);
1557   return (NO_TYPE);
1558 }
1559
1560 /* ---------------------------------------------------------------------------
1561  * searches for an element by its board name.
1562  * The function returns a pointer to the element, NULL if not found
1563  */
1564 ElementTypePtr
1565 SearchElementByName (DataTypePtr Base, char *Name)
1566 {
1567   ElementTypePtr result = NULL;
1568
1569   ELEMENT_LOOP (Base);
1570   {
1571     if (element->Name[1].TextString &&
1572         NSTRCMP (element->Name[1].TextString, Name) == 0)
1573       {
1574         result = element;
1575         return (result);
1576       }
1577   }
1578   END_LOOP;
1579   return result;
1580 }
1581
1582 /* ---------------------------------------------------------------------------
1583  * searches the cursor position for the type
1584  */
1585 int
1586 SearchScreen (LocationType X, LocationType Y, int Type, void **Result1,
1587               void **Result2, void **Result3)
1588 {
1589   int ans;
1590
1591   ans = SearchObjectByLocation (Type, Result1, Result2, Result3,
1592                                 X, Y, SLOP * pixel_slop);
1593   return (ans);
1594 }