diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/gmisc/gmisc.h | 19 | ||||
| -rw-r--r-- | src/gmisc/gmisc.mk | 3 | ||||
| -rw-r--r-- | src/gmisc/gmisc_hittest.c | 117 | ||||
| -rw-r--r-- | src/gmisc/gmisc_mk.c | 1 | ||||
| -rw-r--r-- | src/gmisc/gmisc_options.h | 7 |
5 files changed, 146 insertions, 1 deletions
diff --git a/src/gmisc/gmisc.h b/src/gmisc/gmisc.h index c8b4c21f..f805345c 100644 --- a/src/gmisc/gmisc.h +++ b/src/gmisc/gmisc.h @@ -464,6 +464,25 @@ extern "C" { #endif #endif + +#if GMISC_NEED_HITTEST_POLY || defined(__DOXYGEN__) + /** + * @brief Check whether a point is inside or on the edge of a polygon + * @pre Requires GFX_USE_GMISC and GMISC_NEED_HITTEST_POLY + * + * @note This function works both with convex and concave polygons + * + * @param[in] pntarray The array of points that form the polygon + * @param[in] cnt The number of points in the point array @pntarray + * @param[in] p The point to test + * + * @return @p TRUE if the point @p p is inside or on the edge of the polygon @p pntarray, @p FALSE otherwise. + * + * @api + */ + bool_t gmiscHittestPoly(const point *pntarray, unsigned cnt, const point *p); +#endif // GMISC_NEED_HITTEST_POLY + #ifdef __cplusplus } #endif diff --git a/src/gmisc/gmisc.mk b/src/gmisc/gmisc.mk index 22f1da49..531c1f17 100644 --- a/src/gmisc/gmisc.mk +++ b/src/gmisc/gmisc.mk @@ -6,4 +6,5 @@ GFXSRC += $(GFXLIB)/src/gmisc/gmisc.c \ $(GFXLIB)/src/gmisc/gmisc_arrayops.c \ $(GFXLIB)/src/gmisc/gmisc_matrix2d.c \ - $(GFXLIB)/src/gmisc/gmisc_trig.c + $(GFXLIB)/src/gmisc/gmisc_trig.c \ + $(GFXLIB)/src/gmisc/gmisc_hittest.c diff --git a/src/gmisc/gmisc_hittest.c b/src/gmisc/gmisc_hittest.c new file mode 100644 index 00000000..f84a66cf --- /dev/null +++ b/src/gmisc/gmisc_hittest.c @@ -0,0 +1,117 @@ +/* + * This file is subject to the terms of the GFX License. If a copy of + * the license was not distributed with this file, you can obtain one at: + * + * http://ugfx.org/license.html + */ + +#include "../../gfx.h" + +#if GFX_USE_GMISC + +#if GMISC_NEED_HITTEST_POLY + +/* This function is used by gmiscHittestPoly() + * + * This function projects the point c on an horizontal line to the right. + * If the projection cuts the segment formed by the points a and b, + * the function returns 1. If the point c is on the segment, the function + * returns 0. If they don't intersect, it returns 2. + */ +static char _pointCrossingSegment(const point *a, const point *b, const point *c) { + /* If both points are left from our point, it won't intersect */ + if (a->x < c->x && b->x < c->x) { + return -1; + } + + /* Check if there is a point above and a point below, else + * it won't intersect. + */ + if (c->y <= a->y && c->y >= b->y) { + coord_t crossProduct; + + /* If the line is parallel */ + if (a->y == b->y) { + /* Point on the segment */ + if ((c->x >= a->x && c->x <= b->x) || (c->x <= a->x && c->x >= b->x)) { + return 0; + } else { + return -1; + } + } + + /* If the point is on the same horizontal line as one of the segment point, + * allow to add the intersection once + */ + if (c->y == b->y) { + return -1; + } + + /* Matrix cross product to find if the point is left or right from the segment*/ + crossProduct = (b->x - a->x) * (c->y - a->y) - (b->y - a->y) * (c->x - a->x); + + /* Point left of the segment */ + if (crossProduct < 0) { + return 1; + } + + /* Point on the segment */ + if (crossProduct == 0) { + return 0; + } + } + + return -1; +} + +bool_t gmiscHittestPoly(const point *pntarray, unsigned cnt, const point *p) { + unsigned i = 0; + uint8_t nbrIntersection = 0; + int8_t crossResult; + + // For each pair of points + for (i = 0; i < cnt-1; i++) { + /* Order the two points from top to bottom to simplify the function */ + if (pntarray[i].y >= pntarray[i+1].y) { + crossResult = _pointCrossingSegment(&pntarray[i], &pntarray[i+1], p); + } else { + crossResult = _pointCrossingSegment(&pntarray[i+1], &pntarray[i], p); + } + + /* Point on the edge of the polygon */ + if (crossResult == 0) { + return TRUE; + } + /* Point crossing the polygon */ + else if(crossResult == 1) { + nbrIntersection++; + } + } + + /* Last pair of points, can't be done in the loops + * Same as before + */ + if (pntarray[cnt-1].y >= pntarray[0].y) { + crossResult = _pointCrossingSegment(&pntarray[cnt-1], &pntarray[0], p); + } else { + crossResult = _pointCrossingSegment(&pntarray[0], &pntarray[cnt-1], p); + } + + if (crossResult == 0) { + return TRUE; + } else if(crossResult == 1) { + nbrIntersection++; + } + + /* If we cross an even pair of segments, we are outside */ + if (nbrIntersection % 2 == 0) { + return FALSE; + } + + /* Else we are inside the polygon */ + return TRUE; +} + +#endif // GMISC_NEED_HITTEST_POLY + +#endif // GFX_USE_GMISC diff --git a/src/gmisc/gmisc_mk.c b/src/gmisc/gmisc_mk.c index ab3c4a1d..cc6d0fbf 100644 --- a/src/gmisc/gmisc_mk.c +++ b/src/gmisc/gmisc_mk.c @@ -9,3 +9,4 @@ #include "gmisc_arrayops.c" #include "gmisc_matrix2d.c" #include "gmisc_trig.c" +#include "gmisc_hittest.c" diff --git a/src/gmisc/gmisc_options.h b/src/gmisc/gmisc_options.h index 7f175fd7..5dce4d94 100644 --- a/src/gmisc/gmisc_options.h +++ b/src/gmisc/gmisc_options.h @@ -48,6 +48,13 @@ #ifndef GMISC_NEED_INVSQRT #define GMISC_NEED_INVSQRT FALSE #endif + /** + * @brief Include polygon hit test functions + * @details Defaults to FALSE + */ + #ifndef GMISC_NEED_HITTEST_POLY + #define GMISC_NEED_HITTEST_POLY FALSE + #endif /** * @} * |