src/rubberband.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 /* functions used by 'rubberband moves'
  29  */
  30
  31 #ifdef HAVE_CONFIG_H
  32 #include "config.h"
  33 #endif
  34
  35 #include <stdlib.h>
  36 #ifdef HAVE_STRING_H
  37 #include <string.h>
  38 #endif
  39 #include <memory.h>
  40 #include <math.h>
  41 #ifdef HAVE_UNISTD_H
  42 #include <unistd.h>
  43 #endif
  44
  45 #include "global.h"
  46
  47 #include "create.h"
  48 #include "data.h"
  49 #include "error.h"
  50 #include "misc.h"
  51 #include "polygon.h"
  52 #include "rubberband.h"
  53 #include "rtree.h"
  54 #include "search.h"
  55
  56 #ifdef HAVE_LIBDMALLOC
  57 #include <dmalloc.h>
  58 #endif
  59
  60 /* ---------------------------------------------------------------------------
  61  * some local prototypes
  62  */
  63 static void CheckPadForRubberbandConnection (PadType *);
  64 static void CheckPinForRubberbandConnection (PinType *);
  65 static void CheckLinePointForRubberbandConnection (LayerType *,
  66                                                    LineType *,
  67                                                    PointType *,
  68                                                    bool);
  69 static void CheckPolygonForRubberbandConnection (LayerType *,
  70                                                  PolygonType *);
  71 static void CheckLinePointForRat (LayerType *, PointType *);
  72 static int rubber_callback (const BoxType * b, void *cl);
  73
  74 struct rubber_info
  75 {
  76   Coord radius;
  77   Coord X, Y;
  78   LineType *line;
  79   BoxType box;
  80   LayerType *layer;
  81 };
  82
  83 static int
  84 rubber_callback (const BoxType * b, void *cl)
  85 {
  86   LineType *line = (LineType *) b;
  87   struct rubber_info *i = (struct rubber_info *) cl;
  88   double x, y, rad, dist1, dist2;
  89   Coord t;
  90   int touches = 0;
  91
  92   t = line->Thickness / 2;
  93
  94   if (TEST_FLAG (LOCKFLAG, line))
  95     return 0;
  96   if (line == i->line)
  97     return 0;
  98   /*
  99    * Check to see if the line touches a rectangular region.
 100    * To do this we need to look for the intersection of a circular
 101    * region and a rectangular region.
 102    */
 103   if (i->radius == 0)
 104     {
 105       int found = 0;
 106
 107       if (line->Point1.X + t >= i->box.X1 && line->Point1.X - t <= i->box.X2
 108           && line->Point1.Y + t >= i->box.Y1
 109           && line->Point1.Y - t <= i->box.Y2)
 110         {
 111           if (((i->box.X1 <= line->Point1.X) &&
 112                (line->Point1.X <= i->box.X2)) ||
 113               ((i->box.Y1 <= line->Point1.Y) &&
 114                (line->Point1.Y <= i->box.Y2)))
 115             {
 116               /*
 117                * The circle is positioned such that the closest point
 118                * on the rectangular region boundary is not at a corner
 119                * of the rectangle.  i.e. the shortest line from circle
 120                * center to rectangle intersects the rectangle at 90
 121                * degrees.  In this case our first test is sufficient
 122                */
 123               touches = 1;
 124             }
 125           else
 126             {
 127               /*
 128                * Now we must check the distance from the center of the
 129                * circle to the corners of the rectangle since the
 130                * closest part of the rectangular region is the corner.
 131                */
 132               x = MIN (abs (i->box.X1 - line->Point1.X),
 133                        abs (i->box.X2 - line->Point1.X));
 134               x *= x;
 135               y = MIN (abs (i->box.Y1 - line->Point1.Y),
 136                        abs (i->box.Y2 - line->Point1.Y));
 137               y *= y;
 138               x = x + y - (t * t);
 139
 140               if (x <= 0)
 141                 touches = 1;
 142             }
 143           if (touches)
 144             {
 145               CreateNewRubberbandEntry (i->layer, line, &line->Point1);
 146               found++;
 147             }
 148         }
 149       if (line->Point2.X + t >= i->box.X1 && line->Point2.X - t <= i->box.X2
 150           && line->Point2.Y + t >= i->box.Y1
 151           && line->Point2.Y - t <= i->box.Y2)
 152         {
 153           if (((i->box.X1 <= line->Point2.X) &&
 154                (line->Point2.X <= i->box.X2)) ||
 155               ((i->box.Y1 <= line->Point2.Y) &&
 156                (line->Point2.Y <= i->box.Y2)))
 157             {
 158               touches = 1;
 159             }
 160           else
 161             {
 162               x = MIN (abs (i->box.X1 - line->Point2.X),
 163                        abs (i->box.X2 - line->Point2.X));
 164               x *= x;
 165               y = MIN (abs (i->box.Y1 - line->Point2.Y),
 166                        abs (i->box.Y2 - line->Point2.Y));
 167               y *= y;
 168               x = x + y - (t * t);
 169
 170               if (x <= 0)
 171                 touches = 1;
 172             }
 173           if (touches)
 174             {
 175               CreateNewRubberbandEntry (i->layer, line, &line->Point2);
 176               found++;
 177             }
 178         }
 179       return found;
 180     }
 181   /* circular search region */
 182   if (i->radius < 0)
 183     rad = 0;  /* require exact match */
 184   else
 185     rad = SQUARE(i->radius + t);
 186
 187   x = (i->X - line->Point1.X);
 188   x *= x;
 189   y = (i->Y - line->Point1.Y);
 190   y *= y;
 191   dist1 = x + y - rad;
 192
 193   x = (i->X - line->Point2.X);
 194   x *= x;
 195   y = (i->Y - line->Point2.Y);
 196   y *= y;
 197   dist2 = x + y - rad;
 198
 199   if (dist1 > 0 && dist2 > 0)
 200     return 0;
 201
 202 #ifdef CLOSEST_ONLY     /* keep this to remind me */
 203   if (dist1 < dist2)
 204     CreateNewRubberbandEntry (i->layer, line, &line->Point1);
 205   else
 206     CreateNewRubberbandEntry (i->layer, line, &line->Point2);
 207 #else
 208   if (dist1 <= 0)
 209     CreateNewRubberbandEntry (i->layer, line, &line->Point1);
 210   if (dist2 <= 0)
 211     CreateNewRubberbandEntry (i->layer, line, &line->Point2);
 212 #endif
 213   return 1;
 214 }
 215
 216 /* ---------------------------------------------------------------------------
 217  * checks all visible lines which belong to the same layergroup as the
 218  * passed pad. If one of the endpoints of the line lays inside the pad,
 219  * the line is added to the 'rubberband' list
 220  */
 221 static void
 222 CheckPadForRubberbandConnection (PadType *Pad)
 223 {
 224   Coord half = Pad->Thickness / 2;
 225   Cardinal group;
 226   struct rubber_info info;
 227
 228   info.box.X1 = MIN (Pad->Point1.X, Pad->Point2.X) - half;
 229   info.box.Y1 = MIN (Pad->Point1.Y, Pad->Point2.Y) - half;
 230   info.box.X2 = MAX (Pad->Point1.X, Pad->Point2.X) + half;
 231   info.box.Y2 = MAX (Pad->Point1.Y, Pad->Point2.Y) + half;
 232   info.radius = 0;
 233   info.line = NULL;
 234   group = GetLayerGroupNumberBySide (
 235       TEST_FLAG (ONSOLDERFLAG, Pad) ? BOTTOM_SIDE : TOP_SIDE);
 236
 237   /* check all visible layers in the same group */
 238   GROUP_LOOP (PCB->Data, group);
 239   {
 240     /* check all visible lines of the group member */
 241     info.layer = layer;
 242     if (info.layer->On)
 243       {
 244         r_search (info.layer->line_tree, &info.box, NULL, rubber_callback,
 245                   &info);
 246       }
 247   }
 248   END_LOOP;
 249 }
 250
 251 struct rinfo
 252 {
 253   int type;
 254   Cardinal group;
 255   PinType *pin;
 256   PadType *pad;
 257   PointType *point;
 258 };
 259
 260 static int
 261 rat_callback (const BoxType * box, void *cl)
 262 {
 263   RatType *rat = (RatType *) box;
 264   struct rinfo *i = (struct rinfo *) cl;
 265
 266   switch (i->type)
 267     {
 268     case PIN_TYPE:
 269       if (rat->Point1.X == i->pin->X && rat->Point1.Y == i->pin->Y)
 270         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
 271       else if (rat->Point2.X == i->pin->X && rat->Point2.Y == i->pin->Y)
 272         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
 273       break;
 274     case PAD_TYPE:
 275       if (rat->Point1.X == i->pad->Point1.X &&
 276           rat->Point1.Y == i->pad->Point1.Y && rat->group1 == i->group)
 277         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
 278       else
 279         if (rat->Point2.X == i->pad->Point1.X &&
 280             rat->Point2.Y == i->pad->Point1.Y && rat->group2 == i->group)
 281         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
 282       else
 283         if (rat->Point1.X == i->pad->Point2.X &&
 284             rat->Point1.Y == i->pad->Point2.Y && rat->group1 == i->group)
 285         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
 286       else
 287         if (rat->Point2.X == i->pad->Point2.X &&
 288             rat->Point2.Y == i->pad->Point2.Y && rat->group2 == i->group)
 289         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
 290       else
 291         if (rat->Point1.X == (i->pad->Point1.X + i->pad->Point2.X) / 2 &&
 292             rat->Point1.Y == (i->pad->Point1.Y + i->pad->Point2.Y) / 2 &&
 293             rat->group1 == i->group)
 294         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
 295       else
 296         if (rat->Point2.X == (i->pad->Point1.X + i->pad->Point2.X) / 2 &&
 297             rat->Point2.Y == (i->pad->Point1.Y + i->pad->Point2.Y) / 2 &&
 298             rat->group2 == i->group)
 299         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
 300       break;
 301     case LINEPOINT_TYPE:
 302       if (rat->group1 == i->group &&
 303           rat->Point1.X == i->point->X && rat->Point1.Y == i->point->Y)
 304         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
 305       else
 306         if (rat->group2 == i->group &&
 307             rat->Point2.X == i->point->X && rat->Point2.Y == i->point->Y)
 308         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
 309       break;
 310     default:
 311       Message ("hace: bad rubber-rat lookup callback\n");
 312     }
 313   return 0;
 314 }
 315
 316 static void
 317 CheckPadForRat (PadType *Pad)
 318 {
 319   struct rinfo info;
 320
 321   info.group = GetLayerGroupNumberBySide (
 322                   TEST_FLAG (ONSOLDERFLAG, Pad) ? BOTTOM_SIDE : TOP_SIDE);
 323   info.pad = Pad;
 324   info.type = PAD_TYPE;
 325
 326   r_search (PCB->Data->rat_tree, &Pad->BoundingBox, NULL, rat_callback,
 327             &info);
 328 }
 329
 330 static void
 331 CheckPinForRat (PinType *Pin)
 332 {
 333   struct rinfo info;
 334
 335   info.type = PIN_TYPE;
 336   info.pin = Pin;
 337   r_search (PCB->Data->rat_tree, &Pin->BoundingBox, NULL, rat_callback,
 338             &info);
 339 }
 340
 341 static void
 342 CheckLinePointForRat (LayerType *Layer, PointType *Point)
 343 {
 344   struct rinfo info;
 345   info.group = GetLayerGroupNumberByPointer (Layer);
 346   info.point = Point;
 347   info.type = LINEPOINT_TYPE;
 348
 349   r_search (PCB->Data->rat_tree, (BoxType *) Point, NULL, rat_callback,
 350             &info);
 351 }
 352
 353 /* ---------------------------------------------------------------------------
 354  * checks all visible lines. If one of the endpoints of the line lays
 355  * inside the pin, the line is added to the 'rubberband' list
 356  *
 357  * Square pins are handled as if they were round. Speed
 358  * and readability is more important then the few %
 359  * of failures that are immediately recognized
 360  */
 361 static void
 362 CheckPinForRubberbandConnection (PinType *Pin)
 363 {
 364   struct rubber_info info;
 365   Cardinal n;
 366   Coord t = Pin->Thickness / 2;
 367
 368   info.box.X1 = Pin->X - t;
 369   info.box.X2 = Pin->X + t;
 370   info.box.Y1 = Pin->Y - t;
 371   info.box.Y2 = Pin->Y + t;
 372   info.line = NULL;
 373   if (TEST_FLAG (SQUAREFLAG, Pin))
 374     info.radius = 0;
 375   else
 376     {
 377       info.radius = t;
 378       info.X = Pin->X;
 379       info.Y = Pin->Y;
 380     }
 381
 382   for (n = 0; n < max_copper_layer; n++)
 383     {
 384       info.layer = LAYER_PTR (n);
 385       r_search (info.layer->line_tree, &info.box, NULL, rubber_callback,
 386                 &info);
 387     }
 388 }
 389
 390 /* ---------------------------------------------------------------------------
 391  * checks all visible lines which belong to the same group as the passed line.
 392  * If one of the endpoints of the line lays * inside the passed line,
 393  * the scanned line is added to the 'rubberband' list
 394  */
 395 static void
 396 CheckLinePointForRubberbandConnection (LayerType *Layer,
 397                                        LineType *Line,
 398                                        PointType *LinePoint,
 399                                        bool Exact)
 400 {
 401   Cardinal group;
 402   struct rubber_info info;
 403   Coord t = Line->Thickness / 2;
 404
 405   /* lookup layergroup and check all visible lines in this group */
 406   info.radius = Exact ? -1 : MAX(Line->Thickness / 2, 1);
 407   info.box.X1 = LinePoint->X - t;
 408   info.box.X2 = LinePoint->X + t;
 409   info.box.Y1 = LinePoint->Y - t;
 410   info.box.Y2 = LinePoint->Y + t;
 411   info.line = Line;
 412   info.X = LinePoint->X;
 413   info.Y = LinePoint->Y;
 414   group = GetLayerGroupNumberByPointer (Layer);
 415   GROUP_LOOP (PCB->Data, group);
 416   {
 417     /* check all visible lines of the group member */
 418     if (layer->On)
 419       {
 420         info.layer = layer;
 421         r_search (layer->line_tree, &info.box, NULL, rubber_callback, &info);
 422       }
 423   }
 424   END_LOOP;
 425 }
 426
 427 /* ---------------------------------------------------------------------------
 428  * checks all visible lines which belong to the same group as the passed polygon.
 429  * If one of the endpoints of the line lays inside the passed polygon,
 430  * the scanned line is added to the 'rubberband' list
 431  */
 432 static void
 433 CheckPolygonForRubberbandConnection (LayerType *Layer,
 434                                      PolygonType *Polygon)
 435 {
 436   Cardinal group;
 437
 438   /* lookup layergroup and check all visible lines in this group */
 439   group = GetLayerGroupNumberByPointer (Layer);
 440   GROUP_LOOP (PCB->Data, group);
 441   {
 442     if (layer->On)
 443       {
 444         Coord thick;
 445
 446         /* the following code just stupidly compares the endpoints
 447          * of the lines
 448          */
 449         LINE_LOOP (layer);
 450         {
 451           if (TEST_FLAG (LOCKFLAG, line))
 452             continue;
 453           if (TEST_FLAG (CLEARLINEFLAG, line))
 454             continue;
 455           thick = (line->Thickness + 1) / 2;
 456           if (IsPointInPolygon (line->Point1.X, line->Point1.Y,
 457                                 thick, Polygon))
 458             CreateNewRubberbandEntry (layer, line, &line->Point1);
 459           if (IsPointInPolygon (line->Point2.X, line->Point2.Y,
 460                                 thick, Polygon))
 461             CreateNewRubberbandEntry (layer, line, &line->Point2);
 462         }
 463         END_LOOP;
 464       }
 465   }
 466   END_LOOP;
 467 }
 468
 469 /* ---------------------------------------------------------------------------
 470  * lookup all lines that are connected to an object and save the
 471  * data to 'Crosshair.AttachedObject.Rubberband'
 472  * lookup is only done for visible layers
 473  */
 474 void
 475 LookupRubberbandLines (int Type, void *Ptr1, void *Ptr2, void *Ptr3)
 476 {
 477
 478   /* the function is only supported for some types
 479    * check all visible lines;
 480    * it is only necessary to check if one of the endpoints
 481    * is connected
 482    */
 483   switch (Type)
 484     {
 485     case ELEMENT_TYPE:
 486       {
 487         ElementType *element = (ElementType *) Ptr1;
 488
 489         /* square pins are handled as if they are round. Speed
 490          * and readability is more important then the few %
 491          * of failures that are immediately recognized
 492          */
 493         PIN_LOOP (element);
 494         {
 495           CheckPinForRubberbandConnection (pin);
 496         }
 497         END_LOOP;
 498         PAD_LOOP (element);
 499         {
 500           CheckPadForRubberbandConnection (pad);
 501         }
 502         END_LOOP;
 503         break;
 504       }
 505
 506     case LINE_TYPE:
 507       {
 508         LayerType *layer = (LayerType *) Ptr1;
 509         LineType *line = (LineType *) Ptr2;
 510         if (GetLayerNumber (PCB->Data, layer) < max_copper_layer)
 511           {
 512             CheckLinePointForRubberbandConnection (layer, line,
 513                                                    &line->Point1, false);
 514             CheckLinePointForRubberbandConnection (layer, line,
 515                                                    &line->Point2, false);
 516           }
 517         break;
 518       }
 519
 520     case LINEPOINT_TYPE:
 521       if (GetLayerNumber (PCB->Data, (LayerType *) Ptr1) < max_copper_layer)
 522         CheckLinePointForRubberbandConnection ((LayerType *) Ptr1,
 523                                                (LineType *) Ptr2,
 524                                                (PointType *) Ptr3, true);
 525       break;
 526
 527     case VIA_TYPE:
 528       CheckPinForRubberbandConnection ((PinType *) Ptr1);
 529       break;
 530
 531     case POLYGON_TYPE:
 532       if (GetLayerNumber (PCB->Data, (LayerType *) Ptr1) < max_copper_layer)
 533         CheckPolygonForRubberbandConnection ((LayerType *) Ptr1,
 534                                              (PolygonType *) Ptr2);
 535       break;
 536     }
 537 }
 538
 539 void
 540 LookupRatLines (int Type, void *Ptr1, void *Ptr2, void *Ptr3)
 541 {
 542   switch (Type)
 543     {
 544     case ELEMENT_TYPE:
 545       {
 546         ElementType *element = (ElementType *) Ptr1;
 547
 548         PIN_LOOP (element);
 549         {
 550           CheckPinForRat (pin);
 551         }
 552         END_LOOP;
 553         PAD_LOOP (element);
 554         {
 555           CheckPadForRat (pad);
 556         }
 557         END_LOOP;
 558         break;
 559       }
 560
 561     case LINE_TYPE:
 562       {
 563         LayerType *layer = (LayerType *) Ptr1;
 564         LineType *line = (LineType *) Ptr2;
 565
 566         CheckLinePointForRat (layer, &line->Point1);
 567         CheckLinePointForRat (layer, &line->Point2);
 568         break;
 569       }
 570
 571     case LINEPOINT_TYPE:
 572       CheckLinePointForRat ((LayerType *) Ptr1, (PointType *) Ptr3);
 573       break;
 574
 575     case VIA_TYPE:
 576       CheckPinForRat ((PinType *) Ptr1);
 577       break;
 578     }
 579 }