Graphviz 13.0.0~dev.20241225.0935
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
cvt.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#include <assert.h>
12#include <stdio.h>
13#include <stdlib.h>
14#include <limits.h>
15#include <pathplan/vis.h>
16#include <util/alloc.h>
17
19
20#ifdef DEBUG
21static void printVconfig(vconfig_t * cp);
22static void printVis(char *lbl, COORD * vis, int n);
23static void printDad(int *vis, int n);
24#endif
25
26vconfig_t *Pobsopen(Ppoly_t ** obs, int n_obs)
27{
28 vconfig_t *rv;
29 int poly_i, pt_i, i;
30 int start, end;
31
32 rv = malloc(sizeof(vconfig_t));
33 if (!rv) {
34 return NULL;
35 }
36
37 /* get storage */
38 size_t n = 0;
39 for (poly_i = 0; poly_i < n_obs; poly_i++) {
40 n += obs[poly_i]->pn;
41 }
42 if (n > INT_MAX) { // will this overflow rv->N?
43 free(rv);
44 return NULL;
45 }
46 rv->P = calloc(n, sizeof(Ppoint_t));
47 assert(n_obs >= 0);
48 rv->start = calloc((size_t)n_obs + 1, sizeof(int));
49 rv->next = calloc(n, sizeof(int));
50 rv->prev = calloc(n, sizeof(int));
51 rv->N = (int)n;
52 rv->Npoly = n_obs;
53
54 // bail out if any above allocations failed
55 if (rv->start == NULL || (n > 0 && (rv->P == NULL ||
56 rv->next == NULL ||
57 rv->prev == NULL))) {
58 free(rv->prev);
59 free(rv->next);
60 free(rv->start);
61 free(rv->P);
62 free(rv);
63 return NULL;
64 }
65
66 /* build arrays */
67 i = 0;
68 for (poly_i = 0; poly_i < n_obs; poly_i++) {
69 start = i;
70 rv->start[poly_i] = start;
71 assert(obs[poly_i]->pn <= INT_MAX);
72 end = start + (int)obs[poly_i]->pn - 1;
73 for (pt_i = 0; pt_i < (int)obs[poly_i]->pn; pt_i++) {
74 rv->P[i] = obs[poly_i]->ps[pt_i];
75 rv->next[i] = i + 1;
76 rv->prev[i] = i - 1;
77 i++;
78 }
79 rv->next[end] = start;
80 rv->prev[start] = end;
81 }
82 rv->start[poly_i] = i;
83 visibility(rv);
84 return rv;
85}
86
87void Pobsclose(vconfig_t * config)
88{
89 free(config->P);
90 free(config->start);
91 free(config->next);
92 free(config->prev);
93 if (config->vis) {
94 free(config->vis[0]);
95 free(config->vis);
96 }
97 free(config);
98}
99
100void Pobspath(vconfig_t *config, Ppoint_t p0, int poly0, Ppoint_t p1, int poly1,
101 Ppolyline_t *output_route) {
102 int i, *dad;
103 size_t opn;
104 Ppoint_t *ops;
105 COORD *ptvis0, *ptvis1;
106
107 ptvis0 = ptVis(config, poly0, p0);
108 ptvis1 = ptVis(config, poly1, p1);
109
110 dad = makePath(p0, poly0, ptvis0, p1, poly1, ptvis1, config);
111
112 opn = 1;
113 for (i = dad[config->N]; i != config->N + 1; i = dad[i])
114 opn++;
115 opn++;
116 ops = gv_calloc(opn, sizeof(Ppoint_t));
117
118 size_t j = opn - 1;
119 ops[j--] = p1;
120 for (i = dad[config->N]; i != config->N + 1; i = dad[i])
121 ops[j--] = config->P[i];
122 ops[j] = p0;
123 assert(j == 0);
124
125#ifdef DEBUG
126 printVconfig(config);
127 printVis("p", ptvis0, config->N + 1);
128 printVis("q", ptvis1, config->N + 1);
129 printDad(dad, config->N + 1);
130#endif
131
132 free(ptvis0);
133 free(ptvis1);
134
135 output_route->pn = opn;
136 output_route->ps = ops;
137 free(dad);
138}
139
140#ifdef DEBUG
141static void printVconfig(vconfig_t * cp)
142{
143 int i, j;
144 int *next, *prev;
145 Ppoint_t *pts;
146 array2 arr;
147
148 next = cp->next;
149 prev = cp->prev;
150 pts = cp->P;
151 arr = cp->vis;
152
153 printf("this next prev point\n");
154 for (i = 0; i < cp->N; i++)
155 printf("%3d %3d %3d (%3g,%3g)\n", i, next[i], prev[i],
156 pts[i].x, pts[i].y);
157
158 printf("\n\n");
159
160 for (i = 0; i < cp->N; i++) {
161 for (j = 0; j < cp->N; j++)
162 printf("%4.1f ", arr[i][j]);
163 printf("\n");
164 }
165}
166
167static void printVis(char *lbl, COORD * vis, int n)
168{
169 int i;
170
171 printf("%s: ", lbl);
172 for (i = 0; i < n; i++)
173 printf("%4.1f ", vis[i]);
174 printf("\n");
175}
176
177static void printDad(int *vis, int n)
178{
179 int i;
180
181 printf(" ");
182 for (i = 0; i < n; i++) {
183 printf("%3d ", i);
184 }
185 printf("\n");
186 printf("dad: ");
187 for (i = 0; i < n; i++) {
188 printf("%3d ", vis[i]);
189 }
190 printf("\n");
191}
192#endif
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
Ppoint_t ilcoord_t
Definition cvt.c:18
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
void * malloc(YYSIZE_T)
void free(void *)
node NULL
Definition grammar.y:163
void makePath(unsigned n, edgefn ef)
$2 u p prev
Definition htmlparse.y:297
double COORD
Definition pathutil.h:31
static size_t opn
Definition route.c:34
static Ppoint_t * ops
Definition route.c:33
size_t pn
Definition pathgeom.h:47
Ppoint_t * ps
Definition pathgeom.h:46
int N
Definition vis.h:31
Ppoint_t * P
Definition vis.h:32
int * start
Definition vis.h:33
int * next
Definition vis.h:34
array2 vis
Definition vis.h:38
int * prev
Definition vis.h:35
int Npoly
Definition vis.h:30
VIS_API void visibility(vconfig_t *)
Definition visibility.c:211
COORD ** array2
Definition vis.h:25
VIS_API COORD * ptVis(vconfig_t *, int, Ppoint_t)
Definition visibility.c:245