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