Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

i'm trying to get around the rule of only being able to form concave shapes in the SFML c++ library by forming the non-concave shape out of many concave shapes.

What I don't know is the equation for testing a shapes concaveness:
What is it and how does it work?

share|improve this question
    
Actually according to sfml-dev.org/tutorials/1.4/graphics-shape.php you need the shape to be convex, not concave. –  Robert Israel Jul 14 '11 at 2:47

1 Answer 1

up vote 1 down vote accepted

A polygon is concave if and only if at least one of its interior angles has a measure greater than $\pi$ radians. To calculate this, take three consecutive vertices going clockwise (we will do this for every such list) - $(x_1, y_1)$, $(x_2, y_2)$, and $(x_3, y_3)$. The magnitude in the $z$ direction of the cross product of the angle's two vectors will be $ab\sin(\theta)$, where $a$ and $b$ are the magnitudes and $\theta$ is the angle in between. This will be positive if and only if $\theta > \pi$ radians. So we calculate $(x_2 - x_1)(y_3 - y_2) - (x_3 - x_2)(y_2 - y_1)$, which is the magnitude of the cross product. If, for any set of 3 consecutive vertices (going clockwise, of course), this value is positive, the polygon is concave. Note that in Mathematica (which you tagged this post with), you can split a list of vertices into such groups of 3 with the command Partition[vertices, 3, 1]. If you need the shape to be convex instead, test whether all such cross products are negative.

I only know the solution for polygons, not other shapes.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.