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                                                    bool);
  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   Coord radius;
  82   Coord 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   double x, y, rad, dist1, dist2;
  94   Coord 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   Coord 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 = TEST_FLAG (ONSOLDERFLAG, Pad) ? solder_silk_layer : component_silk_layer;
 240   group = GetLayerGroupNumberByNumber (i);
 241
 242   /* check all visible layers in the same group */
 243   GROUP_LOOP (PCB->Data, group);
 244   {
 245     /* check all visible lines of the group member */
 246     info.layer = layer;
 247     if (info.layer->On)
 248       {
 249         r_search (info.layer->line_tree, &info.box, NULL, rubber_callback,
 250                   &info);
 251       }
 252   }
 253   END_LOOP;
 254 }
 255
 256 struct rinfo
 257 {
 258   int type;
 259   Cardinal group;
 260   PinTypePtr pin;
 261   PadTypePtr pad;
 262   PointTypePtr point;
 263 };
 264
 265 static int
 266 rat_callback (const BoxType * box, void *cl)
 267 {
 268   RatTypePtr rat = (RatTypePtr) box;
 269   struct rinfo *i = (struct rinfo *) cl;
 270
 271   switch (i->type)
 272     {
 273     case PIN_TYPE:
 274       if (rat->Point1.X == i->pin->X && rat->Point1.Y == i->pin->Y)
 275         CreateNewRubberbandEntry (NULL, (LineTypePtr) rat, &rat->Point1);
 276       else if (rat->Point2.X == i->pin->X && rat->Point2.Y == i->pin->Y)
 277         CreateNewRubberbandEntry (NULL, (LineTypePtr) rat, &rat->Point2);
 278       break;
 279     case PAD_TYPE:
 280       if (rat->Point1.X == i->pad->Point1.X &&
 281           rat->Point1.Y == i->pad->Point1.Y && rat->group1 == i->group)
 282         CreateNewRubberbandEntry (NULL, (LineTypePtr) rat, &rat->Point1);
 283       else
 284         if (rat->Point2.X == i->pad->Point1.X &&
 285             rat->Point2.Y == i->pad->Point1.Y && rat->group2 == i->group)
 286         CreateNewRubberbandEntry (NULL, (LineTypePtr) rat, &rat->Point2);
 287       else
 288         if (rat->Point1.X == i->pad->Point2.X &&
 289             rat->Point1.Y == i->pad->Point2.Y && rat->group1 == i->group)
 290         CreateNewRubberbandEntry (NULL, (LineTypePtr) rat, &rat->Point1);
 291       else
 292         if (rat->Point2.X == i->pad->Point2.X &&
 293             rat->Point2.Y == i->pad->Point2.Y && rat->group2 == i->group)
 294         CreateNewRubberbandEntry (NULL, (LineTypePtr) rat, &rat->Point2);
 295       else
 296         if (rat->Point1.X == (i->pad->Point1.X + i->pad->Point2.X) / 2 &&
 297             rat->Point1.Y == (i->pad->Point1.Y + i->pad->Point2.Y) / 2 &&
 298             rat->group1 == i->group)
 299         CreateNewRubberbandEntry (NULL, (LineTypePtr) rat, &rat->Point1);
 300       else
 301         if (rat->Point2.X == (i->pad->Point1.X + i->pad->Point2.X) / 2 &&
 302             rat->Point2.Y == (i->pad->Point1.Y + i->pad->Point2.Y) / 2 &&
 303             rat->group2 == i->group)
 304         CreateNewRubberbandEntry (NULL, (LineTypePtr) rat, &rat->Point2);
 305       break;
 306     case LINEPOINT_TYPE:
 307       if (rat->group1 == i->group &&
 308           rat->Point1.X == i->point->X && rat->Point1.Y == i->point->Y)
 309         CreateNewRubberbandEntry (NULL, (LineTypePtr) rat, &rat->Point1);
 310       else
 311         if (rat->group2 == i->group &&
 312             rat->Point2.X == i->point->X && rat->Point2.Y == i->point->Y)
 313         CreateNewRubberbandEntry (NULL, (LineTypePtr) rat, &rat->Point2);
 314       break;
 315     default:
 316       Message ("hace: bad rubber-rat lookup callback\n");
 317     }
 318   return 0;
 319 }
 320
 321 static void
 322 CheckPadForRat (PadTypePtr Pad)
 323 {
 324   struct rinfo info;
 325   Cardinal i;
 326
 327   i = TEST_FLAG (ONSOLDERFLAG, Pad) ? solder_silk_layer : component_silk_layer;
 328   info.group = GetLayerGroupNumberByNumber (i);
 329   info.pad = Pad;
 330   info.type = PAD_TYPE;
 331
 332   r_search (PCB->Data->rat_tree, &Pad->BoundingBox, NULL, rat_callback,
 333             &info);
 334 }
 335
 336 static void
 337 CheckPinForRat (PinTypePtr Pin)
 338 {
 339   struct rinfo info;
 340
 341   info.type = PIN_TYPE;
 342   info.pin = Pin;
 343   r_search (PCB->Data->rat_tree, &Pin->BoundingBox, NULL, rat_callback,
 344             &info);
 345 }
 346
 347 static void
 348 CheckLinePointForRat (LayerTypePtr Layer, PointTypePtr Point)
 349 {
 350   struct rinfo info;
 351   info.group = GetLayerGroupNumberByPointer (Layer);
 352   info.point = Point;
 353   info.type = LINEPOINT_TYPE;
 354
 355   r_search (PCB->Data->rat_tree, (BoxType *) Point, NULL, rat_callback,
 356             &info);
 357 }
 358
 359 /* ---------------------------------------------------------------------------
 360  * checks all visible lines. If one of the endpoints of the line lays
 361  * inside the pin, the line is added to the 'rubberband' list
 362  *
 363  * Square pins are handled as if they were round. Speed
 364  * and readability is more important then the few %
 365  * of failures that are immediately recognized
 366  */
 367 static void
 368 CheckPinForRubberbandConnection (PinTypePtr Pin)
 369 {
 370   struct rubber_info info;
 371   Cardinal n;
 372   Coord t = Pin->Thickness / 2;
 373
 374   info.box.X1 = Pin->X - t;
 375   info.box.X2 = Pin->X + t;
 376   info.box.Y1 = Pin->Y - t;
 377   info.box.Y2 = Pin->Y + t;
 378   info.line = NULL;
 379   if (TEST_FLAG (SQUAREFLAG, Pin))
 380     info.radius = 0;
 381   else
 382     {
 383       info.radius = t;
 384       info.X = Pin->X;
 385       info.Y = Pin->Y;
 386     }
 387
 388   for (n = 0; n < max_copper_layer; n++)
 389     {
 390       info.layer = LAYER_PTR (n);
 391       r_search (info.layer->line_tree, &info.box, NULL, rubber_callback,
 392                 &info);
 393     }
 394 }
 395
 396 /* ---------------------------------------------------------------------------
 397  * checks all visible lines which belong to the same group as the passed line.
 398  * If one of the endpoints of the line lays * inside the passed line,
 399  * the scanned line is added to the 'rubberband' list
 400  */
 401 static void
 402 CheckLinePointForRubberbandConnection (LayerTypePtr Layer,
 403                                        LineTypePtr Line,
 404                                        PointTypePtr LinePoint,
 405                                        bool Exact)
 406 {
 407   Cardinal group;
 408   struct rubber_info info;
 409   Coord t = Line->Thickness / 2;
 410
 411   /* lookup layergroup and check all visible lines in this group */
 412   info.radius = Exact ? -1 : MAX(Line->Thickness / 2, 1);
 413   info.box.X1 = LinePoint->X - t;
 414   info.box.X2 = LinePoint->X + t;
 415   info.box.Y1 = LinePoint->Y - t;
 416   info.box.Y2 = LinePoint->Y + t;
 417   info.line = Line;
 418   info.X = LinePoint->X;
 419   info.Y = LinePoint->Y;
 420   group = GetLayerGroupNumberByPointer (Layer);
 421   GROUP_LOOP (PCB->Data, group);
 422   {
 423     /* check all visible lines of the group member */
 424     if (layer->On)
 425       {
 426         info.layer = layer;
 427         r_search (layer->line_tree, &info.box, NULL, rubber_callback, &info);
 428       }
 429   }
 430   END_LOOP;
 431 }
 432
 433 /* ---------------------------------------------------------------------------
 434  * checks all visible lines which belong to the same group as the passed polygon.
 435  * If one of the endpoints of the line lays inside the passed polygon,
 436  * the scanned line is added to the 'rubberband' list
 437  */
 438 static void
 439 CheckPolygonForRubberbandConnection (LayerTypePtr Layer,
 440                                      PolygonTypePtr Polygon)
 441 {
 442   Cardinal group;
 443
 444   /* lookup layergroup and check all visible lines in this group */
 445   group = GetLayerGroupNumberByPointer (Layer);
 446   GROUP_LOOP (PCB->Data, group);
 447   {
 448     if (layer->On)
 449       {
 450         Coord thick;
 451
 452         /* the following code just stupidly compares the endpoints
 453          * of the lines
 454          */
 455         LINE_LOOP (layer);
 456         {
 457           if (TEST_FLAG (LOCKFLAG, line))
 458             continue;
 459           if (TEST_FLAG (CLEARLINEFLAG, line))
 460             continue;
 461           thick = (line->Thickness + 1) / 2;
 462           if (IsPointInPolygon (line->Point1.X, line->Point1.Y,
 463                                 thick, Polygon))
 464             CreateNewRubberbandEntry (layer, line, &line->Point1);
 465           if (IsPointInPolygon (line->Point2.X, line->Point2.Y,
 466                                 thick, Polygon))
 467             CreateNewRubberbandEntry (layer, line, &line->Point2);
 468         }
 469         END_LOOP;
 470       }
 471   }
 472   END_LOOP;
 473 }
 474
 475 /* ---------------------------------------------------------------------------
 476  * lookup all lines that are connected to an object and save the
 477  * data to 'Crosshair.AttachedObject.Rubberband'
 478  * lookup is only done for visible layers
 479  */
 480 void
 481 LookupRubberbandLines (int Type, void *Ptr1, void *Ptr2, void *Ptr3)
 482 {
 483
 484   /* the function is only supported for some types
 485    * check all visible lines;
 486    * it is only necessary to check if one of the endpoints
 487    * is connected
 488    */
 489   switch (Type)
 490     {
 491     case ELEMENT_TYPE:
 492       {
 493         ElementTypePtr element = (ElementTypePtr) Ptr1;
 494
 495         /* square pins are handled as if they are round. Speed
 496          * and readability is more important then the few %
 497          * of failures that are immediately recognized
 498          */
 499         PIN_LOOP (element);
 500         {
 501           CheckPinForRubberbandConnection (pin);
 502         }
 503         END_LOOP;
 504         PAD_LOOP (element);
 505         {
 506           CheckPadForRubberbandConnection (pad);
 507         }
 508         END_LOOP;
 509         break;
 510       }
 511
 512     case LINE_TYPE:
 513       {
 514         LayerTypePtr layer = (LayerTypePtr) Ptr1;
 515         LineTypePtr line = (LineTypePtr) Ptr2;
 516         if (GetLayerNumber (PCB->Data, layer) < max_copper_layer)
 517           {
 518             CheckLinePointForRubberbandConnection (layer, line,
 519                                                    &line->Point1, false);
 520             CheckLinePointForRubberbandConnection (layer, line,
 521                                                    &line->Point2, false);
 522           }
 523         break;
 524       }
 525
 526     case LINEPOINT_TYPE:
 527       if (GetLayerNumber (PCB->Data, (LayerTypePtr) Ptr1) < max_copper_layer)
 528         CheckLinePointForRubberbandConnection ((LayerTypePtr) Ptr1,
 529                                                (LineTypePtr) Ptr2,
 530                                                (PointTypePtr) Ptr3, true);
 531       break;
 532
 533     case VIA_TYPE:
 534       CheckPinForRubberbandConnection ((PinTypePtr) Ptr1);
 535       break;
 536
 537     case POLYGON_TYPE:
 538       if (GetLayerNumber (PCB->Data, (LayerTypePtr) Ptr1) < max_copper_layer)
 539         CheckPolygonForRubberbandConnection ((LayerTypePtr) Ptr1,
 540                                              (PolygonTypePtr) Ptr2);
 541       break;
 542     }
 543 }
 544
 545 void
 546 LookupRatLines (int Type, void *Ptr1, void *Ptr2, void *Ptr3)
 547 {
 548   switch (Type)
 549     {
 550     case ELEMENT_TYPE:
 551       {
 552         ElementTypePtr element = (ElementTypePtr) Ptr1;
 553
 554         PIN_LOOP (element);
 555         {
 556           CheckPinForRat (pin);
 557         }
 558         END_LOOP;
 559         PAD_LOOP (element);
 560         {
 561           CheckPadForRat (pad);
 562         }
 563         END_LOOP;
 564         break;
 565       }
 566
 567     case LINE_TYPE:
 568       {
 569         LayerTypePtr layer = (LayerTypePtr) Ptr1;
 570         LineTypePtr line = (LineTypePtr) Ptr2;
 571
 572         CheckLinePointForRat (layer, &line->Point1);
 573         CheckLinePointForRat (layer, &line->Point2);
 574         break;
 575       }
 576
 577     case LINEPOINT_TYPE:
 578       CheckLinePointForRat ((LayerTypePtr) Ptr1, (PointTypePtr) Ptr3);
 579       break;
 580
 581     case VIA_TYPE:
 582       CheckPinForRat ((PinTypePtr) Ptr1);
 583       break;
 584     }
 585 }