<p>If a edge corner is concave then it needs to border 2 of the output polygons.</p>

<p>So one algorithm would be to find all concave corners (including the ones in the holes) and making cuts starting from them to other concave corners. This will split the polygon in two or join 2 holes into 1 or connect a hole to the outside. </p>

<p>The cut from a concave corner should be constrained by the angle or it will create a new concave corner that then needs to be cut again.</p>

CC BY-SA 3.0
2017-07-07T14:32:30.150Z
2017-07-07T15:12:41.807Z
2017-07-07T15:12:41.807Z
ratchet freak
<p>I'm in search for an algorithm that takes the left side of the following graphic as an input and outputs a minimal amount of convex polygons as seen on the right side of the graphic.</p>

<p><a href="https://i.sstatic.net/GMer4.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GMer4.png" alt="input and output of the wanted algorithm"></a></p>

<p>The input mesh can be very complex and could contain several holes. The position of the vertices are not constrained to a grid.</p>

<p>The use case for this is the creation of multiple polygon shapes for the Box2D physics engine.</p>

<p>Additional information:</p>

<ul>
<li>The result does not need to be deterministic.</li>
<li>The result does not need to be vertically striped. </li>
<li>As trichoplax noted, the right part of the picture does not resemble the minimal polygon count that can be achieved. It's just an example.</li>
<li>It's not necessary that it will find the absolute minimum of convex polygons. A fast algorithm is preferred over a "best solution" one.</li>
</ul>

CC BY-SA 3.0
2017-07-07T11:18:53.900Z
I notice that the example output is not minimal according to the definition (there exists an arrangement of 5 convex polygons that covers the mesh). Is this because it's just an example, or are there further requirements that prevent the 5 polygon output being valid? For instance, are the output polygons required to be in vertical strips of fixed width or is that just for the example image?
trichoplax is on Codidact now
CC BY-SA 3.0
2017-07-07T11:41:53.843Z
Thanks trichoplax. I've added the requested additional information to the question. Hope they clarify your questions.
Timm
CC BY-SA 3.0
2017-07-07T15:13:02.573Z
I've identified the difference between the example output and the minimal one I was thinking of: Mine covers the area using convex polygons that use only the existing vertices, but do not use the existing triangles. The example output shows the minimal number of convex polygons if they are required to be constructed from the existing triangles. Is this a requirement?
trichoplax is on Codidact now
CC BY-SA 3.0
2017-07-07T19:23:04.757Z
No this is no requirement. The resulting polygons can be generated with any means available. The only requirement is, that the resulting shape is exactly the same as with triangles.
Timm
<algorithm><computational-geometry><geometry><polygon>
List of triangles to minimum amount of convex polygons
Timm
# List of triangles to minimum amount of convex polygons

(Asked by: username_0 on 2017-07-07)

I'm in search for an algorithm that takes the left side of the following graphic as an input and outputs a minimal amount of convex polygons as seen on the right side of the graphic.

[![input and output of the wanted algorithm](https://i.sstatic.net/GMer4.png)](https://i.sstatic.net/GMer4.png)

The input mesh can be very complex and could contain several holes. The position of the vertices are not constrained to a grid.

The use case for this is the creation of multiple polygon shapes for the Box2D physics engine.

Additional information:

* The result does not need to be deterministic.
* The result does not need to be vertically striped.
* As username_1 noted, the right part of the picture does not resemble the minimal polygon count that can be achieved. It's just an example.
* It's not necessary that it will find the absolute minimum of convex polygons. A fast algorithm is preferred over a "best solution" one.

**Tags:** algorithm, computational-geometry, geometry, polygon

> **Comments:**
> **username_1**: I notice that the example output is not minimal according to the definition (there exists an arrangement of 5 convex polygons that covers the mesh). Is this because it's just an example, or are there further requirements that prevent the 5 polygon output being valid? For instance, are the output polygons required to be in vertical strips of fixed width or is that just for the example image?  
> **username_0**: Thanks username_1. I've added the requested additional information to the question. Hope they clarify your questions.  
> **username_1**: I've identified the difference between the example output and the minimal one I was thinking of: Mine covers the area using convex polygons that use only the existing vertices, but do not use the existing triangles. The example output shows the minimal number of convex polygons if they are required to be constructed from the existing triangles. Is this a requirement?  
> **username_0**: No this is no requirement. The resulting polygons can be generated with any means available. The only requirement is, that the resulting shape is exactly the same as with triangles.  

---

## 1 answers

### Answer by username_2 on 2017-07-07. Score: 1

If a edge corner is concave then it needs to border 2 of the output polygons.

So one algorithm would be to find all concave corners (including the ones in the holes) and making cuts starting from them to other concave corners. This will split the polygon in two or join 2 holes into 1 or connect a hole to the outside.

The cut from a concave corner should be constrained by the angle or it will create a new concave corner that then needs to be cut again.


---

