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 i, 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   i = TEST_FLAG (ONSOLDERFLAG, Pad) ? solder_silk_layer : component_silk_layer;
 235   group = GetLayerGroupNumberByNumber (i);
 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   Cardinal i;
 321
 322   i = TEST_FLAG (ONSOLDERFLAG, Pad) ? solder_silk_layer : component_silk_layer;
 323   info.group = GetLayerGroupNumberByNumber (i);
 324   info.pad = Pad;
 325   info.type = PAD_TYPE;
 326
 327   r_search (PCB->Data->rat_tree, &Pad->BoundingBox, NULL, rat_callback,
 328             &info);
 329 }
 330
 331 static void
 332 CheckPinForRat (PinType *Pin)
 333 {
 334   struct rinfo info;
 335
 336   info.type = PIN_TYPE;
 337   info.pin = Pin;
 338   r_search (PCB->Data->rat_tree, &Pin->BoundingBox, NULL, rat_callback,
 339             &info);
 340 }
 341
 342 static void
 343 CheckLinePointForRat (LayerType *Layer, PointType *Point)
 344 {
 345   struct rinfo info;
 346   info.group = GetLayerGroupNumberByPointer (Layer);
 347   info.point = Point;
 348   info.type = LINEPOINT_TYPE;
 349
 350   r_search (PCB->Data->rat_tree, (BoxType *) Point, NULL, rat_callback,
 351             &info);
 352 }
 353
 354 /* ---------------------------------------------------------------------------
 355  * checks all visible lines. If one of the endpoints of the line lays
 356  * inside the pin, the line is added to the 'rubberband' list
 357  *
 358  * Square pins are handled as if they were round. Speed
 359  * and readability is more important then the few %
 360  * of failures that are immediately recognized
 361  */
 362 static void
 363 CheckPinForRubberbandConnection (PinType *Pin)
 364 {
 365   struct rubber_info info;
 366   Cardinal n;
 367   Coord t = Pin->Thickness / 2;
 368
 369   info.box.X1 = Pin->X - t;
 370   info.box.X2 = Pin->X + t;
 371   info.box.Y1 = Pin->Y - t;
 372   info.box.Y2 = Pin->Y + t;
 373   info.line = NULL;
 374   if (TEST_FLAG (SQUAREFLAG, Pin))
 375     info.radius = 0;
 376   else
 377     {
 378       info.radius = t;
 379       info.X = Pin->X;
 380       info.Y = Pin->Y;
 381     }
 382
 383   for (n = 0; n < max_copper_layer; n++)
 384     {
 385       info.layer = LAYER_PTR (n);
 386       r_search (info.layer->line_tree, &info.box, NULL, rubber_callback,
 387                 &info);
 388     }
 389 }
 390
 391 /* ---------------------------------------------------------------------------
 392  * checks all visible lines which belong to the same group as the passed line.
 393  * If one of the endpoints of the line lays * inside the passed line,
 394  * the scanned line is added to the 'rubberband' list
 395  */
 396 static void
 397 CheckLinePointForRubberbandConnection (LayerType *Layer,
 398                                        LineType *Line,
 399                                        PointType *LinePoint,
 400                                        bool Exact)
 401 {
 402   Cardinal group;
 403   struct rubber_info info;
 404   Coord t = Line->Thickness / 2;
 405
 406   /* lookup layergroup and check all visible lines in this group */
 407   info.radius = Exact ? -1 : MAX(Line->Thickness / 2, 1);
 408   info.box.X1 = LinePoint->X - t;
 409   info.box.X2 = LinePoint->X + t;
 410   info.box.Y1 = LinePoint->Y - t;
 411   info.box.Y2 = LinePoint->Y + t;
 412   info.line = Line;
 413   info.X = LinePoint->X;
 414   info.Y = LinePoint->Y;
 415   group = GetLayerGroupNumberByPointer (Layer);
 416   GROUP_LOOP (PCB->Data, group);
 417   {
 418     /* check all visible lines of the group member */
 419     if (layer->On)
 420       {
 421         info.layer = layer;
 422         r_search (layer->line_tree, &info.box, NULL, rubber_callback, &info);
 423       }
 424   }
 425   END_LOOP;
 426 }
 427
 428 /* ---------------------------------------------------------------------------
 429  * checks all visible lines which belong to the same group as the passed polygon.
 430  * If one of the endpoints of the line lays inside the passed polygon,
 431  * the scanned line is added to the 'rubberband' list
 432  */
 433 static void
 434 CheckPolygonForRubberbandConnection (LayerType *Layer,
 435                                      PolygonType *Polygon)
 436 {
 437   Cardinal group;
 438
 439   /* lookup layergroup and check all visible lines in this group */
 440   group = GetLayerGroupNumberByPointer (Layer);
 441   GROUP_LOOP (PCB->Data, group);
 442   {
 443     if (layer->On)
 444       {
 445         Coord thick;
 446
 447         /* the following code just stupidly compares the endpoints
 448          * of the lines
 449          */
 450         LINE_LOOP (layer);
 451         {
 452           if (TEST_FLAG (LOCKFLAG, line))
 453             continue;
 454           if (TEST_FLAG (CLEARLINEFLAG, line))
 455             continue;
 456           thick = (line->Thickness + 1) / 2;
 457           if (IsPointInPolygon (line->Point1.X, line->Point1.Y,
 458                                 thick, Polygon))
 459             CreateNewRubberbandEntry (layer, line, &line->Point1);
 460           if (IsPointInPolygon (line->Point2.X, line->Point2.Y,
 461                                 thick, Polygon))
 462             CreateNewRubberbandEntry (layer, line, &line->Point2);
 463         }
 464         END_LOOP;
 465       }
 466   }
 467   END_LOOP;
 468 }
 469
 470 /* ---------------------------------------------------------------------------
 471  * lookup all lines that are connected to an object and save the
 472  * data to 'Crosshair.AttachedObject.Rubberband'
 473  * lookup is only done for visible layers
 474  */
 475 void
 476 LookupRubberbandLines (int Type, void *Ptr1, void *Ptr2, void *Ptr3)
 477 {
 478
 479   /* the function is only supported for some types
 480    * check all visible lines;
 481    * it is only necessary to check if one of the endpoints
 482    * is connected
 483    */
 484   switch (Type)
 485     {
 486     case ELEMENT_TYPE:
 487       {
 488         ElementType *element = (ElementType *) Ptr1;
 489
 490         /* square pins are handled as if they are round. Speed
 491          * and readability is more important then the few %
 492          * of failures that are immediately recognized
 493          */
 494         PIN_LOOP (element);
 495         {
 496           CheckPinForRubberbandConnection (pin);
 497         }
 498         END_LOOP;
 499         PAD_LOOP (element);
 500         {
 501           CheckPadForRubberbandConnection (pad);
 502         }
 503         END_LOOP;
 504         break;
 505       }
 506
 507     case LINE_TYPE:
 508       {
 509         LayerType *layer = (LayerType *) Ptr1;
 510         LineType *line = (LineType *) Ptr2;
 511         if (GetLayerNumber (PCB->Data, layer) < max_copper_layer)
 512           {
 513             CheckLinePointForRubberbandConnection (layer, line,
 514                                                    &line->Point1, false);
 515             CheckLinePointForRubberbandConnection (layer, line,
 516                                                    &line->Point2, false);
 517           }
 518         break;
 519       }
 520
 521     case LINEPOINT_TYPE:
 522       if (GetLayerNumber (PCB->Data, (LayerType *) Ptr1) < max_copper_layer)
 523         CheckLinePointForRubberbandConnection ((LayerType *) Ptr1,
 524                                                (LineType *) Ptr2,
 525                                                (PointType *) Ptr3, true);
 526       break;
 527
 528     case VIA_TYPE:
 529       CheckPinForRubberbandConnection ((PinType *) Ptr1);
 530       break;
 531
 532     case POLYGON_TYPE:
 533       if (GetLayerNumber (PCB->Data, (LayerType *) Ptr1) < max_copper_layer)
 534         CheckPolygonForRubberbandConnection ((LayerType *) Ptr1,
 535                                              (PolygonType *) Ptr2);
 536       break;
 537     }
 538 }
 539
 540 void
 541 LookupRatLines (int Type, void *Ptr1, void *Ptr2, void *Ptr3)
 542 {
 543   switch (Type)
 544     {
 545     case ELEMENT_TYPE:
 546       {
 547         ElementType *element = (ElementType *) Ptr1;
 548
 549         PIN_LOOP (element);
 550         {
 551           CheckPinForRat (pin);
 552         }
 553         END_LOOP;
 554         PAD_LOOP (element);
 555         {
 556           CheckPadForRat (pad);
 557         }
 558         END_LOOP;
 559         break;
 560       }
 561
 562     case LINE_TYPE:
 563       {
 564         LayerType *layer = (LayerType *) Ptr1;
 565         LineType *line = (LineType *) Ptr2;
 566
 567         CheckLinePointForRat (layer, &line->Point1);
 568         CheckLinePointForRat (layer, &line->Point2);
 569         break;
 570       }
 571
 572     case LINEPOINT_TYPE:
 573       CheckLinePointForRat ((LayerType *) Ptr1, (PointType *) Ptr3);
 574       break;
 575
 576     case VIA_TYPE:
 577       CheckPinForRat ((PinType *) Ptr1);
 578       break;
 579     }
 580 }