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