diff options
author | Joel Bodenmann <joel@embedded.pro> | 2016-11-14 17:54:41 +0100 |
---|---|---|
committer | Joel Bodenmann <joel@embedded.pro> | 2016-11-14 17:59:16 +0100 |
commit | 152e7e7e26beb4fb3db123a5f49dae7025737666 (patch) | |
tree | 86e42637064b680b587b844657ebba4198a30c43 /src/gmisc/gmisc_hittest.c | |
parent | 7f79b89eda65e2529128710168a5b1de431ff7f0 (diff) | |
download | uGFX-152e7e7e26beb4fb3db123a5f49dae7025737666.tar.gz uGFX-152e7e7e26beb4fb3db123a5f49dae7025737666.tar.bz2 uGFX-152e7e7e26beb4fb3db123a5f49dae7025737666.zip |
Adding gmiscHittestPoly()
Diffstat (limited to 'src/gmisc/gmisc_hittest.c')
-rw-r--r-- | src/gmisc/gmisc_hittest.c | 117 |
1 files changed, 117 insertions, 0 deletions
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 |