2 * Copyright Droids Corporation (2009)
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 * Revision : $Id: f16.h,v 1.6.4.3 2008-05-10 15:06:26 zer0 Exp $
27 #include <vect_base.h>
34 #define debug_printf(args...) printf(args)
36 #define debug_printf(args...)
39 /* default bounding box is (0,0) (100,100) */
40 static int32_t bbox_x1 = 0;
41 static int32_t bbox_y1 = 0;
42 static int32_t bbox_x2 = 100;
43 static int32_t bbox_y2 = 100;
45 void polygon_set_boundingbox(int32_t x1, int32_t y1, int32_t x2, int32_t y2)
53 uint8_t is_in_boundingbox(const point_t *p)
55 if (p->x >= bbox_x1 &&
63 /* Test if a point is in a polygon (including edges)
69 is_in_poly(const point_t *p, poly_t *pol)
77 for (i=0;i<pol->l;i++) {
78 /* is a polygon point */
79 if (p->x == pol->pts[i].x && p->y == pol->pts[i].y)
83 for (i=0;i<pol->l;i++) {
86 v.x = pol->pts[ii].x-p->x;
87 v.y = pol->pts[ii].y-p->y;
88 w.x = pol->pts[i].x-p->x;
89 w.y = pol->pts[i].y-p->y;
90 z = vect_pvect_sign(&v, &w );
100 /* public wrapper for is_in_poly() */
101 uint8_t is_point_in_poly(poly_t *pol, int16_t x, int16_t y)
106 return is_in_poly(&p, pol);
109 /* Is segment crossing polygon? (including edges)
113 * 3 touch out (a segment boundary is on a polygon edge,
114 * and the second segment boundary is out of the polygon)
117 is_crossing_poly(point_t p1, point_t p2, point_t *intersect_pt,
126 debug_printf("%" PRIi32 " %" PRIi32 " -> %" PRIi32 " %" PRIi32 " crossing poly %p ?\n",
127 p1.x, p1.y, p2.x, p2.y, pol);
128 debug_printf("poly is : ");
129 for (i=0; i<pol->l; i++) {
130 debug_printf("%" PRIi32 ",%" PRIi32 " ", pol->pts[i].x, pol->pts[i].y);
134 for (i=0;i<pol->l;i++) {
135 ret = intersect_segment(&p1, &p2, &pol->pts[i], &pol->pts[(i+1)%pol->l], &p);
136 debug_printf("%" PRIi32 ",%" PRIi32 " -> %" PRIi32 ",%" PRIi32
137 " return %d\n", pol->pts[i].x, pol->pts[i].y,
138 pol->pts[(i+1)%pol->l].x, pol->pts[(i+1)%pol->l].y, ret);
166 ret1 = is_in_poly(&p1, pol);
168 ret2 = is_in_poly(&p2, pol);
170 debug_printf("is in poly: p1 %d p2: %d cpt %d\r\n", ret1, ret2, cpt);
172 debug_printf("p intersect: %"PRIi32" %"PRIi32"\r\n", p.x, p.y);
176 if (ret1==1 || ret2==1)
183 if (ret1==1 || ret2==1)
188 if (ret1==1 || ret2==1)
190 if (ret1==0 || ret2==0)
198 /* Giving the list of poygons, compute the graph of "visibility rays".
199 * This rays array is composed of indexes representing 2 polygon
200 * vertices that can "see" each others:
202 * i : the first polygon number in the input polygon list
203 * i+1: the vertex index of this polygon (vertex 1)
204 * i+2: the second polygon number in the input polygon list
205 * i+3: the vertex index of this polygon (vertex 2)
207 * Here, vertex 1 can "see" vertex 2 in our visibility graph
209 * As the first polygon is not a real polygon but the start/stop
210 * point, the polygon is NOT an ocluding polygon (but its vertices
211 * are used to compute visibility to start/stop points)
215 calc_rays(poly_t *polys, uint8_t npolys, uint8_t *rays)
217 uint8_t i, ii, index;
223 /* !\\first poly is the start stop point */
225 /* 1: calc inner polygon rays
226 * compute for each polygon edges, if the vertices can see each others
227 * (usefull if interlaced polygons)
230 for (i=0; i<npolys; i++) {
231 debug_printf("%s(): poly num %d/%d\n", __FUNCTION__, i, npolys);
232 for (ii=0; ii<polys[i].l; ii++) {
233 debug_printf("%s() line num %d/%d\n", __FUNCTION__, ii, polys[i].l);
234 if (! is_in_boundingbox(&polys[i].pts[ii]))
237 n = (ii+1)%polys[i].l;
239 if (!(is_in_boundingbox(&polys[i].pts[n])))
243 /* check if a polygon cross our ray */
244 for (index=1; index<npolys; index++) {
246 /* don't check polygon against itself */
247 if (index == i) continue;
249 if (is_crossing_poly(polys[i].pts[ii], polys[i].pts[n], NULL,
250 &polys[index]) == 1) {
252 debug_printf("is_crossing_poly() returned 1\n");
256 /* if ray is not crossed, add it */
267 /* 2: calc inter polygon rays.
268 * Visibility of inter-polygon vertices.*/
271 for (i=0; i<npolys-1; i++) {
272 for (pt1=0;pt1<polys[i].l;pt1++) {
274 if (!(is_in_boundingbox(&polys[i].pts[pt1])))
278 for (ii=i+1; ii<npolys; ii++) {
279 for (pt2=0;pt2<polys[ii].l;pt2++) {
281 if (!(is_in_boundingbox(&polys[ii].pts[pt2])))
285 /* test if a poly cross */
286 for (index=1;index<npolys;index++) {
287 if (is_crossing_poly(polys[i].pts[pt1],
288 polys[ii].pts[pt2], NULL,
289 &polys[index]) == 1) {
294 /* if not crossed, we found a vilisity ray */
310 /* Compute the weight of every rays: the length of the rays is used
313 * Note the +1 is a little hack to introduce a preference between to
314 * possiblity path: If we have 3 checpoint aligned in a path (say A,
315 * B, C) the algorithm will prefer (A, C) instead of (A, B, C) */
317 calc_rays_weight(poly_t *polys, __attribute__((unused)) uint8_t npolys,
318 uint8_t *rays, uint8_t ray_n, uint16_t *weight)
323 for (i=0;i<ray_n;i+=4) {
324 v.x = polys[rays[i]].pts[rays[i+1]].x - polys[rays[i+2]].pts[rays[i+3]].x;
325 v.y = polys[rays[i]].pts[rays[i+1]].y - polys[rays[i+2]].pts[rays[i+3]].y;
326 weight[i/4] = vect_norm(&v) + 1;