Convex polygon partitioning in MATLAB

Dear community members,

Do you know if there exist a function for partitioning of a nonconvex polygon into minimum number of convex parts in MATLAB?

Best regards,

Elena Hammari

Answer 1

[John D'Errico]

No, there (still) is no solution in MATLAB for this. You could write it however. If you do, then post it on the file exchange. It should be doable. I might first start by computing the interior angle for each vertex. Any vertex in the polygon that has an interior angle that exceeds 180 degrees MUST be a vertex that will help divide the polygon into small pieces, since that vertex cannot be part of a convex polygon.

Next, count the number of such vertices.

1. Consider if a polygon has NO interior angles that exceed 180 degrees. If so, then it is convex, and you are done.
2. If there is only one such vertex, then connect that vertex to ANY other vertex that is not directly connected to the vertex in question. This forms a splitting of the polygon into exactly two shapes, each of which is convex, and again you are done.
3. If there are exactly 2 such vertices, then you can connect the two. Again, this must form a splitting into two convex polygons.
4. With 3 or more such vertices, you can reduce the problem recursively. You should find the number of convex polygons will be related to log2(n), where n is the number of vertices with interior angles that exceed 180 degrees.

For a simple example consider this example (probably invalid as a polygon, because it is a catholic one, i.e., it crosses itself):

px = rand(10,1);px(end+1) = px(1);
py = rand(10,1);py(end+1) = py(1);

intang = mod(atan2d(diff(py),diff(px)),360)
intang =
       27.455
       260.18
        165.2
       261.95
       32.475
       114.91
       238.09
       96.628
       44.567
       207.94
       
find(intang > 180)
ans =
     2
     4
     7
    10

I appended the first point to the end, to make it closed. The count of vertices with interior angles that exceed 180 degrees numbers 4.

Answer 2

[Bruno Luong]

Trivially any mesh generator will do this.

Answer 3

[Boris Blagojevic]

You could use e.g. the Delaunay Triangulation plus the convhull/inpolygon functions. Triangulate your shape, throw all triangles away which have their center outside the shape (check by inpolygon). Then, take some triangle, fuse it with a neighbor and check if the result is convex (by using convhull). Do this until it is no longer the case, then remove all vertices which are only contained in the fused triangles and start again.