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