src/search.c

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