Question

link

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.

Solution

Prerequisite reading: [Question] Check if two line segments intersect.

Suggested by G4G, this is a simple idea to check:

1. Draw a horizontal line to the right of each point and extend it to infinity

2. Count the number of times the line intersects with polygon edges.

3. A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon.

4. Note the special case of point ‘g’.