Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Find if a given point lies inside a given shape

Problem: Given a shape on a plane specified by points (P1, P2, P3 ... Pn).
Find out if a given point Pk 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:
1. Imagine drawing a line from the given point Pk towards right infinity.
2. Count the number of intersections that line makes with the given polygon shape.
3. If number of intersections is odd, point lies inside else outside.
4. 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: