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