Graphviz 13.0.0~dev.20250424.1043
Loading...
Searching...
No Matches
tclpathplan.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11/*
12 * Tcl binding to drive Stephen North's and
13 * Emden Gansner's shortest path code.
14 *
15 * ellson@graphviz.org October 2nd, 1996
16 */
17
18#include "config.h"
19
20#include "../tcl-compat.h"
21#include <sys/types.h>
22#include <stdbool.h>
23#include <stdint.h>
24#include <stdlib.h>
25#include <string.h>
26
27#include <assert.h>
28#include <limits.h>
29#include "makecw.h"
30#include <math.h>
31#include <pathplan/pathutil.h>
32#include <pathplan/vispath.h>
33#include <pathplan/tri.h>
34#include "Plegal_arrangement.h"
35#include <tcl.h>
36#include <util/agxbuf.h>
37#include <util/alloc.h>
38#include <util/list.h>
39#include <util/prisize_t.h>
40
41#if (TCL_MAJOR_VERSION == 8 && TCL_MINOR_VERSION >= 6) || TCL_MAJOR_VERSION > 8
42#else
43#ifndef Tcl_GetStringResult
44#define Tcl_GetStringResult(interp) interp->result
45#endif
46#endif
47
49
50typedef struct poly_s {
51 int id;
54
55DEFINE_LIST(polys, poly)
56
57
58#define HANDLE_FORMAT ("vgpane%" PRISIZE_T)
59
60typedef struct {
61 polys_t poly; // set of polygons
62 vconfig_t *vc; /* visibility graph handle */
63 Tcl_Interp *interp; /* interpreter that owns the binding */
64 char *triangle_cmd; /* why is this here any more */
65 size_t index;
66 bool valid;
67} vgpane_t;
68
69DEFINE_LIST(vgpanes, vgpane_t)
70
71static vgpanes_t vgpaneTable;
72
73static int polyid = 0; /* unique and unchanging id for each poly */
74
75static poly *allocpoly(vgpane_t *vgp, int id, Tcl_Size npts) {
76 polys_append(&vgp->poly, (poly){.id = id});
77 poly *rv = polys_back(&vgp->poly);
78 rv->boundary.pn = 0;
79 rv->boundary.ps = gv_calloc(npts, sizeof(point));
80 return rv;
81}
82
83static void vc_stale(vgpane_t * vgp)
84{
85 if (vgp->vc) {
86 Pobsclose(vgp->vc);
87 vgp->vc = NULL;
88 }
89}
90
91static int vc_refresh(vgpane_t * vgp)
92{
93 if (vgp->vc == NULL) {
94 Ppoly_t **obs = gv_calloc(polys_size(&vgp->poly), sizeof(Ppoly_t*));
95 for (size_t i = 0; i < polys_size(&vgp->poly); i++)
96 obs[i] = &polys_at(&vgp->poly, i)->boundary;
97 if (!Plegal_arrangement(obs, polys_size(&vgp->poly)))
98 fprintf(stderr, "bad arrangement\n");
99 else
100 vgp->vc = Pobsopen(obs, (int)polys_size(&vgp->poly));
101 free(obs);
102 }
103 return vgp->vc != NULL;
104}
105
106static void dgsprintxy(agxbuf *result, int npts, const point p[]) {
107 int i;
108
109 assert(npts > 1);
110 if (agxblen(result) > 0) {
111 agxbputc(result, ' ');
112 }
113 agxbputc(result, '{');
114 const char *separator = "";
115 for (i = 0; i < npts; i++) {
116 agxbprint(result, "%s%g %g", separator, p[i].x, p[i].y);
117 separator = " ";
118 }
119 agxbputc(result, '}');
120}
121
127static void expandPercentsEval(Tcl_Interp *interp, char *before,
128 size_t vgcanvasHandle, int npts,
129 const point *ppos) {
130 agxbuf scripts = {0};
131
132 while (1) {
133 /*
134 * Find everything up to the next % character and append it to the
135 * result string.
136 */
137
138 char *string = strchr(before, '%');
139 if (string != NULL) {
140 agxbput_n(&scripts, before, (size_t)(string - before));
141 before = string;
142 }
143 if (*before == 0) {
144 break;
145 }
146 /*
147 * There's a percent sequence here. Process it.
148 */
149
150 switch (before[1]) {
151 case 'r':
152 agxbprint(&scripts, HANDLE_FORMAT, vgcanvasHandle);
153 break;
154 case 't':
155 dgsprintxy(&scripts, npts, ppos);
156 break;
157 default:
158 agxbputc(&scripts, before[1]);
159 break;
160 }
161 if (before[1] == '\0') {
162 break;
163 }
164 before += 2;
165 }
166 const char *script_value = agxbuse(&scripts);
167 if (Tcl_GlobalEval(interp, script_value) != TCL_OK)
168 fprintf(stderr, "%s while in binding: %s\n\n",
169 Tcl_GetStringResult(interp), script_value);
170 agxbfree(&scripts);
171}
172
173static void triangle_callback(void *vgparg, const point pqr[]) {
174 vgpane_t *vgp = vgparg;
175 if (vgp->triangle_cmd) {
176 const size_t vgcanvasHandle = vgp->index;
177 expandPercentsEval(vgp->interp, vgp->triangle_cmd, vgcanvasHandle, 3, pqr);
178 }
179}
180
181static char *buildBindings(char *s1, const char *s2)
182/*
183 * previous binding in s1 binding to be added in s2 result in s3
184 *
185 * if s2 begins with + then append (separated by \n) else s2 replaces if
186 * resultant string is null then bindings are deleted
187 */
188{
189 char *s3;
190 size_t l;
191
192 if (s2[0] == '+') {
193 if (s1) {
194 l = strlen(s2) - 1;
195 if (l) {
196 agxbuf new = {0};
197 agxbprint(&new, "%s\n%s", s1, s2 + 1);
198 free(s1);
199 return agxbdisown(&new);
200 } else {
201 s3 = s1;
202 }
203 } else {
204 l = strlen(s2) - 1;
205 if (l) {
206 s3 = gv_strdup(s2 + 1);
207 } else {
208 s3 = NULL;
209 }
210 }
211 } else {
212 free(s1);
213 l = strlen(s2);
214 if (l) {
215 s3 = gv_strdup(s2);
216 } else {
217 s3 = NULL;
218 }
219 }
220 return s3;
221}
222
223
224
225/* convert x and y string args to point */
226static int scanpoint(Tcl_Interp * interp, const char *argv[], point * p)
227{
228 if (sscanf(argv[0], "%lg", &p->x) != 1) {
229 Tcl_AppendResult(interp, "invalid x coordinate: \"", argv[0], "\"", NULL);
230 return TCL_ERROR;
231 }
232 if (sscanf(argv[1], "%lg", &p->y) != 1) {
233 Tcl_AppendResult(interp, "invalid y coordinate: \"", argv[1], "\"", NULL);
234 return TCL_ERROR;
235 }
236 return TCL_OK;
237}
238
239static point center(point vertex[], size_t n) {
240 point c;
241
242 c.x = c.y = 0;
243 for (size_t i = 0; i < n; i++) {
244 c.x += vertex[i].x;
245 c.y += vertex[i].y;
246 }
247 c.x /= (int)n;
248 c.y /= (int)n;
249 return c;
250}
251
252static double distance(point p, point q)
253{
254 double dx, dy;
255
256 dx = p.x - q.x;
257 dy = p.y - q.y;
258 return hypot(dx, dy);
259}
260
261static point rotate(point c, point p, double alpha)
262{
263 point q;
264 double beta, r;
265
266 r = distance(c, p);
267 beta = atan2(p.x - c.x, p.y - c.y);
268 const double sina = sin(beta + alpha);
269 const double cosa = cos(beta + alpha);
270 q.x = c.x + r * sina;
271 q.y = c.y - r * cosa; /* adjust for tk y-down */
272 return q;
273}
274
275static point scale(point c, point p, double gain)
276{
277 point q;
278
279 q.x = c.x + gain * (p.x - c.x);
280 q.y = c.y + gain * (p.y - c.y);
281 return q;
282}
283
284static bool remove_poly(vgpane_t *vgp, int id) {
285 for (size_t i = 0; i < polys_size(&vgp->poly); i++) {
286 if (polys_get(&vgp->poly, i).id == id) {
287 free(polys_get(&vgp->poly, i).boundary.ps);
288 for (size_t j = i++; i < polys_size(&vgp->poly); i++, j++) {
289 polys_set(&vgp->poly, j, polys_get(&vgp->poly, i));
290 }
291 polys_resize(&vgp->poly, polys_size(&vgp->poly) - 1, (poly){0});
292 vc_stale(vgp);
293 return true;
294 }
295 }
296 return false;
297}
298
299static int insert_poly(Tcl_Interp *interp, vgpane_t *vgp, int id,
300 const char *vargv[], Tcl_Size vargc) {
301 poly *np;
302 int result;
303
304 np = allocpoly(vgp, id, vargc);
305 for (Tcl_Size i = 0; i < vargc; i += 2) {
306 result = scanpoint(interp, &vargv[i], &np->boundary.ps[np->boundary.pn]);
307 if (result != TCL_OK)
308 return result;
309 np->boundary.pn++;
310 }
311 make_CW(&np->boundary);
312 vc_stale(vgp);
313 return TCL_OK;
314}
315
316static void make_barriers(vgpane_t *vgp, int pp, int qp, Pedge_t **barriers,
317 size_t *n_barriers) {
318
319 size_t n = 0;
320 for (size_t i = 0; i < polys_size(&vgp->poly); i++) {
321 if (polys_get(&vgp->poly, i).id == pp)
322 continue;
323 if (polys_get(&vgp->poly, i).id == qp)
324 continue;
325 n += polys_get(&vgp->poly, i).boundary.pn;
326 }
327 Pedge_t *bar = gv_calloc(n, sizeof(Pedge_t));
328 size_t b = 0;
329 for (size_t i = 0; i < polys_size(&vgp->poly); i++) {
330 if (polys_get(&vgp->poly, i).id == pp)
331 continue;
332 if (polys_get(&vgp->poly, i).id == qp)
333 continue;
334 for (size_t j = 0; j < polys_get(&vgp->poly, i).boundary.pn; j++) {
335 size_t k = j + 1;
336 if (k >= polys_get(&vgp->poly, i).boundary.pn)
337 k = 0;
338 bar[b].a = polys_get(&vgp->poly, i).boundary.ps[j];
339 bar[b].b = polys_get(&vgp->poly, i).boundary.ps[k];
340 b++;
341 }
342 }
343 assert(b == n);
344 *barriers = bar;
345 *n_barriers = n;
346}
347
348/* append the x and y coordinates of a point to the Tcl result */
349static void appendpoint(Tcl_Interp * interp, point p)
350{
351 char buf[30];
352
353 snprintf(buf, sizeof(buf), "%g", p.x);
354 Tcl_AppendElement(interp, buf);
355 snprintf(buf, sizeof(buf), "%g", p.y);
356 Tcl_AppendElement(interp, buf);
357}
358
364static vgpane_t *find_vgpane(vgpanes_t *panes, const char *handle) {
365 assert(panes != NULL);
366 assert(handle != NULL);
367
368 size_t index;
369 if (sscanf(handle, HANDLE_FORMAT, &index) != 1) {
370 return NULL;
371 }
372 if (index >= vgpanes_size(panes)) {
373 return NULL;
374 }
375 vgpane_t *const pane = vgpanes_at(panes, index);
376 if (!pane->valid) {
377 return NULL;
378 }
379
380 return pane;
381}
382
395static void garbage_collect_vgpanes(vgpanes_t *panes) {
396 assert(panes != NULL);
397
398 // shrink list, discarding previously deallocated entries
399 while (!vgpanes_is_empty(panes)) {
400 if (!vgpanes_back(panes)->valid) {
401 (void)vgpanes_pop_back(panes);
402 }
403 }
404
405 // if this left us with none, fully deallocate to make leak checkers happy
406 if (vgpanes_is_empty(panes)) {
407 vgpanes_free(panes);
408 }
409}
410
411/* process vgpane methods */
412static int
413vgpanecmd(ClientData clientData, Tcl_Interp * interp, int argc,
414 const char *argv[])
415{
416 (void)clientData;
417
418 int result;
419 char vbuf[30];
420 vgpane_t *vgp;
421 point p, q, *ps;
422 double alpha, gain;
423 Pvector_t slopes[2];
424 Ppolyline_t line, spline;
425 Pedge_t *barriers;
426
427 if (argc < 2) {
428 Tcl_AppendResult(interp, "wrong # args: should be \"",
429 " ", argv[0], " method ?arg arg ...?\"", NULL);
430 return TCL_ERROR;
431 }
432 if (!(vgp = find_vgpane(&vgpaneTable, argv[0]))) {
433 Tcl_AppendResult(interp, "Invalid handle: \"", argv[0], "\"", NULL);
434 return TCL_ERROR;
435 }
436
437 if (strcmp(argv[1], "coords") == 0) {
438 if (argc < 3) {
439 Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
440 " ", argv[1], " id ?x1 y1 x2 y2...?\"", NULL);
441 return TCL_ERROR;
442 }
443 if (sscanf(argv[2], "%d", &polyid) != 1) {
444 Tcl_AppendResult(interp, "not an integer: ", argv[2], NULL);
445 return TCL_ERROR;
446 }
447 if (argc == 3) {
448 /* find poly and return its coordinates */
449 for (size_t i = 0; i < polys_size(&vgp->poly); i++) {
450 if (polys_get(&vgp->poly, i).id == polyid) {
451 const size_t n = polys_get(&vgp->poly, i).boundary.pn;
452 for (size_t j = 0; j < n; j++) {
453 appendpoint(interp, polys_get(&vgp->poly, i).boundary.ps[j]);
454 }
455 return TCL_OK;
456 }
457 }
458 Tcl_AppendResult(interp, " no such polygon: ", argv[2], NULL);
459 return TCL_ERROR;
460 }
461 /* accept either inline or delimited list */
462 Tcl_Size vargc;
463 const char **vargv;
464 bool vargv_needs_free = false;
465 if (argc == 4) {
466 result = Tcl_SplitList(interp, argv[3], &vargc, &vargv);
467 if (result != TCL_OK) {
468 return result;
469 }
470 vargv_needs_free = true;
471 } else {
472 vargc = (Tcl_Size)argc - 3;
473 vargv = &argv[3];
474 }
475 if (!vargc || vargc % 2) {
476 Tcl_AppendResult(interp,
477 "There must be a multiple of two terms in the list.", NULL);
478 if (vargv_needs_free) {
479 Tcl_Free((char *)vargv);
480 }
481 return TCL_ERROR;
482 }
483
484 /* remove old poly, add modified polygon to the end with
485 the same id as the original */
486
487 if (!remove_poly(vgp, polyid)) {
488 Tcl_AppendResult(interp, " no such polygon: ", argv[2], NULL);
489 if (vargv_needs_free) {
490 Tcl_Free((char *)vargv);
491 }
492 return TCL_ERROR;
493 }
494
495 result = insert_poly(interp, vgp, polyid, vargv, vargc);
496 if (vargv_needs_free) {
497 Tcl_Free((char *)vargv);
498 }
499 return result;
500
501 } else if (strcmp(argv[1], "debug") == 0) {
502 /* debug only */
503 printf("debug output goes here\n");
504 return TCL_OK;
505
506 } else if (strcmp(argv[1], "delete") == 0) {
507 /* delete a vgpane and all memory associated with it */
508 free(vgp->triangle_cmd);
509 if (vgp->vc)
510 Pobsclose(vgp->vc);
511 polys_free(&vgp->poly);
512 Tcl_DeleteCommand(interp, argv[0]);
513 vgp->valid = false;
515 return TCL_OK;
516
517 } else if (strcmp(argv[1], "find") == 0) {
518 /* find the polygon that the point is inside and return it
519 id, or null */
520 if (argc < 3) {
521 Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
522 " ", argv[1], " x y\"", NULL);
523 return TCL_ERROR;
524 }
525 const char **vargv;
526 bool vargv_needs_free = false;
527 if (argc == 3) {
528 result = Tcl_SplitList(interp, argv[2], &(Tcl_Size){0}, &vargv);
529 if (result != TCL_OK) {
530 return result;
531 }
532 vargv_needs_free = true;
533 } else {
534 vargv = &argv[2];
535 }
536 result = scanpoint(interp, &vargv[0], &p);
537 if (vargv_needs_free) {
538 Tcl_Free((char *)vargv);
539 }
540 if (result != TCL_OK)
541 return result;
542
543 /* determine the polygons (if any) that contain the point */
544 for (size_t i = 0; i < polys_size(&vgp->poly); i++) {
545 if (in_poly(polys_get(&vgp->poly, i).boundary, p)) {
546 snprintf(vbuf, sizeof(vbuf), "%d", polys_get(&vgp->poly, i).id);
547 Tcl_AppendElement(interp, vbuf);
548 }
549 }
550 return TCL_OK;
551
552 } else if (strcmp(argv[1], "insert") == 0) {
553 /* add poly to end poly list, and it coordinates to the end of
554 the point list */
555 if (argc < 3) {
556 Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
557 " ", argv[1], " x1 y1 x2 y2 ...\"", NULL);
558 return TCL_ERROR;
559 }
560 /* accept either inline or delimited list */
561 Tcl_Size vargc;
562 const char **vargv;
563 bool vargv_needs_free = false;
564 if (argc == 3) {
565 result = Tcl_SplitList(interp, argv[2], &vargc, &vargv);
566 if (result != TCL_OK) {
567 return result;
568 }
569 vargv_needs_free = true;
570 } else {
571 vargc = (Tcl_Size)argc - 2;
572 vargv = &argv[2];
573 }
574
575 if (!vargc || vargc % 2) {
576 Tcl_AppendResult(interp,
577 "There must be a multiple of two terms in the list.", NULL);
578 if (vargv_needs_free) {
579 Tcl_Free((char *)vargv);
580 }
581 return TCL_ERROR;
582 }
583
584 polyid++;
585
586 result = insert_poly(interp, vgp, polyid, vargv, vargc);
587 if (vargv_needs_free) {
588 Tcl_Free((char *)vargv);
589 }
590 if (result != TCL_OK)
591 return result;
592
593 snprintf(vbuf, sizeof(vbuf), "%d", polyid);
594 Tcl_AppendResult(interp, vbuf, NULL);
595 return TCL_OK;
596
597 } else if (strcmp(argv[1], "list") == 0) {
598 /* return list of polygon ids */
599 for (size_t i = 0; i < polys_size(&vgp->poly); i++) {
600 snprintf(vbuf, sizeof(vbuf), "%d", polys_get(&vgp->poly, i).id);
601 Tcl_AppendElement(interp, vbuf);
602 }
603 return TCL_OK;
604
605 } else if (strcmp(argv[1], "path") == 0) {
606 /* return a list of points corresponding to the shortest path
607 that does not cross the remaining "visible" polygons. */
608 if (argc < 3) {
609 Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
610 " ", argv[1], " x1 y1 x2 y2\"", NULL);
611 return TCL_ERROR;
612 }
613 Tcl_Size vargc;
614 const char **vargv;
615 bool vargv_needs_free = false;
616 if (argc == 3) {
617 result = Tcl_SplitList(interp, argv[2], &vargc, &vargv);
618 if (result != TCL_OK) {
619 return result;
620 }
621 vargv_needs_free = true;
622 } else {
623 vargc = (Tcl_Size)argc - 2;
624 vargv = &argv[2];
625 }
626 if (vargc < 4) {
627 Tcl_AppendResult(interp,
628 "invalid points: should be: \"x1 y1 x2 y2\"", NULL);
629 if (vargv_needs_free) {
630 Tcl_Free((char *)vargv);
631 }
632 return TCL_ERROR;
633 }
634 result = scanpoint(interp, &vargv[0], &p);
635 if (result != TCL_OK) {
636 if (vargv_needs_free) {
637 Tcl_Free((char *)vargv);
638 }
639 return result;
640 }
641 result = scanpoint(interp, &vargv[2], &q);
642 if (vargv_needs_free) {
643 Tcl_Free((char *)vargv);
644 }
645 if (result != TCL_OK)
646 return result;
647
648 /* only recompute the visibility graph if we have to */
649 if (vc_refresh(vgp)) {
650 Pobspath(vgp->vc, p, POLYID_UNKNOWN, q, POLYID_UNKNOWN, &line);
651
652 for (size_t i = 0; i < line.pn; i++) {
653 appendpoint(interp, line.ps[i]);
654 }
655 }
656
657 return TCL_OK;
658
659 } else if (strcmp(argv[1], "bind") == 0) {
660 if (argc < 2 || argc > 4) {
661 Tcl_AppendResult(interp, "wrong # args: should be \"",
662 argv[0], " bind triangle ?command?\"", NULL);
663 return TCL_ERROR;
664 }
665 if (argc == 2) {
666 Tcl_AppendElement(interp, "triangle");
667 return TCL_OK;
668 }
669 char *s = NULL;
670 if (strcmp(argv[2], "triangle") == 0) {
671 s = vgp->triangle_cmd;
672 if (argc == 4)
673 vgp->triangle_cmd = buildBindings(s, argv[3]);
674 } else {
675 Tcl_AppendResult(interp, "unknown event \"", argv[2],
676 "\": must be one of:\n\ttriangle.", NULL);
677 return TCL_ERROR;
678 }
679 if (argc == 3)
680 Tcl_AppendResult(interp, s, NULL);
681 return TCL_OK;
682
683 } else if (strcmp(argv[1], "bpath") == 0) {
684 /* return a list of points corresponding to the shortest path
685 that does not cross the remaining "visible" polygons. */
686 if (argc < 3) {
687 Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
688 " ", argv[1], " x1 y1 x2 y2\"", NULL);
689 return TCL_ERROR;
690 }
691 Tcl_Size vargc;
692 const char **vargv;
693 bool vargv_needs_free = false;
694 if (argc == 3) {
695 result = Tcl_SplitList(interp, argv[2], &vargc, &vargv);
696 if (result != TCL_OK) {
697 return result;
698 }
699 vargv_needs_free = true;
700 } else {
701 vargc = (Tcl_Size)argc - 2;
702 vargv = &argv[2];
703 }
704 if (vargc < 4) {
705 Tcl_AppendResult(interp,
706 "invalid points: should be: \"x1 y1 x2 y2\"", NULL);
707 return TCL_ERROR;
708 }
709
710 result = scanpoint(interp, &vargv[0], &p);
711 if (result != TCL_OK) {
712 if (vargv_needs_free) {
713 Tcl_Free((char *)vargv);
714 }
715 return result;
716 }
717 result = scanpoint(interp, &vargv[2], &q);
718 if (vargv_needs_free) {
719 Tcl_Free((char *)vargv);
720 }
721 if (result != TCL_OK)
722 return result;
723
724 /* determine the polygons (if any) that contain the endpoints */
725 int pp = POLYID_NONE;
726 int qp = POLYID_NONE;
727 for (size_t i = 0; i < polys_size(&vgp->poly); i++) {
728 const poly tpp = polys_get(&vgp->poly, i);
729 if (pp == POLYID_NONE && in_poly(tpp.boundary, p))
730 pp = (int)i;
731 if (qp == POLYID_NONE && in_poly(tpp.boundary, q))
732 qp = (int)i;
733 }
734
735 if (vc_refresh(vgp)) {
736 Pobspath(vgp->vc, p, POLYID_UNKNOWN, q, POLYID_UNKNOWN, &line);
737 size_t n_barriers;
738 make_barriers(vgp, pp, qp, &barriers, &n_barriers);
739 slopes[0].x = slopes[0].y = 0.0;
740 slopes[1].x = slopes[1].y = 0.0;
741 Proutespline(barriers, n_barriers, line, slopes, &spline);
742
743 for (size_t i = 0; i < spline.pn; i++) {
744 appendpoint(interp, spline.ps[i]);
745 }
746 }
747 return TCL_OK;
748
749 } else if (strcmp(argv[1], "bbox") == 0) {
750 if (argc < 3) {
751 Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
752 " ", argv[1], " id\"", NULL);
753 return TCL_ERROR;
754 }
755 if (sscanf(argv[2], "%d", &polyid) != 1) {
756 Tcl_AppendResult(interp, "not an integer: ", argv[2], NULL);
757 return TCL_ERROR;
758 }
759 for (size_t i = 0; i < polys_size(&vgp->poly); i++) {
760 if (polys_get(&vgp->poly, i).id == polyid) {
761 Ppoly_t pp = polys_get(&vgp->poly, i).boundary;
762 point LL, UR;
763 LL = UR = pp.ps[0];
764 for (size_t j = 1; j < pp.pn; j++) {
765 p = pp.ps[j];
766 UR.x = fmax(UR.x, p.x);
767 UR.y = fmax(UR.y, p.y);
768 LL.x = fmin(LL.x, p.x);
769 LL.y = fmin(LL.y, p.y);
770 }
771 appendpoint(interp, LL);
772 appendpoint(interp, UR);
773 return TCL_OK;
774 }
775 }
776 Tcl_AppendResult(interp, " no such polygon: ", argv[2], NULL);
777 return TCL_ERROR;
778
779 } else if (strcmp(argv[1], "center") == 0) {
780 if (argc < 3) {
781 Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
782 " ", argv[1], " id\"", NULL);
783 return TCL_ERROR;
784 }
785 if (sscanf(argv[2], "%d", &polyid) != 1) {
786 Tcl_AppendResult(interp, "not an integer: ", argv[2], NULL);
787 return TCL_ERROR;
788 }
789 for (size_t i = 0; i < polys_size(&vgp->poly); i++) {
790 if (polys_get(&vgp->poly, i).id == polyid) {
791 appendpoint(interp, center(polys_get(&vgp->poly, i).boundary.ps,
792 polys_get(&vgp->poly, i).boundary.pn));
793 return TCL_OK;
794 }
795 }
796 Tcl_AppendResult(interp, " no such polygon: ", argv[2], NULL);
797 return TCL_ERROR;
798
799 } else if (strcmp(argv[1], "triangulate") == 0) {
800 if (argc < 3) {
801 Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
802 " ", argv[1], " id\"", NULL);
803 return TCL_ERROR;
804 }
805
806 if (sscanf(argv[2], "%d", &polyid) != 1) {
807 Tcl_AppendResult(interp, "not an integer: ", argv[2], NULL);
808 return TCL_ERROR;
809 }
810
811 for (size_t i = 0; i < polys_size(&vgp->poly); i++) {
812 if (polys_get(&vgp->poly, i).id == polyid) {
813 Ppoly_t *polygon = &polys_at(&vgp->poly, i)->boundary;
814 if (polygon->pn < 3) {
815 Tcl_AppendResult(interp, "polygon ", argv[2], " has fewer than 3 points "
816 "and thus cannot be triangulated", NULL);
817 return TCL_ERROR;
818 }
820 return TCL_OK;
821 }
822 }
823 Tcl_AppendResult(interp, " no such polygon: ", argv[2], NULL);
824 return TCL_ERROR;
825 } else if (strcmp(argv[1], "rotate") == 0) {
826 if (argc < 4) {
827 Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
828 " ", argv[1], " id alpha\"", NULL);
829 return TCL_ERROR;
830 }
831 if (sscanf(argv[2], "%d", &polyid) != 1) {
832 Tcl_AppendResult(interp, "not an integer: ", argv[2], NULL);
833 return TCL_ERROR;
834 }
835 if (sscanf(argv[3], "%lg", &alpha) != 1) {
836 Tcl_AppendResult(interp, "not an angle in radians: ", argv[3], NULL);
837 return TCL_ERROR;
838 }
839 for (size_t i = 0; i < polys_size(&vgp->poly); i++) {
840 if (polys_get(&vgp->poly, i).id == polyid) {
841 const size_t n = polys_get(&vgp->poly, i).boundary.pn;
842 ps = polys_get(&vgp->poly, i).boundary.ps;
843 p = center(ps, n);
844 for (size_t j = 0; j < n; j++) {
845 appendpoint(interp, rotate(p, ps[j], alpha));
846 }
847 return TCL_OK;
848 }
849 }
850 Tcl_AppendResult(interp, " no such polygon: ", argv[2], NULL);
851 return TCL_ERROR;
852
853 } else if (strcmp(argv[1], "scale") == 0) {
854 if (argc < 4) {
855 Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
856 " ", argv[1], " id gain\"", NULL);
857 return TCL_ERROR;
858 }
859 if (sscanf(argv[2], "%d", &polyid) != 1) {
860 Tcl_AppendResult(interp, "not an integer: ", argv[2], NULL);
861 return TCL_ERROR;
862 }
863 if (sscanf(argv[3], "%lg", &gain) != 1) {
864 Tcl_AppendResult(interp, "not a number: ", argv[3], NULL);
865 return TCL_ERROR;
866 }
867 for (size_t i = 0; i < polys_size(&vgp->poly); i++) {
868 if (polys_get(&vgp->poly, i).id == polyid) {
869 const size_t n = polys_get(&vgp->poly, i).boundary.pn;
870 ps = polys_get(&vgp->poly, i).boundary.ps;
871 p = center(ps, n);
872 for (size_t j = 0; j < n; j++) {
873 appendpoint(interp, scale(p, ps[j], gain));
874 }
875 return TCL_OK;
876 }
877 }
878 Tcl_AppendResult(interp, " no such polygon: ", argv[2], NULL);
879 return TCL_ERROR;
880
881 } else if (strcmp(argv[1], "remove") == 0) {
882 if (argc < 3) {
883 Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
884 " ", argv[1], " id\"", NULL);
885 return TCL_ERROR;
886 }
887 if (sscanf(argv[2], "%d", &polyid) != 1) {
888 Tcl_AppendResult(interp, "not an integer: ", argv[2], NULL);
889 return TCL_ERROR;
890 }
891
892 if (remove_poly(vgp, polyid))
893 return TCL_OK;
894
895 Tcl_AppendResult(interp, " no such polygon: ", argv[2], NULL);
896 return TCL_ERROR;
897 }
898
899 Tcl_AppendResult(interp, "bad method \"", argv[1],
900 "\" must be one of:",
901 "\n\tbbox, bind, bpath, center, coords, delete, find,",
902 "\n\tinsert, list, path, remove, rotate, scale, triangulate.", NULL);
903 return TCL_ERROR;
904}
905
906static int
907vgpane(ClientData clientData, Tcl_Interp * interp, int argc, const char *argv[])
908{
909 (void)clientData;
910 (void)argc;
911 (void)argv;
912
913 const vgpane_t vg = {.interp = interp};
914 vgpanes_append(&vgpaneTable, vg);
915 vgpane_t *const vgp = vgpanes_back(&vgpaneTable);
916 vgp->index = vgpanes_size(&vgpaneTable) - 1;
917 vgp->valid = true;
918
919 agxbuf buffer = {0};
920 agxbprint(&buffer, HANDLE_FORMAT, vgp->index);
921 const char *const vbuf = agxbuse(&buffer);
922
923 Tcl_CreateCommand(interp, vbuf, vgpanecmd, NULL, NULL);
924 Tcl_AppendResult(interp, vbuf, NULL);
925 agxbfree(&buffer);
926 return TCL_OK;
927}
928
929int Tclpathplan_Init(Tcl_Interp *interp);
930int Tclpathplan_Init(Tcl_Interp * interp)
931{
932#ifdef USE_TCL_STUBS
933 if (Tcl_InitStubs(interp, TCL_VERSION, 0) == NULL) {
934 return TCL_ERROR;
935 }
936#else
937 if (Tcl_PkgRequire(interp, "Tcl", TCL_VERSION, 0) == NULL) {
938 return TCL_ERROR;
939 }
940#endif
941 // inter-release Graphviz versions have a number including '~dev.' that does
942 // not comply with TCL version number rules, so replace this with 'b'
943 char adjusted_version[sizeof(PACKAGE_VERSION)] = PACKAGE_VERSION;
944 char *tilde_dev = strstr(adjusted_version, "~dev.");
945 if (tilde_dev != NULL) {
946 *tilde_dev = 'b';
947 memmove(tilde_dev + 1, tilde_dev + strlen("~dev."),
948 strlen(tilde_dev + strlen("~dev.")) + 1);
949 }
950 if (Tcl_PkgProvide(interp, "Tclpathplan", adjusted_version) != TCL_OK) {
951 return TCL_ERROR;
952 }
953
954 Tcl_CreateCommand(interp, "vgpane", vgpane, NULL, NULL);
955
956 return TCL_OK;
957}
958
959int Tclpathplan_SafeInit(Tcl_Interp *interp);
960int Tclpathplan_SafeInit(Tcl_Interp * interp)
961{
962 return Tclpathplan_Init(interp);
963}
static void agxbfree(agxbuf *xb)
free any malloced resources
Definition agxbuf.h:78
static size_t agxbput_n(agxbuf *xb, const char *s, size_t ssz)
append string s of length ssz into xb
Definition agxbuf.h:250
static int agxbprint(agxbuf *xb, const char *fmt,...)
Printf-style output to an agxbuf.
Definition agxbuf.h:234
static WUR char * agxbuse(agxbuf *xb)
Definition agxbuf.h:307
static size_t agxblen(const agxbuf *xb)
return number of characters currently stored
Definition agxbuf.h:89
static int agxbputc(agxbuf *xb, char c)
add character to buffer
Definition agxbuf.h:277
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
vconfig_t * Pobsopen(Ppoly_t **obs, int n_obs)
Definition cvt.c:26
void Pobsclose(vconfig_t *config)
Definition cvt.c:87
void Pobspath(vconfig_t *config, Ppoint_t p0, int poly0, Ppoint_t p1, int poly1, Ppolyline_t *output_route)
Definition cvt.c:100
static float dy
Definition draw.c:37
static float dx
Definition draw.c:36
void free(void *)
node NULL
Definition grammar.y:163
static uint64_t id
Definition gv2gml.c:40
bool in_poly(const Ppoly_t poly, Ppoint_t q)
Definition inpoly.c:24
int Plegal_arrangement(Ppoly_t **polys, int n_polys)
Definition legal.c:413
#define DEFINE_LIST(name, type)
Definition list.h:22
static int * ps
Definition lu.c:51
void make_CW(Ppoly_t *poly)
Definition makecw.c:24
NEATOPROCS_API void s1(graph_t *, node_t *)
Definition stuff.c:671
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
#define alpha
Definition shapes.c:4058
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:27
int y
Definition geom.h:27
int x
Definition geom.h:27
Ppoly_t boundary
Definition tclpathplan.c:52
Definition legal.c:31
char * triangle_cmd
Definition tclpathplan.c:64
size_t index
position within allocated handles list
Definition tclpathplan.c:65
Tcl_Interp * interp
Definition tclpathplan.c:63
polys_t poly
Definition tclpathplan.c:61
vconfig_t * vc
Definition tclpathplan.c:62
bool valid
is this pane currently allocated?
Definition tclpathplan.c:66
#define Tcl_Size
Definition tcl-compat.h:33
static void vc_stale(vgpane_t *vgp)
Definition tclpathplan.c:83
static int vgpane(ClientData clientData, Tcl_Interp *interp, int argc, const char *argv[])
int Tclpathplan_Init(Tcl_Interp *interp)
static char * buildBindings(char *s1, const char *s2)
static int vc_refresh(vgpane_t *vgp)
Definition tclpathplan.c:91
static void garbage_collect_vgpanes(vgpanes_t *panes)
static vgpanes_t vgpaneTable
Definition tclpathplan.c:71
static void appendpoint(Tcl_Interp *interp, point p)
static point scale(point c, point p, double gain)
static void expandPercentsEval(Tcl_Interp *interp, char *before, size_t vgcanvasHandle, int npts, const point *ppos)
static void triangle_callback(void *vgparg, const point pqr[])
int Tclpathplan_SafeInit(Tcl_Interp *interp)
static vgpane_t * find_vgpane(vgpanes_t *panes, const char *handle)
struct poly_s poly
#define HANDLE_FORMAT
printf format for TCL handles
Definition tclpathplan.c:58
static void make_barriers(vgpane_t *vgp, int pp, int qp, Pedge_t **barriers, size_t *n_barriers)
static void dgsprintxy(agxbuf *result, int npts, const point p[])
static int insert_poly(Tcl_Interp *interp, vgpane_t *vgp, int id, const char *vargv[], Tcl_Size vargc)
static int vgpanecmd(ClientData clientData, Tcl_Interp *interp, int argc, const char *argv[])
static point center(point vertex[], size_t n)
static int polyid
Definition tclpathplan.c:73
static double distance(point p, point q)
static point rotate(point c, point p, double alpha)
Ppoint_t point
Definition tclpathplan.c:48
#define Tcl_GetStringResult(interp)
Definition tclpathplan.c:44
static int scanpoint(Tcl_Interp *interp, const char *argv[], point *p)
static bool remove_poly(vgpane_t *vgp, int id)
static poly * allocpoly(vgpane_t *vgp, int id, Tcl_Size npts)
Definition tclpathplan.c:75
TRI_API int Ptriangulate(Ppoly_t *polygon, void(*fn)(void *closure, const Ppoint_t tri[]), void *vc)
Definition grammar.c:93
#define POLYID_UNKNOWN
Definition vispath.h:51
#define POLYID_NONE
Definition vispath.h:50