1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#include "config.h"
15
16#include "render.h"
17#include "pathplan.h"
18#include <setjmp.h>
19
20#ifdef UNUSED
21static box *bs = NULL;
22static int bn;
23static int maxbn = 0;
24#define BINC 300
25#endif
26
27#define PINC 300
28
29#ifdef NOTNOW
30static edge_t *origedge;
31#endif
32
33static int nedges, nboxes; /* total no. of edges and boxes used in routing */
34
35static int routeinit;
36/* static data used across multiple edges */
37static pointf *ps; /* final spline points */
38static int maxpn; /* size of ps[] */
39static Ppoint_t *polypoints; /* vertices of polygon defined by boxes */
40static int polypointn; /* size of polypoints[] */
41static Pedge_t *edges; /* polygon edges passed to Proutespline */
42static int edgen; /* size of edges[] */
43
44static int checkpath(int, boxf*, path*);
45static int mkspacep(int size);
46static void printpath(path * pp);
47#ifdef DEBUG
48static void printboxes(int boxn, boxf* boxes)
49{
50 pointf ll, ur;
51 int bi;
52 char buf[BUFSIZ];
53 int newcnt = Show_cnt + boxn;
54
55 Show_boxes = ALLOC(newcnt+2,Show_boxes,char*);
56 for (bi = 0; bi < boxn; bi++) {
57 ll = boxes[bi].LL, ur = boxes[bi].UR;
58 sprintf(buf, "%d %d %d %d pathbox", (int)ll.x, (int)ll.y, (int)ur.x, (int)ur.y);
59 Show_boxes[bi+1+Show_cnt] = strdup (buf);
60 }
61 Show_cnt = newcnt;
62 Show_boxes[Show_cnt+1] = NULL;
63}
64
65#if DEBUG > 1
66static void psprintpolypts(Ppoint_t * p, int sz)
67{
68 int i;
69
70 fprintf(stderr, "%%!\n");
71 fprintf(stderr, "%% constraint poly\n");
72 fprintf(stderr, "newpath\n");
73 for (i = 0; i < sz; i++)
74 fprintf(stderr, "%f %f %s\n", p[i].x, p[i].y,
75 (i == 0 ? "moveto" : "lineto"));
76 fprintf(stderr, "closepath stroke\n");
77}
78static void psprintpoint(point p)
79{
80 fprintf(stderr, "gsave\n");
81 fprintf(stderr,
82 "newpath %d %d moveto %d %d 2 0 360 arc closepath fill stroke\n",
83 p.x, p.y, p.x, p.y);
84 fprintf(stderr, "/Times-Roman findfont 4 scalefont setfont\n");
85 fprintf(stderr, "%d %d moveto (\\(%d,%d\\)) show\n", p.x + 5, p.y + 5,
86 p.x, p.y);
87 fprintf(stderr, "grestore\n");
88}
89static void psprintpointf(pointf p)
90{
91 fprintf(stderr, "gsave\n");
92 fprintf(stderr,
93 "newpath %.5g %.5g moveto %.5g %.5g 2 0 360 arc closepath fill stroke\n",
94 p.x, p.y, p.x, p.y);
95 fprintf(stderr, "/Times-Roman findfont 4 scalefont setfont\n");
96 fprintf(stderr, "%.5g %.5g moveto (\\(%.5g,%.5g\\)) show\n", p.x + 5, p.y + 5,
97 p.x, p.y);
98 fprintf(stderr, "grestore\n");
99}
100#endif
101
102static void psprintspline(Ppolyline_t spl)
103{
104 char buf[BUFSIZ];
105 int newcnt = Show_cnt + spl.pn + 4;
106 int li, i;
107
108 Show_boxes = ALLOC(newcnt+2,Show_boxes,char*);
109 li = Show_cnt+1;
110 Show_boxes[li++] = strdup ("%%!");
111 Show_boxes[li++] = strdup ("%% spline");
112 Show_boxes[li++] = strdup ("gsave 1 0 0 setrgbcolor newpath");
113 for (i = 0; i < spl.pn; i++) {
114 sprintf(buf, "%f %f %s", spl.ps[i].x, spl.ps[i].y,
115 (i == 0) ? "moveto" : ((i % 3 == 0) ? "curveto" : ""));
116 Show_boxes[li++] = strdup (buf);
117 }
118 Show_boxes[li++] = strdup ("stroke grestore");
119 Show_cnt = newcnt;
120 Show_boxes[Show_cnt+1] = NULL;
121}
122
123static void psprintline(Ppolyline_t pl)
124{
125 char buf[BUFSIZ];
126 int newcnt = Show_cnt + pl.pn + 4;
127 int i, li;
128
129 Show_boxes = ALLOC(newcnt+2,Show_boxes,char*);
130 li = Show_cnt+1;
131 Show_boxes[li++] = strdup ("%%!");
132 Show_boxes[li++] = strdup ("%% line");
133 Show_boxes[li++] = strdup ("gsave 0 0 1 setrgbcolor newpath");
134 for (i = 0; i < pl.pn; i++) {
135 sprintf(buf, "%f %f %s", pl.ps[i].x, pl.ps[i].y,
136 (i == 0 ? "moveto" : "lineto"));
137 Show_boxes[li++] = strdup (buf);
138 }
139 Show_boxes[li++] = strdup ("stroke grestore");
140 Show_cnt = newcnt;
141 Show_boxes[Show_cnt+1] = NULL;
142}
143
144static void psprintpoly(Ppoly_t p)
145{
146 char buf[BUFSIZ];
147 int newcnt = Show_cnt + p.pn + 3;
148 point tl, hd;
149 int bi, li;
150 char* pfx;
151
152 Show_boxes = ALLOC(newcnt+2,Show_boxes,char*);
153 li = Show_cnt+1;
154 Show_boxes[li++] = strdup ("%% poly list");
155 Show_boxes[li++] = strdup ("gsave 0 1 0 setrgbcolor");
156 for (bi = 0; bi < p.pn; bi++) {
157 tl.x = (int)p.ps[bi].x;
158 tl.y = (int)p.ps[bi].y;
159 hd.x = (int)p.ps[(bi+1) % p.pn].x;
160 hd.y = (int)p.ps[(bi+1) % p.pn].y;
161 if ((tl.x == hd.x) && (tl.y == hd.y)) pfx = "%%";
162 else pfx ="";
163 sprintf(buf, "%s%d %d %d %d makevec", pfx, tl.x, tl.y, hd.x, hd.y);
164 Show_boxes[li++] = strdup (buf);
165 }
166 Show_boxes[li++] = strdup ("grestore");
167
168 Show_cnt = newcnt;
169 Show_boxes[Show_cnt+1] = NULL;
170}
171
172static void psprintboxes(int boxn, boxf* boxes)
173{
174 char buf[BUFSIZ];
175 int newcnt = Show_cnt + 5*boxn + 3;
176 pointf ll, ur;
177 int bi, li;
178
179 Show_boxes = ALLOC(newcnt+2,Show_boxes,char*);
180 li = Show_cnt+1;
181 Show_boxes[li++] = strdup ("%% box list");
182 Show_boxes[li++] = strdup ("gsave 0 1 0 setrgbcolor");
183 for (bi = 0; bi < boxn; bi++) {
184 ll = boxes[bi].LL, ur = boxes[bi].UR;
185 sprintf(buf, "newpath\n%d %d moveto", (int)ll.x, (int)ll.y);
186 Show_boxes[li++] = strdup (buf);
187 sprintf(buf, "%d %d lineto", (int)ll.x, (int)ur.y);
188 Show_boxes[li++] = strdup (buf);
189 sprintf(buf, "%d %d lineto", (int)ur.x, (int)ur.y);
190 Show_boxes[li++] = strdup (buf);
191 sprintf(buf, "%d %d lineto", (int)ur.x, (int)ll.y);
192 Show_boxes[li++] = strdup (buf);
193 Show_boxes[li++] = strdup ("closepath stroke");
194 }
195 Show_boxes[li++] = strdup ("grestore");
196
197 Show_cnt = newcnt;
198 Show_boxes[Show_cnt+1] = NULL;
199}
200
201static void psprintinit (int begin)
202{
203 int newcnt = Show_cnt + 1;
204
205 Show_boxes = ALLOC(newcnt+2,Show_boxes,char*);
206 if (begin)
207 Show_boxes[1+Show_cnt] = strdup ("dbgstart");
208 else
209 Show_boxes[1+Show_cnt] = strdup ("grestore");
210 Show_cnt = newcnt;
211 Show_boxes[Show_cnt+1] = NULL;
212}
213
214static int debugleveln(edge_t* realedge, int i)
215{
216 return (GD_showboxes(agraphof(aghead(realedge))) == i ||
217 GD_showboxes(agraphof(agtail(realedge))) == i ||
218 ED_showboxes(realedge) == i ||
219 ND_showboxes(aghead(realedge)) == i ||
220 ND_showboxes(agtail(realedge)) == i);
221}
222#endif /* DEBUG */
223
224
225
226/* simpleSplineRoute:
227 * Given a simple (ccw) polygon, route an edge from tp to hp.
228 */
229pointf*
230simpleSplineRoute (pointf tp, pointf hp, Ppoly_t poly, int* n_spl_pts,
231 int polyline)
232{
233 Ppolyline_t pl, spl;
234 Ppoint_t eps[2];
235 Pvector_t evs[2];
236 int i;
237
238 eps[0].x = tp.x;
239 eps[0].y = tp.y;
240 eps[1].x = hp.x;
241 eps[1].y = hp.y;
242 if (Pshortestpath(&poly, eps, &pl) < 0)
243 return NULL;
244
245 if (polyline)
246 make_polyline (pl, &spl);
247 else {
248 if (poly.pn > edgen) {
249 edges = ALLOC(poly.pn, edges, Pedge_t);
250 edgen = poly.pn;
251 }
252 for (i = 0; i < poly.pn; i++) {
253 edges[i].a = poly.ps[i];
254 edges[i].b = poly.ps[(i + 1) % poly.pn];
255 }
256#if 0
257 if (pp->start.constrained) {
258 evs[0].x = cos(pp->start.theta);
259 evs[0].y = sin(pp->start.theta);
260 } else
261#endif
262 evs[0].x = evs[0].y = 0;
263#if 0
264 if (pp->end.constrained) {
265 evs[1].x = -cos(pp->end.theta);
266 evs[1].y = -sin(pp->end.theta);
267 } else
268#endif
269 evs[1].x = evs[1].y = 0;
270 if (Proutespline(edges, poly.pn, pl, evs, &spl) < 0)
271 return NULL;
272 }
273
274 if (mkspacep(spl.pn))
275 return NULL;
276 for (i = 0; i < spl.pn; i++) {
277 ps[i] = spl.ps[i];
278 }
279 *n_spl_pts = spl.pn;
280 return ps;
281}
282
283/* routesplinesinit:
284 * Data initialized once until matching call to routeplineterm
285 * Allows recursive calls to dot
286 */
287int
288routesplinesinit()
289{
290 if (++routeinit > 1) return 0;
291 if (!(ps = N_GNEW(PINC, pointf))) {
292 agerr(AGERR, "routesplinesinit: cannot allocate ps\n");
293 return 1;
294 }
295 maxpn = PINC;
296#ifdef DEBUG
297 if (Show_boxes) {
298 int i;
299 for (i = 0; Show_boxes[i]; i++)
300 free (Show_boxes[i]);
301 free (Show_boxes);
302 Show_boxes = NULL;
303 Show_cnt = 0;
304 }
305#endif
306 nedges = 0;
307 nboxes = 0;
308 if (Verbose)
309 start_timer();
310 return 0;
311}
312
313void routesplinesterm()
314{
315 if (--routeinit > 0) return;
316 free(ps);
317#ifdef UNUSED
318 free(bs), bs = NULL /*, maxbn = bn = 0 */ ;
319#endif
320 if (Verbose)
321 fprintf(stderr,
322 "routesplines: %d edges, %d boxes %.2f sec\n",
323 nedges, nboxes, elapsed_sec());
324}
325
326static void
327limitBoxes (boxf* boxes, int boxn, pointf *pps, int pn, int delta)
328{
329 int bi, si, splinepi;
330 double t;
331 pointf sp[4];
332 int num_div = delta * boxn;
333
334 for (splinepi = 0; splinepi + 3 < pn; splinepi += 3) {
335 for (si = 0; si <= num_div; si++) {
336 t = si / (double)num_div;
337 sp[0] = pps[splinepi];
338 sp[1] = pps[splinepi + 1];
339 sp[2] = pps[splinepi + 2];
340 sp[3] = pps[splinepi + 3];
341 sp[0].x = sp[0].x + t * (sp[1].x - sp[0].x);
342 sp[0].y = sp[0].y + t * (sp[1].y - sp[0].y);
343 sp[1].x = sp[1].x + t * (sp[2].x - sp[1].x);
344 sp[1].y = sp[1].y + t * (sp[2].y - sp[1].y);
345 sp[2].x = sp[2].x + t * (sp[3].x - sp[2].x);
346 sp[2].y = sp[2].y + t * (sp[3].y - sp[2].y);
347 sp[0].x = sp[0].x + t * (sp[1].x - sp[0].x);
348 sp[0].y = sp[0].y + t * (sp[1].y - sp[0].y);
349 sp[1].x = sp[1].x + t * (sp[2].x - sp[1].x);
350 sp[1].y = sp[1].y + t * (sp[2].y - sp[1].y);
351 sp[0].x = sp[0].x + t * (sp[1].x - sp[0].x);
352 sp[0].y = sp[0].y + t * (sp[1].y - sp[0].y);
353 for (bi = 0; bi < boxn; bi++) {
354/* this tested ok on 64bit machines, but on 32bit we need this FUDGE
355 * or graphs/directed/records.gv fails */
356#define FUDGE .0001
357 if (sp[0].y <= boxes[bi].UR.y+FUDGE && sp[0].y >= boxes[bi].LL.y-FUDGE) {
358 if (boxes[bi].LL.x > sp[0].x)
359 boxes[bi].LL.x = sp[0].x;
360 if (boxes[bi].UR.x < sp[0].x)
361 boxes[bi].UR.x = sp[0].x;
362 }
363 }
364 }
365 }
366}
367
368#define INIT_DELTA 10
369#define LOOP_TRIES 15 /* number of times to try to limiting boxes to regain space, using smaller divisions */
370
371/* routesplines:
372 * Route a path using the path info in pp. This includes start and end points
373 * plus a collection of contiguous boxes contain the terminal points. The boxes
374 * are converted into a containing polygon. A shortest path is constructed within
375 * the polygon from between the terminal points. If polyline is true, this path
376 * is converted to a spline representation. Otherwise, we call the path planner to
377 * convert the polyline into a smooth spline staying within the polygon. In both
378 * cases, the function returns an array of the computed control points. The number
379 * of these points is given in npoints.
380 *
381 * Note that the returned points are stored in a single array, so the points must be
382 * used before another call to this function.
383 *
384 * During cleanup, the function determines the x-extent of the spline in the box, so
385 * the box can be shrunk to the minimum width. The extra space can then be used by other
386 * edges.
387 *
388 * If a catastrophic error, return NULL and npoints is 0.
389 */
390static pointf *_routesplines(path * pp, int *npoints, int polyline)
391{
392 Ppoly_t poly;
393 Ppolyline_t pl, spl;
394 int splinepi;
395 Ppoint_t eps[2];
396 Pvector_t evs[2];
397 int edgei, prev, next;
398 int pi, bi;
399 boxf *boxes;
400 int boxn;
401 edge_t* realedge;
402 int flip;
403 int loopcnt, delta = INIT_DELTA;
404 boolean unbounded;
405
406 *npoints = 0;
407 nedges++;
408 nboxes += pp->nbox;
409
410 for (realedge = (edge_t *) pp->data;
411#ifdef NOTNOW
412 origedge = realedge;
413#endif
414 realedge && ED_edge_type(realedge) != NORMAL;
415 realedge = ED_to_orig(realedge));
416 if (!realedge) {
417 agerr(AGERR, "in routesplines, cannot find NORMAL edge\n");
418 return NULL;
419 }
420
421 boxes = pp->boxes;
422 boxn = pp->nbox;
423
424 if (checkpath(boxn, boxes, pp))
425 return NULL;
426
427#ifdef DEBUG
428 if (debugleveln(realedge, 1))
429 printboxes(boxn, boxes);
430 if (debugleveln(realedge, 3)) {
431 psprintinit(1);
432 psprintboxes(boxn, boxes);
433 }
434#endif
435
436 if (boxn * 8 > polypointn) {
437 polypoints = ALLOC(boxn * 8, polypoints, Ppoint_t);
438 polypointn = boxn * 8;
439 }
440
441 if ((boxn > 1) && (boxes[0].LL.y > boxes[1].LL.y)) {
442 flip = 1;
443 for (bi = 0; bi < boxn; bi++) {
444 double v = boxes[bi].UR.y;
445 boxes[bi].UR.y = -1*boxes[bi].LL.y;
446 boxes[bi].LL.y = -v;
447 }
448 }
449 else flip = 0;
450
451 if (agtail(realedge) != aghead(realedge)) {
452 /* I assume that the path goes either down only or
453 up - right - down */
454 for (bi = 0, pi = 0; bi < boxn; bi++) {
455 next = prev = 0;
456 if (bi > 0)
457 prev = (boxes[bi].LL.y > boxes[bi - 1].LL.y) ? -1 : 1;
458 if (bi < boxn - 1)
459 next = (boxes[bi + 1].LL.y > boxes[bi].LL.y) ? 1 : -1;
460 if (prev != next) {
461 if (next == -1 || prev == 1) {
462 polypoints[pi].x = boxes[bi].LL.x;
463 polypoints[pi++].y = boxes[bi].UR.y;
464 polypoints[pi].x = boxes[bi].LL.x;
465 polypoints[pi++].y = boxes[bi].LL.y;
466 } else {
467 polypoints[pi].x = boxes[bi].UR.x;
468 polypoints[pi++].y = boxes[bi].LL.y;
469 polypoints[pi].x = boxes[bi].UR.x;
470 polypoints[pi++].y = boxes[bi].UR.y;
471 }
472 }
473 else if (prev == 0) { /* single box */
474 polypoints[pi].x = boxes[bi].LL.x;
475 polypoints[pi++].y = boxes[bi].UR.y;
476 polypoints[pi].x = boxes[bi].LL.x;
477 polypoints[pi++].y = boxes[bi].LL.y;
478 }
479 else {
480 if (!(prev == -1 && next == -1)) {
481 agerr(AGERR, "in routesplines, illegal values of prev %d and next %d, line %d\n", prev, next, __LINE__);
482 return NULL;
483 }
484 }
485 }
486 for (bi = boxn - 1; bi >= 0; bi--) {
487 next = prev = 0;
488 if (bi < boxn - 1)
489 prev = (boxes[bi].LL.y > boxes[bi + 1].LL.y) ? -1 : 1;
490 if (bi > 0)
491 next = (boxes[bi - 1].LL.y > boxes[bi].LL.y) ? 1 : -1;
492 if (prev != next) {
493 if (next == -1 || prev == 1 ) {
494 polypoints[pi].x = boxes[bi].LL.x;
495 polypoints[pi++].y = boxes[bi].UR.y;
496 polypoints[pi].x = boxes[bi].LL.x;
497 polypoints[pi++].y = boxes[bi].LL.y;
498 } else {
499 polypoints[pi].x = boxes[bi].UR.x;
500 polypoints[pi++].y = boxes[bi].LL.y;
501 polypoints[pi].x = boxes[bi].UR.x;
502 polypoints[pi++].y = boxes[bi].UR.y;
503 }
504 }
505 else if (prev == 0) { /* single box */
506 polypoints[pi].x = boxes[bi].UR.x;
507 polypoints[pi++].y = boxes[bi].LL.y;
508 polypoints[pi].x = boxes[bi].UR.x;
509 polypoints[pi++].y = boxes[bi].UR.y;
510 }
511 else {
512 if (!(prev == -1 && next == -1)) {
513 /* it went badly, e.g. degenerate box in boxlist */
514 agerr(AGERR, "in routesplines, illegal values of prev %d and next %d, line %d\n", prev, next, __LINE__);
515 return NULL; /* for correctness sake, it's best to just stop */
516 }
517 polypoints[pi].x = boxes[bi].UR.x;
518 polypoints[pi++].y = boxes[bi].LL.y;
519 polypoints[pi].x = boxes[bi].UR.x;
520 polypoints[pi++].y = boxes[bi].UR.y;
521 polypoints[pi].x = boxes[bi].LL.x;
522 polypoints[pi++].y = boxes[bi].UR.y;
523 polypoints[pi].x = boxes[bi].LL.x;
524 polypoints[pi++].y = boxes[bi].LL.y;
525 }
526 }
527 }
528 else {
529 agerr(AGERR, "in routesplines, edge is a loop at %s\n", agnameof(aghead(realedge)));
530 return NULL;
531 }
532
533 if (flip) {
534 int i;
535 for (bi = 0; bi < boxn; bi++) {
536 double v = boxes[bi].UR.y;
537 boxes[bi].UR.y = -1*boxes[bi].LL.y;
538 boxes[bi].LL.y = -v;
539 }
540 for (i = 0; i < pi; i++)
541 polypoints[i].y *= -1;
542 }
543
544 for (bi = 0; bi < boxn; bi++)
545 boxes[bi].LL.x = INT_MAX, boxes[bi].UR.x = INT_MIN;
546 poly.ps = polypoints, poly.pn = pi;
547 eps[0].x = pp->start.p.x, eps[0].y = pp->start.p.y;
548 eps[1].x = pp->end.p.x, eps[1].y = pp->end.p.y;
549 if (Pshortestpath(&poly, eps, &pl) < 0) {
550 agerr(AGERR, "in routesplines, Pshortestpath failed\n");
551 return NULL;
552 }
553#ifdef DEBUG
554 if (debugleveln(realedge, 3)) {
555 psprintpoly(poly);
556 psprintline(pl);
557 }
558#endif
559
560 if (polyline) {
561 make_polyline (pl, &spl);
562 }
563 else {
564 if (poly.pn > edgen) {
565 edges = ALLOC(poly.pn, edges, Pedge_t);
566 edgen = poly.pn;
567 }
568 for (edgei = 0; edgei < poly.pn; edgei++) {
569 edges[edgei].a = polypoints[edgei];
570 edges[edgei].b = polypoints[(edgei + 1) % poly.pn];
571 }
572 if (pp->start.constrained) {
573 evs[0].x = cos(pp->start.theta);
574 evs[0].y = sin(pp->start.theta);
575 } else
576 evs[0].x = evs[0].y = 0;
577 if (pp->end.constrained) {
578 evs[1].x = -cos(pp->end.theta);
579 evs[1].y = -sin(pp->end.theta);
580 } else
581 evs[1].x = evs[1].y = 0;
582
583 if (Proutespline(edges, poly.pn, pl, evs, &spl) < 0) {
584 agerr(AGERR, "in routesplines, Proutespline failed\n");
585 return NULL;
586 }
587#ifdef DEBUG
588 if (debugleveln(realedge, 3)) {
589 psprintspline(spl);
590 psprintinit(0);
591 }
592#endif
593 }
594 if (mkspacep(spl.pn))
595 return NULL; /* Bailout if no memory left */
596
597 for (bi = 0; bi < boxn; bi++) {
598 boxes[bi].LL.x = INT_MAX;
599 boxes[bi].UR.x = INT_MIN;
600 }
601 unbounded = TRUE;
602 for (splinepi = 0; splinepi < spl.pn; splinepi++) {
603 ps[splinepi] = spl.ps[splinepi];
604 }
605
606 for (loopcnt = 0; unbounded && (loopcnt < LOOP_TRIES); loopcnt++) {
607 limitBoxes (boxes, boxn, ps, spl.pn, delta);
608
609 /* The following check is necessary because if a box is not very
610 * high, it is possible that the sampling above might miss it.
611 * Therefore, we make the sample finer until all boxes have
612 * valid values. cf. bug 456. Would making sp[] pointfs help?
613 */
614 for (bi = 0; bi < boxn; bi++) {
615 /* these fp equality tests are used only to detect if the
616 * values have been changed since initialization - ok */
617 if ((boxes[bi].LL.x == INT_MAX) || (boxes[bi].UR.x == INT_MIN)) {
618 delta *= 2; /* try again with a finer interval */
619 if (delta > INT_MAX/boxn) /* in limitBoxes, boxn*delta must fit in an int, so give up */
620 loopcnt = LOOP_TRIES;
621 break;
622 }
623 }
624 if (bi == boxn)
625 unbounded = FALSE;
626 }
627 if (unbounded) {
628 /* Either an extremely short, even degenerate, box, or some failure with the path
629 * planner causing the spline to miss some boxes. In any case, use the shortest path
630 * to bound the boxes. This will probably mean a bad edge, but we avoid an infinite
631 * loop and we can see the bad edge, and even use the showboxes scaffolding.
632 */
633 Ppolyline_t polyspl;
634 agerr(AGWARN, "Unable to reclaim box space in spline routing for edge \"%s\" -> \"%s\". Something is probably seriously wrong.\n", agnameof(agtail(realedge)), agnameof(aghead(realedge)));
635 make_polyline (pl, &polyspl);
636 limitBoxes (boxes, boxn, polyspl.ps, polyspl.pn, INIT_DELTA);
637 }
638
639 *npoints = spl.pn;
640
641#ifdef DEBUG
642 if (GD_showboxes(agraphof(aghead(realedge))) == 2 ||
643 GD_showboxes(agraphof(agtail(realedge))) == 2 ||
644 ED_showboxes(realedge) == 2 ||
645 ND_showboxes(aghead(realedge)) == 2 ||
646 ND_showboxes(agtail(realedge)) == 2)
647 printboxes(boxn, boxes);
648#endif
649
650 return ps;
651}
652
653pointf *routesplines(path * pp, int *npoints)
654{
655 return _routesplines (pp, npoints, 0);
656}
657
658pointf *routepolylines(path * pp, int *npoints)
659{
660 return _routesplines (pp, npoints, 1);
661}
662
663static int overlap(int i0, int i1, int j0, int j1)
664{
665 /* i'll bet there's an elegant way to do this */
666 if (i1 <= j0)
667 return 0;
668 if (i0 >= j1)
669 return 0;
670 if ((j0 <= i0) && (i0 <= j1))
671 return (j1 - i0);
672 if ((j0 <= i1) && (i1 <= j1))
673 return (i1 - j0);
674 return MIN(i1 - i0, j1 - j0);
675}
676
677
678/*
679 * repairs minor errors in the boxpath, such as boxes not joining
680 * or slightly intersecting. it's sort of the equivalent of the
681 * audit process in the 5E control program - if you've given up on
682 * fixing all the bugs, at least try to engineer around them!
683 * in postmodern CS, we could call this "self-healing code."
684 *
685 * Return 1 on failure; 0 on success.
686 */
687static int checkpath(int boxn, boxf* boxes, path* thepath)
688{
689 boxf *ba, *bb;
690 int bi, i, errs, l, r, d, u;
691 int xoverlap, yoverlap;
692
693#ifndef DONTFIXPATH
694 /* remove degenerate boxes. */
695 i = 0;
696 for (bi = 0; bi < boxn; bi++) {
697 if (ABS(boxes[bi].LL.y - boxes[bi].UR.y) < .01)
698 continue;
699 if (ABS(boxes[bi].LL.x - boxes[bi].UR.x) < .01)
700 continue;
701 if (i != bi)
702 boxes[i] = boxes[bi];
703 i++;
704 }
705 boxn = i;
706#endif /* DONTFIXPATH */
707
708 ba = &boxes[0];
709 if (ba->LL.x > ba->UR.x || ba->LL.y > ba->UR.y) {
710 agerr(AGERR, "in checkpath, box 0 has LL coord > UR coord\n");
711 printpath(thepath);
712 return 1;
713 }
714 for (bi = 0; bi < boxn - 1; bi++) {
715 ba = &boxes[bi], bb = &boxes[bi + 1];
716 if (bb->LL.x > bb->UR.x || bb->LL.y > bb->UR.y) {
717 agerr(AGERR, "in checkpath, box %d has LL coord > UR coord\n",
718 bi + 1);
719 printpath(thepath);
720 return 1;
721 }
722 l = (ba->UR.x < bb->LL.x) ? 1 : 0;
723 r = (ba->LL.x > bb->UR.x) ? 1 : 0;
724 d = (ba->UR.y < bb->LL.y) ? 1 : 0;
725 u = (ba->LL.y > bb->UR.y) ? 1 : 0;
726 errs = l + r + d + u;
727 if (errs > 0 && Verbose) {
728 fprintf(stderr, "in checkpath, boxes %d and %d don't touch\n",
729 bi, bi + 1);
730 printpath(thepath);
731 }
732#ifndef DONTFIXPATH
733 if (errs > 0) {
734 int xy;
735
736 if (l == 1)
737 xy = ba->UR.x, ba->UR.x = bb->LL.x, bb->LL.x = xy, l = 0;
738 else if (r == 1)
739 xy = ba->LL.x, ba->LL.x = bb->UR.x, bb->UR.x = xy, r = 0;
740 else if (d == 1)
741 xy = ba->UR.y, ba->UR.y = bb->LL.y, bb->LL.y = xy, d = 0;
742 else if (u == 1)
743 xy = ba->LL.y, ba->LL.y = bb->UR.y, bb->UR.y = xy, u = 0;
744 for (i = 0; i < errs - 1; i++) {
745 if (l == 1)
746 xy = (ba->UR.x + bb->LL.x) / 2.0 + 0.5, ba->UR.x =
747 bb->LL.x = xy, l = 0;
748 else if (r == 1)
749 xy = (ba->LL.x + bb->UR.x) / 2.0 + 0.5, ba->LL.x =
750 bb->UR.x = xy, r = 0;
751 else if (d == 1)
752 xy = (ba->UR.y + bb->LL.y) / 2.0 + 0.5, ba->UR.y =
753 bb->LL.y = xy, d = 0;
754 else if (u == 1)
755 xy = (ba->LL.y + bb->UR.y) / 2.0 + 0.5, ba->LL.y =
756 bb->UR.y = xy, u = 0;
757 }
758 }
759#else
760 abort();
761#endif
762#ifndef DONTFIXPATH
763 /* check for overlapping boxes */
764 xoverlap = overlap(ba->LL.x, ba->UR.x, bb->LL.x, bb->UR.x);
765 yoverlap = overlap(ba->LL.y, ba->UR.y, bb->LL.y, bb->UR.y);
766 if (xoverlap && yoverlap) {
767 if (xoverlap < yoverlap) {
768 if (ba->UR.x - ba->LL.x > bb->UR.x - bb->LL.x) {
769 /* take space from ba */
770 if (ba->UR.x < bb->UR.x)
771 ba->UR.x = bb->LL.x;
772 else
773 ba->LL.x = bb->UR.x;
774 } else {
775 /* take space from bb */
776 if (ba->UR.x < bb->UR.x)
777 bb->LL.x = ba->UR.x;
778 else
779 bb->UR.x = ba->LL.x;
780 }
781 } else { /* symmetric for y coords */
782 if (ba->UR.y - ba->LL.y > bb->UR.y - bb->LL.y) {
783 /* take space from ba */
784 if (ba->UR.y < bb->UR.y)
785 ba->UR.y = bb->LL.y;
786 else
787 ba->LL.y = bb->UR.y;
788 } else {
789 /* take space from bb */
790 if (ba->UR.y < bb->UR.y)
791 bb->LL.y = ba->UR.y;
792 else
793 bb->UR.y = ba->LL.y;
794 }
795 }
796 }
797 }
798#endif /* DONTFIXPATH */
799
800 if (thepath->start.p.x < boxes[0].LL.x
801 || thepath->start.p.x > boxes[0].UR.x
802 || thepath->start.p.y < boxes[0].LL.y
803 || thepath->start.p.y > boxes[0].UR.y) {
804 if (Verbose) {
805 fprintf(stderr, "in checkpath, start port not in first box\n");
806 printpath(thepath);
807 }
808#ifndef DONTFIXPATH
809 if (thepath->start.p.x < boxes[0].LL.x)
810 thepath->start.p.x = boxes[0].LL.x;
811 if (thepath->start.p.x > boxes[0].UR.x)
812 thepath->start.p.x = boxes[0].UR.x;
813 if (thepath->start.p.y < boxes[0].LL.y)
814 thepath->start.p.y = boxes[0].LL.y;
815 if (thepath->start.p.y > boxes[0].UR.y)
816 thepath->start.p.y = boxes[0].UR.y;
817#else
818 abort();
819#endif
820 }
821 if (thepath->end.p.x < boxes[boxn - 1].LL.x
822 || thepath->end.p.x > boxes[boxn - 1].UR.x
823 || thepath->end.p.y < boxes[boxn - 1].LL.y
824 || thepath->end.p.y > boxes[boxn - 1].UR.y) {
825 if (Verbose) {
826 fprintf(stderr, "in checkpath, end port not in last box\n");
827 printpath(thepath);
828 }
829#ifndef DONTFIXPATH
830 if (thepath->end.p.x < boxes[boxn - 1].LL.x)
831 thepath->end.p.x = boxes[boxn - 1].LL.x;
832 if (thepath->end.p.x > boxes[boxn - 1].UR.x)
833 thepath->end.p.x = boxes[boxn - 1].UR.x;
834 if (thepath->end.p.y < boxes[boxn - 1].LL.y)
835 thepath->end.p.y = boxes[boxn - 1].LL.y;
836 if (thepath->end.p.y > boxes[boxn - 1].UR.y)
837 thepath->end.p.y = boxes[boxn - 1].UR.y;
838#else
839 abort();
840#endif
841 }
842 return 0;
843}
844
845static int mkspacep(int size)
846{
847 if (size > maxpn) {
848 int newmax = maxpn + (size / PINC + 1) * PINC;
849 ps = RALLOC(newmax, ps, pointf);
850 if (!ps) {
851 agerr(AGERR, "cannot re-allocate ps\n");
852 return 1;
853 }
854 maxpn = newmax;
855 }
856 return 0;
857}
858
859static void printpath(path * pp)
860{
861 int bi;
862
863#ifdef NOTNOW
864 fprintf(stderr, "edge %d from %s to %s\n", nedges,
865 realedge->tail->name, realedge->head->name);
866 if (ED_count(origedge) > 1)
867 fprintf(stderr, " (it's part of a concentrator edge)\n");
868#endif
869 fprintf(stderr, "%d boxes:\n", pp->nbox);
870 for (bi = 0; bi < pp->nbox; bi++)
871 fprintf(stderr, "%d (%.5g, %.5g), (%.5g, %.5g)\n", bi,
872 pp->boxes[bi].LL.x, pp->boxes[bi].LL.y,
873 pp->boxes[bi].UR.x, pp->boxes[bi].UR.y);
874 fprintf(stderr, "start port: (%.5g, %.5g), tangent angle: %.5g, %s\n",
875 pp->start.p.x, pp->start.p.y, pp->start.theta,
876 pp->start.constrained ? "constrained" : "not constrained");
877 fprintf(stderr, "end port: (%.5g, %.5g), tangent angle: %.5g, %s\n",
878 pp->end.p.x, pp->end.p.y, pp->end.theta,
879 pp->end.constrained ? "constrained" : "not constrained");
880}
881
882static pointf get_centroid(Agraph_t *g)
883{
884 int cnt = 0;
885 static pointf sum = {0.0, 0.0};
886 static Agraph_t *save;
887 Agnode_t *n;
888
889 sum.x = (GD_bb(g).LL.x + GD_bb(g).UR.x) / 2.0;
890 sum.y = (GD_bb(g).LL.y + GD_bb(g).UR.y) / 2.0;
891 return sum;
892
893 if (save == g) return sum;
894 save = g;
895 for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
896 sum.x += ND_pos(n)[0];
897 sum.y += ND_pos(n)[1];
898 cnt++;
899 }
900 sum.x = sum.x / cnt;
901 sum.y = sum.y / cnt;
902 return sum;
903}
904
905#define __CYCLE_CENTROID
906#ifdef __CYCLE_CENTROID
907//generic vector structure
908typedef struct _tag_vec
909{
910 void** _mem;
911 size_t _elems;
912 size_t _capelems;
913} vec;
914
915static vec* vec_new()
916{
917 vec* pvec = (vec*)malloc(sizeof(vec));
918 pvec->_capelems = 10;
919 pvec->_elems = 0;
920 pvec->_mem = (void**)malloc(pvec->_capelems * sizeof(void*));
921 return pvec;
922}
923
924static void vec_delete(vec* pvec)
925{
926 free(pvec->_mem);
927 free(pvec);
928}
929
930static void vec_push_back(vec* pvec, void* data)
931{
932 if (pvec->_elems == pvec->_capelems) {
933 pvec->_capelems += 10;
934 pvec->_mem = (void**)realloc(pvec->_mem, pvec->_capelems * sizeof(void*));
935 }
936 pvec->_mem[pvec->_elems++] = data;
937}
938
939static size_t vec_length(vec* pvec)
940{
941 return pvec->_elems;
942}
943
944static void* vec_get(vec* pvec, size_t index)
945{
946 assert(index < pvec->_elems);
947 return pvec->_mem[index];
948}
949
950static void* vec_pop(vec* pvec)
951{
952 if (pvec->_elems > 0)
953 return pvec->_mem[--pvec->_elems];
954 return NULL;
955}
956
957static boolean vec_contains(vec* pvec, void* item)
958{
959 size_t i;
960
961 for (i=0; i < pvec->_elems; ++i) {
962 if (pvec->_mem[i] == item)
963 return TRUE;
964 }
965
966 return FALSE;
967}
968
969static vec* vec_copy(vec* pvec)
970{
971 vec* nvec = (vec*)malloc(sizeof(vec));
972 nvec->_capelems = pvec->_capelems;
973 nvec->_elems = pvec->_elems;
974 nvec->_mem = (void**)malloc(pvec->_capelems * sizeof(void*));
975 memcpy(nvec->_mem, pvec->_mem, pvec->_elems * sizeof(void*));
976 return nvec;
977}
978//end generic vector structure
979
980static boolean cycle_contains_edge(vec* cycle, edge_t* edge)
981{
982 node_t* start = agtail(edge);
983 node_t* end = aghead(edge);
984 node_t* c_start;
985 node_t* c_end;
986
987 size_t cycle_len = vec_length(cycle);
988 size_t i;
989
990 for (i=0; i < cycle_len; ++i) {
991 if (i == 0) {
992 c_start = (node_t*)vec_get(cycle, cycle_len-1);
993 } else {
994 c_start = (node_t*)vec_get(cycle, i-1);
995 }
996
997 c_end = (node_t*)vec_get(cycle, i);
998
999 if (c_start == start && c_end == end)
1000 return TRUE;
1001 }
1002
1003
1004 return FALSE;
1005}
1006
1007static boolean is_cycle_unique(vec* cycles, vec* cycle)
1008{
1009 size_t cycle_len = vec_length(cycle);
1010 size_t n_cycles = vec_length(cycles);
1011 size_t c; //cycles counter
1012 size_t i; //node counter
1013
1014 vec* cur_cycle;
1015 size_t cur_cycle_len;
1016 void* cur_cycle_item;
1017 boolean all_items_match;
1018
1019 for (c=0; c < n_cycles; ++c) {
1020 cur_cycle = (vec*)vec_get(cycles, c);
1021 cur_cycle_len = vec_length(cur_cycle);
1022
1023 //if all the items match in equal length cycles then we're not unique
1024 if (cur_cycle_len == cycle_len) {
1025 all_items_match = TRUE;
1026 for (i=0; i < cur_cycle_len; ++i) {
1027 cur_cycle_item = vec_get(cur_cycle, i);
1028 if (!vec_contains(cycle, cur_cycle_item)) {
1029 all_items_match = FALSE;
1030 break;
1031 }
1032 }
1033 if (all_items_match)
1034 return FALSE;
1035 }
1036 }
1037
1038 return TRUE;
1039}
1040
1041static void dfs(graph_t *g, node_t* search, vec* visited, node_t* end, vec* cycles)
1042{
1043 edge_t* e;
1044 node_t* n;
1045
1046 if (vec_contains(visited, search)) {
1047 if (search == end) {
1048 if (is_cycle_unique(cycles, visited)) {
1049 vec* cycle = vec_copy(visited);
1050 vec_push_back(cycles, cycle);
1051 }
1052 }
1053 } else {
1054 vec_push_back(visited, search);
1055 for (e = agfstout(g, search); e; e = agnxtout(g, e)) {
1056 n = aghead(e);
1057 dfs(g, n, visited, end, cycles);
1058 }
1059 vec_pop(visited);
1060 }
1061}
1062
1063static vec* find_all_cycles(graph_t *g)
1064{
1065 node_t *n;
1066
1067 vec* alloced_cycles = vec_new(); //vector of vectors of nodes -- AKA cycles to delete
1068 vec* cycles = vec_new(); //vector of vectors of nodes AKA a vector of cycles
1069 vec* cycle;
1070
1071 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1072 cycle = vec_new();
1073 vec_push_back(alloced_cycles, cycle); //keep track of all items we allocate to clean up at the end of this function
1074
1075 dfs(g, n, cycle, n, cycles);
1076 }
1077
1078 vec_delete(alloced_cycles); //cycles contains copied vecs
1079 return cycles;
1080}
1081
1082static vec* find_shortest_cycle_with_edge(vec* cycles, edge_t* edge, size_t min_size)
1083{
1084 size_t c; //cycle counter
1085 size_t cycles_len = vec_length(cycles);
1086 vec* cycle;
1087 size_t cycle_len;
1088 vec* shortest = 0;
1089
1090 for (c=0; c < cycles_len; ++c) {
1091 cycle = (vec*)vec_get(cycles, c);
1092 cycle_len = vec_length(cycle);
1093
1094 if (cycle_len < min_size)
1095 continue;
1096
1097 if (!shortest || vec_length(shortest) > cycle_len) {
1098 if (cycle_contains_edge(cycle, edge)) {
1099 shortest = cycle;
1100 }
1101 }
1102 }
1103 return shortest;
1104}
1105
1106static pointf get_cycle_centroid(graph_t *g, edge_t* edge)
1107{
1108 static vec* cycles = 0;
1109 static graph_t* ref_g = 0;
1110
1111 if (cycles == 0 || ref_g != g) {
1112 //free the memory we're using to hold the previous cycles
1113 if (cycles != 0) {
1114 size_t i;
1115 for (i=0; i < vec_length(cycles); ++i) {
1116 vec_delete(vec_get(cycles, i));
1117 }
1118 vec_delete(cycles);
1119 }
1120 cycles = find_all_cycles(g);
1121 ref_g = g;
1122 }
1123
1124 //find the center of the shortest cycle containing this edge
1125 //cycles of length 2 do their own thing, we want 3 or
1126 vec* cycle = find_shortest_cycle_with_edge(cycles, edge, 3);
1127 size_t cycle_len;
1128 size_t cnt = 0;
1129 pointf sum = {0.0, 0.0};
1130 size_t idx; //edge index
1131 node_t *n;
1132
1133 if (!cycle)
1134 return get_centroid(g);
1135
1136 cycle_len = vec_length(cycle);
1137
1138 for (idx=0; idx < cycle_len; ++idx) {
1139 n = (node_t*)vec_get(cycle, idx);
1140 sum.x += ND_coord(n).x;
1141 sum.y += ND_coord(n).y;
1142 cnt++;
1143 }
1144
1145 sum.x = sum.x / cnt;
1146 sum.y = sum.y / cnt;
1147 return sum;
1148}
1149#endif
1150
1151static void bend(pointf spl[4], pointf centroid)
1152{
1153 pointf midpt,a;
1154 double r;
1155 double dist,dx,dy;
1156
1157 midpt.x = (spl[0].x + spl[3].x)/2.0;
1158 midpt.y = (spl[0].y + spl[3].y)/2.0;
1159 dx = (spl[3].x - spl[0].x);
1160 dy = (spl[3].y - spl[0].y);
1161 dist = sqrt(dx*dx + dy*dy);
1162 r = dist/5.0;
1163 {
1164 double vX = centroid.x - midpt.x;
1165 double vY = centroid.y - midpt.y;
1166 double magV = sqrt(vX*vX + vY*vY);
1167 if (magV == 0) return; /* if midpoint == centroid, don't divide by zero */
1168 a.x = midpt.x - vX / magV * r; /* + would be closest point */
1169 a.y = midpt.y - vY / magV * r;
1170 }
1171 /* this can be improved */
1172 spl[1].x = spl[2].x = a.x;
1173 spl[1].y = spl[2].y = a.y;
1174}
1175
1176/* makeStraightEdge:
1177 *
1178 * FIX: handle ports on boundary?
1179 */
1180#define MAX_EDGE 20
1181void
1182makeStraightEdge(graph_t * g, edge_t * e, int et, splineInfo* sinfo)
1183{
1184 edge_t *e0;
1185 edge_t** edges;
1186 edge_t* elist[MAX_EDGE];
1187 int i, e_cnt;
1188
1189 e_cnt = 1;
1190 e0 = e;
1191 while ((e0 != ED_to_virt(e0)) && (e0 = ED_to_virt(e0))) e_cnt++;
1192
1193 if (e_cnt <= MAX_EDGE)
1194 edges = elist;
1195 else
1196 edges = N_NEW(e_cnt,edge_t*);
1197 e0 = e;
1198 for (i = 0; i < e_cnt; i++) {
1199 edges[i] = e0;
1200 e0 = ED_to_virt(e0);
1201 }
1202 makeStraightEdges (g, edges, e_cnt, et, sinfo);
1203 if (e_cnt > MAX_EDGE) free (edges);
1204
1205}
1206
1207void
1208makeStraightEdges(graph_t * g, edge_t** edges, int e_cnt, int et, splineInfo* sinfo)
1209{
1210 pointf dumb[4];
1211 node_t *n;
1212 node_t *head;
1213 int curved = (et == ET_CURVED);
1214 pointf perp;
1215 pointf del;
1216 edge_t *e0;
1217 edge_t *e;
1218 int i, j, xstep, dx;
1219 double l_perp;
1220 pointf dumber[4];
1221 pointf p, q;
1222
1223 e = edges[0];
1224 n = agtail(e);
1225 head = aghead(e);
1226 p = dumb[1] = dumb[0] = add_pointf(ND_coord(n), ED_tail_port(e).p);
1227 q = dumb[2] = dumb[3] = add_pointf(ND_coord(head), ED_head_port(e).p);
1228 if ((e_cnt == 1) || Concentrate) {
1229#ifndef __CYCLE_CENTROID
1230 if (curved) bend(dumb,get_centroid(g));
1231#else
1232 if (curved) bend(dumb,get_cycle_centroid(g, edges[0]));
1233#endif
1234 clip_and_install(e, aghead(e), dumb, 4, sinfo);
1235 addEdgeLabels(g, e, p, q);
1236 return;
1237 }
1238
1239 e0 = e;
1240 if (APPROXEQPT(dumb[0], dumb[3], MILLIPOINT)) {
1241 /* degenerate case */
1242 dumb[1] = dumb[0];
1243 dumb[2] = dumb[3];
1244 del.x = 0;
1245 del.y = 0;
1246 }
1247 else {
1248 perp.x = dumb[0].y - dumb[3].y;
1249 perp.y = dumb[3].x - dumb[0].x;
1250 l_perp = LEN(perp.x, perp.y);
1251 xstep = GD_nodesep(g->root);
1252 dx = xstep * (e_cnt - 1) / 2;
1253 dumb[1].x = dumb[0].x + (dx * perp.x) / l_perp;
1254 dumb[1].y = dumb[0].y + (dx * perp.y) / l_perp;
1255 dumb[2].x = dumb[3].x + (dx * perp.x) / l_perp;
1256 dumb[2].y = dumb[3].y + (dx * perp.y) / l_perp;
1257 del.x = -xstep * perp.x / l_perp;
1258 del.y = -xstep * perp.y / l_perp;
1259 }
1260
1261 for (i = 0; i < e_cnt; i++) {
1262 e0 = edges[i];
1263 if (aghead(e0) == head) {
1264 p = dumb[0];
1265 q = dumb[3];
1266 for (j = 0; j < 4; j++) {
1267 dumber[j] = dumb[j];
1268 }
1269 } else {
1270 p = dumb[3];
1271 q = dumb[0];
1272 for (j = 0; j < 4; j++) {
1273 dumber[3 - j] = dumb[j];
1274 }
1275 }
1276 if (et == ET_PLINE) {
1277 Ppoint_t pts[4];
1278 Ppolyline_t spl, line;
1279
1280 line.pn = 4;
1281 line.ps = pts;
1282 for (j=0; j < 4; j++) {
1283 pts[j] = dumber[j];
1284 }
1285 make_polyline (line, &spl);
1286 clip_and_install(e0, aghead(e0), spl.ps, spl.pn, sinfo);
1287 }
1288 else
1289 clip_and_install(e0, aghead(e0), dumber, 4, sinfo);
1290
1291 addEdgeLabels(g, e0, p, q);
1292 dumb[1].x += del.x;
1293 dumb[1].y += del.y;
1294 dumb[2].x += del.x;
1295 dumb[2].y += del.y;
1296 }
1297}
1298