Graphviz 13.1.2~dev.20250807.2324
Loading...
Searching...
No Matches
routespl.c
Go to the documentation of this file.
1
3/*************************************************************************
4 * Copyright (c) 2011 AT&T Intellectual Property
5 * All rights reserved. This program and the accompanying materials
6 * are made available under the terms of the Eclipse Public License v1.0
7 * which accompanies this distribution, and is available at
8 * https://www.eclipse.org/legal/epl-v10.html
9 *
10 * Contributors: Details at https://graphviz.org
11 *************************************************************************/
12
13#include "config.h"
14#include <assert.h>
15#include <common/geomprocs.h>
16#include <common/render.h>
17#include <float.h>
18#include <limits.h>
19#include <math.h>
20#include <pathplan/pathplan.h>
21#include <stdbool.h>
22#include <stdint.h>
23#include <stdlib.h>
24#include <string.h>
25#include <util/agxbuf.h>
26#include <util/alloc.h>
27#include <util/debug.h>
28#include <util/gv_math.h>
29#include <util/list.h>
30#include <util/prisize_t.h>
31
32static int nedges;
33static size_t nboxes;
34
35static int routeinit;
36
37static int checkpath(size_t, boxf *, path *);
38static void printpath(path * pp);
39#ifdef DEBUG
40static void printboxes(size_t boxn, boxf *boxes) {
41 pointf ll, ur;
42
43 for (size_t bi = 0; bi < boxn; bi++) {
44 ll = boxes[bi].LL, ur = boxes[bi].UR;
45 agxbuf buf = {0};
46 agxbprint(&buf, "%.0f %.0f %.0f %.0f pathbox", ll.x, ll.y, ur.x, ur.y);
47 show_boxes_append(&Show_boxes, agxbdisown(&buf));
48 }
49}
50
51#if DEBUG > 1
52static void psprintpolypts(Ppoint_t * p, int sz)
53{
54 int i;
55
56 fprintf(stderr, "%%!\n");
57 fprintf(stderr, "%% constraint poly\n");
58 fprintf(stderr, "newpath\n");
59 for (i = 0; i < sz; i++)
60 fprintf(stderr, "%f %f %s\n", p[i].x, p[i].y, i == 0 ? "moveto" : "lineto");
61 fprintf(stderr, "closepath stroke\n");
62}
63static void psprintpoint(point p)
64{
65 fprintf(stderr, "gsave\n");
66 fprintf(stderr,
67 "newpath %d %d moveto %d %d 2 0 360 arc closepath fill stroke\n",
68 p.x, p.y, p.x, p.y);
69 fprintf(stderr, "/Times-Roman findfont 4 scalefont setfont\n");
70 fprintf(stderr, "%d %d moveto (\\(%d,%d\\)) show\n", p.x + 5, p.y + 5,
71 p.x, p.y);
72 fprintf(stderr, "grestore\n");
73}
74static void psprintpointf(pointf p)
75{
76 fprintf(stderr, "gsave\n");
77 fprintf(stderr,
78 "newpath %.5g %.5g moveto %.5g %.5g 2 0 360 arc closepath fill stroke\n",
79 p.x, p.y, p.x, p.y);
80 fprintf(stderr, "/Times-Roman findfont 4 scalefont setfont\n");
81 fprintf(stderr, "%.5g %.5g moveto (\\(%.5g,%.5g\\)) show\n", p.x + 5, p.y + 5,
82 p.x, p.y);
83 fprintf(stderr, "grestore\n");
84}
85#endif
86
87static void psprintspline(Ppolyline_t spl)
88{
89 show_boxes_append(&Show_boxes, gv_strdup("%%!"));
90 show_boxes_append(&Show_boxes, gv_strdup("%% spline"));
91 show_boxes_append(&Show_boxes, gv_strdup("gsave 1 0 0 setrgbcolor newpath"));
92 for (size_t i = 0; i < spl.pn; i++) {
93 agxbuf buf = {0};
94 agxbprint(&buf, "%f %f %s", spl.ps[i].x, spl.ps[i].y,
95 i == 0 ? "moveto" : (i % 3 == 0 ? "curveto" : ""));
96 show_boxes_append(&Show_boxes, agxbdisown(&buf));
97 }
98 show_boxes_append(&Show_boxes, gv_strdup("stroke grestore"));
99}
100
101static void psprintline(Ppolyline_t pl)
102{
103 show_boxes_append(&Show_boxes, gv_strdup("%%!"));
104 show_boxes_append(&Show_boxes, gv_strdup("%% line"));
105 show_boxes_append(&Show_boxes, gv_strdup("gsave 0 0 1 setrgbcolor newpath"));
106 for (size_t i = 0; i < pl.pn; i++) {
107 agxbuf buf = {0};
108 agxbprint(&buf, "%f %f %s", pl.ps[i].x, pl.ps[i].y,
109 i == 0 ? "moveto" : "lineto");
110 show_boxes_append(&Show_boxes, agxbdisown(&buf));
111 }
112 show_boxes_append(&Show_boxes, gv_strdup("stroke grestore"));
113}
114
115static void psprintpoly(Ppoly_t p)
116{
117 char* pfx;
118
119 show_boxes_append(&Show_boxes, gv_strdup("%% poly list"));
120 show_boxes_append(&Show_boxes, gv_strdup("gsave 0 1 0 setrgbcolor"));
121 for (size_t bi = 0; bi < p.pn; bi++) {
122 const pointf tail = p.ps[bi];
123 const pointf head = p.ps[(bi + 1) % p.pn];
124 if (fabs(tail.x - head.x) < 1 && fabs(tail.y - head.y) < 1) pfx = "%%";
125 else pfx ="";
126 agxbuf buf = {0};
127 agxbprint(&buf, "%s%.0f %.0f %.0f %.0f makevec", pfx, tail.x, tail.y, head.x,
128 head.y);
129 show_boxes_append(&Show_boxes, agxbdisown(&buf));
130 }
131 show_boxes_append(&Show_boxes, gv_strdup("grestore"));
132}
133
134static void psprintboxes(size_t boxn, boxf *boxes) {
135 pointf ll, ur;
136
137 show_boxes_append(&Show_boxes, gv_strdup("%% box list"));
138 show_boxes_append(&Show_boxes, gv_strdup("gsave 0 1 0 setrgbcolor"));
139 for (size_t bi = 0; bi < boxn; bi++) {
140 ll = boxes[bi].LL, ur = boxes[bi].UR;
141 agxbuf buf = {0};
142 agxbprint(&buf, "newpath\n%.0f %.0f moveto", ll.x, ll.y);
143 show_boxes_append(&Show_boxes, agxbdisown(&buf));
144 agxbprint(&buf, "%.0f %.0f lineto", ll.x, ur.y);
145 show_boxes_append(&Show_boxes, agxbdisown(&buf));
146 agxbprint(&buf, "%.0f %.0f lineto", ur.x, ur.y);
147 show_boxes_append(&Show_boxes, agxbdisown(&buf));
148 agxbprint(&buf, "%.0f %.0f lineto", ur.x, ll.y);
149 show_boxes_append(&Show_boxes, agxbdisown(&buf));
150 show_boxes_append(&Show_boxes, gv_strdup("closepath stroke"));
151 }
152 show_boxes_append(&Show_boxes, gv_strdup("grestore"));
153}
154
155static void psprintinit (int begin)
156{
157 if (begin)
158 show_boxes_append(&Show_boxes, gv_strdup("dbgstart"));
159 else
160 show_boxes_append(&Show_boxes, gv_strdup("grestore"));
161}
162
163static bool debugleveln(edge_t* realedge, int i)
164{
165 return GD_showboxes(agraphof(aghead(realedge))) == i ||
166 GD_showboxes(agraphof(agtail(realedge))) == i ||
167 ED_showboxes(realedge) == i ||
168 ND_showboxes(aghead(realedge)) == i ||
169 ND_showboxes(agtail(realedge)) == i;
170}
171#endif /* DEBUG */
172
174pointf *simpleSplineRoute(pointf tp, pointf hp, Ppoly_t poly, size_t *n_spl_pts,
175 int polyline) {
176 Ppolyline_t pl, spl;
177 Ppoint_t eps[2];
178 Pvector_t evs[2];
179
180 eps[0].x = tp.x;
181 eps[0].y = tp.y;
182 eps[1].x = hp.x;
183 eps[1].y = hp.y;
184 if (Pshortestpath(&poly, eps, &pl) < 0)
185 return NULL;
186
187 if (polyline)
188 make_polyline (pl, &spl);
189 else {
190 // polygon edges passed to Proutespline
191 Pedge_t *edges = gv_calloc(poly.pn, sizeof(Pedge_t));
192 for (size_t i = 0; i < poly.pn; i++) {
193 edges[i].a = poly.ps[i];
194 edges[i].b = poly.ps[(i + 1) % poly.pn];
195 }
196 evs[0].x = evs[0].y = 0;
197 evs[1].x = evs[1].y = 0;
198 if (Proutespline(edges, poly.pn, pl, evs, &spl) < 0) {
199 free(edges);
200 return NULL;
201 }
202 free(edges);
203 }
204
205 pointf *ps = calloc(spl.pn, sizeof(ps[0]));
206 if (ps == NULL) {
207 agerrorf("cannot allocate ps\n");
208 return NULL;
209 }
210 for (size_t i = 0; i < spl.pn; i++) {
211 ps[i] = spl.ps[i];
212 }
213 *n_spl_pts = spl.pn;
214 return ps;
215}
216
220int
222{
223 if (++routeinit > 1) return 0;
224#ifdef DEBUG
225 show_boxes_free(&Show_boxes);
226#endif
227 nedges = 0;
228 nboxes = 0;
229 if (Verbose)
230 start_timer();
231 return 0;
232}
233
235{
236 if (--routeinit > 0) return;
237 GV_DEBUG("routesplines: %d edges, %" PRISIZE_T " boxes %.2f sec",
239}
240
241static void limitBoxes(boxf *boxes, size_t boxn, const pointf *pps, size_t pn,
242 double delta) {
243 double t;
244 pointf sp[4];
245 const double num_div = delta * (double)boxn;
246
247 for (size_t splinepi = 0; splinepi + 3 < pn; splinepi += 3) {
248 for (double si = 0; si <= num_div; si++) {
249 t = si / num_div;
250 sp[0] = pps[splinepi];
251 sp[1] = pps[splinepi + 1];
252 sp[2] = pps[splinepi + 2];
253 sp[3] = pps[splinepi + 3];
254 sp[0].x += t * (sp[1].x - sp[0].x);
255 sp[0].y += t * (sp[1].y - sp[0].y);
256 sp[1].x += t * (sp[2].x - sp[1].x);
257 sp[1].y += t * (sp[2].y - sp[1].y);
258 sp[2].x += t * (sp[3].x - sp[2].x);
259 sp[2].y += t * (sp[3].y - sp[2].y);
260 sp[0].x += t * (sp[1].x - sp[0].x);
261 sp[0].y += t * (sp[1].y - sp[0].y);
262 sp[1].x += t * (sp[2].x - sp[1].x);
263 sp[1].y += t * (sp[2].y - sp[1].y);
264 sp[0].x += t * (sp[1].x - sp[0].x);
265 sp[0].y += t * (sp[1].y - sp[0].y);
266 for (size_t bi = 0; bi < boxn; bi++) {
267/* this tested ok on 64bit machines, but on 32bit we need this FUDGE
268 * or graphs/directed/records.gv fails */
269#define FUDGE .0001
270 if (sp[0].y <= boxes[bi].UR.y+FUDGE && sp[0].y >= boxes[bi].LL.y-FUDGE) {
271 boxes[bi].LL.x = fmin(boxes[bi].LL.x, sp[0].x);
272 boxes[bi].UR.x = fmax(boxes[bi].UR.x, sp[0].x);
273 }
274 }
275 }
276 }
277}
278
279#define INIT_DELTA 10
280#define LOOP_TRIES 15 /* number of times to try to limiting boxes to regain space, using smaller divisions */
281
297static pointf *routesplines_(path *pp, size_t *npoints, int polyline) {
299 Ppolyline_t pl, spl;
300 Ppoint_t eps[2];
301 Pvector_t evs[2];
302 int prev, next;
303 boxf *boxes;
304 edge_t* realedge;
305 bool flip;
306 int loopcnt;
307 bool unbounded;
308
309 *npoints = 0;
310 nedges++;
311 nboxes += pp->nbox;
312
313 for (realedge = pp->data;
314 realedge && ED_edge_type(realedge) != NORMAL;
315 realedge = ED_to_orig(realedge));
316 if (!realedge) {
317 agerrorf("in routesplines, cannot find NORMAL edge\n");
318 return NULL;
319 }
320
321 boxes = pp->boxes;
322 const size_t boxn = pp->nbox;
323
324 if (checkpath(boxn, boxes, pp))
325 return NULL;
326
327#ifdef DEBUG
328 if (debugleveln(realedge, 1))
329 printboxes(boxn, boxes);
330 if (debugleveln(realedge, 3)) {
331 psprintinit(1);
332 psprintboxes(boxn, boxes);
333 }
334#endif
335
336 // vertices of polygon defined by boxes
337 Ppoint_t *polypoints = gv_calloc(boxn * 8, sizeof(Ppoint_t));
338
339 if (boxn > 1 && boxes[0].LL.y > boxes[1].LL.y) {
340 flip = true;
341 for (size_t bi = 0; bi < boxn; bi++) {
342 double v = boxes[bi].UR.y;
343 boxes[bi].UR.y = -1*boxes[bi].LL.y;
344 boxes[bi].LL.y = -v;
345 }
346 }
347 else flip = false;
348
349 size_t pi;
350 if (agtail(realedge) != aghead(realedge)) {
351 /* I assume that the path goes either down only or
352 up - right - down */
353 size_t bi;
354 for (bi = 0, pi = 0; bi < boxn; bi++) {
355 next = prev = 0;
356 if (bi > 0)
357 prev = boxes[bi].LL.y > boxes[bi - 1].LL.y ? -1 : 1;
358 if (bi + 1 < boxn)
359 next = boxes[bi + 1].LL.y > boxes[bi].LL.y ? 1 : -1;
360 if (prev != next) {
361 if (next == -1 || prev == 1) {
362 polypoints[pi].x = boxes[bi].LL.x;
363 polypoints[pi++].y = boxes[bi].UR.y;
364 polypoints[pi].x = boxes[bi].LL.x;
365 polypoints[pi++].y = boxes[bi].LL.y;
366 } else {
367 polypoints[pi].x = boxes[bi].UR.x;
368 polypoints[pi++].y = boxes[bi].LL.y;
369 polypoints[pi].x = boxes[bi].UR.x;
370 polypoints[pi++].y = boxes[bi].UR.y;
371 }
372 }
373 else if (prev == 0) { /* single box */
374 polypoints[pi].x = boxes[bi].LL.x;
375 polypoints[pi++].y = boxes[bi].UR.y;
376 polypoints[pi].x = boxes[bi].LL.x;
377 polypoints[pi++].y = boxes[bi].LL.y;
378 }
379 else {
380 if (!(prev == -1 && next == -1)) {
381 free(polypoints);
382 agerrorf("in routesplines, illegal values of prev %d and next %d, line %d\n", prev, next, __LINE__);
383 return NULL;
384 }
385 }
386 }
387 for (bi = boxn - 1; bi != SIZE_MAX; bi--) {
388 next = prev = 0;
389 if (bi + 1 < boxn)
390 prev = boxes[bi].LL.y > boxes[bi + 1].LL.y ? -1 : 1;
391 if (bi > 0)
392 next = boxes[bi - 1].LL.y > boxes[bi].LL.y ? 1 : -1;
393 if (prev != next) {
394 if (next == -1 || prev == 1 ) {
395 polypoints[pi].x = boxes[bi].LL.x;
396 polypoints[pi++].y = boxes[bi].UR.y;
397 polypoints[pi].x = boxes[bi].LL.x;
398 polypoints[pi++].y = boxes[bi].LL.y;
399 } else {
400 polypoints[pi].x = boxes[bi].UR.x;
401 polypoints[pi++].y = boxes[bi].LL.y;
402 polypoints[pi].x = boxes[bi].UR.x;
403 polypoints[pi++].y = boxes[bi].UR.y;
404 }
405 }
406 else if (prev == 0) { /* single box */
407 polypoints[pi].x = boxes[bi].UR.x;
408 polypoints[pi++].y = boxes[bi].LL.y;
409 polypoints[pi].x = boxes[bi].UR.x;
410 polypoints[pi++].y = boxes[bi].UR.y;
411 }
412 else {
413 if (!(prev == -1 && next == -1)) {
414 /* it went badly, e.g. degenerate box in boxlist */
415 free(polypoints);
416 agerrorf("in routesplines, illegal values of prev %d and next %d, line %d\n", prev, next, __LINE__);
417 return NULL; /* for correctness sake, it's best to just stop */
418 }
419 polypoints[pi].x = boxes[bi].UR.x;
420 polypoints[pi++].y = boxes[bi].LL.y;
421 polypoints[pi].x = boxes[bi].UR.x;
422 polypoints[pi++].y = boxes[bi].UR.y;
423 polypoints[pi].x = boxes[bi].LL.x;
424 polypoints[pi++].y = boxes[bi].UR.y;
425 polypoints[pi].x = boxes[bi].LL.x;
426 polypoints[pi++].y = boxes[bi].LL.y;
427 }
428 }
429 }
430 else {
431 free(polypoints);
432 agerrorf("in routesplines, edge is a loop at %s\n", agnameof(aghead(realedge)));
433 return NULL;
434 }
435
436 if (flip) {
437 for (size_t bi = 0; bi < boxn; bi++) {
438 double v = boxes[bi].UR.y;
439 boxes[bi].UR.y = -1*boxes[bi].LL.y;
440 boxes[bi].LL.y = -v;
441 }
442 for (size_t i = 0; i < pi; i++)
443 polypoints[i].y *= -1;
444 }
445
446 static const double INITIAL_LLX = DBL_MAX;
447 static const double INITIAL_URX = -DBL_MAX;
448 for (size_t bi = 0; bi < boxn; bi++) {
449 boxes[bi].LL.x = INITIAL_LLX;
450 boxes[bi].UR.x = INITIAL_URX;
451 }
452 poly.ps = polypoints, poly.pn = pi;
453 eps[0].x = pp->start.p.x, eps[0].y = pp->start.p.y;
454 eps[1].x = pp->end.p.x, eps[1].y = pp->end.p.y;
455 if (Pshortestpath(&poly, eps, &pl) < 0) {
456 free(polypoints);
457 agerrorf("in routesplines, Pshortestpath failed\n");
458 return NULL;
459 }
460#ifdef DEBUG
461 if (debugleveln(realedge, 3)) {
462 psprintpoly(poly);
463 psprintline(pl);
464 }
465#endif
466
467 if (polyline) {
468 make_polyline (pl, &spl);
469 }
470 else {
471 Pedge_t *edges = gv_calloc(poly.pn, sizeof(Pedge_t));
472 for (size_t edgei = 0; edgei < poly.pn; edgei++) {
473 edges[edgei].a = polypoints[edgei];
474 edges[edgei].b = polypoints[(edgei + 1) % poly.pn];
475 }
476 if (pp->start.constrained) {
477 evs[0].x = cos(pp->start.theta);
478 evs[0].y = sin(pp->start.theta);
479 } else
480 evs[0].x = evs[0].y = 0;
481 if (pp->end.constrained) {
482 evs[1].x = -cos(pp->end.theta);
483 evs[1].y = -sin(pp->end.theta);
484 } else
485 evs[1].x = evs[1].y = 0;
486
487 if (Proutespline(edges, poly.pn, pl, evs, &spl) < 0) {
488 free(edges);
489 free(polypoints);
490 agerrorf("in routesplines, Proutespline failed\n");
491 return NULL;
492 }
493 free(edges);
494#ifdef DEBUG
495 if (debugleveln(realedge, 3)) {
496 psprintspline(spl);
497 psprintinit(0);
498 }
499#endif
500 }
501 pointf *ps = calloc(spl.pn, sizeof(ps[0]));
502 if (ps == NULL) {
503 free(polypoints);
504 agerrorf("cannot allocate ps\n");
505 return NULL; /* Bailout if no memory left */
506 }
507
508 unbounded = true;
509 for (size_t splinepi = 0; splinepi < spl.pn; splinepi++) {
510 ps[splinepi] = spl.ps[splinepi];
511 }
512
513 {
514 // does the spline go straight left/right?
515 bool is_horizontal = spl.pn > 0;
516 for (size_t i = 0; i < spl.pn; ++i) {
517 if (fabs(ps[0].y - ps[i].y) > FUDGE) {
518 is_horizontal = false;
519 break;
520 }
521 }
522 if (is_horizontal) {
523 GV_INFO("spline [%.03f, %.03f] -- [%.03f, %.03f] is horizontal;"
524 " will be trivially bounded", ps[0].x, ps[0].y, ps[spl.pn - 1].x,
525 ps[spl.pn - 1].y);
526 }
527
528 // does the spline go straight up/down?
529 bool is_vertical = spl.pn > 0;
530 for (size_t i = 0; i < spl.pn; ++i) {
531 if (fabs(ps[0].x - ps[i].x) > FUDGE) {
532 is_vertical = false;
533 break;
534 }
535 }
536 if (is_vertical) {
537 GV_INFO("spline [%.03f, %.03f] -- [%.03f, %.03f] is vertical;"
538 " will be trivially bounded", ps[0].x, ps[0].y, ps[spl.pn - 1].x,
539 ps[spl.pn - 1].y);
540 }
541
542 // if the spline is horizontal or vertical, the `limitBoxes` loop will not
543 // converge, but we know the expected outcome trivially
544 if (is_horizontal || is_vertical) {
545 for (size_t i = 0; i < boxn; ++i) {
546 boxes[i].LL.x = ps[0].x;
547 boxes[i].UR.x = ps[0].x;
548 }
549 unbounded = false;
550 }
551 }
552
553 double delta = INIT_DELTA;
554
555 for (loopcnt = 0; unbounded && loopcnt < LOOP_TRIES; loopcnt++) {
556 limitBoxes(boxes, boxn, ps, spl.pn, delta);
557
558 /* The following check is necessary because if a box is not very
559 * high, it is possible that the sampling above might miss it.
560 * Therefore, we make the sample finer until all boxes have
561 * valid values. cf. bug 456.
562 */
563 size_t bi;
564 for (bi = 0; bi < boxn; bi++) {
565 /* these fp equality tests are used only to detect if the
566 * values have been changed since initialization - ok */
567 if (is_exactly_equal(boxes[bi].LL.x, INITIAL_LLX) ||
568 is_exactly_equal(boxes[bi].UR.x, INITIAL_URX)) {
569 delta *= 2; /* try again with a finer interval */
570 break;
571 }
572 }
573 if (bi == boxn)
574 unbounded = false;
575 }
576 if (unbounded) {
577 /* Either an extremely short, even degenerate, box, or some failure with the path
578 * planner causing the spline to miss some boxes. In any case, use the shortest path
579 * to bound the boxes. This will probably mean a bad edge, but we avoid an infinite
580 * loop and we can see the bad edge, and even use the showboxes scaffolding.
581 */
582 Ppolyline_t polyspl;
583 agwarningf("Unable to reclaim box space in spline routing for edge \"%s\" -> \"%s\". Something is probably seriously wrong.\n", agnameof(agtail(realedge)), agnameof(aghead(realedge)));
584 make_polyline (pl, &polyspl);
585 limitBoxes(boxes, boxn, polyspl.ps, polyspl.pn, INIT_DELTA);
586 }
587
588 *npoints = spl.pn;
589
590#ifdef DEBUG
591 if (GD_showboxes(agraphof(aghead(realedge))) == 2 ||
592 GD_showboxes(agraphof(agtail(realedge))) == 2 ||
593 ED_showboxes(realedge) == 2 ||
594 ND_showboxes(aghead(realedge)) == 2 ||
595 ND_showboxes(agtail(realedge)) == 2)
596 printboxes(boxn, boxes);
597#endif
598
599 free(polypoints);
600 return ps;
601}
602
603pointf *routesplines(path *pp, size_t *npoints) {
604 return routesplines_(pp, npoints, 0);
605}
606
607pointf *routepolylines(path *pp, size_t *npoints) {
608 return routesplines_(pp, npoints, 1);
609}
610
611static double overlap(double i0, double i1, double j0, double j1) {
612 if (i1 <= j0)
613 return 0;
614 if (i0 >= j1)
615 return 0;
616
617 // does the first interval subsume the second?
618 if (i0 <= j0 && i1 >= j1)
619 return i1 - i0;
620 // does the second interval subsume the first?
621 if (j0 <= i0 && j1 >= i1)
622 return j1 - j0;
623
624 if (j0 <= i0 && i0 <= j1)
625 return j1 - i0;
626 assert(j0 <= i1 && i1 <= j1);
627 return i1 - j0;
628}
629
630
631/*
632 * repairs minor errors in the boxpath, such as boxes not joining
633 * or slightly intersecting. it's sort of the equivalent of the
634 * audit process in the 5E control program - if you've given up on
635 * fixing all the bugs, at least try to engineer around them!
636 * in postmodern CS, we could call this "self-healing code."
637 *
638 * Return 1 on failure; 0 on success.
639 */
640static int checkpath(size_t boxn, boxf *boxes, path *thepath) {
641 boxf *ba, *bb;
642 int errs, l, r, d, u;
643
644 /* remove degenerate boxes. */
645 size_t i = 0;
646 for (size_t bi = 0; bi < boxn; bi++) {
647 if (fabs(boxes[bi].LL.y - boxes[bi].UR.y) < .01)
648 continue;
649 if (fabs(boxes[bi].LL.x - boxes[bi].UR.x) < .01)
650 continue;
651 boxes[i] = boxes[bi];
652 i++;
653 }
654 boxn = i;
655
656 ba = &boxes[0];
657 if (ba->LL.x > ba->UR.x || ba->LL.y > ba->UR.y) {
658 agerrorf("in checkpath, box 0 has LL coord > UR coord\n");
659 printpath(thepath);
660 return 1;
661 }
662 for (size_t bi = 0; bi + 1 < boxn; bi++) {
663 ba = &boxes[bi], bb = &boxes[bi + 1];
664 if (bb->LL.x > bb->UR.x || bb->LL.y > bb->UR.y) {
665 agerrorf("in checkpath, box %" PRISIZE_T " has LL coord > UR coord\n",
666 bi + 1);
667 printpath(thepath);
668 return 1;
669 }
670 l = ba->UR.x < bb->LL.x ? 1 : 0;
671 r = ba->LL.x > bb->UR.x ? 1 : 0;
672 d = ba->UR.y < bb->LL.y ? 1 : 0;
673 u = ba->LL.y > bb->UR.y ? 1 : 0;
674 errs = l + r + d + u;
675 if (errs > 0 && Verbose) {
676 fprintf(stderr, "in checkpath, boxes %" PRISIZE_T " and %" PRISIZE_T
677 " don't touch\n", bi, bi + 1);
678 printpath(thepath);
679 }
680 if (errs > 0) {
681 double xy;
682
683 if (l == 1)
684 xy = ba->UR.x, ba->UR.x = bb->LL.x, bb->LL.x = xy, l = 0;
685 else if (r == 1)
686 xy = ba->LL.x, ba->LL.x = bb->UR.x, bb->UR.x = xy, r = 0;
687 else if (d == 1)
688 xy = ba->UR.y, ba->UR.y = bb->LL.y, bb->LL.y = xy, d = 0;
689 else if (u == 1)
690 xy = ba->LL.y, ba->LL.y = bb->UR.y, bb->UR.y = xy, u = 0;
691 for (int j = 0; j < errs - 1; j++) {
692 if (l == 1)
693 xy = (ba->UR.x + bb->LL.x) / 2.0 + 0.5, ba->UR.x =
694 bb->LL.x = xy, l = 0;
695 else if (r == 1)
696 xy = (ba->LL.x + bb->UR.x) / 2.0 + 0.5, ba->LL.x =
697 bb->UR.x = xy, r = 0;
698 else if (d == 1)
699 xy = (ba->UR.y + bb->LL.y) / 2.0 + 0.5, ba->UR.y =
700 bb->LL.y = xy, d = 0;
701 else if (u == 1)
702 xy = (ba->LL.y + bb->UR.y) / 2.0 + 0.5, ba->LL.y =
703 bb->UR.y = xy, u = 0;
704 }
705 }
706 /* check for overlapping boxes */
707 double xoverlap = overlap(ba->LL.x, ba->UR.x, bb->LL.x, bb->UR.x);
708 double yoverlap = overlap(ba->LL.y, ba->UR.y, bb->LL.y, bb->UR.y);
709 if (xoverlap > 0 && yoverlap > 0) {
710 if (xoverlap < yoverlap) {
711 if (ba->UR.x - ba->LL.x > bb->UR.x - bb->LL.x) {
712 /* take space from ba */
713 if (ba->UR.x < bb->UR.x)
714 ba->UR.x = bb->LL.x;
715 else
716 ba->LL.x = bb->UR.x;
717 } else {
718 /* take space from bb */
719 if (ba->UR.x < bb->UR.x)
720 bb->LL.x = ba->UR.x;
721 else
722 bb->UR.x = ba->LL.x;
723 }
724 } else { /* symmetric for y coords */
725 if (ba->UR.y - ba->LL.y > bb->UR.y - bb->LL.y) {
726 /* take space from ba */
727 if (ba->UR.y < bb->UR.y)
728 ba->UR.y = bb->LL.y;
729 else
730 ba->LL.y = bb->UR.y;
731 } else {
732 /* take space from bb */
733 if (ba->UR.y < bb->UR.y)
734 bb->LL.y = ba->UR.y;
735 else
736 bb->UR.y = ba->LL.y;
737 }
738 }
739 }
740 }
741
742 if (thepath->start.p.x < boxes[0].LL.x
743 || thepath->start.p.x > boxes[0].UR.x
744 || thepath->start.p.y < boxes[0].LL.y
745 || thepath->start.p.y > boxes[0].UR.y) {
746 thepath->start.p.x = fmax(thepath->start.p.x, boxes[0].LL.x);
747 thepath->start.p.x = fmin(thepath->start.p.x, boxes[0].UR.x);
748 thepath->start.p.y = fmax(thepath->start.p.y, boxes[0].LL.y);
749 thepath->start.p.y = fmin(thepath->start.p.y, boxes[0].UR.y);
750 }
751 if (thepath->end.p.x < boxes[boxn - 1].LL.x
752 || thepath->end.p.x > boxes[boxn - 1].UR.x
753 || thepath->end.p.y < boxes[boxn - 1].LL.y
754 || thepath->end.p.y > boxes[boxn - 1].UR.y) {
755 thepath->end.p.x = fmax(thepath->end.p.x, boxes[boxn - 1].LL.x);
756 thepath->end.p.x = fmin(thepath->end.p.x, boxes[boxn - 1].UR.x);
757 thepath->end.p.y = fmax(thepath->end.p.y, boxes[boxn - 1].LL.y);
758 thepath->end.p.y = fmin(thepath->end.p.y, boxes[boxn - 1].UR.y);
759 }
760 return 0;
761}
762
763static void printpath(path * pp)
764{
765 fprintf(stderr, "%" PRISIZE_T " boxes:\n", pp->nbox);
766 for (size_t bi = 0; bi < pp->nbox; bi++)
767 fprintf(stderr, "%" PRISIZE_T " (%.5g, %.5g), (%.5g, %.5g)\n", bi,
768 pp->boxes[bi].LL.x, pp->boxes[bi].LL.y,
769 pp->boxes[bi].UR.x, pp->boxes[bi].UR.y);
770 fprintf(stderr, "start port: (%.5g, %.5g), tangent angle: %.5g, %s\n",
771 pp->start.p.x, pp->start.p.y, pp->start.theta,
772 pp->start.constrained ? "constrained" : "not constrained");
773 fprintf(stderr, "end port: (%.5g, %.5g), tangent angle: %.5g, %s\n",
774 pp->end.p.x, pp->end.p.y, pp->end.theta,
775 pp->end.constrained ? "constrained" : "not constrained");
776}
777
779{
780 pointf sum = {0.0, 0.0};
781
782 sum.x = (GD_bb(g).LL.x + GD_bb(g).UR.x) / 2.0;
783 sum.y = (GD_bb(g).LL.y + GD_bb(g).UR.y) / 2.0;
784 return sum;
785}
786
787DEFINE_LIST(nodes, node_t *)
788
789static void nodes_delete(nodes_t *pvec) {
790 if (pvec != NULL) {
791 nodes_free(pvec);
792 }
793 free(pvec);
794}
795
796DEFINE_LIST_WITH_DTOR(cycles, nodes_t *, nodes_delete)
797
798static bool cycle_contains_edge(nodes_t *cycle, edge_t *edge) {
799 node_t* start = agtail(edge);
800 node_t* end = aghead(edge);
801
802 const size_t cycle_len = nodes_size(cycle);
803
804 for (size_t i=0; i < cycle_len; ++i) {
805 const node_t *c_start = nodes_get(cycle, i == 0 ? cycle_len - 1 : i - 1);
806 const node_t *c_end = nodes_get(cycle, i);
807
808 if (c_start == start && c_end == end)
809 return true;
810 }
811
812
813 return false;
814}
815
816static bool eq(const node_t *a, const node_t *b) { return a == b; }
817
818static bool is_cycle_unique(cycles_t *cycles, nodes_t *cycle) {
819 const size_t cycle_len = nodes_size(cycle);
820 size_t i; //node counter
821
822 bool all_items_match;
823
824 for (size_t c = 0; c < cycles_size(cycles); ++c) {
825 nodes_t *cur_cycle = cycles_get(cycles, c);
826 const size_t cur_cycle_len = nodes_size(cur_cycle);
827
828 //if all the items match in equal length cycles then we're not unique
829 if (cur_cycle_len == cycle_len) {
830 all_items_match = true;
831 for (i=0; i < cur_cycle_len; ++i) {
832 node_t *cur_cycle_item = nodes_get(cur_cycle, i);
833 if (!nodes_contains(cycle, cur_cycle_item, eq)) {
834 all_items_match = false;
835 break;
836 }
837 }
838 if (all_items_match)
839 return false;
840 }
841 }
842
843 return true;
844}
845
846static void dfs(graph_t *g, node_t *search, nodes_t *visited, node_t *end,
847 cycles_t *cycles) {
848 edge_t* e;
849 node_t* n;
850
851 if (nodes_contains(visited, search, eq)) {
852 if (search == end) {
853 if (is_cycle_unique(cycles, visited)) {
854 nodes_t *cycle = gv_alloc(sizeof(nodes_t));
855 *cycle = nodes_copy(visited);
856 cycles_append(cycles, cycle);
857 }
858 }
859 } else {
860 nodes_append(visited, search);
861 for (e = agfstout(g, search); e; e = agnxtout(g, e)) {
862 n = aghead(e);
863 dfs(g, n, visited, end, cycles);
864 }
865 if (!nodes_is_empty(visited)) {
866 (void)nodes_pop_back(visited);
867 }
868 }
869}
870
871// Returns a vec of vec of nodes (aka a vector of cycles)
872static cycles_t find_all_cycles(graph_t *g) {
873 node_t *n;
874
875 // vector of vectors of nodes -- AKA cycles to delete
876 cycles_t alloced_cycles = {0};
877 cycles_t cycles = {0}; // vector of vectors of nodes AKA a vector of cycles
878
879 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
880 nodes_t *cycle = gv_alloc(sizeof(nodes_t));
881 // keep track of all items we allocate to clean up at the end of this function
882 cycles_append(&alloced_cycles, cycle);
883
884 dfs(g, n, cycle, n, &cycles);
885 }
886
887 cycles_free(&alloced_cycles); // cycles contains copied vecs
888 return cycles;
889}
890
891static nodes_t *find_shortest_cycle_with_edge(cycles_t *cycles, edge_t *edge,
892 size_t min_size) {
893 nodes_t *shortest = NULL;
894
895 for (size_t c = 0; c < cycles_size(cycles); ++c) {
896 nodes_t *cycle = cycles_get(cycles, c);
897 size_t cycle_len = nodes_size(cycle);
898
899 if (cycle_len < min_size)
900 continue;
901
902 if (shortest == NULL || nodes_size(shortest) > cycle_len) {
903 if (cycle_contains_edge(cycle, edge)) {
904 shortest = cycle;
905 }
906 }
907 }
908 return shortest;
909}
910
912{
913 cycles_t cycles = find_all_cycles(g);
914
915 //find the center of the shortest cycle containing this edge
916 //cycles of length 2 do their own thing, we want 3 or
917 nodes_t *cycle = find_shortest_cycle_with_edge(&cycles, edge, 3);
918 pointf sum = {0.0, 0.0};
919
920 if (cycle == NULL) {
921 cycles_free(&cycles);
922 return get_centroid(g);
923 }
924
925 double cnt = 0;
926 for (size_t idx = 0; idx < nodes_size(cycle); ++idx) {
927 node_t *n = nodes_get(cycle, idx);
928 sum.x += ND_coord(n).x;
929 sum.y += ND_coord(n).y;
930 cnt++;
931 }
932
933 cycles_free(&cycles);
934
935 sum.x /= cnt;
936 sum.y /= cnt;
937 return sum;
938}
939
940static void bend(pointf spl[4], pointf centroid)
941{
942 pointf a;
943 double r;
944
945 pointf midpt = mid_pointf(spl[0], spl[3]);
946 double dist = DIST(spl[3], spl[0]);
947 r = dist/5.0;
948 {
949 double vX = centroid.x - midpt.x;
950 double vY = centroid.y - midpt.y;
951 double magV = hypot(vX, vY);
952 if (magV == 0) return; /* if midpoint == centroid, don't divide by zero */
953 a.x = midpt.x - vX / magV * r; /* + would be closest point */
954 a.y = midpt.y - vY / magV * r;
955 }
956 /* this can be improved */
957 spl[1].x = spl[2].x = a.x;
958 spl[1].y = spl[2].y = a.y;
959}
960
961// FIX: handle ports on boundary?
962void
964{
965 edge_t *e0;
966
967 size_t e_cnt = 1;
968 e0 = e;
969 while (e0 != ED_to_virt(e0) && (e0 = ED_to_virt(e0))) e_cnt++;
970
971 edge_t **edge_list = gv_calloc(e_cnt, sizeof(edge_t *));
972 e0 = e;
973 for (size_t i = 0; i < e_cnt; i++) {
974 edge_list[i] = e0;
975 e0 = ED_to_virt(e0);
976 }
977 assert(e_cnt <= INT_MAX);
978 makeStraightEdges(g, edge_list, e_cnt, et, sinfo);
979 free(edge_list);
980}
981
982void makeStraightEdges(graph_t *g, edge_t **edge_list, size_t e_cnt, int et,
983 splineInfo *sinfo) {
984 pointf dumb[4];
985 bool curved = et == EDGETYPE_CURVED;
986 pointf del;
987
988 edge_t *e = edge_list[0];
989 node_t *n = agtail(e);
990 node_t *head = aghead(e);
991 dumb[1] = dumb[0] = add_pointf(ND_coord(n), ED_tail_port(e).p);
992 dumb[2] = dumb[3] = add_pointf(ND_coord(head), ED_head_port(e).p);
993 if (e_cnt == 1 || Concentrate) {
994 if (curved) bend(dumb,get_cycle_centroid(g, edge_list[0]));
995 clip_and_install(e, aghead(e), dumb, 4, sinfo);
996 addEdgeLabels(e);
997 return;
998 }
999
1000 if (APPROXEQPT(dumb[0], dumb[3], MILLIPOINT)) {
1001 /* degenerate case */
1002 dumb[1] = dumb[0];
1003 dumb[2] = dumb[3];
1004 del.x = 0;
1005 del.y = 0;
1006 }
1007 else {
1008 pointf perp = {
1009 .x = dumb[0].y - dumb[3].y,
1010 .y = dumb[3].x - dumb[0].x
1011 };
1012 double l_perp = hypot(perp.x, perp.y);
1013 int xstep = GD_nodesep(g->root);
1014 assert(e_cnt - 1 <= INT_MAX);
1015 int dx = xstep * (int)(e_cnt - 1) / 2;
1016 dumb[1].x = dumb[0].x + dx * perp.x / l_perp;
1017 dumb[1].y = dumb[0].y + dx * perp.y / l_perp;
1018 dumb[2].x = dumb[3].x + dx * perp.x / l_perp;
1019 dumb[2].y = dumb[3].y + dx * perp.y / l_perp;
1020 del.x = -xstep * perp.x / l_perp;
1021 del.y = -xstep * perp.y / l_perp;
1022 }
1023
1024 for (size_t i = 0; i < e_cnt; i++) {
1025 edge_t *e0 = edge_list[i];
1026 pointf dumber[4];
1027 if (aghead(e0) == head) {
1028 for (size_t j = 0; j < 4; j++) {
1029 dumber[j] = dumb[j];
1030 }
1031 } else {
1032 for (size_t j = 0; j < 4; j++) {
1033 dumber[3 - j] = dumb[j];
1034 }
1035 }
1036 if (et == EDGETYPE_PLINE) {
1037 Ppoint_t pts[] = {dumber[0], dumber[1], dumber[2], dumber[3]};
1038 Ppolyline_t spl, line = {.pn = 4, .ps = pts};
1039 make_polyline (line, &spl);
1040 clip_and_install(e0, aghead(e0), spl.ps, (size_t)spl.pn, sinfo);
1041 }
1042 else
1043 clip_and_install(e0, aghead(e0), dumber, 4, sinfo);
1044
1045 addEdgeLabels(e0);
1046 dumb[1] = add_pointf(dumb[1], del);
1047 dumb[2] = add_pointf(dumb[2], del);
1048 }
1049}
static int agxbprint(agxbuf *xb, const char *fmt,...)
Printf-style output to an agxbuf.
Definition agxbuf.h:234
static char * agxbdisown(agxbuf *xb)
Definition agxbuf.h:327
Memory allocation wrappers that exit on failure.
static char * gv_strdup(const char *original)
Definition alloc.h:101
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
static void * gv_alloc(size_t size)
Definition alloc.h:47
#define NORMAL
Definition const.h:24
#define EDGETYPE_CURVED
Definition const.h:250
#define EDGETYPE_PLINE
Definition const.h:251
helpers for verbose/debug printing
#define GV_DEBUG(...)
Definition debug.h:39
#define GV_INFO(...)
Definition debug.h:15
static splineInfo sinfo
Definition dotsplines.c:129
static float dx
Definition draw.c:38
#define head
Definition dthdr.h:15
static void del(Dict_t *d, Dtlink_t **set, Agedge_t *e)
Definition edge.c:156
static double dist(int dim, double *x, double *y)
#define MILLIPOINT
Definition geom.h:74
#define APPROXEQPT(p, q, tol)
Definition geom.h:71
#define DIST(p, q)
Definition geom.h:56
geometric functions (e.g. on points and boxes)
static pointf mid_pointf(pointf p, pointf q)
Definition geomprocs.h:106
static pointf add_pointf(pointf p, pointf q)
Definition geomprocs.h:88
static pointf perp(pointf p)
Definition geomprocs.h:146
bool Concentrate
Definition globals.h:59
show_boxes_t Show_boxes
Definition globals.h:57
static bool Verbose
Definition gml2gv.c:24
void free(void *)
edge
Definition gmlparse.y:239
#define SIZE_MAX
Definition gmlscan.c:347
node NULL
Definition grammar.y:180
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:196
#define ED_to_orig(e)
Definition types.h:598
#define ED_showboxes(e)
Definition types.h:594
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:26
#define agtail(e)
Definition cgraph.h:988
#define ED_edge_type(e)
Definition types.h:582
#define aghead(e)
Definition cgraph.h:989
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:41
#define ED_head_port(e)
Definition types.h:588
#define ED_tail_port(e)
Definition types.h:597
#define ED_to_virt(e)
Definition types.h:599
void agwarningf(const char *fmt,...)
Definition agerror.c:173
void agerrorf(const char *fmt,...)
Definition agerror.c:165
#define GD_bb(g)
Definition types.h:354
#define GD_showboxes(g)
Definition types.h:401
#define GD_nodesep(g)
Definition types.h:394
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:48
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:41
#define ND_showboxes(n)
Definition types.h:530
#define ND_coord(n)
Definition types.h:490
Agraph_t * agraphof(void *obj)
Definition obj.c:185
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
Arithmetic helper functions.
static bool is_exactly_equal(double a, double b)
are two values precisely the same?
Definition gv_math.h:45
$2 u p prev
Definition htmlparse.y:297
#define DEFINE_LIST_WITH_DTOR(name, type, dtor)
Definition list.h:30
#define DEFINE_LIST(name, type)
Definition list.h:22
static int * ps
Definition lu.c:51
#define delta
Definition maze.c:136
finds and smooths shortest paths
void make_polyline(Ppolyline_t line, Ppolyline_t *sline)
Definition util.c:59
int Proutespline(Pedge_t *barriers, size_t n_barriers, Ppolyline_t input_route, Pvector_t endpoint_slopes[2], Ppolyline_t *output_route)
Definition route.c:69
int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2], Ppolyline_t *output_route)
Definition shortest.c:83
#define PRISIZE_T
Definition prisize_t.h:25
void clip_and_install(edge_t *fe, node_t *hn, pointf *ps, size_t pn, splineInfo *info)
Definition splines.c:239
void addEdgeLabels(edge_t *e)
Definition splines.c:1324
static bool is_cycle_unique(cycles_t *cycles, nodes_t *cycle)
Definition routespl.c:818
#define INIT_DELTA
Definition routespl.c:279
static void printpath(path *pp)
Definition routespl.c:763
static int routeinit
Definition routespl.c:35
static pointf get_centroid(Agraph_t *g)
Definition routespl.c:778
static void dfs(graph_t *g, node_t *search, nodes_t *visited, node_t *end, cycles_t *cycles)
Definition routespl.c:846
int routesplinesinit(void)
Definition routespl.c:221
static int nedges
total no. of edges used in routing
Definition routespl.c:32
static void nodes_delete(nodes_t *pvec)
Definition routespl.c:789
pointf * simpleSplineRoute(pointf tp, pointf hp, Ppoly_t poly, size_t *n_spl_pts, int polyline)
Given a simple (ccw) polygon, route an edge from tp to hp.
Definition routespl.c:174
static nodes_t * find_shortest_cycle_with_edge(cycles_t *cycles, edge_t *edge, size_t min_size)
Definition routespl.c:891
static bool eq(const node_t *a, const node_t *b)
Definition routespl.c:816
static bool cycle_contains_edge(nodes_t *cycle, edge_t *edge)
Definition routespl.c:798
static cycles_t find_all_cycles(graph_t *g)
Definition routespl.c:872
#define LOOP_TRIES
Definition routespl.c:280
static size_t nboxes
total no. of boxes used in routing
Definition routespl.c:33
static void limitBoxes(boxf *boxes, size_t boxn, const pointf *pps, size_t pn, double delta)
Definition routespl.c:241
static int checkpath(size_t, boxf *, path *)
Definition routespl.c:640
static pointf get_cycle_centroid(graph_t *g, edge_t *edge)
Definition routespl.c:911
static double overlap(double i0, double i1, double j0, double j1)
Definition routespl.c:611
#define FUDGE
void routesplinesterm(void)
Definition routespl.c:234
void makeStraightEdges(graph_t *g, edge_t **edge_list, size_t e_cnt, int et, splineInfo *sinfo)
Definition routespl.c:982
void makeStraightEdge(graph_t *g, edge_t *e, int et, splineInfo *sinfo)
Definition routespl.c:963
pointf * routesplines(path *pp, size_t *npoints)
Definition routespl.c:603
pointf * routepolylines(path *pp, size_t *npoints)
Definition routespl.c:607
static pointf * routesplines_(path *pp, size_t *npoints, int polyline)
Definition routespl.c:297
graph or subgraph
Definition cgraph.h:424
Agraph_t * root
subgraphs - ancestors
Definition cgraph.h:433
Ppoint_t b
Definition pathgeom.h:53
Ppoint_t a
Definition pathgeom.h:53
size_t pn
Definition pathgeom.h:47
Ppoint_t * ps
Definition pathgeom.h:46
double x
Definition pathgeom.h:38
double y
Definition pathgeom.h:38
Definition geom.h:41
pointf UR
Definition geom.h:41
pointf LL
Definition geom.h:41
Definition types.h:81
port start
Definition types.h:82
boxf * boxes
Definition types.h:85
port end
Definition types.h:83
size_t nbox
number of subdivisions
Definition types.h:84
void * data
Definition types.h:86
Definition geom.h:27
int y
Definition geom.h:27
int x
Definition geom.h:27
double x
Definition geom.h:29
double y
Definition geom.h:29
pointf p
Definition types.h:49
double theta
Definition types.h:50
bool constrained
Definition types.h:55
bend
Definition structures.h:32
struct poly_s poly
double elapsed_sec(void)
Definition timing.c:48
void start_timer(void)
Definition timing.c:43