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