Given a polygon and a point ‘p’, find if ‘p’ lies inside the polygon or not. The points lying on the border are considered inside.
Prerequisite reading: [Question] Check if two line segments intersect.
Suggested by G4G, this is a simple idea to check:
Draw a horizontal line to the right of each point and extend it to infinity
Count the number of times the line intersects with polygon edges.
A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon.
Note the special case of point ‘g’.