jostle.c

00001 /* jostle plug-in for PCB
00002 
00003    Pushes lines out of the way.
00004 
00005    Copyright (C) 2007 Ben Jackson <ben@ben.com>
00006 
00007    Licensed under the terms of the GNU General Public License, version
00008    2 or later.
00009 */
00010 
00011 /* $Id: jostle.c,v 1.9 2007/12/02 20:32:04 bjj Exp bjj $ */
00012 
00013 #include <stdio.h>
00014 #include <math.h>
00015 #include <float.h>
00016 #include <stdlib.h>
00017 #include <unistd.h>
00018 
00019 #include "global.h"
00020 #include "data.h"
00021 #include "hid.h"
00022 #include "misc.h"
00023 #include "create.h"
00024 #include "rtree.h"
00025 #include "undo.h"
00026 #include "rats.h"
00027 #include "polygon.h"
00028 #include "remove.h"
00029 #include "error.h"
00030 #include "set.h"
00031 
00032 //#define DEBUG_POLYAREA
00033 
00034 double vect_dist2 (Vector v1, Vector v2);
00035 #define Vcpy2(r,a)              {(r)[0] = (a)[0]; (r)[1] = (a)[1];}
00036 #define Vswp2(a,b) { long t; \
00037         t = (a)[0], (a)[0] = (b)[0], (b)[0] = t; \
00038         t = (a)[1], (a)[1] = (b)[1], (b)[1] = t; \
00039 }
00040 
00041 //{if (!Marked.status && side==NORTHWEST) { DrawMark(True); Marked.status = True; Marked.X = p[0]; Marked.Y = p[1]; DrawMark(False);} }
00042 
00043 enum {
00044         NORTH, NORTHEAST, EAST, SOUTHEAST, SOUTH, SOUTHWEST, WEST, NORTHWEST
00045 };
00046 const char *dirnames[] = {
00047         "NORTH", "NORTHEAST", "EAST", "SOUTHEAST", "SOUTH", "SOUTHWEST", "WEST", "NORTHWEST"
00048 };
00049 
00050 #define ARG(n) (argc > (n) ? argv[n] : 0)
00051 
00052 static const char jostle_syntax[] = "Jostle(diameter)";
00053 
00054 /* DEBUG */
00055 static void
00056 DebugPOLYAREA (POLYAREA *s, char *color)
00057 {
00058   int *x, *y, n, i = 0;
00059   PLINE *pl;
00060   VNODE *v;
00061   POLYAREA *p;
00062 
00063 #ifndef DEBUG_POLYAREA
00064  return;
00065 #endif
00066  p = s;
00067  do {
00068  for (pl = p->contours; pl; pl = pl->next) {
00069   n = pl->Count;
00070   x = (int *) malloc (n * sizeof (int));
00071   y = (int *) malloc (n * sizeof (int));
00072   for (v = &pl->head; i < n; v = v->next)
00073     {
00074       x[i] = v->point[0];
00075       y[i++] = v->point[1];
00076     }
00077   if (1)
00078     {
00079       gui->set_color (Output.fgGC, color ? color : PCB->ConnectedColor);
00080       gui->set_line_width (Output.fgGC, 1);
00081       for (i = 0; i < n - 1; i++)
00082         {
00083           gui->draw_line (Output.fgGC, x[i], y[i], x[i + 1], y[i + 1]);
00084           //  gui->fill_circle (Output.fgGC, x[i], y[i], 30);
00085         }
00086       gui->draw_line (Output.fgGC, x[n - 1], y[n - 1], x[0], y[0]);
00087     }
00088   free (x);
00089   free (y);
00090  }
00091  } while ((p = p->f) != s);
00092  hid_action("Busy");
00093  sleep(3);
00094 }
00095 
00096 
00097 #if 0
00098 enum {
00099         K_X,
00100         K_Y,
00101         K_Lefts,
00102         K_Rights,
00103         K_Tops,
00104         K_Bottoms,
00105         K_Centers,
00106         K_Marks,
00107         K_Gaps,
00108         K_First,
00109         K_Last,
00110         K_Average,
00111         K_Crosshair,
00112         K_Gridless,
00113         K_none,
00114         K_align,
00115         K_distribute
00116 };
00117 
00118 static const char *keywords[] = {
00119         [K_X]           "X",
00120         [K_Y]           "Y",
00121         [K_Lefts]       "Lefts",
00122         [K_Rights]      "Rights",
00123         [K_Tops]        "Tops",
00124         [K_Bottoms]     "Bottoms",
00125         [K_Centers]     "Centers",
00126         [K_Marks]       "Marks",
00127         [K_Gaps]        "Gaps",
00128         [K_First]       "First",
00129         [K_Last]        "Last",
00130         [K_Average]     "Average",
00131         [K_Crosshair]   "Crosshair",
00132         [K_Gridless]    "Gridless",
00133 };
00134 
00135 static int
00136 keyword(const char *s)
00137 {
00138         int i;
00139 
00140         if (! s) {
00141                 return K_none;
00142         }
00143         for (i = 0; i < ENTRIES(keywords); ++i) {
00144                 if (keywords[i] && strcasecmp(s, keywords[i]) == 0)
00145                         return i;
00146         }
00147         return -1;
00148 }
00149 #endif
00150 
00151 /*
00152  * Find the bounding box of a POLYAREA
00153  * POLYAREAs linked by ->f/b are outlines.  n->contours->next would
00154  * be the start of the inner holes (irrelevant for bounding box)
00155  */
00156 static BoxType
00157 POLYAREA_boundingBox(POLYAREA *a)
00158 {
00159         POLYAREA *n;
00160         PLINE *pa;
00161         BoxType box;
00162         int first = 1;
00163 
00164         n = a;
00165         do {
00166                 pa = n->contours;
00167                 if (first) {
00168                         box.X1 = pa->xmin;
00169                         box.X2 = pa->xmax + 1;
00170                         box.Y1 = pa->ymin;
00171                         box.Y2 = pa->ymax + 1;
00172                         first = 0;
00173                 } else {
00174                         MAKEMIN(box.X1, pa->xmin);
00175                         MAKEMAX(box.X2, pa->xmax + 1);
00176                         MAKEMIN(box.Y1, pa->ymin);
00177                         MAKEMAX(box.Y2, pa->ymax + 1);
00178                 }
00179         } while ((n = n->f) != a);
00180         return box;
00181 }
00182 
00183 /*
00184  * Given a polygon and a side of it (a direction north/northeast/etc), find
00185  * a line tangent to that side, offset by clearance, and return it as a
00186  * pair of vectors PQ.
00187  * Make it long so it will intersect everything in the area.
00188  */
00189 static void
00190 POLYAREA_findXmostLine(POLYAREA *a, int side, Vector p, Vector q, BDimension clearance)
00191 {
00192         p[0] = p[1] = 0;
00193         q[0] = q[1] = 0;
00194         int extra = a->contours->xmax - a->contours->xmin +
00195                     a->contours->ymax - a->contours->ymin;
00196 
00197         switch (side) {
00198         case NORTH:
00199                 p[1] = q[1] = a->contours->ymin - clearance;
00200                 p[0] = a->contours->xmin - extra;
00201                 q[0] = a->contours->xmax + extra;
00202                 break;
00203         case SOUTH:
00204                 p[1] = q[1] = a->contours->ymax + clearance;
00205                 p[0] = a->contours->xmin - extra;
00206                 q[0] = a->contours->xmax + extra;
00207                 break;
00208         case EAST:
00209                 p[0] = q[0] = a->contours->xmax + clearance;
00210                 p[1] = a->contours->ymin - extra;
00211                 q[1] = a->contours->ymax + extra;
00212                 break;
00213         case WEST:
00214                 p[0] = q[0] = a->contours->xmin - clearance;
00215                 p[1] = a->contours->ymin - extra;
00216                 q[1] = a->contours->ymax + extra;
00217                 break;
00218         default: {                      /* diagonal case */
00219                 int kx, ky, minmax, dq, ckx, cky;
00220                 LocationType mm[2] = {MAX_COORD, -MAX_COORD};
00221                 Vector mmp[2];
00222                 VNODE *v;
00223 
00224                 switch (side) {
00225                 case NORTHWEST:
00226                         kx = 1;         /* new_x = kx * x + ky * y */
00227                         ky = 1;
00228                         dq = -1;        /* extend line in +x, dq*y */
00229                         ckx = cky = -1; /* clear line in ckx*clear, cky*clear */
00230                         minmax = 0;     /* min or max */
00231                         break;
00232                 case SOUTHWEST:
00233                         kx = 1;
00234                         ky = -1;
00235                         dq = 1;
00236                         ckx = -1;
00237                         cky = 1;
00238                         minmax = 0;
00239                         break;
00240                 case NORTHEAST:
00241                         kx = 1;
00242                         ky = -1;
00243                         dq = 1;
00244                         ckx = 1;
00245                         cky = -1;
00246                         minmax = 1;
00247                         break;
00248                 case SOUTHEAST:
00249                         kx = ky = 1;
00250                         dq = -1;
00251                         ckx = cky = 1;
00252                         minmax = 1;
00253                         break;
00254                 default:
00255                         Message("bjj: aiee, what side?");
00256                         return;
00257                 }
00258                 v = &a->contours->head;
00259                 do {
00260                         int test = kx * v->point[0] + ky * v->point[1];
00261                         if (test < mm[0]) {
00262                                 mm[0] = test;
00263                                 mmp[0][0] = v->point[0];
00264                                 mmp[0][1] = v->point[1];
00265                         }
00266                         if (test > mm[1]) {
00267                                 mm[1] = test;
00268                                 mmp[1][0] = v->point[0];
00269                                 mmp[1][1] = v->point[1];
00270                         }
00271                 } while ((v = v->next) != &a->contours->head);
00272                 Vcpy2(p, mmp[minmax]);
00273                 /* add clearance in the right direction */
00274                 clearance *= 0.707123;  /* = cos(45) = sqrt(2)/2 */
00275                 p[0] += ckx * clearance;
00276                 p[1] += cky * clearance;
00277                 /* now create a tangent line to that point */
00278                 Vcpy2(q, p);
00279                 p[0] += -extra;
00280                 p[1] += -extra * dq;
00281                 q[0] += extra;
00282                 q[1] += extra * dq;
00283         }
00284         }
00285 }
00286 
00287 /*
00288  * Given a 'side' from the NORTH/SOUTH/etc enum, rotate it by n
00289  */
00290 static int
00291 rotateSide(int side, int n)
00292 {
00293         return (side + n + 8) % 8;
00294 }
00295 
00296 /*
00297  * Wrapper for CreateNewLineOnLayer that takes vectors and deals with Undo
00298  */
00299 static LineTypePtr
00300 CreateVectorLineOnLayer(LayerTypePtr layer, Vector a, Vector b, BDimension thickness, BDimension clearance, FlagType flags)
00301 {
00302         LineTypePtr line;
00303 
00304         line = CreateNewLineOnLayer(layer, a[0], a[1], b[0], b[1], thickness, clearance, flags);
00305         if (line) {
00306                 AddObjectToCreateUndoList (LINE_TYPE, layer, line, line);
00307         }
00308         return line;
00309 }
00310 
00311 static LineTypePtr
00312 MakeBypassLine(LayerTypePtr layer, Vector a, Vector b, LineTypePtr orig, POLYAREA **expandp)
00313 {
00314         LineTypePtr line;
00315 
00316         line = CreateVectorLineOnLayer(layer, a, b,
00317                 orig->Thickness, orig->Clearance, orig->Flags);
00318         if (line && expandp) {
00319                 POLYAREA *p = LinePoly(line, line->Thickness + line->Clearance);
00320                 poly_Boolean_free(*expandp, p, expandp, PBO_UNITE);
00321         }
00322         return line;
00323 }
00324 
00325 /*
00326  * Given a 'brush' that's pushing things out of the way (possibly already
00327  * cut down to just the part relevant to our line) and a line that
00328  * intersects it on some layer, find the 45/90 lines required to go around
00329  * the brush on the named side.  Create them and remove the original.
00330  */
00331 static int
00332 MakeBypassingLines(POLYAREA *brush, LayerTypePtr layer, LineType *line, int side, POLYAREA **expandp)
00333 {
00334         Vector pA, pB, flatA, flatB, qA, qB;
00335         Vector lA, lB;
00336         Vector a, b, c, d, junk;
00337         int hits;
00338 
00339         SET_FLAG(DRCFLAG, line);        /* will cause sublines to inherit */
00340         lA[0] = line->Point1.X;
00341         lA[1] = line->Point1.Y;
00342         lB[0] = line->Point2.X;
00343         lB[1] = line->Point2.Y;
00344 
00345         /*
00346          * Imagine side = north:
00347          *
00348          *                 /      \
00349          *            ----b##FLAT##c----
00350          *               Q          P
00351          *   lA-ORIG####a            d####ORIG-lB
00352          *             /              \
00353          *
00354          * First find the extended three lines that go around the brush.
00355          * Then intersect them with each other and the original to find
00356          * points a, b, c, d.  Finally connect the dots and remove the
00357          * old straight line.
00358          */
00359         POLYAREA_findXmostLine(brush, side, flatA, flatB, line->Thickness / 2);
00360         POLYAREA_findXmostLine(brush, rotateSide(side, 1), pA, pB, line->Thickness / 2);
00361         POLYAREA_findXmostLine(brush, rotateSide(side, -1), qA, qB, line->Thickness / 2);
00362         hits = vect_inters2(lA, lB, qA, qB, a, junk) + 
00363                vect_inters2(qA, qB, flatA, flatB, b, junk) +
00364                vect_inters2(pA, pB, flatA, flatB, c, junk) +
00365                vect_inters2(lA, lB, pA, pB, d, junk);
00366         if (hits != 4) {
00367                 return 0;
00368         }
00369         /* flip the line endpoints to match up with a/b */
00370         if (vect_dist2(lA, d) < vect_dist2(lA, a)) {
00371                 Vswp2(lA, lB);
00372         }
00373         MakeBypassLine(layer, lA, a, line, NULL);
00374         MakeBypassLine(layer, a, b, line, expandp);
00375         MakeBypassLine(layer, b, c, line, expandp);
00376         MakeBypassLine(layer, c, d, line, expandp);
00377         MakeBypassLine(layer, d, lB, line, NULL);
00378         RemoveLine(layer, line);
00379         return 1;
00380 }
00381 
00382 struct info {
00383         BoxType box;
00384         POLYAREA *brush;
00385         LayerTypePtr layer;
00386 
00387         POLYAREA *smallest;     /* after cutting brush with line,
00388                                  * the smallest chunk, which we will go
00389                                  * around on 'side' */
00390         LineTypePtr line;
00391         int side;
00392         double centroid;        /* smallest difference between slices of
00393                                  * brush after cutting with line, trying
00394                                  * to find the line closest to the centroid
00395                                  * to process first */
00396 };
00397 
00398 /*
00399  * Process lines that intersect our 'brush'
00400  */
00401 static int
00402 jostle_callback(const BoxType *targ, void *private)
00403 {
00404         LineType *line = (LineType *) targ;
00405         struct info *info = private;
00406         POLYAREA *lp, *copy, *tmp, *n, *smallest = NULL;
00407         Vector p;
00408         int inside = 0, side, r;
00409         double small, big;
00410         int nocentroid = 0;
00411 
00412         if (TEST_FLAG(DRCFLAG, line)) {
00413                 return 0;
00414         }
00415         fprintf(stderr, "hit! %p\n", line);
00416         p[0] = line->Point1.X;
00417         p[1] = line->Point1.Y;
00418         if (poly_InsideContour(info->brush->contours, p)) {
00419                 fprintf(stderr, "\tinside1 %d,%d\n", p[0],p[1]);
00420                 inside++;
00421         }
00422         p[0] = line->Point2.X;
00423         p[1] = line->Point2.Y;
00424         if (poly_InsideContour(info->brush->contours, p)) {
00425                 fprintf(stderr, "\tinside2 %d,%d\n", p[0],p[1]);
00426                 inside++;
00427         }
00428         lp = LinePoly(line, line->Thickness);
00429         if (! Touching(lp, info->brush)) {
00430                 /* not a factor */
00431                 return 0;
00432         }
00433         poly_Free(&lp);
00434 
00435         if (inside) {
00436                 // XXX not done!
00437                 // XXX if this is part of a series of lines passing
00438                 // XXX through, need to process as a group.
00439                 // XXX if it just ends in here, shorten it??
00440                 return 0;
00441         }
00442         /*
00443          * Cut the brush with the line to figure out which side to go
00444          * around.  Use a very fine line.  XXX can still graze
00445          */
00446         lp = LinePoly(line, 1);
00447         if (!poly_M_Copy0(&copy, info->brush))
00448                 return 0;
00449         r = poly_Boolean_free(copy, lp, &tmp, PBO_SUB);
00450         if (r != err_ok) {
00451                 fprintf(stderr, "Error while jostling PBO_SUB: %d\n", r);
00452                 return 0;
00453         }
00454         if (tmp == tmp->f) {
00455                 /* it didn't slice, must have glanced.  intersect instead
00456                  * to get the glancing sliver??
00457                  */
00458 fprintf(stderr, "try isect??\n");
00459                 lp = LinePoly(line, line->Thickness);
00460                 r = poly_Boolean_free(tmp, lp, &tmp, PBO_ISECT);
00461                 if (r != err_ok) {
00462                         fprintf(stderr, "Error while jostling PBO_ISECT: %d\n", r);
00463                         return 0;
00464                 }
00465                 nocentroid = 1;
00466         }
00467         /* XXX if this operation did not create two chunks, bad things are about to happen */
00468         if (! tmp)
00469                 return 0;
00470 
00471         n = tmp;
00472         small = big = tmp->contours->area;
00473         do {
00474 fprintf(stderr, "\t\tarea %g, %d,%d %d,%d\n", n->contours->area, n->contours->xmin,n->contours->ymin, n->contours->xmax,n->contours->ymax);
00475                 if (n->contours->area <= small) {
00476                         smallest = n;
00477                         small = n->contours->area;
00478                 }
00479                 if (n->contours->area >= big) {
00480                         big = n->contours->area;
00481                 }
00482         } while((n = n->f) != tmp);
00483         if (line->Point1.X == line->Point2.X) {                 /* | */
00484                 if (info->box.X2 - smallest->contours->xmax >
00485                     smallest->contours->xmin - info->box.X1)
00486                         side = WEST;
00487                 else
00488                         side = EAST;
00489         } else if (line->Point1.Y == line->Point2.Y) {          /* - */
00490                 if (info->box.Y2 - smallest->contours->ymax >
00491                     smallest->contours->ymin - info->box.Y1)
00492                         side = NORTH;
00493                 else
00494                         side = SOUTH;
00495         } else if ((line->Point1.X > line->Point2.X) ==
00496                    (line->Point1.Y > line->Point2.Y)) {         /* \ */
00497                 if (info->box.X2 - smallest->contours->xmax >
00498                     smallest->contours->xmin - info->box.X1)
00499                         side = SOUTHWEST;
00500                 else
00501                         side = NORTHEAST;
00502         } else {                                                /* / */
00503                 if (info->box.X2 - smallest->contours->xmax >
00504                     smallest->contours->xmin - info->box.X1)
00505                         side = NORTHWEST;
00506                 else
00507                         side = SOUTHEAST;
00508         }
00509 fprintf(stderr, "\t%s\n", dirnames[side]);
00510         if (info->line == NULL ||
00511             (!nocentroid && (big - small) < info->centroid))  {
00512 fprintf(stderr, "\tkeep it!\n");
00513                 if (info->smallest) {
00514                         poly_Free(&info->smallest);
00515                 }
00516                 info->centroid = nocentroid ? DBL_MAX : (big - small);
00517                 info->side = side;
00518                 info->line = line;
00519                 info->smallest = smallest;
00520                 return 1;
00521         }
00522         return 0;
00523 }
00524 
00525 static int
00526 jostle(int argc, char **argv, int x, int y)
00527 {
00528         bool rel;
00529         POLYAREA *expand;
00530         float value;
00531         struct info info;
00532         int found;
00533 
00534         if (argc == 2)
00535                 value = GetValue(ARG(0), ARG(1), &rel);
00536         else
00537                 value = Settings.ViaThickness + (PCB->Bloat + 1) * 2 + 50;
00538 
00539         x = Crosshair.X;
00540         y = Crosshair.Y;
00541 fprintf(stderr, "%d, %d, %f\n", x, y, value);
00542         info.brush = CirclePoly(x, y, value / 2);
00543         info.layer = CURRENT;
00544         LINE_LOOP(info.layer);
00545         {
00546                 CLEAR_FLAG(DRCFLAG, line);
00547         }
00548         END_LOOP;
00549         do {
00550                 info.box = POLYAREA_boundingBox(info.brush);
00551 DebugPOLYAREA (info.brush, NULL);
00552 fprintf(stderr, "search (%d,%d)->(%d,%d):\n", info.box.X1,info.box.Y1, info.box.X2,info.box.Y2);
00553                 info.line = NULL;
00554                 info.smallest = NULL;
00555                 found = r_search(info.layer->line_tree, &info.box, NULL, jostle_callback, &info);
00556                 if (found) {
00557                         expand = NULL;
00558                         MakeBypassingLines(info.smallest, info.layer,
00559                                 info.line, info.side, &expand);
00560                         poly_Free(&info.smallest);
00561                         poly_Boolean_free(info.brush, expand, &info.brush,
00562                                 PBO_UNITE);
00563                 }
00564         } while (found);
00565         SetChangedFlag(true);
00566         IncrementUndoSerialNumber();
00567 
00568         return 0;
00569 }
00570 
00571 static HID_Action jostle_action_list[] = {
00572         {"jostle", NULL, jostle, "Move lines out of the way", jostle_syntax},
00573 };
00574 
00575 REGISTER_ACTIONS (jostle_action_list)
00576 
00577 void
00578 hid_jostle_init()
00579 {
00580         register_jostle_action_list();
00581 }

Generated on Tue Aug 17 15:28:04 2010 for pcb-plugins by  doxygen 1.4.6-NO