How to form a Concave shape out of Convex shapes?

Question

i'm trying to get around the rule of only being able to form convex shapes in the SFML c++ library.

To do this I'm planning on testing given vertices, and if concave, splitting the vertices into groups, testing each groups' concaveness, and repeating until a full set of concave shapes results that look just like the original shape when put together

What I would like to know is...

• What the equation for testing a shapes concaveness is: What is it and how does it work?

• How would i split up the vertices of the concave shape so in the end the shape is formed out of as few convex shapes as possible?

• Whats the best practice for achieving my goal?

Thanks!

---

Answer 1

You can test for a shape being a convex hull by going round all the edges and checking the next edge is always moving in the same direction (left/right handed). This is a quick and cheap algorithm. There is an implementation of this here: en.wikipedia.org/wiki/Graham_scan

If you don't have a convex hull, perform a package wrapping algorithm to get a convex hull that encompasses all your points (again quite fast). en.wikipedia.org/wiki/Gift_wrapping_algorithm

Now, look for points that are on your shape, but aren't on the convex hull. For each run of these points, create a new shape from these points (plus the 2 either side on the convex hull).

Recursion is now your friend: do the exact same process on each of the sub-shapes you have just made.

I have used this techniques to test for a point being contained inside an arbitrary shape: i.e. the point must be inside the convex hull (easy to test), but not any of the sub-shapes, or their sub-shapes, or their sub-shapes....

Answer 2

The Boost Geometry library that was published yesterday, has an implementation of Convex Hull algorithm. A picture says more than a thousand words:

Although this constructs a 'new' shape that is non-concave (i.e. convex); This may or may not be precisely what you want. However, in the process the algorithm is bound to be able to classify shape a concave/convex, so you'd likely be interested in the library nonetheless.

General information on convex hull algorithm:

• http://en.wikipedia.org/wiki/Convex_hull
• http://en.wikipedia.org/wiki/Convex_hull_algorithms

---

Since Adrian Japon more or less suggested that 'hit testing' (containment test) is of a usual reason to care about convex/concave geometries, without further ado, I'll highlight the corresponding Boost Geometry algorithm for that: within.

_{Again, really because the picture is so pretty. Note that though the picture suggests querying for a point against a polygon, the algorithms are fully generic and can be used to test complete containment on n-dimensional polygons in another}

Answer 3

Alright, just to mash all the info together:

• To test polygon Concaveness, look at this page given by Adrian Taylor
• One way to accomplish my goal is to use Monotone Decomposition and Triangulation
• You can learn about Monotone Decomposition at this lovely site: (summary of it below)

• Finally, triangulate the now Monotone shapes using the information in this Powerpoint:

  1. Push u1 and u2 on the stack.
  2. j = 3 /* j is index of current vertex */
  3. u = uj
  4. Case (i): u is adjacent to v1 but not vi. add diagonals uv2, uv3, …, uvi. pop vi, vi-1, …, v1 from stack. push vi, u on stack. Case (ii): u is adjacent to vi but not v1. while i > 1 and angle uvivi-1 <  add diagonal uvi-1 pop vi from stack endwhile push u Case (iii): u adjacent to both v1 and vi. add diagonals uv2, uv3, …, uvi-1. exit
  5. j = j + 1 Go to step 3.

---

**Note:**
By “adjacent” we mean connected by an edge in P.   
Recall that v1 is the bottom of the stack, vi is the top.    
By “Push” we mean push the item(s) to the back of the list    

---

Hope this helps someone... but I'm still looking for any better/faster solutions.