src/puller.c

   1 /* $Id$ */
   2
   3 /*
   4  *                            COPYRIGHT
   5  *
   6  *  PCB, interactive printed circuit board design
   7  *  Copyright (C) 2006 DJ Delorie
   8  *  Copyright (C) 2011 PCB Contributers (See ChangeLog for details)
   9  *
  10  *  This program is free software; you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License as published by
  12  *  the Free Software Foundation; either version 2 of the License, or
  13  *  (at your option) any later version.
  14  *
  15  *  This program is distributed in the hope that it will be useful,
  16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  *  GNU General Public License for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License
  21  *  along with this program; if not, write to the Free Software
  22  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  23  *
  24  *  Contact addresses for paper mail and Email:
  25  *  DJ Delorie, 334 North Road, Deerfield NH 03037-1110, USA
  26  *  dj@delorie.com
  27  *
  28  */
  29
  30 /* FIXME: Things that need to be fixed before this is "perfect".
  31    Add to this list as we find things.
  32
  33    - respect the outline layer.
  34
  35    - don't consider points that are perpendicular to our start_arc.
  36      I.e. when we have busses going around corners, we have a *lot* of
  37      arcs and endpoints that are all in the same direction and all
  38      equally "good", but rounding the arc angles to integers causes
  39      all sorts of tiny differences that result in bumps, reversals,
  40      and other messes.
  41
  42    - Store the X,Y values in our shadow struct so we don't fill up the
  43      undo buffer with all our line reversals.
  44
  45    - at least check the other layers in our layer group.
  46
  47 */
  48
  49 #ifdef HAVE_CONFIG_H
  50 #include "config.h"
  51 #endif
  52
  53 #include "global.h"
  54
  55 #include <math.h>
  56 #include <memory.h>
  57 #include <limits.h>
  58 #include <setjmp.h>
  59
  60
  61 #include "create.h"
  62 #include "data.h"
  63 #include "draw.h"
  64 #include "misc.h"
  65 #include "move.h"
  66 #include "pcb-printf.h"
  67 #include "remove.h"
  68 #include "rtree.h"
  69 #include "strflags.h"
  70 #include "undo.h"
  71
  72 #ifdef HAVE_LIBDMALLOC
  73 #include <dmalloc.h>
  74 #endif
  75
  76 RCSID ("$Id$");
  77
  78 #define abort1() fprintf(stderr, "abort at line %d\n", __LINE__), abort()
  79
  80 #define TRACE0 0
  81 #define TRACE1 0
  82
  83 /* sine of one degree */
  84 #define SIN1D   0.0174524064372835
  85
  86 static jmp_buf abort_buf;
  87
  88 #define sqr(x) (1.0*(x)*(x))
  89
  90 static int multi, line_exact, arc_exact;
  91 static LineTypePtr the_line;
  92 static ArcTypePtr the_arc;
  93 static double arc_dist;
  94
  95 /* We canonicalize the arc and line such that the point to be moved is
  96    always Point2 for the line, and at start+delta for the arc.  */
  97
  98 static int x, y;                /* the point we're moving */
  99 static int cx, cy;              /* centerpoint of the arc */
 100 static int ex, ey;              /* fixed end of the line */
 101
 102 /* 0 is left (-x), 90 is down (+y), 180 is right (+x), 270 is up (-y) */
 103
 104 static int
 105 within (int x1, int y1, int x2, int y2, int r)
 106 {
 107   return Distance (x1, y1, x2, y2) <= r / 2;
 108 }
 109
 110 static int
 111 arc_endpoint_is (ArcTypePtr a, int angle, int x, int y)
 112 {
 113   int ax = a->X, ay = a->Y;
 114
 115   if (angle % 90 == 0)
 116     {
 117       int ai = (int) (angle / 90) & 3;
 118       switch (ai)
 119         {
 120         case 0:
 121           ax -= a->Width;
 122           break;
 123         case 1:
 124           ay += a->Height;
 125           break;
 126         case 2:
 127           ax += a->Width;
 128           break;
 129         case 3:
 130           ay -= a->Height;
 131           break;
 132         }
 133     }
 134   else
 135     {
 136       double rad = angle * M_PI / 180;
 137       ax -= a->Width * cos (rad);
 138       ay += a->Width * sin (rad);
 139     }
 140 #if TRACE1
 141   pcb_printf (" - arc endpoint %#mD\n", ax, ay);
 142 #endif
 143   arc_dist = Distance (ax, ay, x, y);
 144   if (arc_exact)
 145     return arc_dist < 2;
 146   return arc_dist < a->Thickness / 2;
 147 }
 148
 149 /* Cross c->u and c->v, return the magnitute */
 150 static double
 151 cross2d (int cx, int cy, int ux, int uy, int vx, int vy)
 152 {
 153   ux -= cx;
 154   uy -= cy;
 155   vx -= cx;
 156   vy -= cy;
 157   return (double)ux * vy - (double)uy * vx;
 158 }
 159
 160 /* Likewise, for dot product. */
 161 static double
 162 dot2d (int cx, int cy, int ux, int uy, int vx, int vy)
 163 {
 164   ux -= cx;
 165   uy -= cy;
 166   vx -= cx;
 167   vy -= cy;
 168   return (double)ux * vx + (double)uy * vy;
 169 }
 170
 171 #if 0
 172 /* angle of c->v, relative to c->u, in radians.  Range is -pi..pi */
 173 static double
 174 angle2d (int cx, int cy, int ux, int uy, int vx, int vy)
 175 {
 176   double cross;
 177   double magu, magv, sintheta;
 178 #if TRACE1
 179   printf("angle2d %d,%d %d,%d %d,%d\n", cx, cy, ux, uy, vx, vy);
 180 #endif
 181   ux -= cx;
 182   uy -= cy;
 183   vx -= cx;
 184   vy -= cy;
 185 #if TRACE1
 186   printf(" = %d,%d %d,%d\n", ux, uy, vx, vy);
 187 #endif
 188   cross = (double)ux * vy - (double)uy * vx;
 189   magu = sqrt((double)ux*ux + (double)uy*uy);
 190   magv = sqrt((double)vx*vx + (double)vy*vy);
 191   sintheta = cross / (magu * magv);
 192 #if TRACE1
 193   printf(" = %f / (%f * %f) = %f\n", cross, magu, magv, sintheta);
 194 #endif
 195   return asin (sintheta);
 196 }
 197 #endif
 198
 199 static int
 200 same_sign (double a, double b)
 201 {
 202   return (a * b >= 0);
 203 }
 204
 205 static double
 206 r2d (double r)
 207 {
 208   return 180.0 * r / M_PI;
 209 }
 210
 211 static double
 212 d2r (double d)
 213 {
 214   return M_PI * d / 180.0;
 215 }
 216
 217 /* | a b |
 218    | c d | */
 219 static double
 220 det (double a, double b, double c, double d)
 221 {
 222   return a * d - b * c;
 223 }
 224
 225 /* The lines are x1y1-x2y2 and x3y3-x4y4.  Returns true if they
 226    intersect.  */
 227 static int
 228 intersection_of_lines (int x1, int y1, int x2, int y2,
 229                        int x3, int y3, int x4, int y4,
 230                        int *xr, int *yr)
 231 {
 232   double x, y, d;
 233   d = det (x1 - x2, y1 - y2, x3 - x4, y3 - y4);
 234   if (!d)
 235     return 0;
 236   x = (det (det (x1, y1, x2, y2), x1 - x2,
 237             det (x3, y3, x4, y4), x3 - x4) / d);
 238   y = (det (det (x1, y1, x2, y2), y1 - y2,
 239             det (x3, y3, x4, y4), y3 - y4) / d);
 240   *xr = (int) (x + 0.5);
 241   *yr = (int) (y + 0.5);
 242   return 1;
 243 }
 244
 245 /* Same, for line segments.  Returns true if they intersect.  For this
 246    function, xr and yr may be NULL if you don't need the values.  */
 247 static int
 248 intersection_of_linesegs (int x1, int y1, int x2, int y2,
 249                           int x3, int y3, int x4, int y4,
 250                           int *xr, int *yr)
 251 {
 252   double x, y, d;
 253   d = det (x1 - x2, y1 - y2, x3 - x4, y3 - y4);
 254   if (!d)
 255     return 0;
 256   x = (det (det (x1, y1, x2, y2), x1 - x2,
 257             det (x3, y3, x4, y4), x3 - x4) / d);
 258   y = (det (det (x1, y1, x2, y2), y1 - y2,
 259             det (x3, y3, x4, y4), y3 - y4) / d);
 260   if (MIN (x1, x2) > x || x > MAX (x1, x2)
 261       || MIN (y1, y2) > y || y > MAX (y1, y2))
 262     return 0;
 263   if (MIN (x3, x4) > x || x > MAX (x3, x4)
 264       || MIN (y3, y4) > y || y > MAX (y3, y4))
 265     return 0;
 266   if (xr)
 267     *xr = (int) (x + 0.5);
 268   if (yr)
 269     *yr = (int) (y + 0.5);
 270   return 1;
 271 }
 272
 273 /* distance between a line and a point */
 274 static double
 275 dist_lp (int x1, int y1, int x2, int y2, int px, int py)
 276 {
 277   double den = Distance (x1, y1, x2, y2);
 278   double rv = (fabs (((double)x2 - x1) * ((double)y1 - py)
 279                      - ((double)x1 - px) * ((double)y2 - y1))
 280                / den);
 281 #if TRACE1
 282   pcb_printf("dist %#mD-%#mD to %#mD is %f\n",
 283          x1, y1, x2, y2, px, py, rv);
 284 #endif
 285   return rv;
 286 }
 287
 288 /* distance between a line segment and a point */
 289 static double
 290 dist_lsp (int x1, int y1, int x2, int y2, int px, int py)
 291 {
 292   double d;
 293   if (dot2d (x1, y1, x2, y2, px, py) < 0)
 294     return Distance (x1, y1, px, py);
 295   if (dot2d (x2, y2, x1, y1, px, py) < 0)
 296     return Distance (x2, y2, px, py);
 297   d = (fabs (((double)x2 - x1) * ((double)y1 - py)
 298              - ((double)x1 - px) * ((double)y2 - y1))
 299        / Distance (x1, y1, x2, y2));
 300   return d;
 301 }
 302
 303 /*****************************************************************************/
 304 /*                                                                           */
 305 /*                       Single Point Puller                                 */
 306 /*                                                                           */
 307 /*****************************************************************************/
 308
 309 static int
 310 line_callback (const BoxType * b, void *cl)
 311 {
 312   /* LayerTypePtr layer = (LayerTypePtr)cl; */
 313   LineTypePtr l = (LineTypePtr) b;
 314   double d1, d2, t;
 315 #if TRACE1
 316   pcb_printf ("line %#mD .. %#mD\n",
 317           l->Point1.X, l->Point1.Y, l->Point2.X, l->Point2.Y);
 318 #endif
 319   d1 = Distance (l->Point1.X, l->Point1.Y, x, y);
 320   d2 = Distance (l->Point2.X, l->Point2.Y, x, y);
 321   if ((d1 < 2 || d2 < 2) && !line_exact)
 322     {
 323       line_exact = 1;
 324       the_line = 0;
 325     }
 326   t = line_exact ? 2 : l->Thickness / 2;
 327   if (d1 < t || d2 < t)
 328     {
 329       if (the_line)
 330         multi = 1;
 331       the_line = l;
 332 #if TRACE1
 333       printf ("picked, exact %d\n", line_exact);
 334 #endif
 335     }
 336   return 1;
 337 }
 338
 339 static int
 340 arc_callback (const BoxType * b, void *cl)
 341 {
 342   /* LayerTypePtr layer = (LayerTypePtr) cl; */
 343   ArcTypePtr a = (ArcTypePtr) b;
 344
 345 #if TRACE1
 346   pcb_printf ("arc a %#mD r %#mS sa %ld d %ld\n", a->X, a->Y, a->Width,
 347           a->StartAngle, a->Delta);
 348 #endif
 349   if (!arc_endpoint_is (a, a->StartAngle, x, y)
 350       && !arc_endpoint_is (a, a->StartAngle + a->Delta, x, y))
 351     return 1;
 352   if (arc_dist < 2)
 353     {
 354       if (!arc_exact)
 355         {
 356           arc_exact = 1;
 357           the_arc = 0;
 358         }
 359       if (the_arc)
 360         multi = 1;
 361       the_arc = a;
 362 #if TRACE1
 363       printf ("picked, exact %d\n", arc_exact);
 364 #endif
 365     }
 366   else if (!arc_exact)
 367     {
 368       if (the_arc)
 369         multi = 1;
 370       the_arc = a;
 371 #if TRACE1
 372       printf ("picked, exact %d\n", arc_exact);
 373 #endif
 374     }
 375   return 1;
 376 }
 377
 378 static int
 379 find_pair (int Px, int Py)
 380 {
 381   BoxType spot;
 382
 383 #if TRACE1
 384   pcb_printf ("\nPuller find_pair at %#mD\n", Crosshair.X, Crosshair.Y);
 385 #endif
 386
 387   x = Px;
 388   y = Py;
 389   multi = 0;
 390   line_exact = arc_exact = 0;
 391   the_line = 0;
 392   the_arc = 0;
 393   spot.X1 = x - 1;
 394   spot.Y1 = y - 1;
 395   spot.X2 = x + 1;
 396   spot.Y2 = y + 1;
 397   r_search (CURRENT->line_tree, &spot, NULL, line_callback, CURRENT);
 398   r_search (CURRENT->arc_tree, &spot, NULL, arc_callback, CURRENT);
 399   if (the_line && the_arc && !multi)
 400     return 1;
 401   x = Px;
 402   y = Py;
 403   return 0;
 404 }
 405
 406
 407 static const char puller_syntax[] = "Puller()";
 408
 409 static const char puller_help[] = "Pull an arc-line junction tight.";
 410
 411 /* %start-doc actions Puller
 412
 413 The @code{Puller()} action is a special-purpose optimization.  When
 414 invoked while the crosshair is over the junction of an arc and a line,
 415 it will adjust the arc's angle and the connecting line's endpoint such
 416 that the line intersects the arc at a tangent.  In the example below,
 417 the left side is ``before'' with the black target marking where to put
 418 the crosshair:
 419
 420 @center @image{puller,,,Example of how puller works,png}
 421
 422 The right side is ``after'' with the black target marking where the
 423 arc-line intersection was moved to.
 424
 425 %end-doc */
 426
 427 static int
 428 Puller (int argc, char **argv, Coord Ux, Coord Uy)
 429 {
 430   double arc_angle, base_angle;
 431 #if TRACE1
 432   double line_angle, rel_angle;
 433 #endif
 434   double tangent;
 435   int new_delta_angle;
 436
 437   if (!find_pair (Crosshair.X, Crosshair.Y))
 438     if (!find_pair (Ux, Uy))
 439       return 0;
 440
 441   if (within (the_line->Point1.X, the_line->Point1.Y,
 442               x, y, the_line->Thickness))
 443     {
 444       ex = the_line->Point2.X;
 445       ey = the_line->Point2.Y;
 446       the_line->Point2.X = the_line->Point1.X;
 447       the_line->Point2.Y = the_line->Point1.Y;
 448       the_line->Point1.X = ex;
 449       the_line->Point1.Y = ey;
 450     }
 451   else if (!within (the_line->Point2.X, the_line->Point2.Y,
 452                     x, y, the_line->Thickness))
 453     {
 454 #if TRACE1
 455       printf ("Line endpoint not at cursor\n");
 456 #endif
 457       return 1;
 458     }
 459   ex = the_line->Point1.X;
 460   ey = the_line->Point1.Y;
 461
 462   cx = the_arc->X;
 463   cy = the_arc->Y;
 464   if (arc_endpoint_is (the_arc, the_arc->StartAngle, x, y))
 465     {
 466       ChangeArcAngles (CURRENT, the_arc, the_arc->StartAngle + the_arc->Delta,
 467                        -the_arc->Delta);
 468     }
 469   else if (!arc_endpoint_is (the_arc, the_arc->StartAngle + the_arc->Delta,
 470                              x, y))
 471     {
 472 #if TRACE1
 473       printf ("arc not endpoints\n");
 474 #endif
 475       return 1;
 476     }
 477
 478   if (within (cx, cy, ex, ey, the_arc->Width * 2))
 479     {
 480 #if TRACE1
 481       printf ("line ends inside arc\n");
 482 #endif
 483       return 1;
 484     }
 485
 486   if (the_arc->Delta > 0)
 487     arc_angle = the_arc->StartAngle + the_arc->Delta + 90;
 488   else
 489     arc_angle = the_arc->StartAngle + the_arc->Delta - 90;
 490   base_angle = r2d (atan2 (ey - cy, cx - ex));
 491
 492   tangent = r2d (acos (the_arc->Width / Distance (cx, cy, ex, ey)));
 493
 494 #if TRACE1
 495   line_angle = r2d (atan2 (ey - y, x - ex));
 496   rel_angle = line_angle - arc_angle;
 497   printf ("arc %g line %g rel %g base %g\n", arc_angle, line_angle, rel_angle,
 498           base_angle);
 499   printf ("tangent %g\n", tangent);
 500
 501   printf ("arc was start %ld end %ld\n", the_arc->StartAngle,
 502           the_arc->StartAngle + the_arc->Delta);
 503 #endif
 504
 505   if (the_arc->Delta > 0)
 506     arc_angle = base_angle - tangent;
 507   else
 508     arc_angle = base_angle + tangent;
 509 #if TRACE1
 510   printf ("new end angle %g\n", arc_angle);
 511 #endif
 512
 513   new_delta_angle = arc_angle - the_arc->StartAngle;
 514   if (new_delta_angle > 180)
 515     new_delta_angle -= 360;
 516   if (new_delta_angle < -180)
 517     new_delta_angle += 360;
 518   ChangeArcAngles (CURRENT, the_arc, the_arc->StartAngle, new_delta_angle);
 519
 520 #if TRACE1
 521   printf ("arc now start %ld end %ld\n", the_arc->StartAngle,
 522           the_arc->StartAngle + new_delta_angle);
 523 #endif
 524
 525   arc_angle = the_arc->StartAngle + the_arc->Delta;
 526   x = the_arc->X - the_arc->Width * cos (d2r (arc_angle)) + 0.5;
 527   y = the_arc->Y + the_arc->Height * sin (d2r (arc_angle)) + 0.5;
 528
 529   MoveObject (LINEPOINT_TYPE, CURRENT, the_line, &(the_line->Point2),
 530               x - the_line->Point2.X, y - the_line->Point2.Y);
 531
 532   gui->invalidate_all ();
 533   IncrementUndoSerialNumber ();
 534
 535   return 1;
 536 }
 537
 538 /*****************************************************************************/
 539 /*                                                                           */
 540 /*                          Global Puller                                    */
 541 /*                                                                           */
 542 /*****************************************************************************/
 543
 544 static const char globalpuller_syntax[] =
 545 "GlobalPuller()";
 546
 547 static const char globalpuller_help[] =
 548 "Pull all traces tight.";
 549
 550 /* %start-doc actions GlobalPuller
 551
 552 %end-doc */
 553
 554 /* Ok, here's the deal.  We look for the intersection of two traces.
 555    The triangle formed by those traces is searched for things we need
 556    to avoid. From the other two corners of the triangle, we compute
 557    the angle to each obstacle, and remember the ones closest to the
 558    start angles.  If the two traces hit the same obstacle, we put in
 559    the arc and we're done.  Else, we bring the traces up to the
 560    obstacles and start again.
 561
 562    Note that we assume each start point is a tangent to an arc.  We
 563    start with a radius of zero, but future steps use the arcs we
 564    create as we go.
 565
 566    For obstacles, we list each round pin, pad, via, and line/arc
 567    endpoints as points with a given radius.  For each square pin, pad,
 568    via, and polygon points, we list each corner with a zero radius.
 569    We also list arcs from their centerpoint.
 570
 571    We don't currently do anything to move vias, or intersections of
 572    three or more traces.  In the future, three-way intersections will
 573    be handles similarly to two-way - calculate the range of angles
 574    valid from each of the three other endpoints, choose the angle
 575    closest to making 120 degree angles at the center.  For four-way or
 576    more intersections, we break them up into multiple three-way
 577    intersections.
 578
 579    For simplicity, we only do the current layer at this time.  We will
 580    also edit the lines and arcs in place so that the intersection is
 581    always on the second point, and the other ends are always at
 582    start+delta for arcs.
 583
 584    We also defer intersections which are blocked by other
 585    intersections yet to be moved; the idea is to wait until those have
 586    been moved so we don't end up with arcs that no longer wrap around
 587    things.  At a later point, we may choose to pull arced corners in
 588    also.
 589
 590    You'll see lots of variables of the form "foo_sign" which keep
 591    track of which way things are pointing.  This is because everything
 592    is relative to corners and arcs, not absolute directions.
 593 */
 594
 595 static int nloops, npulled;
 596
 597 static void
 598 status ()
 599 {
 600   fprintf(stderr, "%6d loops, %d pulled   \r", nloops, npulled);
 601 }
 602
 603 /* Extra data we need to temporarily attach to all lines and arcs.  */
 604 typedef struct End {
 605   /* These point to "multi_next" if there are more than one.  */
 606   struct Extra *next;
 607   void *pin;
 608   unsigned char in_pin:1;
 609   unsigned char at_pin:1;
 610   unsigned char is_pad:1;
 611   unsigned char pending:1; /* set if this may be moved later */
 612   int x, y; /* arc endpoint */
 613   /* If not NULL, points to End with pending==1 we're blocked on. */
 614   struct End *waiting_for;
 615 } End;
 616
 617 typedef struct Extra {
 618   End start;
 619   End end;
 620   unsigned char found:1;
 621   unsigned char deleted:1;
 622   int type;
 623   union {
 624     LineType *line;
 625     ArcType *arc;
 626   } parent;
 627 } Extra;
 628
 629 static Extra multi_next;
 630 static GHashTable *lines;
 631 static GHashTable *arcs;
 632 static int did_something;
 633 static int current_is_component, current_is_solder;
 634
 635 /* If set, these are the pins/pads/vias that this path ends on.  */
 636 /* static void *start_pin_pad, *end_pin_pad; */
 637
 638 #if TRACE1
 639 static void trace_paths ();
 640 #endif
 641 static void mark_line_for_deletion (LineTypePtr);
 642
 643 #define LINE2EXTRA(l)    ((Extra *)g_hash_table_lookup (lines, l))
 644 #define ARC2EXTRA(a)     ((Extra *)g_hash_table_lookup (arcs, a))
 645 #define EXTRA2LINE(e)    (e->parent.line)
 646 #define EXTRA2ARC(e)     (e->parent.arc)
 647 #define EXTRA_IS_LINE(e) (e->type == LINE_TYPE)
 648 #define EXTRA_IS_ARC(e)  (e->type == ARC_TYPE)
 649
 650 static void
 651 unlink_end (Extra *x, Extra **e)
 652 {
 653   if (*e)
 654     {
 655       if ((*e)->start.next == x)
 656         {
 657 #if TRACE1
 658           printf("%d: unlink_end, was %p\n", __LINE__, (*e)->start.next);
 659 #endif
 660           (*e)->start.next = &multi_next;
 661         }
 662       if ((*e)->end.next == x)
 663         {
 664 #if TRACE1
 665           printf("%d: unlink_end, was %p\n", __LINE__, (*e)->start.next);
 666 #endif
 667           (*e)->end.next = &multi_next;
 668         }
 669     }
 670 #if TRACE1
 671   printf("%d: unlink_end, was %p\n", __LINE__, (*e));
 672 #endif
 673   (*e) = &multi_next;
 674 }
 675
 676 #if TRACE1
 677
 678 static void
 679 clear_found_cb (AnyObjectType *ptr, Extra *extra, void *userdata)
 680 {
 681   extra->found = 0;
 682 }
 683
 684 static void
 685 clear_found ()
 686 {
 687   g_hash_table_foreach (lines, (GHFunc)clear_found_cb, NULL);
 688   g_hash_table_foreach (arcs, (GHFunc)clear_found_cb, NULL);
 689 }
 690 #endif
 691
 692 static void
 693 fix_arc_extra (ArcTypePtr a, Extra *e)
 694 {
 695 #if TRACE1
 696   printf("new arc angles %ld %ld\n", a->StartAngle, a->Delta);
 697 #endif
 698   e->start.x = a->X - (a->Width * cos (d2r (a->StartAngle)) + 0.5);
 699   e->start.y = a->Y + (a->Height * sin (d2r (a->StartAngle)) + 0.5);
 700   e->end.x = a->X - (a->Width * cos (d2r (a->StartAngle+a->Delta)) + 0.5);
 701   e->end.y = a->Y + (a->Height * sin (d2r (a->StartAngle+a->Delta)) + 0.5);
 702 #if TRACE1
 703   pcb_printf("new X,Y is %#mD to %#mD\n", e->start.x, e->start.y, e->end.x, e->end.y);
 704 #endif
 705 }
 706
 707 typedef struct {
 708   void *me;
 709   int x, y;
 710   int is_arc;
 711   Extra **extra_ptr;
 712 } FindPairCallbackStruct;
 713
 714 #define NEAR(a,b) ((a) <= (b) + 2 && (a) >= (b) - 2)
 715
 716 static int
 717 find_pair_line_callback (const BoxType * b, void *cl)
 718 {
 719   LineTypePtr line = (LineTypePtr) b;
 720 #if TRACE1
 721   Extra *e = LINE2EXTRA (line);
 722 #endif
 723   FindPairCallbackStruct *fpcs = (FindPairCallbackStruct *) cl;
 724
 725   if (line == fpcs->me)
 726     return 0;
 727 #ifdef CHECK_LINE_PT_NEG
 728   if (line->Point1.X < 0)
 729     abort1();
 730 #endif
 731 #if TRACE1
 732   pcb_printf(" - %p line %#mD or %#mD\n", e, line->Point1.X, line->Point1.Y,
 733          line->Point2.X, line->Point2.Y);
 734 #endif
 735   if ((NEAR (line->Point1.X, fpcs->x) && NEAR (line->Point1.Y, fpcs->y))
 736       || (NEAR (line->Point2.X, fpcs->x) && NEAR (line->Point2.Y, fpcs->y)))
 737     {
 738       if (* fpcs->extra_ptr)
 739         {
 740 #if TRACE1
 741           printf("multiple, was %p\n", *fpcs->extra_ptr);
 742 #endif
 743           *fpcs->extra_ptr = & multi_next;
 744         }
 745       else
 746         {
 747           *fpcs->extra_ptr = LINE2EXTRA (line);
 748 #if TRACE1
 749           printf(" - next now %p\n", *fpcs->extra_ptr);
 750 #endif
 751         }
 752     }
 753   return 0;
 754 }
 755
 756 static int
 757 find_pair_arc_callback (const BoxType * b, void *cl)
 758 {
 759   ArcTypePtr arc = (ArcTypePtr) b;
 760   Extra *e = ARC2EXTRA (arc);
 761   FindPairCallbackStruct *fpcs = (FindPairCallbackStruct *) cl;
 762
 763   if (arc == fpcs->me)
 764     return 0;
 765 #if TRACE1
 766   pcb_printf(" - %p arc %#mD or %#mD\n", e, e->start.x, e->start.y, e->end.x, e->end.y);
 767 #endif
 768   if ((NEAR (e->start.x, fpcs->x) && NEAR (e->start.y, fpcs->y))
 769       || (NEAR (e->end.x, fpcs->x) && NEAR (e->end.y, fpcs->y)))
 770     {
 771       if (* fpcs->extra_ptr)
 772         {
 773 #if TRACE1
 774           printf("multiple, was %p\n", *fpcs->extra_ptr);
 775 #endif
 776           *fpcs->extra_ptr = & multi_next;
 777         }
 778       else
 779         *fpcs->extra_ptr = e;
 780     }
 781   return 0;
 782 }
 783
 784 static void
 785 find_pairs_1 (void *me, Extra **e, int x, int y)
 786 {
 787   FindPairCallbackStruct fpcs;
 788   BoxType b;
 789
 790   if (*e)
 791     return;
 792
 793   fpcs.me = me;
 794   fpcs.extra_ptr = e;
 795   fpcs.x = x;
 796   fpcs.y = y;
 797 #if TRACE1
 798   pcb_printf("looking for %#mD\n", x, y);
 799 #endif
 800   b.X1 = x - 10;
 801   b.X2 = x + 10;
 802   b.Y1 = y - 10;
 803   b.Y2 = y + 10;
 804   r_search(CURRENT->line_tree, &b, NULL, find_pair_line_callback, &fpcs);
 805   r_search(CURRENT->arc_tree, &b, NULL, find_pair_arc_callback, &fpcs);
 806 }
 807
 808 static int
 809 check_point_in_pin (PinTypePtr pin, int x, int y, End *e)
 810 {
 811   int inside_p;
 812   int t = (pin->Thickness+1)/2;
 813   if (TEST_FLAG (SQUAREFLAG, pin))
 814     inside_p = (x >= pin->X - t && x <= pin->X + t
 815                 && y >= pin->Y - t && y <= pin->Y + t);
 816   else
 817     inside_p = (Distance (pin->X, pin->Y, x, y) <= t);
 818
 819   if (inside_p)
 820     {
 821       e->in_pin = 1;
 822       if (pin->X == x && pin->Y == y)
 823         e->at_pin = 1;
 824       e->pin = pin;
 825       return 1;
 826     }
 827   return 0;
 828 }
 829
 830 static int
 831 find_pair_pinline_callback (const BoxType * b, void *cl)
 832 {
 833   LineTypePtr line = (LineTypePtr) b;
 834   PinTypePtr pin = (PinTypePtr) cl;
 835   Extra *e = LINE2EXTRA (line);
 836   int hits;
 837
 838 #ifdef CHECK_LINE_PT_NEG
 839   if (line->Point1.X < 0)
 840     abort1();
 841 #endif
 842
 843   hits = check_point_in_pin (pin, line->Point1.X, line->Point1.Y, &(e->start));
 844   hits += check_point_in_pin (pin, line->Point2.X, line->Point2.Y, &(e->end));
 845
 846   if (hits)
 847     return 0;
 848
 849   /* See if the line passes through this pin.  */
 850   /* FIXME: this assumes round pads, but it's good enough for square
 851      ones for now.  */
 852   if (dist_lsp (line->Point1.X, line->Point1.Y,
 853                 line->Point2.X, line->Point2.Y,
 854                 pin->X, pin->Y) <= pin->Thickness/2)
 855     {
 856 #if TRACE1
 857       pcb_printf("splitting line %#mD-%#mD because it passes through pin %#mD r%d\n",
 858              line->Point1.X, line->Point1.Y,
 859              line->Point2.X, line->Point2.Y,
 860              pin->X, pin->Y, pin->Thickness/2);
 861 #endif
 862       unlink_end (e, &e->start.next);
 863       unlink_end (e, &e->end.next);
 864     }
 865   return 0;
 866 }
 867
 868 static int
 869 find_pair_pinarc_callback (const BoxType * b, void *cl)
 870 {
 871   ArcTypePtr arc = (ArcTypePtr) b;
 872   PinTypePtr pin = (PinTypePtr) cl;
 873   Extra *e = ARC2EXTRA (arc);
 874   int hits;
 875
 876   hits = check_point_in_pin (pin, e->start.x, e->start.y, &(e->start));
 877   hits += check_point_in_pin (pin, e->end.x, e->end.y, &(e->end));
 878   return 0;
 879 }
 880
 881 static int
 882 check_point_in_pad (PadTypePtr pad, int x, int y, End *e)
 883 {
 884   int inside_p;
 885   int t;
 886
 887   pcb_printf("pad %#mD - %#mD t %#mS  vs  %#mD\n", pad->Point1.X, pad->Point1.Y,
 888          pad->Point2.X, pad->Point2.Y, pad->Thickness, x, y);
 889   t = (pad->Thickness+1)/2;
 890   if (TEST_FLAG (SQUAREFLAG, pad))
 891     {
 892     inside_p = (x >= MIN (pad->Point1.X - t, pad->Point2.X - t)
 893                 && x <= MAX (pad->Point1.X + t, pad->Point2.X + t)
 894                 && y >= MIN (pad->Point1.Y - t, pad->Point2.Y - t)
 895                 && y <= MAX (pad->Point1.Y + t, pad->Point2.Y + t));
 896     printf(" - inside_p = %d\n", inside_p);
 897     }
 898   else
 899     {
 900       if (pad->Point1.X == pad->Point2.X)
 901         {
 902           inside_p = (x >= pad->Point1.X - t
 903                       && x <= pad->Point1.X + t
 904                       && y >= MIN (pad->Point1.Y, pad->Point2.Y)
 905                       && y <= MAX (pad->Point1.Y, pad->Point2.Y));
 906         }
 907       else
 908         {
 909           inside_p = (x >= MIN (pad->Point1.X, pad->Point2.X)
 910                       && x <= MAX (pad->Point1.X, pad->Point2.X)
 911                       && y >= pad->Point1.Y - t
 912                       && y <= pad->Point1.Y + t);
 913         }
 914       if (!inside_p)
 915         {
 916           if (Distance (pad->Point1.X, pad->Point1.Y, x, y) <= t
 917               || Distance (pad->Point2.X, pad->Point2.Y, x, y) <= t)
 918             inside_p = 1;
 919         }
 920     }
 921
 922   if (inside_p)
 923     {
 924       e->in_pin = 1;
 925       if (pad->Point1.X == x && pad->Point1.Y == y)
 926         e->at_pin = 1;
 927       if (pad->Point2.X == x && pad->Point2.Y == y)
 928         e->at_pin = 1;
 929       e->pin = pad;
 930       e->is_pad = 1;
 931       return 1;
 932     }
 933   return 0;
 934 }
 935
 936 static int
 937 find_pair_padline_callback (const BoxType * b, void *cl)
 938 {
 939   LineTypePtr line = (LineTypePtr) b;
 940   PadTypePtr pad = (PadTypePtr) cl;
 941   Extra *e = LINE2EXTRA (line);
 942   int hits;
 943   double t;
 944   int intersect;
 945   double p1_d, p2_d;
 946
 947   if (TEST_FLAG (ONSOLDERFLAG, pad))
 948     {
 949       if (!current_is_solder)
 950         return 0;
 951     }
 952   else
 953     {
 954       if (!current_is_component)
 955         return 0;
 956     }
 957
 958 #ifdef CHECK_LINE_PT_NEG
 959   if (line->Point1.X < 0)
 960     abort1();
 961 #endif
 962
 963   hits = check_point_in_pad (pad, line->Point1.X, line->Point1.Y, &(e->start));
 964   hits += check_point_in_pad (pad, line->Point2.X, line->Point2.Y, &(e->end));
 965
 966   if (hits)
 967     return 0;
 968
 969   /* Ok, something strange.  The line intersects our space, but
 970      doesn't end in our space.  See if it just passes through us, and
 971      mark it anyway.  */
 972
 973   t = (pad->Thickness + 1)/2;
 974   /* FIXME: this is for round pads.  Good enough for now, but add
 975      square pad support later.  */
 976   intersect = intersection_of_linesegs (pad->Point1.X, pad->Point1.Y,
 977                                          pad->Point2.X, pad->Point2.Y,
 978                                          line->Point1.X, line->Point1.Y,
 979                                          line->Point2.X, line->Point2.Y,
 980                                          NULL, NULL);
 981   p1_d = dist_lsp(line->Point1.X, line->Point1.Y,
 982                   line->Point2.X, line->Point2.Y,
 983                   pad->Point1.X, pad->Point1.Y);
 984   p2_d = dist_lsp(line->Point1.X, line->Point1.Y,
 985                   line->Point2.X, line->Point2.Y,
 986                   pad->Point2.X, pad->Point2.Y);
 987
 988   if (intersect || p1_d < t || p2_d < t)
 989     {
 990       /* It does.  */
 991       /* FIXME: we should split the line.  */
 992 #if TRACE1
 993       pcb_printf("splitting line %#mD-%#mD because it passes through pad %#mD-%#mD r %#mS\n",
 994              line->Point1.X, line->Point1.Y,
 995              line->Point2.X, line->Point2.Y,
 996              pad->Point1.X, pad->Point1.Y,
 997              pad->Point2.X, pad->Point2.Y,
 998              pad->Thickness/2);
 999 #endif
1000       unlink_end (e, &e->start.next);
1001       unlink_end (e, &e->end.next);
1002     }
1003
1004   return 0;
1005 }
1006
1007 static int
1008 find_pair_padarc_callback (const BoxType * b, void *cl)
1009 {
1010   ArcTypePtr arc = (ArcTypePtr) b;
1011   PadTypePtr pad = (PadTypePtr) cl;
1012   Extra *e = ARC2EXTRA (arc);
1013   int hits;
1014
1015   if (TEST_FLAG (ONSOLDERFLAG, pad))
1016     {
1017       if (!current_is_solder)
1018         return 0;
1019     }
1020   else
1021     {
1022       if (!current_is_component)
1023         return 0;
1024     }
1025
1026   hits = check_point_in_pad (pad, e->start.x, e->start.y, &(e->start));
1027   hits += check_point_in_pad (pad, e->end.x, e->end.y, &(e->end));
1028   return 0;
1029 }
1030
1031 static void
1032 null_multi_next_ends (AnyObjectType *ptr, Extra *extra, void *userdata)
1033 {
1034   if (extra->start.next == &multi_next)
1035     extra->start.next = NULL;
1036
1037   if (extra->end.next == &multi_next)
1038     extra->end.next = NULL;
1039 }
1040
1041 static Extra *
1042 new_line_extra (LineType *line)
1043 {
1044   Extra *extra = g_slice_new0 (Extra);
1045   g_hash_table_insert (lines, line, extra);
1046   extra->parent.line = line;
1047   extra->type = LINE_TYPE;
1048   return extra;
1049 }
1050
1051 static Extra *
1052 new_arc_extra (ArcType *arc)
1053 {
1054   Extra *extra = g_slice_new0 (Extra);
1055   g_hash_table_insert (arcs, arc, extra);
1056   extra->parent.arc = arc;
1057   extra->type = ARC_TYPE;
1058   return extra;
1059 }
1060
1061 static void
1062 find_pairs ()
1063 {
1064   ARC_LOOP (CURRENT); {
1065     Extra *e = new_arc_extra (arc);
1066     fix_arc_extra (arc, e);
1067   } END_LOOP;
1068
1069   LINE_LOOP (CURRENT); {
1070     new_line_extra (line);
1071   } END_LOOP;
1072
1073   LINE_LOOP (CURRENT); {
1074     Extra *e = LINE2EXTRA (line);
1075     if (line->Point1.X >= 0)
1076       {
1077         find_pairs_1 (line, & e->start.next, line->Point1.X, line->Point1.Y);
1078         find_pairs_1 (line, & e->end.next, line->Point2.X, line->Point2.Y);
1079       }
1080   } END_LOOP;
1081
1082   ARC_LOOP (CURRENT); {
1083     Extra *e = ARC2EXTRA (arc);
1084     if (!e->deleted)
1085       {
1086         find_pairs_1 (arc, & e->start.next, e->start.x, e->start.y);
1087         find_pairs_1 (arc, & e->end.next, e->end.x, e->end.y);
1088       }
1089   } END_LOOP;
1090
1091   ALLPIN_LOOP (PCB->Data); {
1092     BoxType box;
1093     box.X1 = pin->X - pin->Thickness/2;
1094     box.Y1 = pin->Y - pin->Thickness/2;
1095     box.X2 = pin->X + pin->Thickness/2;
1096     box.Y2 = pin->Y + pin->Thickness/2;
1097     r_search (CURRENT->line_tree, &box, NULL, find_pair_pinline_callback, pin);
1098     r_search (CURRENT->arc_tree, &box, NULL, find_pair_pinarc_callback, pin);
1099   } ENDALL_LOOP;
1100
1101   VIA_LOOP (PCB->Data); {
1102     BoxType box;
1103     box.X1 = via->X - via->Thickness/2;
1104     box.Y1 = via->Y - via->Thickness/2;
1105     box.X2 = via->X + via->Thickness/2;
1106     box.Y2 = via->Y + via->Thickness/2;
1107     r_search (CURRENT->line_tree, &box, NULL, find_pair_pinline_callback, via);
1108     r_search (CURRENT->arc_tree, &box, NULL, find_pair_pinarc_callback, via);
1109   } END_LOOP;
1110
1111   ALLPAD_LOOP (PCB->Data); {
1112     BoxType box;
1113     box.X1 = MIN(pad->Point1.X, pad->Point2.X) - pad->Thickness/2;
1114     box.Y1 = MIN(pad->Point1.Y, pad->Point2.Y) - pad->Thickness/2;
1115     box.X2 = MAX(pad->Point1.X, pad->Point2.X) + pad->Thickness/2;
1116     box.Y2 = MAX(pad->Point1.Y, pad->Point2.Y) + pad->Thickness/2;
1117     r_search (CURRENT->line_tree, &box, NULL, find_pair_padline_callback, pad);
1118     r_search (CURRENT->arc_tree, &box, NULL, find_pair_padarc_callback, pad);
1119
1120   } ENDALL_LOOP;
1121
1122   g_hash_table_foreach (lines, (GHFunc)null_multi_next_ends, NULL);
1123   g_hash_table_foreach (arcs, (GHFunc)null_multi_next_ends, NULL);
1124 }
1125
1126 #define PROP_NEXT(e,n,f)                \
1127       if (f->next->start.next == e) {   \
1128         e = f->next;                    \
1129         n = & e->start;                 \
1130         f = & e->end;                   \
1131       } else {                          \
1132         e = f->next;                    \
1133         n = & e->end;                   \
1134         f = & e->start; }
1135
1136 static void
1137 propogate_ends_at (Extra *e, End *near, End *far)
1138 {
1139   while (far->in_pin && far->pin == near->pin)
1140     {
1141       far->in_pin = 0;
1142       if (!far->next)
1143         return;
1144       PROP_NEXT (e, near, far);
1145       near->in_pin = 0;
1146     }
1147 }
1148
1149 static void
1150 propogate_end_pin (Extra *e, End *near, End *far)
1151 {
1152   void *pinpad = near->pin;
1153   int ispad = near->is_pad;
1154   while (far->next)
1155     {
1156       PROP_NEXT (e, near, far);
1157       if (near->pin == pinpad)
1158         break;
1159       near->pin = pinpad;
1160       near->is_pad = ispad;
1161     }
1162 }
1163
1164 static void
1165 propogate_end_step1_cb (AnyObjectType *ptr, Extra *extra, void *userdata)
1166 {
1167   if (extra->start.next != NULL &&
1168       extra->start.next == extra->end.next)
1169     {
1170       extra->end.next = NULL;
1171       mark_line_for_deletion ((LineType *)ptr);
1172     }
1173
1174   if (extra->start.at_pin)
1175     propogate_ends_at (extra, &extra->start, &extra->end);
1176
1177   if (extra->end.at_pin)
1178     propogate_ends_at (extra, &extra->end, &extra->start);
1179 }
1180
1181 static void
1182 propogate_end_step2_cb (AnyObjectType *ptr, Extra *extra, void *userdata)
1183 {
1184   if (extra->start.in_pin)
1185     {
1186 #if TRACE1
1187       printf("MULTI at %d: was %p\n", __LINE__, extra->start.next);
1188 #endif
1189       extra->start.next = NULL;
1190     }
1191   if (extra->end.in_pin)
1192     {
1193 #if TRACE1
1194       printf("MULTI at %d: was %p\n", __LINE__, extra->end.next);
1195 #endif
1196       extra->end.next = NULL;
1197     }
1198 }
1199
1200 static void
1201 propogate_end_step3_cb (AnyObjectType *ptr, Extra *extra, void *userdata)
1202 {
1203   if (extra->start.next)
1204     propogate_end_pin (extra, &extra->end, &extra->start);
1205   if (extra->end.next)
1206     propogate_end_pin (extra, &extra->start, &extra->end);
1207 }
1208
1209 static void
1210 propogate_ends ()
1211 {
1212   /* First, shut of "in pin" when we have an "at pin".  We also clean
1213      up zero-length lines.  */
1214   g_hash_table_foreach (lines, (GHFunc)propogate_end_step1_cb, NULL);
1215
1216   /* Now end all paths at pins/pads.  */
1217   g_hash_table_foreach (lines, (GHFunc)propogate_end_step2_cb, NULL);
1218
1219   /* Now, propogate the pin/pad/vias along paths.  */
1220   g_hash_table_foreach (lines, (GHFunc)propogate_end_step3_cb, NULL);
1221 }
1222
1223 static Extra *last_pextra = 0;
1224
1225 static void
1226 print_extra (Extra *e, Extra *prev)
1227 {
1228   int which = 0;
1229   if (e->start.next == last_pextra)
1230     which = 1;
1231   else if (e->end.next == last_pextra)
1232     which = 2;
1233   switch (which) {
1234   case 0:
1235     printf("%10p %10p %10p :", e, e->start.next, e->end.next);
1236     break;
1237   case 1:
1238     printf("%10p \033[33m%10p\033[0m %10p :", e, e->start.next, e->end.next);
1239     break;
1240   case 2:
1241     printf("%10p %10p \033[33m%10p\033[0m :", e, e->start.next, e->end.next);
1242     break;
1243   }
1244   last_pextra = e;
1245   printf(" %c%c",
1246          e->deleted ? 'd' : '-',
1247          e->found   ? 'f' : '-');
1248   printf(" s:%s%s%s%s",
1249          e->start.in_pin ? "I" : "-",
1250          e->start.at_pin ? "A" : "-",
1251          e->start.is_pad ? "P" : "-",
1252          e->start.pending ? "p" : "-");
1253   printf(" e:%s%s%s%s ",
1254          e->end.in_pin ? "I" : "-",
1255          e->end.at_pin ? "A" : "-",
1256          e->end.is_pad ? "P" : "-",
1257          e->end.pending ? "p" : "-");
1258
1259   if (EXTRA_IS_LINE (e))
1260     {
1261       LineTypePtr line = EXTRA2LINE (e);
1262       pcb_printf(" %p L %#mD-%#mD", line, line->Point1.X, line->Point1.Y, line->Point2.X, line->Point2.Y);
1263       printf("  %s %p %s %p\n",
1264              e->start.is_pad ? "pad" : "pin", e->start.pin,
1265              e->end.is_pad ? "pad" : "pin", e->end.pin);
1266     }
1267   else if (EXTRA_IS_ARC (e))
1268     {
1269       ArcTypePtr arc = EXTRA2ARC (e);
1270       pcb_printf(" %p A %#mD-%#mD", arc, e->start.x, e->start.y, e->end.x, e->end.y);
1271       pcb_printf(" at %#mD ang %ld,%ld\n", arc->X, arc->Y, arc->StartAngle, arc->Delta);
1272     }
1273   else if (e == &multi_next)
1274     {
1275       printf("-- Multi-next\n");
1276     }
1277   else
1278     {
1279       printf("-- Unknown extra: %p\n", e);
1280     }
1281 }
1282
1283 #if TRACE1
1284 static void
1285 trace_path (Extra *e)
1286 {
1287   Extra *prev = 0;
1288   if ((e->start.next && e->end.next)
1289       || (!e->start.next && !e->end.next))
1290     return;
1291   if (e->found)
1292     return;
1293   printf("- path -\n");
1294   last_pextra = 0;
1295   while (e)
1296     {
1297       e->found = 1;
1298       print_extra (e, prev);
1299       if (e->start.next == prev)
1300         {
1301           prev = e;
1302           e = e->end.next;
1303         }
1304       else
1305         {
1306           prev = e;
1307           e = e->start.next;
1308         }
1309     }
1310 }
1311
1312 static void
1313 trace_paths ()
1314 {
1315   Extra *e;
1316
1317   clear_found ();
1318   LINE_LOOP (CURRENT); {
1319     e = LINE2EXTRA (line);
1320     trace_path (e);
1321   } END_LOOP;
1322   ARC_LOOP (CURRENT); {
1323     e = ARC2EXTRA (arc);
1324     trace_path (e);
1325   } END_LOOP;
1326 }
1327 #endif
1328
1329 static void
1330 reverse_line (LineTypePtr line)
1331 {
1332   Extra *e = LINE2EXTRA (line);
1333   int x, y;
1334   End etmp;
1335
1336   x = line->Point1.X;
1337   y = line->Point1.Y;
1338 #if 1
1339   MoveObject (LINEPOINT_TYPE, CURRENT, line, &(line->Point1),
1340               line->Point2.X - line->Point1.X,
1341               line->Point2.Y - line->Point1.Y);
1342   MoveObject (LINEPOINT_TYPE, CURRENT, line, &(line->Point2),
1343               x - line->Point2.X,
1344               y - line->Point2.Y);
1345 #else
1346   /* In theory, we should be using the above so that undo works.  */
1347   line->Point1.X = line->Point2.X;
1348   line->Point1.Y = line->Point2.Y;
1349   line->Point2.X = x;
1350   line->Point2.Y = y;
1351 #endif
1352   memcpy (&etmp, &e->start, sizeof (End));
1353   memcpy (&e->start, &e->end, sizeof (End));
1354   memcpy (&e->end, &etmp, sizeof (End));
1355 }
1356
1357 static void
1358 reverse_arc (ArcTypePtr arc)
1359 {
1360   Extra *e = ARC2EXTRA (arc);
1361   End etmp;
1362
1363 #if 1
1364   ChangeArcAngles (CURRENT, arc,
1365                    arc->StartAngle + arc->Delta, -arc->Delta);
1366 #else
1367   /* Likewise, see above.  */
1368   arc->StartAngle += arc->Delta;
1369   arc->Delta *= -1;
1370 #endif
1371   memcpy (&etmp, &e->start, sizeof (End));
1372   memcpy (&e->start, &e->end, sizeof (End));
1373   memcpy (&e->end, &etmp, sizeof (End));
1374 }
1375
1376 static void
1377 expand_box (BoxTypePtr b, int x, int y, int t)
1378 {
1379   b->X1 = MIN (b->X1, x-t);
1380   b->X2 = MAX (b->X2, x+t);
1381   b->Y1 = MIN (b->Y1, y-t);
1382   b->Y2 = MAX (b->Y2, y+t);
1383 }
1384
1385 /* ---------------------------------------------------------------------- */
1386 /* These are the state variables for the intersection we're currently
1387    working on. */
1388
1389 /* what we're working with */
1390 static ArcTypePtr start_arc;
1391 static LineTypePtr start_line;
1392 static LineTypePtr end_line;
1393 static ArcTypePtr end_arc;
1394 static Extra *start_extra, *end_extra;
1395 static Extra *sarc_extra, *earc_extra;
1396 static void *start_pinpad, *end_pinpad;
1397 static int thickness;
1398
1399 /* Pre-computed values.  Note that all values are computed according
1400    to CARTESIAN coordinates, not PCB coordinates.  Do an up-down board
1401    flip before wrapping your brain around the math.  */
1402
1403 /* se_sign is positive when you make a right turn going from start to end. */
1404 /* sa_sign is positive when start's arc is on the same side of start as end.  */
1405 /* ea_sign is positive when end's arc is on the same side of end as start.  */
1406 /* sa_sign and ea_sign may be zero if there's no arc.  */
1407 static double se_sign, sa_sign, ea_sign;
1408
1409 static double best_angle, start_angle, end_dist;
1410 /* arc radii are positive when they're on the same side as the things
1411    we're interested in. */
1412 static int sa_r, ea_r;
1413 static int sa_x, sa_y; /* start "arc" point */
1414
1415 /* what we've found so far */
1416 static int fx, fy, fr, fp;
1417 static End *fp_end;
1418 static double fa; /* relative angle */
1419
1420 #define gp_point(x,y,t,e) gp_point_2(x,y,t,e,0,0,__FUNCTION__)
1421
1422 static int
1423 gp_point_force (int x, int y, int t, End *e, int esa, int eda, int force, const char *name)
1424 {
1425   double r, a, d;
1426   int scx, scy, sr;
1427   double base_angle, rel_angle, point_angle;
1428
1429 #if TRACE1
1430   pcb_printf("\033[34mgp_point_force %#mD %#mS via %s\033[0m\n", x, y, t, name);
1431 #endif
1432
1433   if (start_arc)
1434     {
1435       scx = start_arc->X;
1436       scy = start_arc->Y;
1437       sr = start_arc->Width;
1438     }
1439   else
1440     {
1441       scx = start_line->Point1.X;
1442       scy = start_line->Point1.Y;
1443       sr = 0;
1444     }
1445
1446   r = t + thickness;
1447
1448   /* See if the point is inside our start arc. */
1449   d = Distance (scx, scy, x, y);
1450 #if TRACE1
1451   pcb_printf("%f = dist #mD to %#mD\n", d, scx, scy, x, y);
1452   pcb_printf("sr %#mS r %f d %f\n", sr, r, d);
1453 #endif
1454   if (d  < sr - r)
1455     {
1456 #if TRACE1
1457       printf("inside start arc, %f < %f\n", d, sr-r);
1458 #endif
1459       return 0;
1460     }
1461   if (sr == 0 && d < r)
1462     {
1463 #if TRACE1
1464       printf("start is inside arc, %f < %f\n", d, r);
1465 #endif
1466       return 0;
1467     }
1468
1469   /* Now for the same tricky math we needed for the single puller.
1470      sr and r are the radii for the two points scx,scy and x,y.  */
1471
1472   /* angle between points (NOT pcb arc angles) */
1473   base_angle = atan2 (y - scy, x - scx);
1474 #if TRACE1
1475   pcb_printf("%.1f = atan2 (%#mS-%#mS = %#mS, %#mS-%#mS = %#mS)\n",
1476              r2d(base_angle), y, scy, y-scy, x, scx, x-scx);
1477 #endif
1478
1479   if ((sa_sign * sr - r) / d > 1
1480       || (sa_sign * sr - r) / d < -1)
1481     return 0;
1482
1483   /* Angle of tangent, relative to the angle between point centers.  */
1484   rel_angle = se_sign * asin ((sa_sign * sr - r) / d);
1485 #if TRACE1
1486   printf("%.1f = %d * asin ((%d * %d - %f) / %f)\n",
1487          r2d(rel_angle), (int)se_sign, (int)sa_sign, sr, r, d);
1488 #endif
1489
1490   /* Absolute angle of tangent.  */
1491   point_angle = base_angle + rel_angle;
1492 #if TRACE1
1493   printf("base angle %.1f rel_angle %.1f point_angle %.1f\n",
1494          r2d(base_angle),
1495          r2d(rel_angle),
1496          r2d(point_angle));
1497 #endif
1498
1499   if (eda)
1500     {
1501       /* Check arc angles */
1502       double pa = point_angle;
1503       double sa = d2r(180-esa);
1504       double da = d2r(-eda);
1505
1506       if (da < 0)
1507         {
1508           sa = sa + da;
1509           da = -da;
1510         }
1511
1512       pa -= se_sign * M_PI/2;
1513       while (sa+da < pa)
1514         sa += M_PI*2;
1515       while (sa > pa)
1516         sa -= M_PI*2;
1517       if (sa+da < pa)
1518         {
1519 #if TRACE1
1520           printf("arc doesn't apply: sa %.1f da %.1f pa %.1f\n",
1521                  r2d(sa), r2d(da), r2d(pa));
1522 #endif
1523           return 0;
1524         }
1525     }
1526
1527   a = point_angle - start_angle;
1528   while (a > M_PI)
1529     a -= M_PI*2;
1530   while (a < -M_PI)
1531     a += M_PI*2;
1532 #if TRACE1
1533   printf(" - angle relative to S-E baseline is %.1f\n", r2d(a));
1534 #endif
1535
1536   if (!force && a * se_sign < -0.007)
1537     {
1538       double new_r;
1539 #if TRACE1
1540       printf("skipping, would increase angle (%f * %f)\n", a, se_sign);
1541 #endif
1542       new_r = dist_lp (start_line->Point1.X, start_line->Point1.Y,
1543                        start_line->Point2.X, start_line->Point2.Y,
1544                        x, y);
1545 #if TRACE1
1546       pcb_printf("point %#mD dist %#mS vs thickness %#mS\n", x, y, new_r, thickness);
1547 #endif
1548       new_r -= thickness;
1549       new_r = (int)new_r - 1;
1550 #if TRACE1
1551       pcb_printf(" - new thickness %f old %#mS\n", new_r, t);
1552 #endif
1553       if (new_r < t)
1554         gp_point_force (x, y, new_r, e, esa, eda, 1, __FUNCTION__);
1555       return 0;
1556     }
1557
1558 #if TRACE1
1559   printf("%f * %f < %f * %f ?\n", a, se_sign, best_angle, se_sign);
1560 #endif
1561   if (a * se_sign == best_angle * se_sign)
1562     {
1563       double old_d = Distance (start_line->Point1.X, start_line->Point1.Y,
1564                            fx, fy);
1565       double new_d = Distance (start_line->Point1.X, start_line->Point1.Y,
1566                            x, y);
1567       if (new_d > old_d)
1568         {
1569           best_angle = a;
1570           fx = x;
1571           fy = y;
1572           fr = r;
1573           fa = a;
1574           fp = e ? e->pending : 0;
1575           fp_end = e;
1576         }
1577     }
1578   else if (a * se_sign < best_angle * se_sign)
1579     {
1580       best_angle = a;
1581       fx = x;
1582       fy = y;
1583       fr = r;
1584       fa = a;
1585       fp = e ? e->pending : 0;
1586       fp_end = e;
1587     }
1588
1589   return 1;
1590 }
1591 static int
1592 gp_point_2 (int x, int y, int t, End *e, int esa, int eda, const char *func)
1593 {
1594   double sc, ec;
1595   double sd, ed;
1596
1597   if (x == sa_x && y ==sa_y)
1598     return 0;
1599
1600 #if TRACE1
1601   pcb_printf("\033[34mgp_point %#mD %#mS via %s\033[0m\n", x, y, t, func);
1602 #endif
1603
1604   /* There are two regions we care about.  For points inside our
1605      triangle, we check the crosses against start_line and end_line to
1606      make sure the point is "inside" the triangle.  For points on the
1607      other side of the s-e line of the triangle, we check the dots to
1608      make sure it's between our endpoints.  */
1609
1610   /* See what side of the s-e line we're on */
1611   sc = cross2d (start_line->Point1.X, start_line->Point1.Y,
1612                 end_line->Point2.X, end_line->Point2.Y,
1613                 x, y);
1614 #if TRACE1
1615   printf("s-e cross = %f\n", sc);
1616 #endif
1617   if (t >= 0)
1618     {
1619       if (same_sign (sc, se_sign))
1620         {
1621           /* Outside, check dots.  */
1622
1623           /* Ok, is it "in front of" our vectors? */
1624           sd = dot2d (start_line->Point1.X, start_line->Point1.Y,
1625                       end_line->Point2.X, end_line->Point2.Y,
1626                       x, y);
1627 #if TRACE1
1628           printf("sd = %f\n", sd);
1629 #endif
1630           if (sd <= 0)
1631             return 0;
1632
1633           ed = dot2d (end_line->Point2.X, end_line->Point2.Y,
1634                       start_line->Point1.X, start_line->Point1.Y,
1635                       x, y);
1636 #if TRACE1
1637           printf("ed = %f\n", ed);
1638 #endif
1639           if (ed <= 0)
1640             return 0;
1641
1642           sd = dist_lp (start_line->Point1.X, start_line->Point1.Y,
1643                         end_line->Point2.X, end_line->Point2.Y,
1644                         x, y);
1645           if (sd > t + thickness)
1646             return 0;
1647         }
1648       else
1649         {
1650           /* Inside, check crosses.  */
1651
1652           /* First off, is it on the correct side of the start line? */
1653           sc = cross2d (start_line->Point1.X, start_line->Point1.Y,
1654                         start_line->Point2.X, start_line->Point2.Y,
1655                         x, y);
1656 #if TRACE1
1657           printf("sc = %f\n", sc);
1658 #endif
1659           if (! same_sign (sc, se_sign))
1660             return 0;
1661
1662           /* Ok, is it on the correct side of the end line? */
1663           ec = cross2d (end_line->Point1.X, end_line->Point1.Y,
1664                         end_line->Point2.X, end_line->Point2.Y,
1665                         x, y);
1666 #if TRACE1
1667           printf("ec = %f\n", ec);
1668 #endif
1669           if (! same_sign (ec, se_sign))
1670             return 0;
1671         }
1672     }
1673
1674 #if TRACE1
1675   printf("in range!\n");
1676 #endif
1677
1678   return gp_point_force (x, y, t, e, esa, eda, 0, func);
1679 }
1680
1681 static int
1682 gp_line_cb (const BoxType *b, void *cb)
1683 {
1684   const LineTypePtr l = (LineTypePtr) b;
1685   Extra *e = LINE2EXTRA(l);
1686   if (l == start_line || l == end_line)
1687     return 0;
1688   if (e->deleted)
1689     return 0;
1690 #ifdef CHECK_LINE_PT_NEG
1691   if (l->Point1.X < 0)
1692     abort1();
1693 #endif
1694   if (! e->start.next
1695       || ! EXTRA_IS_ARC (e->start.next))
1696     gp_point (l->Point1.X, l->Point1.Y, l->Thickness/2, &e->start);
1697   if (! e->end.next
1698       || ! EXTRA_IS_ARC (e->end.next))
1699     gp_point (l->Point2.X, l->Point2.Y, l->Thickness/2, &e->end);
1700   return 0;
1701 }
1702
1703 static int
1704 gp_arc_cb (const BoxType *b, void *cb)
1705 {
1706   const ArcTypePtr a = (ArcTypePtr) b;
1707   Extra *e = ARC2EXTRA(a);
1708   if (a == start_arc || a == end_arc)
1709     return 0;
1710   if (e->deleted)
1711     return 0;
1712   gp_point_2 (a->X, a->Y, a->Width + a->Thickness/2, 0, a->StartAngle, a->Delta, __FUNCTION__);
1713   if (start_arc
1714       && a->X == start_arc->X
1715       && a->Y == start_arc->Y)
1716     return 0;
1717   if (end_arc
1718       && a->X != end_arc->X
1719       && a->Y != end_arc->Y)
1720      return 0;
1721
1722   if (e->start.next || e->end.next)
1723     return 0;
1724
1725   gp_point (e->start.x, e->start.y, a->Thickness/2, 0);
1726   gp_point (e->end.x, e->end.y, a->Thickness/2, 0);
1727   return 0;
1728 }
1729
1730 static int
1731 gp_text_cb (const BoxType *b, void *cb)
1732 {
1733   const TextTypePtr t = (TextTypePtr) b;
1734   /* FIXME: drop in the actual text-line endpoints later. */
1735   gp_point (t->BoundingBox.X1, t->BoundingBox.Y1, 0, 0);
1736   gp_point (t->BoundingBox.X1, t->BoundingBox.Y2, 0, 0);
1737   gp_point (t->BoundingBox.X2, t->BoundingBox.Y2, 0, 0);
1738   gp_point (t->BoundingBox.X2, t->BoundingBox.Y1, 0, 0);
1739   return 0;
1740 }
1741
1742 static int
1743 gp_poly_cb (const BoxType *b, void *cb)
1744 {
1745   int i;
1746   const PolygonTypePtr p = (PolygonTypePtr) b;
1747   for (i=0; i<p->PointN; i++)
1748     gp_point (p->Points[i].X, p->Points[i].Y, 0, 0);
1749   return 0;
1750 }
1751
1752 static int
1753 gp_pin_cb (const BoxType *b, void *cb)
1754 {
1755   const PinTypePtr p = (PinTypePtr) b;
1756   int t2 = (p->Thickness+1)/2;
1757
1758   if (p == start_pinpad || p == end_pinpad)
1759     return 0;
1760
1761   /* FIXME: we lump octagonal pins in with square; safe, but not
1762      optimal.  */
1763   if (TEST_FLAG (SQUAREFLAG, p) || TEST_FLAG (OCTAGONFLAG, p))
1764     {
1765       gp_point (p->X - t2, p->Y - t2, 0, 0);
1766       gp_point (p->X - t2, p->Y + t2, 0, 0);
1767       gp_point (p->X + t2, p->Y + t2, 0, 0);
1768       gp_point (p->X + t2, p->Y - t2, 0, 0);
1769     }
1770   else
1771     {
1772       gp_point (p->X, p->Y, t2, 0);
1773     }
1774   return 0;
1775 }
1776
1777 static int
1778 gp_pad_cb (const BoxType *b, void *cb)
1779 {
1780   const PadTypePtr p = (PadTypePtr) b;
1781   int t2 = (p->Thickness+1)/2;
1782
1783   if (p == start_pinpad || p == end_pinpad)
1784     return 0;
1785
1786   if (TEST_FLAG (ONSOLDERFLAG, p))
1787     {
1788       if (!current_is_solder)
1789         return 0;
1790     }
1791   else
1792     {
1793       if (!current_is_component)
1794         return 0;
1795     }
1796
1797   /* FIXME: we lump octagonal pads in with square; safe, but not
1798      optimal.  I don't think we even support octagonal pads.  */
1799   if (TEST_FLAG (SQUAREFLAG, p) || TEST_FLAG (OCTAGONFLAG, p))
1800     {
1801       if (p->Point1.X == p->Point2.X)
1802         {
1803           int y1 = MIN (p->Point1.Y, p->Point2.Y) - t2;
1804           int y2 = MAX (p->Point1.Y, p->Point2.Y) + t2;
1805
1806           gp_point (p->Point1.X - t2, y1, 0, 0);
1807           gp_point (p->Point1.X - t2, y2, 0, 0);
1808           gp_point (p->Point1.X + t2, y1, 0, 0);
1809           gp_point (p->Point1.X + t2, y2, 0, 0);
1810         }
1811       else
1812         {
1813           int x1 = MIN (p->Point1.X, p->Point2.X) - t2;
1814           int x2 = MAX (p->Point1.X, p->Point2.X) + t2;
1815
1816           gp_point (x1, p->Point1.Y - t2, 0, 0);
1817           gp_point (x2, p->Point1.Y - t2, 0, 0);
1818           gp_point (x1, p->Point1.Y + t2, 0, 0);
1819           gp_point (x2, p->Point1.Y + t2, 0, 0);
1820         }
1821     }
1822   else
1823     {
1824       gp_point (p->Point1.X, p->Point1.Y, t2, 0);
1825       gp_point (p->Point2.X, p->Point2.Y, t2, 0);
1826     }
1827   return 0;
1828 }
1829
1830 static LineTypePtr
1831 create_line (LineTypePtr sample, int x1, int y1, int x2, int y2)
1832 {
1833 #if TRACE1
1834   Extra *e;
1835   pcb_printf("create_line from %#mD to %#mD\n", x1, y1, x2, y2);
1836 #endif
1837   LineTypePtr line = CreateNewLineOnLayer (CURRENT, x1, y1, x2, y2,
1838                                            sample->Thickness, sample->Clearance, sample->Flags);
1839   AddObjectToCreateUndoList (LINE_TYPE, CURRENT, line, line);
1840
1841 #if TRACE1
1842   e =
1843 #endif
1844     new_line_extra (line);
1845 #if TRACE1
1846   printf(" - line extra is %p\n", e);
1847 #endif
1848   return line;
1849 }
1850
1851 static ArcTypePtr
1852 create_arc (LineTypePtr sample, int x, int y, int r, int sa, int da)
1853 {
1854   Extra *e;
1855   ArcTypePtr arc;
1856
1857   if (r % 100 == 1)
1858     r--;
1859   if (r % 100 == 99)
1860     r++;
1861 #if TRACE1
1862   pcb_printf("create_arc at %#mD r %#mS sa %d delta %d\n", x, y, r, sa, da);
1863 #endif
1864   arc = CreateNewArcOnLayer (CURRENT, x, y, r, r, sa, da,
1865                                         sample->Thickness, sample->Clearance, sample->Flags);
1866   if (arc == 0)
1867     {
1868       arc = CreateNewArcOnLayer (CURRENT, x, y, r, r, sa, da*2,
1869                                  sample->Thickness, sample->Clearance, sample->Flags);
1870     }
1871   AddObjectToCreateUndoList (ARC_TYPE, CURRENT, arc, arc);
1872
1873   if (!arc)
1874     longjmp (abort_buf, 1);
1875
1876   e = new_arc_extra (arc);
1877 #if TRACE1
1878   printf(" - arc extra is %p\n", e);
1879 #endif
1880   fix_arc_extra (arc, e);
1881   return arc;
1882 }
1883
1884 static void
1885 unlink_extras (Extra *e)
1886 {
1887 #if TRACE1
1888   fprintf(stderr, "unlink %p\n", e);
1889   print_extra(e,0);
1890 #endif
1891   if (e->start.next)
1892     {
1893 #if TRACE1
1894       print_extra(e->start.next, 0);
1895 #endif
1896       if (e->start.next->start.next == e)
1897         {
1898 #if TRACE1
1899           fprintf(stderr, " - %p->start points to me\n", e->start.next);
1900 #endif
1901           e->start.next->start.next = e->end.next;
1902         }
1903       else if (e->start.next->end.next == e)
1904         {
1905 #if TRACE1
1906           fprintf(stderr, " - %p->end points to me\n", e->start.next);
1907 #endif
1908           e->start.next->end.next = e->end.next;
1909         }
1910       else
1911         {
1912           fprintf(stderr, " - %p doesn't point to me!\n", e->start.next);
1913           abort();
1914         }
1915     }
1916   if (e->end.next)
1917     {
1918 #if TRACE1
1919       print_extra(e->end.next, 0);
1920 #endif
1921       if (e->end.next->start.next == e)
1922         {
1923 #if TRACE1
1924           fprintf(stderr, " - %p->end points to me\n", e->end.next);
1925 #endif
1926           e->end.next->start.next = e->start.next;
1927         }
1928       else if (e->end.next->end.next == e)
1929         {
1930 #if TRACE1
1931           fprintf(stderr, " - %p->end points to me\n", e->end.next);
1932 #endif
1933           e->end.next->end.next = e->start.next;
1934         }
1935       else
1936         {
1937           fprintf(stderr, " - %p doesn't point to me!\n", e->end.next);
1938           abort();
1939         }
1940     }
1941   e->start.next = e->end.next = 0;
1942 }
1943
1944 static void
1945 mark_line_for_deletion (LineTypePtr l)
1946 {
1947   Extra *e = LINE2EXTRA(l);
1948   if (e->deleted)
1949     {
1950       fprintf(stderr, "double delete?\n");
1951       abort();
1952     }
1953   e->deleted = 1;
1954   unlink_extras (e);
1955 #if TRACE1
1956   pcb_printf("Marked line %p for deletion %#mD to %#mD\n",
1957          e, l->Point1.X, l->Point1.Y, l->Point2.X, l->Point2.Y);
1958 #endif
1959 #if 0
1960   if (l->Point1.X < 0)
1961     {
1962       fprintf(stderr, "double neg move?\n");
1963       abort();
1964     }
1965   MoveObject (LINEPOINT_TYPE, CURRENT, l, &(l->Point1),
1966               -1 - l->Point1.X,
1967               -1 - l->Point1.Y);
1968   MoveObject (LINEPOINT_TYPE, CURRENT, l, &(l->Point2),
1969               -1 - l->Point2.X,
1970               -1 - l->Point2.Y);
1971 #endif
1972 }
1973
1974 static void
1975 mark_arc_for_deletion (ArcTypePtr a)
1976 {
1977   Extra *e = ARC2EXTRA(a);
1978   e->deleted = 1;
1979   unlink_extras (e);
1980 #if TRACE1
1981   printf("Marked arc %p for deletion %ld < %ld\n",
1982          e, a->StartAngle, a->Delta);
1983 #endif
1984 }
1985
1986 /* Given a starting line, which may be attached to an arc, and which
1987    intersects with an ending line, which also may be attached to an
1988    arc, maybe pull them.  We assume start_line is attached to the arc
1989    via Point1, and attached to the end line via Point2.  Likewise, we
1990    make end_line attach to the start_line via Point1 and the arc via
1991    Point 2.  We also make the arcs attach on the Delta end, not the
1992    Start end.  Here's a picture:
1993
1994      S            S+D  P1            P2   P1          P2  S+D          S
1995    *--- start_arc ---*--- start_line ---*--- end_line ---*--- end_arc ---*
1996      S             E   S              E   S            E   E           S
1997 */
1998
1999 static void
2000 maybe_pull_1 (LineTypePtr line)
2001 {
2002   BoxType box;
2003   /* Line half-thicknesses, including line space */
2004   int ex, ey;
2005   LineTypePtr new_line;
2006   Extra *new_lextra;
2007   ArcTypePtr new_arc;
2008   Extra *new_aextra;
2009   double abs_angle;
2010
2011   start_line = line;
2012   start_extra = LINE2EXTRA (start_line);
2013   end_extra = start_extra->end.next;
2014   end_line = EXTRA2LINE (end_extra);
2015   if (end_extra->deleted)
2016     {
2017       start_extra->end.pending = 0;
2018       return;
2019     }
2020
2021   if (end_extra->end.next == start_extra)
2022     reverse_line (end_line);
2023
2024   if (start_extra->start.next
2025       && EXTRA_IS_ARC (start_extra->start.next))
2026     {
2027       sarc_extra = start_extra->start.next;
2028       start_arc = EXTRA2ARC (sarc_extra);
2029       if (sarc_extra->start.next == start_extra)
2030         reverse_arc (start_arc);
2031     }
2032   else
2033     {
2034       start_arc = 0;
2035       sarc_extra = 0;
2036     }
2037
2038   if (end_extra->end.next
2039       && EXTRA_IS_ARC (end_extra->end.next))
2040     {
2041       earc_extra = end_extra->end.next;
2042       end_arc = EXTRA2ARC (earc_extra);
2043       if (earc_extra->start.next == end_extra)
2044         reverse_arc (end_arc);
2045     }
2046   else
2047     {
2048       end_arc = 0;
2049       earc_extra = 0;
2050     }
2051
2052 #if TRACE1
2053   printf("maybe_pull_1 %p %p %p %p\n", sarc_extra, start_extra, end_extra, earc_extra);
2054   if (sarc_extra)
2055     print_extra(sarc_extra,0);
2056   print_extra(start_extra,0);
2057   print_extra(end_extra,0);
2058   if (earc_extra)
2059     print_extra(earc_extra,0);
2060
2061   if (start_extra->deleted
2062       || end_extra->deleted
2063       || (sarc_extra && sarc_extra->deleted)
2064       || (earc_extra && earc_extra->deleted))
2065     {
2066       printf(" one is deleted?\n");
2067       fflush(stdout);
2068       abort();
2069     }
2070 #endif
2071
2072   if (!start_extra->end.pending)
2073     return;
2074 #if 0
2075   if (start_extra->end.waiting_for
2076       && start_extra->end.waiting_for->pending)
2077     return;
2078 #endif
2079
2080   if (start_line->Thickness != end_line->Thickness)
2081     return;
2082   thickness = (start_line->Thickness + 1)/2 + PCB->Bloat;
2083
2084   /* At this point, our expectations are all met.  */
2085
2086   box.X1 = start_line->Point1.X - thickness;
2087   box.X2 = start_line->Point1.X + thickness;
2088   box.Y1 = start_line->Point1.Y - thickness;
2089   box.Y2 = start_line->Point1.Y + thickness;
2090   expand_box (&box, start_line->Point2.X, start_line->Point2.Y, thickness);
2091   expand_box (&box, end_line->Point2.X, end_line->Point2.Y, thickness);
2092   if (start_arc)
2093     expand_box (&box, sarc_extra->start.x, sarc_extra->start.y, start_arc->Thickness/2);
2094   if (end_arc)
2095     expand_box (&box, earc_extra->start.x, earc_extra->start.y, end_arc->Thickness/2);
2096
2097
2098   se_sign = copysign (1, cross2d (start_line->Point1.X, start_line->Point1.Y,
2099                                   start_line->Point2.X, start_line->Point2.Y,
2100                                   end_line->Point2.X, end_line->Point2.Y));
2101   best_angle = se_sign * M_PI;
2102   if (start_arc)
2103     {
2104       sa_sign = copysign (1, -start_arc->Delta);
2105       sa_sign *= se_sign;
2106     }
2107   else
2108     sa_sign = 0;
2109   if (end_arc)
2110     {
2111       ea_sign = copysign (1, -end_arc->Delta);
2112       ea_sign *= -se_sign;
2113     }
2114   else
2115     ea_sign = 0;
2116
2117   start_angle = atan2 (start_line->Point2.Y - start_line->Point1.Y,
2118                        start_line->Point2.X - start_line->Point1.X);
2119 #if TRACE1
2120   printf("se_sign %f sa_sign %f ea_sign %f best_angle %f start_angle %f\n",
2121          se_sign, sa_sign, ea_sign, r2d (best_angle), r2d(start_angle));
2122 #endif
2123
2124   if (start_arc)
2125     {
2126       sa_x = start_arc->X;
2127       sa_y = start_arc->Y;
2128       if (same_sign (start_arc->Delta, se_sign))
2129         sa_r = - start_arc->Width;
2130       else
2131         sa_r = start_arc->Width;
2132     }
2133   else
2134     {
2135       sa_x = start_line->Point1.X;
2136       sa_y = start_line->Point1.Y;
2137       sa_r = 0;
2138     }
2139
2140   if (end_arc)
2141     {
2142       if (ea_sign < 0)
2143         ea_r = end_arc->Width;
2144       else
2145         ea_r = - end_arc->Width;
2146     }
2147   else
2148     ea_r = 0;
2149
2150 #if TRACE1
2151   trace_path (sarc_extra ? sarc_extra : start_extra);
2152 #endif
2153
2154   if (end_arc)
2155     {
2156       gp_point_force (end_arc->X, end_arc->Y, -ea_r-thickness, 0, 0, 0, 1, "end arc");
2157       ex = end_arc->X;
2158       ey = end_arc->Y;
2159     }
2160   else
2161     {
2162       gp_point_force (end_line->Point2.X, end_line->Point2.Y, -thickness, 0, 0, 0, 1, "end arc");
2163       ex = end_line->Point2.X;
2164       ey = end_line->Point2.Y;
2165     }
2166
2167   fx = ex;
2168   fy = ey;
2169   if (fx < 0)
2170     {
2171       pcb_fprintf(stderr, "end line corrupt? f is %#mD\n", fx, fy);
2172       print_extra (end_extra, 0);
2173       if (earc_extra)
2174         print_extra(earc_extra, 0);
2175       abort();
2176     }
2177
2178   end_dist = Distance (end_line->Point1.X, end_line->Point1.Y,
2179                    end_line->Point2.X, end_line->Point2.Y);
2180
2181   start_pinpad = start_extra->start.pin;
2182   end_pinpad = start_extra->end.pin;
2183   fp = 0;
2184
2185   r_search(CURRENT->line_tree, &box, NULL, gp_line_cb, 0);
2186   r_search(CURRENT->arc_tree, &box, NULL, gp_arc_cb, 0);
2187   r_search(CURRENT->text_tree, &box, NULL, gp_text_cb, 0);
2188   r_search(CURRENT->polygon_tree, &box, NULL, gp_poly_cb, 0);
2189   r_search(PCB->Data->pin_tree, &box, NULL, gp_pin_cb, 0);
2190   r_search(PCB->Data->via_tree, &box, NULL, gp_pin_cb, 0);
2191   r_search(PCB->Data->pad_tree, &box, NULL, gp_pad_cb, 0);
2192
2193   /* radians, absolute angle of (at the moment) the start_line */
2194   abs_angle = fa + start_angle;
2195
2196 #if TRACE1
2197   pcb_printf("\033[43;30mBest: at %#mD r %#mS, angle %.1f fp %d\033[0m\n", fx, fy, fr, r2d(fa), fp);
2198 #endif
2199
2200 #if 0
2201   if (fa > M_PI/2 || fa < -M_PI/2)
2202     {
2203       SET_FLAG (FOUNDFLAG, line);
2204       longjmp (abort_buf, 1);
2205     }
2206 #endif
2207
2208   if (fp)
2209     {
2210       start_extra->end.waiting_for = fp_end;
2211       return;
2212     }
2213   start_extra->end.pending = 0;
2214
2215   /* Step 0: check for merged arcs (special case).  */
2216
2217   if (fx == ex && fy == ey
2218       && start_arc && end_arc
2219       && start_arc->X == end_arc->X && start_arc->Y == end_arc->Y)
2220     {
2221       /* Merge arcs */
2222       int new_delta;
2223
2224       new_delta = end_arc->StartAngle - start_arc->StartAngle;
2225       if (start_arc->Delta > 0)
2226         {
2227           while (new_delta > 360)
2228             new_delta -= 360;
2229           while (new_delta < 0)
2230             new_delta += 360;
2231         }
2232       else
2233         {
2234           while (new_delta < -360)
2235             new_delta += 360;
2236           while (new_delta > 0)
2237             new_delta -= 360;
2238         }
2239 #if TRACE1
2240       pcb_printf("merging arcs at %#mS nd %d\n", start_arc->X, start_arc->Y, new_delta);
2241       print_extra(sarc_extra, 0);
2242       print_extra(earc_extra, 0);
2243 #endif
2244       mark_arc_for_deletion (end_arc);
2245       mark_line_for_deletion (start_line);
2246       mark_line_for_deletion (end_line);
2247       ChangeArcAngles (CURRENT, start_arc, start_arc->StartAngle, new_delta);
2248       fix_arc_extra (start_arc, sarc_extra);
2249       did_something ++;
2250       return;
2251     }
2252
2253   /* Step 1: adjust start_arc's angles and move start_line's Point1 to
2254      match it. */
2255
2256   if (start_arc)
2257     {
2258       double new_delta;
2259       int del_arc = 0;
2260
2261       /* We must always round towards "larger arcs", whichever way that is. */
2262       new_delta = 180 - r2d(abs_angle);
2263 #if TRACE1
2264       printf("new_delta starts at %d vs %d < %d\n",
2265              (int)new_delta, (int)start_arc->StartAngle, (int)start_arc->Delta);
2266 #endif
2267       if (start_arc->Delta < 0)
2268         new_delta = (int)(new_delta) + 90;
2269       else
2270         new_delta = (int)new_delta - 90;
2271       new_delta =  new_delta - start_arc->StartAngle;
2272       while (new_delta > start_arc->Delta+180)
2273         new_delta -= 360;
2274       while (new_delta < start_arc->Delta-180)
2275         new_delta += 360;
2276 #if TRACE1
2277       printf("new_delta adjusts to %d\n", (int)new_delta);
2278       printf("fa = %f, new_delta ends at %.1f vs start %d\n",
2279              fa, new_delta, (int)start_arc->StartAngle);
2280 #endif
2281
2282       if (new_delta * start_arc->Delta <= 0)
2283         del_arc = 1;
2284
2285       ChangeArcAngles (CURRENT, start_arc, start_arc->StartAngle, new_delta);
2286       fix_arc_extra (start_arc, sarc_extra);
2287       MoveObject (LINEPOINT_TYPE, CURRENT, start_line, &(start_line->Point1),
2288                   sarc_extra->end.x - start_line->Point1.X,
2289                   sarc_extra->end.y - start_line->Point1.Y);
2290
2291       if (del_arc)
2292         {
2293           MoveObject (LINEPOINT_TYPE, CURRENT, start_line, &(start_line->Point1),
2294                       sarc_extra->start.x - start_line->Point1.X,
2295                       sarc_extra->start.y - start_line->Point1.Y);
2296           mark_arc_for_deletion (start_arc);
2297         }
2298     }
2299
2300   /* Step 1.5: If the "obstacle" is right at the end, ignore it.  */
2301
2302   {
2303     double oa = start_angle+fa - M_PI/2*se_sign;
2304     double ox = fx + fr * cos(oa);
2305     double oy = fy + fr * sin(oa);
2306 #if TRACE1
2307     pcb_printf("obstacle at %#mD angle %d = arc starts at %#mD\n",
2308            fx, fy, (int)r2d(oa), (int)ox, (int)oy);
2309 #endif
2310
2311     if (Distance (ox, oy, end_line->Point2.X, end_line->Point2.Y)
2312         < fr * SIN1D)
2313       {
2314         /* Pretend it doesn't exist.  */
2315         fx = ex;
2316         fy = ey;
2317       }
2318   }
2319
2320   /* Step 2: If we have no obstacles, connect start and end.  */
2321
2322 #if TRACE1
2323   pcb_printf("fx %#mS ex %#mS fy %#mS ey %#mS\n", fx, ex, fy, ey);
2324 #endif
2325   if (fx == ex && fy == ey)
2326     {
2327       /* No obstacles.  */
2328 #if TRACE1
2329       printf("\033[32mno obstacles\033[0m\n");
2330 #endif
2331       if (end_arc)
2332         {
2333           int del_arc = 0;
2334           int new_delta, end_angle, pcb_fa, end_change;
2335
2336           end_angle = end_arc->StartAngle + end_arc->Delta;
2337           if (end_arc->Delta < 0)
2338             end_angle -= 90;
2339           else
2340             end_angle += 90;
2341
2342           /* We must round so as to make the larger arc.  */
2343           if (end_arc->Delta < 0)
2344             pcb_fa = - r2d(start_angle + fa);
2345           else
2346             pcb_fa = 1 - r2d(start_angle + fa);
2347           end_change = pcb_fa - end_angle;
2348
2349           while (end_change > 180)
2350             end_change -= 360;
2351           while (end_change < -180)
2352             end_change += 360;
2353           new_delta = end_arc->Delta + end_change;
2354
2355           if (new_delta * end_arc->Delta <= 0)
2356             del_arc = 1;
2357
2358           ChangeArcAngles (CURRENT, end_arc, end_arc->StartAngle, new_delta);
2359           fix_arc_extra (end_arc, earc_extra);
2360           MoveObject (LINEPOINT_TYPE, CURRENT, start_line, &(start_line->Point2),
2361                       earc_extra->end.x - start_line->Point2.X,
2362                       earc_extra->end.y - start_line->Point2.Y);
2363
2364           if (del_arc)
2365             {
2366               MoveObject (LINEPOINT_TYPE, CURRENT, start_line, &(start_line->Point2),
2367                           earc_extra->start.x - start_line->Point2.X,
2368                           earc_extra->start.y - start_line->Point2.Y);
2369               mark_arc_for_deletion (end_arc);
2370             }
2371         }
2372       else
2373         {
2374           MoveObject (LINEPOINT_TYPE, CURRENT, start_line, &(start_line->Point2),
2375                       end_line->Point2.X - start_line->Point2.X,
2376                       end_line->Point2.Y - start_line->Point2.Y);
2377         }
2378       mark_line_for_deletion (end_line);
2379       start_extra->end.pending = 1;
2380
2381 #if TRACE1
2382       printf("\033[35mdid_something: no obstacles\033[0m\n");
2383 #endif
2384       did_something ++;
2385       npulled ++;
2386       status();
2387       return;
2388     }
2389
2390   /* Step 3: Compute the new intersection of start_line and end_line.  */
2391
2392   ex = start_line->Point1.X + cos(start_angle + fa) * 10000.0;
2393   ey = start_line->Point1.Y + sin(start_angle + fa) * 10000.0;
2394 #if TRACE1
2395   pcb_printf("temp point %#mS\n", ex, ey);
2396   pcb_printf("intersect %#mS-%#mS with %#mS-%#mS\n",
2397          start_line->Point1.X, start_line->Point1.Y,
2398          ex, ey,
2399          end_line->Point1.X, end_line->Point1.Y,
2400          end_line->Point2.X, end_line->Point2.Y);
2401 #endif
2402   if (! intersection_of_lines (start_line->Point1.X, start_line->Point1.Y,
2403                                ex, ey,
2404                                end_line->Point1.X, end_line->Point1.Y,
2405                                end_line->Point2.X, end_line->Point2.Y,
2406                                &ex, &ey))
2407     {
2408       ex = end_line->Point2.X;
2409       ey = end_line->Point2.Y;
2410     }
2411 #if TRACE1
2412   pcb_printf("new point %#mS\n", ex, ey);
2413 #endif
2414   MoveObject (LINEPOINT_TYPE, CURRENT, end_line, &(end_line->Point1),
2415               ex - end_line->Point1.X,
2416               ey - end_line->Point1.Y);
2417
2418   /* Step 4: Split start_line at the obstacle and insert a zero-delta
2419      arc at it.  */
2420
2421   new_arc = create_arc (start_line, fx, fy, fr,
2422                         90-(int)(r2d(start_angle+fa)+0.5) + 90 + 90*se_sign, -se_sign);
2423   new_aextra = ARC2EXTRA (new_arc);
2424
2425   if (start_arc) sarc_extra = ARC2EXTRA (start_arc);
2426   if (end_arc) earc_extra = ARC2EXTRA (end_arc);
2427
2428   MoveObject (LINEPOINT_TYPE, CURRENT, start_line, &(start_line->Point2),
2429               new_aextra->start.x - start_line->Point2.X,
2430               new_aextra->start.y - start_line->Point2.Y);
2431
2432   new_line = create_line (start_line, new_aextra->end.x, new_aextra->end.y, ex, ey);
2433   start_extra = LINE2EXTRA (start_line);
2434   new_lextra = LINE2EXTRA (new_line);
2435   end_extra = LINE2EXTRA (end_line);
2436
2437   new_lextra->start.pin = start_extra->start.pin;
2438   new_lextra->end.pin = start_extra->end.pin;
2439   new_lextra->start.pending = 1;
2440   new_lextra->end.pending = 1;
2441
2442   start_extra->end.next = new_aextra;
2443   new_aextra->start.next = start_extra;
2444   new_aextra->end.next = new_lextra;
2445   new_lextra->start.next = new_aextra;
2446   new_lextra->end.next = end_extra;
2447   end_extra->start.next = new_lextra;
2448
2449   /* Step 5: Recurse.  */
2450
2451   did_something ++;
2452   npulled ++;
2453   status();
2454 #if TRACE0
2455   printf("\033[35mdid_something: recursing\033[0m\n");
2456   {
2457     int i = gui->confirm_dialog("recurse?", 0);
2458     printf("confirm = %d\n", i);
2459     if (i == 0)
2460       return;
2461   }
2462   printf("\n\033[33mRECURSING\033[0m\n\n");
2463   IncrementUndoSerialNumber();
2464 #endif
2465   maybe_pull_1 (new_line);
2466 }
2467
2468 /* Given a line with a end_next, attempt to pull both ends.  */
2469 static void
2470 maybe_pull (LineTypePtr line, Extra *e)
2471 {
2472 #if TRACE0
2473   printf("maybe_pull: ");
2474   print_extra (e, 0);
2475 #endif
2476   if (e->end.next && EXTRA_IS_LINE (e->end.next))
2477     {
2478       maybe_pull_1 (line);
2479     }
2480   else
2481     {
2482       e->end.pending = 0;
2483       if (e->start.next && EXTRA_IS_LINE (e->start.next))
2484         {
2485           reverse_line (line);
2486           maybe_pull_1 (line);
2487         }
2488       else
2489         e->start.pending = 0;
2490     }
2491 }
2492
2493 static void
2494 validate_pair (Extra *e, End *end)
2495 {
2496   if (!end->next)
2497     return;
2498   if (end->next->start.next == e)
2499     return;
2500   if (end->next->end.next == e)
2501     return;
2502   fprintf(stderr, "no backlink!\n");
2503   print_extra (e, 0);
2504   print_extra (end->next, 0);
2505   abort();
2506 }
2507
2508 static void
2509 validate_pair_cb (AnyObjectType *ptr, Extra *extra, void *userdata)
2510 {
2511   validate_pair (extra, &extra->start);
2512   validate_pair (extra, &extra->end);
2513 }
2514
2515 static void
2516 validate_pairs ()
2517 {
2518   g_hash_table_foreach (lines, (GHFunc)validate_pair_cb, NULL);
2519 #if TRACE1
2520   printf("\narcs\n");
2521 #endif
2522   g_hash_table_foreach (arcs, (GHFunc)validate_pair_cb, NULL);
2523 }
2524
2525 static void
2526 FreeExtra (Extra *extra)
2527 {
2528   g_slice_free (Extra, extra);
2529 }
2530
2531 static void
2532 mark_ends_pending (LineType *line, Extra *extra, void *userdata)
2533 {
2534   int *select_flags = userdata;
2535   if (TEST_FLAGS (*select_flags, line))
2536     {
2537       extra->start.pending = 1;
2538       extra->end.pending = 1;
2539     }
2540 }
2541
2542 #if TRACE1
2543 static void
2544 trace_print_extra (AnyObjectType *ptr, Extra *extra, void *userdata)
2545 {
2546     last_pextra = (Extra *)1;
2547     print_extra(extra, 0);
2548 }
2549
2550 static void
2551 trace_print_lines_arcs (void)
2552 {
2553   printf("\nlines\n");
2554   g_hash_table_foreach (lines, (GHFunc)trace_print_extra, NULL);
2555
2556   printf("\narcs\n");
2557   g_hash_table_foreach (arcs, (GHFunc)trace_print_extra, NULL);
2558
2559   printf("\n");
2560 }
2561 #endif
2562
2563 static int
2564 GlobalPuller(int argc, char **argv, Coord x, Coord y)
2565 {
2566   int select_flags = 0;
2567
2568   setbuf(stdout, 0);
2569   nloops = 0;
2570   npulled = 0;
2571   printf("puller! %s\n", argc > 0 ? argv[0] : "");
2572
2573   if (argc > 0 && strcasecmp (argv[0], "selected") == 0)
2574     select_flags = SELECTEDFLAG;
2575   if (argc > 0 && strcasecmp (argv[0], "found") == 0)
2576     select_flags = FOUNDFLAG;
2577
2578   printf("optimizing...\n");
2579   /* This canonicalizes all the lines, and cleans up near-misses.  */
2580   /* hid_actionl ("djopt", "puller", 0); */
2581
2582   current_is_solder = (GetLayerGroupNumberByPointer(CURRENT)
2583                        == GetLayerGroupNumberByNumber (solder_silk_layer));
2584   current_is_component = (GetLayerGroupNumberByPointer(CURRENT)
2585                           == GetLayerGroupNumberByNumber (component_silk_layer));
2586
2587   lines = g_hash_table_new_full (NULL, NULL, NULL, (GDestroyNotify)FreeExtra);
2588   arcs  = g_hash_table_new_full (NULL, NULL, NULL, (GDestroyNotify)FreeExtra);
2589
2590   printf("pairing...\n");
2591   find_pairs ();
2592   validate_pairs ();
2593
2594   g_hash_table_foreach (lines, (GHFunc)mark_ends_pending, &select_flags);
2595
2596 #if TRACE1
2597   trace_print_lines_arcs ();
2598 #endif
2599
2600   propogate_ends ();
2601
2602 #if TRACE1
2603   trace_print_lines_arcs ();
2604   trace_paths ();
2605 #endif
2606
2607   printf("pulling...\n");
2608   if (setjmp(abort_buf) == 0)
2609     {
2610 #if TRACE0
2611       int old_did_something = -1;
2612 #endif
2613       did_something = 1;
2614       while (did_something)
2615         {
2616           nloops ++;
2617           status();
2618           did_something = 0;
2619           LINE_LOOP (CURRENT); {
2620             Extra *e = LINE2EXTRA (line);
2621             if (e->deleted)
2622               continue;
2623 #ifdef CHECK_LINE_PT_NEG
2624             if (line->Point1.X < 0)
2625               abort1();
2626 #endif
2627             if (e->start.next || e->end.next)
2628               maybe_pull (line, e);
2629 #if TRACE0
2630             if (did_something != old_did_something)
2631               {
2632                 IncrementUndoSerialNumber();
2633                 old_did_something = did_something;
2634                 if (gui->confirm_dialog("more?", 0) == 0)
2635                   {
2636                     did_something = 0;
2637                     break;
2638                   }
2639               }
2640 #endif
2641             /*gui->progress(0,0,0);*/
2642           } END_LOOP;
2643         }
2644     }
2645
2646 #if TRACE0
2647   printf("\nlines\n");
2648   g_hash_table_foreach (lines, (GHFunc)trace_print_extra, NULL);
2649   printf("\narcs\n");
2650   g_hash_table_foreach (arcs, (GHFunc)trace_print_extra, NULL);
2651   printf("\n");
2652   printf("\nlines\n");
2653 #endif
2654
2655   LINE_LOOP (CURRENT);
2656     {
2657       if (LINE2EXTRA (line)->deleted)
2658         RemoveLine (CURRENT, line);
2659     }
2660   END_LOOP;
2661
2662   ARC_LOOP (CURRENT);
2663     {
2664       if (ARC2EXTRA (arc)->deleted)
2665         RemoveArc (CURRENT, arc);
2666     }
2667   END_LOOP;
2668
2669   g_hash_table_unref (lines);
2670   g_hash_table_unref (arcs);
2671
2672   IncrementUndoSerialNumber();
2673   return 0;
2674 }
2675
2676 /*****************************************************************************/
2677 /*                                                                           */
2678 /*                             Actions                                       */
2679 /*                                                                           */
2680 /*****************************************************************************/
2681
2682 HID_Action puller_action_list[] = {
2683   {"Puller", "Click on a line-arc intersection or line segment", Puller,
2684    puller_help, puller_syntax},
2685   {"GlobalPuller", 0, GlobalPuller,
2686    globalpuller_help, globalpuller_syntax}
2687 };
2688
2689 REGISTER_ACTIONS (puller_action_list)