version 2.8
gmisc_hittest.c
1 /*
2  * This file is subject to the terms of the GFX License. If a copy of
3  * the license was not distributed with this file, you can obtain one at:
4  *
5  * http://ugfx.org/license.html
6  */
7 
8 #include "../../gfx.h"
9 
10 #if GFX_USE_GMISC
11 
12 #if GMISC_NEED_HITTEST_POLY
13 
14 /* This function is used by gmiscHittestPoly()
15  *
16  * This function projects the point c on an horizontal line to the right.
17  * If the projection cuts the segment formed by the points a and b,
18  * the function returns 1. If the point c is on the segment, the function
19  * returns 0. If they don't intersect, it returns 2.
20  */
21 static char _pointCrossingSegment(const point *a, const point *b, const point *c) {
22  /* If both points are left from our point, it won't intersect */
23  if (a->x < c->x && b->x < c->x) {
24  return -1;
25  }
26 
27  /* Check if there is a point above and a point below, else
28  * it won't intersect.
29  */
30  if (c->y <= a->y && c->y >= b->y) {
31  coord_t crossProduct;
32 
33  /* If the line is parallel */
34  if (a->y == b->y) {
35  /* Point on the segment */
36  if ((c->x >= a->x && c->x <= b->x) || (c->x <= a->x && c->x >= b->x)) {
37  return 0;
38  } else {
39  return -1;
40  }
41  }
42 
43  /* If the point is on the same horizontal line as one of the segment point,
44  * allow to add the intersection once
45  */
46  if (c->y == b->y) {
47  return -1;
48  }
49 
50  /* Matrix cross product to find if the point is left or right from the segment*/
51  crossProduct = (b->x - a->x) * (c->y - a->y) - (b->y - a->y) * (c->x - a->x);
52 
53  /* Point left of the segment */
54  if (crossProduct < 0) {
55  return 1;
56  }
57 
58  /* Point on the segment */
59  if (crossProduct == 0) {
60  return 0;
61  }
62  }
63 
64  return -1;
65 }
66 
67 bool_t gmiscHittestPoly(const point *pntarray, unsigned cnt, const point *p) {
68  unsigned i = 0;
69  uint8_t nbrIntersection = 0;
70  int8_t crossResult;
71 
72  // For each pair of points
73  for (i = 0; i < cnt-1; i++) {
74  /* Order the two points from top to bottom to simplify the function */
75  if (pntarray[i].y >= pntarray[i+1].y) {
76  crossResult = _pointCrossingSegment(&pntarray[i], &pntarray[i+1], p);
77  } else {
78  crossResult = _pointCrossingSegment(&pntarray[i+1], &pntarray[i], p);
79  }
80 
81  /* Point on the edge of the polygon */
82  if (crossResult == 0) {
83  return TRUE;
84  }
85  /* Point crossing the polygon */
86  else if(crossResult == 1) {
87  nbrIntersection++;
88  }
89  }
90 
91  /* Last pair of points, can't be done in the loops
92  * Same as before
93  */
94  if (pntarray[cnt-1].y >= pntarray[0].y) {
95  crossResult = _pointCrossingSegment(&pntarray[cnt-1], &pntarray[0], p);
96  } else {
97  crossResult = _pointCrossingSegment(&pntarray[0], &pntarray[cnt-1], p);
98  }
99 
100  if (crossResult == 0) {
101  return TRUE;
102  } else if(crossResult == 1) {
103  nbrIntersection++;
104  }
105 
106  /* If we cross an even pair of segments, we are outside */
107  if (nbrIntersection % 2 == 0) {
108  return FALSE;
109  }
110 
111  /* Else we are inside the polygon */
112  return TRUE;
113 }
114 
115 #endif // GMISC_NEED_HITTEST_POLY
116 
117 #endif // GFX_USE_GMISC
int16_t coord_t
The type for a coordinate or length on the screen.
Definition: gdisp.h:39
coord_t y
Definition: gdisp.h:53
#define FALSE
Generic &#39;false&#39; boolean constant.
Definition: gfx.h:31
Type for a 2D point on the screen.
Definition: gdisp.h:51
coord_t x
Definition: gdisp.h:52
#define TRUE
Generic &#39;true&#39; boolean constant.
Definition: gfx.h:38
bool_t gmiscHittestPoly(const point *pntarray, unsigned cnt, const point *p)
Check whether a point is inside or on the edge of a polygon.