CODEWITHSUNDEEP
algorithmlanguage-agnosticcomputational-geometry
user466534
user466534

Reputation:

determine if line segment is inside polygon

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

Upvotes: 3

Views: 8228

Answers (2)

Niklas B.
Niklas B.

Reputation: 95308

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

Upvotes: 9

Pontus.G
Pontus.G

Reputation: 1

If your polygon is convex and you add a new point to it outside of the current polygon, that is, the point you want to check whether it is outside or inside of the polygon, the resulting polygon will be convex. In practice it means that the Graham scan described above never will fail and the point added is outside of the polygon.

However a faster and better method is to project the point onto the normal axes of the edges of the polygon. This relies on the separating plane theorem. If there is a line between the point and the edge of the polygon it is outside. For each edge of the polygon take the normal. Project the point onto the normal axis of that edge. Do this for all normals and check if the point is within the max and min projection of the polygon for that projection axis. If this always is the case the point is inside the polygon. If it fails, you can stop since it is outside due to a separating plane.

This will make the algorithm run in linear time instead of O(n log n) since you don't have to sort the vertices based on their angles. This is ideal when you got a large number of vertices.

Upvotes: 0

Related Questions