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!

I think you might have the terminology backwards. Do you want to decompose a [concave](http://en.wikipedia.org/wiki/Concave) polygon into [convex](http://en.wikipedia.org/wiki/Convex) ones? If so, you might want to look into [polygon triangulation](http://en.wikipedia.org/wiki/Polygon_triangulation). (Triangles are the simplest convex polygons). — hammar, Jul 13 '11 at 22:41
The reason I'm asking is that since convex polygons are easier to deal with than concave ones, it is quite common for libraries only to support convex ones. I've never heard of a library which only supported concave ones. [This page seems to confirm this](http://www.sfml-dev.org/documentation/1.6/classsf_1_1Shape.php). — hammar, Jul 13 '11 at 22:50

score 6 · Accepted Answer · edited Jul 18 '11 at 15:21

6

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....

edited Jul 18 '11 at 15:21

BlueRaja - Danny Pflughoeft

84,206
33
197
283

answered Jul 13 '11 at 23:21

Adrian Taylor

452
2
3

+1 I like your description of the process. Note that the boost library also facilitates a fully generalized 'containment' test **[`within`](http://www.boost.org/doc/libs/1_47_0/libs/geometry/doc/html/geometry/reference/algorithms/within/within_2.html) that would probably do about the same given a _point_ and a free _polygon_ – sehe Jul 13 '11 at 23:42
1

Could you get a little more detailed on what to do after you've made a convex hull? do i form a shape from the starter point and the off-hull point, and then continue itterating through the points from the off-hull point? – Griffin Jul 14 '11 at 06:00
Also when "repeating the process on each sub-shape" do i create a new border for each sub-shape, or just look for more off-hull points? – Griffin Jul 14 '11 at 06:02
Lastly could you look at the last problem i edited into the question? – Griffin Jul 14 '11 at 06:03
I think we might be at cross purposes: I was proposing you create a convex hull from all the points, then create a set of sub-shapes that are the 'holes' between your shape and the hull. You do this recursively until all your 'holes' shapes are decomposed into convex hulls themselves: meaning you can then handle any geometric task fairly easily. This is the usual (and easiest) way to deal with concave shapes. Building up your shape as a set of convex hulls is harder: using triangles is the probably the best way for this. – Adrian Taylor Jul 15 '11 at 16:02

sehe · Answer 2 · 2011-07-13T23:47:57.033

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

enter image description here

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:

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}

enter image description here

score 3 · Answer 3 · edited Apr 15 '18 at 10:17

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.

score 1 · Answer 4 · answered Jul 13 '11 at 22:31

Some things to think about:

Left-handed and right-handed corners (the sign of the cross-product is an easy way to distinguish). All corners in a convex shape are the same handed-ness.
Extending an edge and adding a new vertex may give you better results than adding edges between existing vertices.

score 1 · Answer 5 · answered Jul 13 '11 at 23:23

I assume you have your polygon as a list of point, a very simple way would be to go around your polygon and consider the sequence of triplet of consecutive points (A,B,C).

Then you just check that at one point det(AB,BC) changes its sign, where

det(AB,AC) = (x_a-x_b)(yc-yb) - (x_c-x_b)(y_a-y_b)

How to form a Concave shape out of Convex shapes?

5 Answers5

Linked