algorithm - determine if line segment is inside polygon

Question

suppose we have convex polygon with vertices

(v0,v1,....vn)

my aim is to determine if for given point p(x,y) any line segment connecting this point and any vertices of polygon is inside polygon or even for given two point

p(x0,y0)  `p(x1,y1)`

line segment connecting these two point is inside polygon? i have searched many sites about this ,but i am still confused,generally i think we have to compare coordinates of vertices and by determing coordinates of which point is less or greater to another point's coordinates,we could determine location of any line segment,but i am not sure how correct is this,please help me

Answer 1

Assume a point P and a convex polygon with n vertices V_1 to V_n (n > 2).

Sort the vertices of the polygon by their angle relative to a selected vertex, so that they are in clock-wise or counter-clockwise order. The edges of the polygon are then V_1 -> V_2, V_2 -> V_3, ..., V_(n-1) -> V_n, V_n -> V_1.

Now, for every edge, check the value of the cross product (V_(i+1) - V_i) x (P - V_i). Now P is inside the polygon iif all the values are >= 0 or all the values are <= 0.

There's a good tutorial on TopCoder for the more general problem where the polygon doesn't have to be convex. What they do is send a ray from the test point and check how many edges it intersects.

NOTE: The cross product used here is defined as (u1, u2) x (v1, v2) := u1*v2 - u2*v1