Adding gmiscHittestPoly()

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
 /**
  * @}
  *