pcb 4.1.1
An interactive printed circuit board layout editor.

rubberband.c

Go to the documentation of this file.
00001 
00036 #ifdef HAVE_CONFIG_H
00037 #include "config.h"
00038 #endif
00039 
00040 #include <stdlib.h>
00041 #ifdef HAVE_STRING_H
00042 #include <string.h>
00043 #endif
00044 #include <memory.h>
00045 #include <math.h>
00046 #ifdef HAVE_UNISTD_H
00047 #include <unistd.h>
00048 #endif
00049 
00050 #include "global.h"
00051 
00052 #include "create.h"
00053 #include "data.h"
00054 #include "error.h"
00055 #include "misc.h"
00056 #include "polygon.h"
00057 #include "rubberband.h"
00058 #include "rtree.h"
00059 #include "search.h"
00060 
00061 #ifdef HAVE_LIBDMALLOC
00062 #include <dmalloc.h>
00063 #endif
00064 
00065 /* ---------------------------------------------------------------------------
00066  * some local prototypes
00067  */
00068 static void CheckPadForRubberbandConnection (PadType *);
00069 static void CheckPinForRubberbandConnection (PinType *);
00070 static void CheckLinePointForRubberbandConnection (LayerType *,
00071                                                    LineType *,
00072                                                    PointType *,
00073                                                    bool);
00074 static void CheckArcPointForRubberbandConnection (LayerType *Layer,
00075                                                   ArcType *Arc,
00076                                                   PointType *ArcPoint,
00077                                                   bool Exact);
00078 static void CheckPolygonForRubberbandConnection (LayerType *,
00079                                                  PolygonType *);
00080 static void CheckLinePointForRat (LayerType *, PointType *);
00081 static int rubber_callback (const BoxType * b, void *cl);
00082 
00083 struct rubber_info
00084 {
00085   Coord radius;
00086   Coord X, Y;
00087   LineType *line;
00088   BoxType box;
00089   LayerType *layer;
00090 };
00091 
00092 static int
00093 rubber_callback (const BoxType * b, void *cl)
00094 {
00095   LineType *line = (LineType *) b;
00096   struct rubber_info *i = (struct rubber_info *) cl;
00097   double x, y, rad, dist1, dist2;
00098   Coord t;
00099   int touches = 0, n = 0 ;
00100 
00101   t = line->Thickness / 2;
00102 
00103   /* Check to see if the line is already in the rubberband list */
00104   for (n = 0; n < Crosshair.AttachedObject.RubberbandN; n++)
00105     if (Crosshair.AttachedObject.Rubberband[n].Line == line)
00106       return 0;
00107     
00108   if (TEST_FLAG (LOCKFLAG, line))
00109     return 0;
00110   if (line == i->line)
00111     return 0;
00112   /* 
00113    * Check to see if the line touches a rectangular region.
00114    * To do this we need to look for the intersection of a circular
00115    * region and a rectangular region.
00116    */
00117   if (i->radius == 0)
00118     {
00119       int found = 0;
00120 
00121       if (line->Point1.X + t >= i->box.X1 && line->Point1.X - t <= i->box.X2
00122           && line->Point1.Y + t >= i->box.Y1
00123           && line->Point1.Y - t <= i->box.Y2)
00124         {
00125           if (((i->box.X1 <= line->Point1.X) &&
00126                (line->Point1.X <= i->box.X2)) ||
00127               ((i->box.Y1 <= line->Point1.Y) &&
00128                (line->Point1.Y <= i->box.Y2)))
00129             {
00130               /* 
00131                * The circle is positioned such that the closest point
00132                * on the rectangular region boundary is not at a corner
00133                * of the rectangle.  i.e. the shortest line from circle
00134                * center to rectangle intersects the rectangle at 90
00135                * degrees.  In this case our first test is sufficient
00136                */
00137               touches = 1;
00138             }
00139           else
00140             {
00141               /* 
00142                * Now we must check the distance from the center of the
00143                * circle to the corners of the rectangle since the
00144                * closest part of the rectangular region is the corner.
00145                */
00146               x = MIN (abs (i->box.X1 - line->Point1.X),
00147                        abs (i->box.X2 - line->Point1.X));
00148               x *= x;
00149               y = MIN (abs (i->box.Y1 - line->Point1.Y),
00150                        abs (i->box.Y2 - line->Point1.Y));
00151               y *= y;
00152               x = x + y - (t * t);
00153 
00154               if (x <= 0)
00155                 touches = 1;
00156             }
00157           if (touches)
00158             {
00159               CreateNewRubberbandEntry (i->layer, line, &line->Point1);
00160               found++;
00161             }
00162         }
00163       if (line->Point2.X + t >= i->box.X1 && line->Point2.X - t <= i->box.X2
00164           && line->Point2.Y + t >= i->box.Y1
00165           && line->Point2.Y - t <= i->box.Y2)
00166         {
00167           if (((i->box.X1 <= line->Point2.X) &&
00168                (line->Point2.X <= i->box.X2)) ||
00169               ((i->box.Y1 <= line->Point2.Y) &&
00170                (line->Point2.Y <= i->box.Y2)))
00171             {
00172               touches = 1;
00173             }
00174           else
00175             {
00176               x = MIN (abs (i->box.X1 - line->Point2.X),
00177                        abs (i->box.X2 - line->Point2.X));
00178               x *= x;
00179               y = MIN (abs (i->box.Y1 - line->Point2.Y),
00180                        abs (i->box.Y2 - line->Point2.Y));
00181               y *= y;
00182               x = x + y - (t * t);
00183 
00184               if (x <= 0)
00185                 touches = 1;
00186             }
00187           if (touches)
00188             {
00189               CreateNewRubberbandEntry (i->layer, line, &line->Point2);
00190               found++;
00191             }
00192         }
00193       return found;
00194     }
00195   /* circular search region */
00196   if (i->radius < 0)
00197     rad = 0;  /* require exact match */
00198   else
00199     rad = SQUARE(i->radius + t);
00200 
00201   x = (i->X - line->Point1.X);
00202   x *= x;
00203   y = (i->Y - line->Point1.Y);
00204   y *= y;
00205   dist1 = x + y - rad;
00206 
00207   x = (i->X - line->Point2.X);
00208   x *= x;
00209   y = (i->Y - line->Point2.Y);
00210   y *= y;
00211   dist2 = x + y - rad;
00212 
00213   if (dist1 > 0 && dist2 > 0)
00214     return 0;
00215 
00216 #ifdef CLOSEST_ONLY     /* keep this to remind me */
00217   if (dist1 < dist2)
00218     CreateNewRubberbandEntry (i->layer, line, &line->Point1);
00219   else
00220     CreateNewRubberbandEntry (i->layer, line, &line->Point2);
00221 #else
00222   if (dist1 <= 0)
00223     CreateNewRubberbandEntry (i->layer, line, &line->Point1);
00224   if (dist2 <= 0)
00225     CreateNewRubberbandEntry (i->layer, line, &line->Point2);
00226 #endif
00227   return 1;
00228 }
00229 
00237 static void
00238 CheckPadForRubberbandConnection (PadType *Pad)
00239 {
00240   Coord half = Pad->Thickness / 2;
00241   Cardinal group;
00242   struct rubber_info info;
00243 
00244   info.box.X1 = MIN (Pad->Point1.X, Pad->Point2.X) - half;
00245   info.box.Y1 = MIN (Pad->Point1.Y, Pad->Point2.Y) - half;
00246   info.box.X2 = MAX (Pad->Point1.X, Pad->Point2.X) + half;
00247   info.box.Y2 = MAX (Pad->Point1.Y, Pad->Point2.Y) + half;
00248   info.radius = 0;
00249   info.line = NULL;
00250   group = GetLayerGroupNumberBySide (
00251       TEST_FLAG (ONSOLDERFLAG, Pad) ? BOTTOM_SIDE : TOP_SIDE);
00252 
00253   /* check all visible layers in the same group */
00254   GROUP_LOOP (PCB->Data, group);
00255   {
00256     /* check all visible lines of the group member */
00257     info.layer = layer;
00258     if (info.layer->On)
00259       {
00260         r_search (info.layer->line_tree, &info.box, NULL, rubber_callback,
00261                   &info);
00262       }
00263   }
00264   END_LOOP;
00265 }
00266 
00267 struct rinfo
00268 {
00269   int type;
00270   Cardinal group;
00271   PinType *pin;
00272   PadType *pad;
00273   PointType *point;
00274 };
00275 
00276 static int
00277 rat_callback (const BoxType * box, void *cl)
00278 {
00279   RatType *rat = (RatType *) box;
00280   struct rinfo *i = (struct rinfo *) cl;
00281 
00282   switch (i->type)
00283     {
00284     case PIN_TYPE:
00285       if (rat->Point1.X == i->pin->X && rat->Point1.Y == i->pin->Y)
00286         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
00287       else if (rat->Point2.X == i->pin->X && rat->Point2.Y == i->pin->Y)
00288         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
00289       break;
00290     case PAD_TYPE:
00291       if (rat->Point1.X == i->pad->Point1.X &&
00292           rat->Point1.Y == i->pad->Point1.Y && rat->group1 == i->group)
00293         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
00294       else
00295         if (rat->Point2.X == i->pad->Point1.X &&
00296             rat->Point2.Y == i->pad->Point1.Y && rat->group2 == i->group)
00297         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
00298       else
00299         if (rat->Point1.X == i->pad->Point2.X &&
00300             rat->Point1.Y == i->pad->Point2.Y && rat->group1 == i->group)
00301         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
00302       else
00303         if (rat->Point2.X == i->pad->Point2.X &&
00304             rat->Point2.Y == i->pad->Point2.Y && rat->group2 == i->group)
00305         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
00306       else
00307         if (rat->Point1.X == (i->pad->Point1.X + i->pad->Point2.X) / 2 &&
00308             rat->Point1.Y == (i->pad->Point1.Y + i->pad->Point2.Y) / 2 &&
00309             rat->group1 == i->group)
00310         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
00311       else
00312         if (rat->Point2.X == (i->pad->Point1.X + i->pad->Point2.X) / 2 &&
00313             rat->Point2.Y == (i->pad->Point1.Y + i->pad->Point2.Y) / 2 &&
00314             rat->group2 == i->group)
00315         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
00316       break;
00317     case LINEPOINT_TYPE:
00318       if (rat->group1 == i->group &&
00319           rat->Point1.X == i->point->X && rat->Point1.Y == i->point->Y)
00320         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point1);
00321       else
00322         if (rat->group2 == i->group &&
00323             rat->Point2.X == i->point->X && rat->Point2.Y == i->point->Y)
00324         CreateNewRubberbandEntry (NULL, (LineType *) rat, &rat->Point2);
00325       break;
00326     default:
00327       Message ("hace: bad rubber-rat lookup callback\n");
00328     }
00329   return 0;
00330 }
00331 
00332 static void
00333 CheckPadForRat (PadType *Pad)
00334 {
00335   struct rinfo info;
00336 
00337   info.group = GetLayerGroupNumberBySide (
00338                   TEST_FLAG (ONSOLDERFLAG, Pad) ? BOTTOM_SIDE : TOP_SIDE);
00339   info.pad = Pad;
00340   info.type = PAD_TYPE;
00341 
00342   r_search (PCB->Data->rat_tree, &Pad->BoundingBox, NULL, rat_callback,
00343             &info);
00344 }
00345 
00346 static void
00347 CheckPinForRat (PinType *Pin)
00348 {
00349   struct rinfo info;
00350 
00351   info.type = PIN_TYPE;
00352   info.pin = Pin;
00353   r_search (PCB->Data->rat_tree, &Pin->BoundingBox, NULL, rat_callback,
00354             &info);
00355 }
00356 
00357 static void
00358 CheckLinePointForRat (LayerType *Layer, PointType *Point)
00359 {
00360   struct rinfo info;
00361   info.group = GetLayerGroupNumberByPointer (Layer);
00362   info.point = Point;
00363   info.type = LINEPOINT_TYPE;
00364 
00365   r_search (PCB->Data->rat_tree, (BoxType *) Point, NULL, rat_callback,
00366             &info);
00367 }
00368 
00380 static void
00381 CheckPinForRubberbandConnection (PinType *Pin)
00382 {
00383   struct rubber_info info;
00384   Cardinal n;
00385   Coord t = Pin->Thickness / 2;
00386 
00387   info.box.X1 = Pin->X - t;
00388   info.box.X2 = Pin->X + t;
00389   info.box.Y1 = Pin->Y - t;
00390   info.box.Y2 = Pin->Y + t;
00391   info.line = NULL;
00392   if (TEST_FLAG (SQUAREFLAG, Pin))
00393     info.radius = 0;
00394   else
00395     {
00396       info.radius = t;
00397       info.X = Pin->X;
00398       info.Y = Pin->Y;
00399     }
00400 
00401   for (n = 0; n < max_copper_layer; n++)
00402     {
00403       info.layer = LAYER_PTR (n);
00404       r_search (info.layer->line_tree, &info.box, NULL, rubber_callback,
00405                 &info);
00406     }
00407 }
00408 
00416 static void
00417 CheckLinePointForRubberbandConnection (LayerType *Layer,
00418                                        LineType *Line,
00419                                        PointType *LinePoint,
00420                                        bool Exact)
00421 {
00422   Cardinal group;
00423   struct rubber_info info;
00424   Coord t = Line->Thickness / 2;
00425 
00426   /* lookup layergroup and check all visible lines in this group */
00427   info.radius = Exact ? -1 : MAX(Line->Thickness / 2, 1);
00428   info.box.X1 = LinePoint->X - t;
00429   info.box.X2 = LinePoint->X + t;
00430   info.box.Y1 = LinePoint->Y - t;
00431   info.box.Y2 = LinePoint->Y + t;
00432   info.line = Line;
00433   info.X = LinePoint->X;
00434   info.Y = LinePoint->Y;
00435   group = GetLayerGroupNumberByPointer (Layer);
00436   GROUP_LOOP (PCB->Data, group);
00437   {
00438     /* check all visible lines of the group member */
00439     if (layer->On)
00440       {
00441         info.layer = layer;
00442         r_search (layer->line_tree, &info.box, NULL, rubber_callback, &info);
00443       }
00444   }
00445   END_LOOP;
00446 }
00447 
00455 static void
00456 CheckArcPointForRubberbandConnection (LayerType *Layer,
00457                                       ArcType *Arc,
00458                                       PointType *ArcPoint,
00459                                       bool Exact)
00460 {
00461   Cardinal group;
00462   struct rubber_info info;
00463   Coord t = Arc->Thickness / 2;
00464 
00465   /* lookup layergroup and check all visible lines in this group */
00466   info.radius = Exact ? -1 : MAX(Arc->Thickness / 2, 1);
00467   info.box.X1 = ArcPoint->X - t;
00468   info.box.X2 = ArcPoint->X + t;
00469   info.box.Y1 = ArcPoint->Y - t;
00470   info.box.Y2 = ArcPoint->Y + t;
00471   info.line = NULL;
00472   info.X = ArcPoint->X;
00473   info.Y = ArcPoint->Y;
00474   group = GetLayerGroupNumberByPointer (Layer);
00475   GROUP_LOOP (PCB->Data, group);
00476   {
00477     /* check all visible lines of the group member */
00478     if (layer->On)
00479       {
00480         info.layer = layer;
00481         r_search (layer->line_tree, &info.box, NULL, rubber_callback, &info);
00482       }
00483   }
00484   END_LOOP;
00485 }
00486 
00487 /* ---------------------------------------------------------------------------
00488  * checks all visible lines which belong to the same group as the passed polygon.
00489  * If one of the endpoints of the line lays inside the passed polygon,
00490  * the scanned line is added to the 'rubberband' list.
00491  */
00492 static void
00493 CheckPolygonForRubberbandConnection (LayerType *Layer,
00494                                      PolygonType *Polygon)
00495 {
00496   Cardinal group;
00497 
00498   /* lookup layergroup and check all visible lines in this group */
00499   group = GetLayerGroupNumberByPointer (Layer);
00500   GROUP_LOOP (PCB->Data, group);
00501   {
00502     if (layer->On)
00503       {
00504         Coord thick;
00505 
00506         /* the following code just stupidly compares the endpoints
00507          * of the lines
00508          */
00509         LINE_LOOP (layer);
00510         {
00511           if (TEST_FLAG (LOCKFLAG, line))
00512             continue;
00513           if (TEST_FLAG (CLEARLINEFLAG, line))
00514             continue;
00515           thick = (line->Thickness + 1) / 2;
00516           if (IsPointInPolygon (line->Point1.X, line->Point1.Y,
00517                                 thick, Polygon))
00518             CreateNewRubberbandEntry (layer, line, &line->Point1);
00519           if (IsPointInPolygon (line->Point2.X, line->Point2.Y,
00520                                 thick, Polygon))
00521             CreateNewRubberbandEntry (layer, line, &line->Point2);
00522         }
00523         END_LOOP;
00524       }
00525   }
00526   END_LOOP;
00527 }
00528 
00535 void
00536 LookupRubberbandLines (int Type, void *Ptr1, void *Ptr2, void *Ptr3)
00537 {
00538 
00539   /* the function is only supported for some types
00540    * check all visible lines;
00541    * it is only necessary to check if one of the endpoints
00542    * is connected
00543    */
00544   switch (Type)
00545     {
00546     case ELEMENT_TYPE:
00547       {
00548         ElementType *element = (ElementType *) Ptr1;
00549 
00550         /* square pins are handled as if they are round. Speed
00551          * and readability is more important then the few %
00552          * of failures that are immediately recognized
00553          */
00554         PIN_LOOP (element);
00555         {
00556           CheckPinForRubberbandConnection (pin);
00557         }
00558         END_LOOP;
00559         PAD_LOOP (element);
00560         {
00561           CheckPadForRubberbandConnection (pad);
00562         }
00563         END_LOOP;
00564         break;
00565       }
00566 
00567     case LINE_TYPE:
00568       {
00569         LayerType *layer = (LayerType *) Ptr1;
00570         LineType *line = (LineType *) Ptr2;
00571         if (GetLayerNumber (PCB->Data, layer) < max_copper_layer)
00572           {
00573             CheckLinePointForRubberbandConnection (layer, line,
00574                                                    &line->Point1, false);
00575             CheckLinePointForRubberbandConnection (layer, line,
00576                                                    &line->Point2, false);
00577           }
00578         break;
00579       }
00580 
00581     case LINEPOINT_TYPE:
00582       if (GetLayerNumber (PCB->Data, (LayerType *) Ptr1) < max_copper_layer)
00583         CheckLinePointForRubberbandConnection ((LayerType *) Ptr1,
00584                                                (LineType *) Ptr2,
00585                                                (PointType *) Ptr3, true);
00586       break;
00587 
00588     case ARC_TYPE:
00589       {
00590         LayerType *layer = (LayerType *) Ptr1;
00591         ArcType *arc = (ArcType *) Ptr2;
00592         if (GetLayerNumber (PCB->Data, layer) < max_copper_layer)
00593           {
00594             CheckArcPointForRubberbandConnection (layer, arc,
00595                                                   &arc->Point1, false);
00596             CheckArcPointForRubberbandConnection (layer, arc,
00597                                                   &arc->Point2, false);
00598           }
00599         break;
00600       }
00601 
00602     case VIA_TYPE:
00603       CheckPinForRubberbandConnection ((PinType *) Ptr1);
00604       break;
00605 
00606     case POLYGON_TYPE:
00607       if (GetLayerNumber (PCB->Data, (LayerType *) Ptr1) < max_copper_layer)
00608         CheckPolygonForRubberbandConnection ((LayerType *) Ptr1,
00609                                              (PolygonType *) Ptr2);
00610       break;
00611     }
00612 }
00613 
00614 void
00615 LookupRatLines (int Type, void *Ptr1, void *Ptr2, void *Ptr3)
00616 {
00617   switch (Type)
00618     {
00619     case ELEMENT_TYPE:
00620       {
00621         ElementType *element = (ElementType *) Ptr1;
00622 
00623         PIN_LOOP (element);
00624         {
00625           CheckPinForRat (pin);
00626         }
00627         END_LOOP;
00628         PAD_LOOP (element);
00629         {
00630           CheckPadForRat (pad);
00631         }
00632         END_LOOP;
00633         break;
00634       }
00635 
00636     case LINE_TYPE:
00637       {
00638         LayerType *layer = (LayerType *) Ptr1;
00639         LineType *line = (LineType *) Ptr2;
00640 
00641         CheckLinePointForRat (layer, &line->Point1);
00642         CheckLinePointForRat (layer, &line->Point2);
00643         break;
00644       }
00645 
00646     case LINEPOINT_TYPE:
00647       CheckLinePointForRat ((LayerType *) Ptr1, (PointType *) Ptr3);
00648       break;
00649 
00650     case VIA_TYPE:
00651       CheckPinForRat ((PinType *) Ptr1);
00652       break;
00653     }
00654 }