Sign in to follow this  

Is a polygon convex or concave?

Recommended Posts

Iterate through all your vertices. For each vertex you take the cross product of the two vectors pointing to the adjacent points (connected by the two adjoining edges), and checking that the sign of these cross products are all the same. They should all have the same direction if convex, otherwise some will point in the opposite direction.

In general, you can just check the sign for each component of the cross product. It is often sufficient to just use (and therefore compute) one component, but this assumes that the plane of the polygon is not parallel to the associated axis.

For efficiency, I would take the first 3 vertices, compute normal of their triangle, and find the largest component. For the rest of the vertices, I would only compute the component of the cross product associated wit this component. This is roughly equivalent to choosing a non-degenerate projection plane and projecting it to 2D and searching for reflex angles.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this