Graphviz  2.41.20170921.2350
cvt.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 
15 #include <stdio.h>
16 #include "vis.h"
17 
18 #ifdef DMALLOC
19 #include "dmalloc.h"
20 #endif
21 
23 
24 #ifdef DEBUG
25 static void printVconfig(vconfig_t * cp);
26 static void printVis(char *lbl, COORD * vis, int n);
27 static void printDad(int *vis, int n);
28 #endif
29 
30 #ifdef GASP
31 static void gasp_print_obstacles(vconfig_t * conf);
32 static void gasp_print_point(Ppoint_t p);
33 static void gasp_print_polyline(Ppolyline_t * route);
34 static void gasp_print_bezier(Ppolyline_t * route);
35 #endif
36 
37 #if 0 /* not used */
38 static void *myrealloc(void *p, size_t newsize)
39 {
40  void *rv;
41 
42  if (p == (void *) 0)
43  rv = malloc(newsize);
44  else
45  rv = realloc(p, newsize);
46  return rv;
47 }
48 #endif
49 
50 static void *mymalloc(size_t newsize)
51 {
52  void *rv;
53 
54  if (newsize > 0)
55  rv = malloc(newsize);
56  else
57  rv = (void *) 0;
58  return rv;
59 }
60 
61 
62 vconfig_t *Pobsopen(Ppoly_t ** obs, int n_obs)
63 {
64  vconfig_t *rv;
65  int poly_i, pt_i, i, n;
66  int start, end;
67 
68  rv = malloc(sizeof(vconfig_t));
69  if (!rv) {
70  return NULL;
71  }
72 
73  /* get storage */
74  n = 0;
75  for (poly_i = 0; poly_i < n_obs; poly_i++)
76  n = n + obs[poly_i]->pn;
77  rv->P = mymalloc(n * sizeof(Ppoint_t));
78  rv->start = mymalloc((n_obs + 1) * sizeof(int));
79  rv->next = mymalloc(n * sizeof(int));
80  rv->prev = mymalloc(n * sizeof(int));
81  rv->N = n;
82  rv->Npoly = n_obs;
83 
84  /* build arrays */
85  i = 0;
86  for (poly_i = 0; poly_i < n_obs; poly_i++) {
87  start = i;
88  rv->start[poly_i] = start;
89  end = start + obs[poly_i]->pn - 1;
90  for (pt_i = 0; pt_i < obs[poly_i]->pn; pt_i++) {
91  rv->P[i] = obs[poly_i]->ps[pt_i];
92  rv->next[i] = i + 1;
93  rv->prev[i] = i - 1;
94  i++;
95  }
96  rv->next[end] = start;
97  rv->prev[start] = end;
98  }
99  rv->start[poly_i] = i;
100  visibility(rv);
101  return rv;
102 }
103 
104 void Pobsclose(vconfig_t * config)
105 {
106  free(config->P);
107  free(config->start);
108  free(config->next);
109  free(config->prev);
110  if (config->vis) {
111  free(config->vis[0]);
112  free(config->vis);
113  }
114  free(config);
115 }
116 
117 int Pobspath(vconfig_t * config, Ppoint_t p0, int poly0, Ppoint_t p1,
118  int poly1, Ppolyline_t * output_route)
119 {
120  int i, j, *dad;
121  size_t opn;
122  Ppoint_t *ops;
123  COORD *ptvis0, *ptvis1;
124 
125 #ifdef GASP
126  gasp_print_obstacles(config);
127 #endif
128  ptvis0 = ptVis(config, poly0, p0);
129  ptvis1 = ptVis(config, poly1, p1);
130 
131 #ifdef GASP
132  gasp_print_point(p0);
133  gasp_print_point(p1);
134 #endif
135  dad = makePath(p0, poly0, ptvis0, p1, poly1, ptvis1, config);
136 
137  opn = 1;
138  for (i = dad[config->N]; i != config->N + 1; i = dad[i])
139  opn++;
140  opn++;
141  ops = malloc(opn * sizeof(Ppoint_t));
142 
143  j = opn - 1;
144  ops[j--] = p1;
145  for (i = dad[config->N]; i != config->N + 1; i = dad[i])
146  ops[j--] = config->P[i];
147  ops[j] = p0;
148  assert(j == 0);
149 
150 #ifdef DEBUG
151  printVconfig(config);
152  printVis("p", ptvis0, config->N + 1);
153  printVis("q", ptvis1, config->N + 1);
154  printDad(dad, config->N + 1);
155 #endif
156 
157  if (ptvis0)
158  free(ptvis0);
159  if (ptvis1)
160  free(ptvis1);
161 
162  output_route->pn = opn;
163  output_route->ps = ops;
164 #ifdef GASP
165  gasp_print_polyline(output_route);
166 #endif
167  free(dad);
168  return TRUE;
169 }
170 
171 int Pobsbarriers(vconfig_t * config, Pedge_t ** barriers, int *n_barriers)
172 {
173  int i, j;
174 
175  *barriers = malloc(config->N * sizeof(Pedge_t));
176  *n_barriers = config->N;
177 
178  for (i = 0; i < config->N; i++) {
179  barriers[i]->a.x = config->P[i].x;
180  barriers[i]->a.y = config->P[i].y;
181  j = config->next[i];
182  barriers[i]->b.x = config->P[j].x;
183  barriers[i]->b.y = config->P[j].y;
184  }
185  return 1;
186 }
187 
188 #ifdef DEBUG
189 static void printVconfig(vconfig_t * cp)
190 {
191  int i, j;
192  int *next, *prev;
193  Ppoint_t *pts;
194  array2 arr;
195 
196  next = cp->next;
197  prev = cp->prev;
198  pts = cp->P;
199  arr = cp->vis;
200 
201  printf("this next prev point\n");
202  for (i = 0; i < cp->N; i++)
203  printf("%3d %3d %3d (%3g,%3g)\n", i, next[i], prev[i],
204  pts[i].x, pts[i].y);
205 
206  printf("\n\n");
207 
208  for (i = 0; i < cp->N; i++) {
209  for (j = 0; j < cp->N; j++)
210  printf("%4.1f ", arr[i][j]);
211  printf("\n");
212  }
213 }
214 
215 static void printVis(char *lbl, COORD * vis, int n)
216 {
217  int i;
218 
219  printf("%s: ", lbl);
220  for (i = 0; i < n; i++)
221  printf("%4.1f ", vis[i]);
222  printf("\n");
223 }
224 
225 static void printDad(int *vis, int n)
226 {
227  int i;
228 
229  printf(" ");
230  for (i = 0; i < n; i++) {
231  printf("%3d ", i);
232  }
233  printf("\n");
234  printf("dad: ");
235  for (i = 0; i < n; i++) {
236  printf("%3d ", vis[i]);
237  }
238  printf("\n");
239 }
240 #endif
241 
242 #ifdef GASP
243 
244 static Ppoint_t Bezpt[1000];
245 static int Bezctr;
246 
247 static void addpt(Ppoint_t p)
248 {
249  if ((Bezctr == 0) ||
250  (Bezpt[Bezctr - 1].x != p.x) || (Bezpt[Bezctr - 1].y != p.y))
251  Bezpt[Bezctr++] = p;
252 }
253 
254 #define W_DEGREE 5
255 static ilcoord_t Bezier(ilcoord_t * V, int degree, double t,
256  ilcoord_t * Left, ilcoord_t * Right)
257 {
258  int i, j; /* Index variables */
259  ilcoord_t Vtemp[W_DEGREE + 1][W_DEGREE + 1];
260 
261  /* Copy control points */
262  for (j = 0; j <= degree; j++) {
263  Vtemp[0][j] = V[j];
264  }
265 
266  /* Triangle computation */
267  for (i = 1; i <= degree; i++) {
268  for (j = 0; j <= degree - i; j++) {
269  Vtemp[i][j].x =
270  (1.0 - t) * Vtemp[i - 1][j].x + t * Vtemp[i - 1][j + 1].x;
271  Vtemp[i][j].y =
272  (1.0 - t) * Vtemp[i - 1][j].y + t * Vtemp[i - 1][j + 1].y;
273  }
274  }
275 
276  if (Left != NIL(ilcoord_t *))
277  for (j = 0; j <= degree; j++)
278  Left[j] = Vtemp[j][0];
279  if (Right != NIL(ilcoord_t *))
280  for (j = 0; j <= degree; j++)
281  Right[j] = Vtemp[degree - j][j];
282  return (Vtemp[degree][0]);
283 }
284 
285 static void append_bezier(Ppoint_t * bezier)
286 {
287  double a;
288  ilcoord_t left[4], right[4];
289 
290  a = fabs(area2(bezier[0], bezier[1], bezier[2]))
291  + fabs(area2(bezier[2], bezier[3], bezier[0]));
292  if (a < .5) {
293  addpt(bezier[0]);
294  addpt(bezier[3]);
295  } else {
296  (void) Bezier(bezier, 3, .5, left, right);
297  append_bezier(left);
298  append_bezier(right);
299  }
300 }
301 
302 FILE *GASPout = stderr;
303 
304 static void gasp_print_point(Ppoint_t p)
305 {
306  fprintf(GASPout, "%3g %3g\n", p.x, p.y);
307 }
308 
309 void gasp_print_obstacles(vconfig_t * conf)
310 {
311  int i, j;
312  Ppoly_t poly;
313 
314  fprintf(GASPout, "%d\n", conf->Npoly);
315  for (i = 0; i < conf->Npoly; i++) {
316  poly.ps = &(conf->P[conf->start[i]]);
317  poly.pn = conf->start[i + 1] - conf->start[i];
318  fprintf(GASPout, "%d\n", poly.pn);
319  for (j = 0; j < poly.pn; j++)
320  gasp_print_point(poly.ps[j]);
321  }
322 }
323 
324 void gasp_print_bezier(Ppolyline_t * route)
325 {
326  int i;
327 
328  Bezctr = 0;
329  for (i = 0; i + 3 < route->pn; i += 3)
330  append_bezier(route->ps + i);
331  fprintf(GASPout, "%d\n", Bezctr);
332  for (i = 0; i < Bezctr; i++)
333  gasp_print_point(Bezpt[i]);
334  Bezctr = 0;
335 }
336 
337 void gasp_print_polyline(Ppolyline_t * route)
338 {
339  int i;
340 
341  fprintf(GASPout, "%d\n", route->pn);
342  for (i = 0; i < route->pn; i++)
343  gasp_print_point(route->ps[i]);
344 }
345 #endif
COORD * ptVis(vconfig_t *, int, Ppoint_t)
Definition: visibility.c:339
array2 vis
Definition: vis.h:47
int pn
Definition: pathgeom.h:36
int * prev
Definition: vis.h:44
int Npoly
Definition: vis.h:39
int * start
Definition: vis.h:42
Ppoint_t * P
Definition: vis.h:41
Ppoint_t ilcoord_t
Definition: cvt.c:22
double x
Definition: pathgeom.h:27
#define assert(x)
Definition: cghdr.h:47
double COORD
Definition: pathutil.h:41
COORD area2(Ppoint_t, Ppoint_t, Ppoint_t)
Definition: visibility.c:56
void visibility(vconfig_t *)
Definition: visibility.c:305
Ppoint_t b
Definition: pathgeom.h:42
int N
Definition: vis.h:40
int Pobsbarriers(vconfig_t *config, Pedge_t **barriers, int *n_barriers)
Definition: cvt.c:171
#define NIL(t)
Definition: dthdr.h:13
COORD ** array2
Definition: vis.h:29
vconfig_t * Pobsopen(Ppoly_t **obs, int n_obs)
Definition: cvt.c:62
htmllabel_t * lbl
Definition: htmlparse.c:81
void Pobsclose(vconfig_t *config)
Definition: cvt.c:104
Ppoint_t * ps
Definition: pathgeom.h:35
pointf Bezier(pointf *V, int degree, double t, pointf *Left, pointf *Right)
Definition: utils.c:221
void addpt(Point *c, Point a, Point b)
Definition: geometry.c:51
#define NULL
Definition: logic.h:39
#define W_DEGREE
Definition: utils.c:212
int * makePath(Ppoint_t p, int pp, COORD *pvis, Ppoint_t q, int qp, COORD *qvis, vconfig_t *conf)
Definition: shortestpth.c:100
#define right(i)
Definition: closest.c:87
Definition: types.h:108
Ppoint_t a
Definition: pathgeom.h:42
int Pobspath(vconfig_t *config, Ppoint_t p0, int poly0, Ppoint_t p1, int poly1, Ppolyline_t *output_route)
Definition: cvt.c:117
#define left
Definition: dthdr.h:16
Definition: pathgeom.h:26
double y
Definition: pathgeom.h:27
int * next
Definition: vis.h:43
Definition: vis.h:38
#define TRUE
Definition: cgraph.h:38