13 #define debug_printf(args...) printf(args)
15 #define debug_printf(args...)
18 /* default bounding box is (0,0) (100,100) */
19 static int32_t bbox_x1 = 0;
20 static int32_t bbox_y1 = 0;
21 static int32_t bbox_x2 = 100;
22 static int32_t bbox_y2 = 100;
24 void polygon_set_boundingbox(int32_t x1, int32_t y1, int32_t x2, int32_t y2)
32 uint8_t is_in_boundingbox(const point_t *p)
34 if (p->x >= bbox_x1 &&
42 /* Test if a point is in a polygon (including edges)
48 is_in_poly(const point_t *p, poly_t *pol)
56 for (i=0;i<pol->l;i++) {
57 /* is a polygon point */
58 if (p->x == pol->pts[i].x && p->y == pol->pts[i].y)
62 for (i=0;i<pol->l;i++) {
65 v.x = pol->pts[ii].x-p->x;
66 v.y = pol->pts[ii].y-p->y;
67 w.x = pol->pts[i].x-p->x;
68 w.y = pol->pts[i].y-p->y;
69 z = vect_pvect_sign(&v, &w );
79 /* public wrapper for is_in_poly() */
80 uint8_t is_point_in_poly(poly_t *pol, int16_t x, int16_t y)
85 return is_in_poly(&p, pol);
88 /* Is segment crossing polygon? (including edges)
92 * 3 touch out (a segment boundary is on a polygon edge,
93 * and the second segment boundary is out of the polygon)
96 is_crossing_poly(point_t p1, point_t p2, point_t *intersect_pt,
105 debug_printf("%" PRIi32 " %" PRIi32 " -> %" PRIi32 " %" PRIi32 " crossing poly %p ?\n",
106 p1.x, p1.y, p2.x, p2.y, pol);
107 debug_printf("poly is : ");
108 for (i=0; i<pol->l; i++) {
109 debug_printf("%" PRIi32 ",%" PRIi32 " ", pol->pts[i].x, pol->pts[i].y);
113 for (i=0;i<pol->l;i++) {
114 ret = intersect_segment(&p1, &p2, &pol->pts[i], &pol->pts[(i+1)%pol->l], &p);
115 debug_printf("%" PRIi32 ",%" PRIi32 " -> %" PRIi32 ",%" PRIi32
116 " return %d\n", pol->pts[i].x, pol->pts[i].y,
117 pol->pts[(i+1)%pol->l].x, pol->pts[(i+1)%pol->l].y, ret);
145 ret1 = is_in_poly(&p1, pol);
147 ret2 = is_in_poly(&p2, pol);
149 debug_printf("is in poly: p1 %d p2: %d cpt %d\r\n", ret1, ret2, cpt);
151 debug_printf("p intersect: %"PRIi32" %"PRIi32"\r\n", p.x, p.y);
155 if (ret1==1 || ret2==1)
162 if (ret1==1 || ret2==1)
167 if (ret1==1 || ret2==1)
169 if (ret1==0 || ret2==0)
177 /* Giving the list of poygons, compute the graph of "visibility rays".
178 * This rays array is composed of indexes representing 2 polygon
179 * vertices that can "see" each others:
181 * i : the first polygon number in the input polygon list
182 * i+1: the vertex index of this polygon (vertex 1)
183 * i+2: the second polygon number in the input polygon list
184 * i+3: the vertex index of this polygon (vertex 2)
186 * Here, vertex 1 can "see" vertex 2 in our visibility graph
188 * As the first polygon is not a real polygon but the start/stop
189 * point, the polygon is NOT an ocluding polygon (but its vertices
190 * are used to compute visibility to start/stop points)
194 calc_rays(poly_t *polys, uint8_t npolys, uint8_t *rays)
196 uint8_t i, ii, index;
202 /* !\\first poly is the start stop point */
204 /* 1: calc inner polygon rays
205 * compute for each polygon edges, if the vertices can see each others
206 * (usefull if interlaced polygons)
209 for (i=0; i<npolys; i++) {
210 debug_printf("%s(): poly num %d/%d\n", __FUNCTION__, i, npolys);
211 for (ii=0; ii<polys[i].l; ii++) {
212 debug_printf("%s() line num %d/%d\n", __FUNCTION__, ii, polys[i].l);
213 if (! is_in_boundingbox(&polys[i].pts[ii]))
216 n = (ii+1)%polys[i].l;
218 if (!(is_in_boundingbox(&polys[i].pts[n])))
222 /* check if a polygon cross our ray */
223 for (index=1; index<npolys; index++) {
225 /* don't check polygon against itself */
226 if (index == i) continue;
228 if (is_crossing_poly(polys[i].pts[ii], polys[i].pts[n], NULL,
229 &polys[index]) == 1) {
231 debug_printf("is_crossing_poly() returned 1\n");
235 /* if ray is not crossed, add it */
246 /* 2: calc inter polygon rays.
247 * Visibility of inter-polygon vertices.*/
250 for (i=0; i<npolys-1; i++) {
251 for (pt1=0;pt1<polys[i].l;pt1++) {
253 if (!(is_in_boundingbox(&polys[i].pts[pt1])))
257 for (ii=i+1; ii<npolys; ii++) {
258 for (pt2=0;pt2<polys[ii].l;pt2++) {
260 if (!(is_in_boundingbox(&polys[ii].pts[pt2])))
264 /* test if a poly cross */
265 for (index=1;index<npolys;index++) {
266 if (is_crossing_poly(polys[i].pts[pt1],
267 polys[ii].pts[pt2], NULL,
268 &polys[index]) == 1) {
273 /* if not crossed, we found a vilisity ray */
289 /* Compute the weight of every rays: the length of the rays is used
292 * Note the +1 is a little hack to introduce a preference between to
293 * possiblity path: If we have 3 checpoint aligned in a path (say A,
294 * B, C) the algorithm will prefer (A, C) instead of (A, B, C) */
296 calc_rays_weight(poly_t *polys, uint8_t npolys, uint8_t *rays,
297 uint8_t ray_n, uint16_t *weight)
302 for (i=0;i<ray_n;i+=4) {
303 v.x = polys[rays[i]].pts[rays[i+1]].x - polys[rays[i+2]].pts[rays[i+3]].x;
304 v.y = polys[rays[i]].pts[rays[i+1]].y - polys[rays[i+2]].pts[rays[i+3]].y;
305 weight[i/4] = vect_norm(&v) + 1;