How to form a concave shape from convex shapes?

Question

I am trying to get around the rule only for the possibility of creating convex forms in the CML SFML library.

To do this, I plan to test the given vertices, and if concave, breaking the vertices into groups, checking the concavity of each group, and repeat until a complete set of concave shapes appear that look exactly the same as the original shape when layout

What I would like to know ...

• What is the equation for testing the concavity of a figure: what is it and how does it work?

• How would I divide the vertices of a concave shape so that in the end the shape is formed from as many convex shapes as possible?

• What is the best practice to achieve my goal?

Thanks!

---

Answer 1

You can check if the shape is a convex hull, bypassing all the edges, and checking the next edge always moves in one direction (left / right). This is a fast and cheap algorithm. There is an implementation of this here: en.wikipedia.org/wiki/Graham_scan

If you don’t have a convex hull, follow the batch packing algorithm to get a convex hull that spans all your points (again pretty quickly). en.wikipedia.org/wiki/Gift_wrapping_algorithm

Now find the points that are on your shape, but not on the convex hull. For each run of these points, create a new shape from these points (plus two sides on the convex hull).

Recursion is now your friend: follow the same process on each of the subforms you just made.

I used these methods to verify that the point is contained inside an arbitrary shape: that is, the point should be inside the convex hull (easy to check), but not any of the subforms or their subforms, or their subforms ....

Answer 2

The geometry acceleration library , which was published yesterday , has an implementation of the Convex Hull algorithm . Over a thousand words are written in the picture:

Although this creates a “new” shape that is not concave (ie convex); This may or may not be exactly what you want. However, in this process, the algorithm should be able to classify the shape concave / convex, so you will probably be interested in the library.

General information about the 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 the “impact test” (leak test) is a common concern for convex / concave geometries, without further ado, I outlined the appropriate Boost Geometry algorithm for this: within .

_{Again, really, because the picture is so beautiful. Please note that although the image suggests asking for a point against the polygon, the algorithms are completely generalized and can be used to check for full localization on n dimensional polygons in another}

Answer 3

Ok, just crumple all the information together:

• To check the Closed Polygon, see this page provided by Adrian Taylor.
• One way to achieve my goal is to use monotonic decomposition and triangulation.
• You can find out about Monotone Decomposition on this beautiful site : (summary of this below)

• Finally, now we triangulate monotonous figures using the information in this Poweroint :

  • Press u1 and u2 on the stack.
  • j = 3 / * j - index of the current vertex * /
  • u = uj
  • Case (i): u is adjacent to v1, but not vi. add the diagonals uv2, uv3, ..., uvi. pop vi, vi-1, ..., v1 from the stack. push vi, u on the stack. Case (ii): u is adjacent to vi, but not v1. while i> 1 and angle uvivi-1 < add the diagonal uvi-1 pop vi from the ENDWHILE stack press u Case (iii): u adjacent to both v1 and vi. add the diagonals uv2, uv3, ..., uvi-1. Exit
  • 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 / quick solutions.

Answer 4

Some things to think about:

• Left and right corners (cross-product sign is an easy way to distinguish). All angles in convex form have the same strength.

• Expanding an edge and adding a new vertex can give you better results than adding edges between existing vertices.

Answer 5

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

Then you just check that at some 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)