CODEWITHSUNDEEP
algorithmgeometry
Aseem Goyal
Aseem Goyal

Reputation: 2723

a given point lies inside or outside a polygon

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. polygon

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 ?

Upvotes: 1

Views: 2280

Answers (2)

Vikram Bhat
Vikram Bhat

Reputation: 6246

The algorithm you suggest only works for convex polygons & in fact used for calculation of the convex hull but would fail for concave which is again proved by correctness of convex hull algorithm.

Another way to use this algorithm is to divide your polygon into convex polygons and then apply the algorithm on the divided parts to see if the point is inside anyone of them

Polygon triangulation

Upvotes: 0

Juraj Blaho
Juraj Blaho

Reputation: 13471

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.

Upvotes: 2

Related Questions