From 152e7e7e26beb4fb3db123a5f49dae7025737666 Mon Sep 17 00:00:00 2001
From: Joel Bodenmann <joel@embedded.pro>
Date: Mon, 14 Nov 2016 17:54:41 +0100
Subject: Adding gmiscHittestPoly()
---
docs/releases.txt | 1 +
gfxconf.example.h | 1 +
src/gmisc/gmisc.h | 19 ++++++++
src/gmisc/gmisc.mk | 3 +-
src/gmisc/gmisc_hittest.c | 117 ++++++++++++++++++++++++++++++++++++++++++++++
src/gmisc/gmisc_mk.c | 1 +
src/gmisc/gmisc_options.h | 7 +++
7 files changed, 148 insertions(+), 1 deletion(-)
create mode 100644 src/gmisc/gmisc_hittest.c
diff --git a/docs/releases.txt b/docs/releases.txt
index 517539c1..02d85879 100644
--- a/docs/releases.txt
+++ b/docs/releases.txt
@@ -22,6 +22,7 @@ FIX: Fixed an issue in the filled polygon drawing function which caused irregul
FEATURE: Added high-level functions to modify image color palettes
FIX: Improving gdispDrawThickLine()
FEATURE: Added gdispAddFont() for adding a dynamic font to the permanent font list
+FEATURE: Added gmiscHittestPoly() for checking whether a point is inside of a polygon
*** Release 2.6 ***
diff --git a/gfxconf.example.h b/gfxconf.example.h
index 8b3a53b5..468d46d0 100644
--- a/gfxconf.example.h
+++ b/gfxconf.example.h
@@ -335,5 +335,6 @@
// #define GMISC_INVSQRT_REAL_SLOW FALSE
//#define GMISC_NEED_MATRIXFLOAT2D FALSE
//#define GMISC_NEED_MATRIXFIXED2D FALSE
+//#define GMISC_NEED_HITTEST_POLY FALSE
#endif /* _GFXCONF_H */
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
/**
* @}
*
--
cgit v1.2.3