src/search.c

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