Find if a given point lies inside a given shape

Table of Contents

Find if a given point lies inside a given shape

Problem: Given a shape on a plane specified by points (P₁, P₂, P₃ ... P_n).
Find out if a given point P_k lies inside or outside that shape.
Each point contains the coordinates (x,y)

Note: The given array of points are in order. So there is no need to find the order of points required to form a closed shape.

Solution:

Imagine drawing a line from the given point P_k towards right infinity.
Count the number of intersections that line makes with the given polygon shape.
If number of intersections is odd, point lies inside else outside.
A case left out in the above is when the point is co-linear with any of the vertices. To handle this, check the same in an extra loop.

Also see: Linear programming and Intersection of two lines

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email:	(Your email is not shared with anybody)

Comment:

Facebook comments:

Site Owner: Sachin Goyal