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
22typedef Ppoint_t ilcoord_t;
23
24#ifdef DEBUG
25static void printVconfig(vconfig_t * cp);
26static void printVis(char *lbl, COORD * vis, int n);
27static void printDad(int *vis, int n);
28#endif
29
30#ifdef GASP
31static void gasp_print_obstacles(vconfig_t * conf);
32static void gasp_print_point(Ppoint_t p);
33static void gasp_print_polyline(Ppolyline_t * route);
34static void gasp_print_bezier(Ppolyline_t * route);
35#endif
36
37#if 0 /* not used */
38static 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
50static 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
62vconfig_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
104void 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
117int 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
171int 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
189static 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
215static 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
225static 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
244static Ppoint_t Bezpt[1000];
245static int Bezctr;
246
247static 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
255static 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
285static 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
302FILE *GASPout = stderr;
303
304static void gasp_print_point(Ppoint_t p)
305{
306 fprintf(GASPout, "%3g %3g\n", p.x, p.y);
307}
308
309void 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
324void 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
337void 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
346