a given point lies inside or outside a polygon

Question

I was trying this question and found a solution :

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

1) Count the number of times the line intersects with polygon edges.
2) A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon. If none of the conditions is true, then point lies outside.

But i think there is a simple solution to this :

for(all sides in same order)
find vector product of the 3 points (given point and end points of each side)

if all products are > or < 0 : point lies inside polygon or on boundary else outside

isn't my solution better and efficient ?
is there another simpler algorithm than this ?

Isn't this really a question for the Mathematics forum? math.stackexchange.com — Roy Dictus
Does your algorithm take into account the possible intermediate concavity of the polygon? (vertex internal angle > 270 or 300 degrees) — Abhishek Bansal
i think it should be independent of concavity or convexity . we just have to see the sign of cross product . The important thing is to move in same direction (clockwise or counter-clockwise). — Aseem Goyal
What do you mean by vector product of 3 points? (vector(A->B)) x vector(P)? — Abhishek Bansal
area of triangle formed by the 3 points : (x2 - x1)*(y3 - y1)-(y2 - y1)*(x3 - x1) — Aseem Goyal

Juraj Blaho Juraj Blaho · Accepted Answer · 2013-12-03T11:24:29

The proposed algorithm using cross product check only works for convex polygons. For non-convex polygon it is quite easy to find an example where it does not work. Try any of the points c, d or e in the polygon given.

a given point lies inside or outside a polygon

2 Answers