- Consider if a polygon has NO interior angles that exceed 180 degrees. If so, then it is convex, and you are done.
- 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.
- If there are exactly 2 such vertices, then you can connect the two. Again, this must form a splitting into two convex polygons.
- 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.
Convex polygon partitioning in MATLAB
21 views (last 30 days)
John D'Errico on 1 Oct 2020
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.
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)
find(intang > 180)
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.
Boris Blagojevic on 18 May 2021
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.