Convex polygon partitioning in MATLAB

36 views (last 30 days)
Elena
Elena on 4 Apr 2011
Answered: Boris Blagojevic on 18 May 2021
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

Answers (3)

John D'Errico
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.
  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.

Bruno Luong
Bruno Luong on 2 Oct 2020
Trivially any mesh generator will do this.

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

Categories

Find more on Spatial Search in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!