0
$\begingroup$

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?

  • 0
    Act$u$ally according to http://www.sfml-dev.org/tutorials/1.4/graphics-shape.php you need the shape to be conve$x$, not concave.2011-07-14

1 Answers 1

1

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.