Hi is there an algorithm which cuts a polygon into a minimum amount of preferably rectangles and where not possible (e.g. edges) into triangles?

$\begingroup$ What specific quantity are you trying to minimize? Total number of polygons? $\endgroup$– S. Carnahan ♦Jun 15, 2010 at 19:47

$\begingroup$ You are probably looking for a space partititioning algorith (en.wikipedia.org/wiki/Space_partitioning) in computational geometry. Perhaps the equivalent of a Delaunay triangulation but with rectangles (en.wikipedia.org/wiki/Delaunay_triangulation) $\endgroup$– SandeepJJun 15, 2010 at 20:33

$\begingroup$ Another possible interpretation of the question would be to partition a polygon into a minimum number of pieces, each of which is either a triangle or a rectangle. My guess is that this version is a difficult problem. $\endgroup$– Joseph O'RourkeJun 16, 2010 at 0:51
1 Answer
I'm not sure what you mean about the triangles, but if a polygon has all its sides axisparallel, it is possible to find a partition into the minimum possible number of rectangles in polynomial time. The idea is to find the maximum number of disjoint axisparallel diagonals that have two concave vertices as endpoints, split along those, and then form one more split for each remaining concave vertex. To find the maximum number of disjoint axisparallel diagonals, form the intersection graph of the diagonals; this graph is bipartite so its maximum independent set can be found in polynomial time by graph matching techniques.
This method comes from several independent papers:
 W. Lipski, Jr., E. Lodi, F. Luccio, C. Mugnai, and L. Pagli. On twodimensional data organization II. Fundamenta Informaticae, 2:245–260, 1979.
 T. Ohtsuki. Minimum dissection of rectilinear regions. In Proc. IEEE Int. Symp. Circuits and Systems, pages 1210–1213, 1982.
 L. Ferrari, P. V. Sankar, and J. Sklansky. Minimal rectangular partitions of digitized blobs. Computer Vision, Graphics, and Image Processing, 28(1):58–71, 1984.
It's described in more detail in section 3 of my survey paper arXiv:0908.3916.

$\begingroup$ In your linked paper you write, after finding a maximum matching in the graph, the vertices should be partitioned by length of the shortest alternating path to an unmatched vertex and the ones with even values should be used to section the polygon. I do not understand what to do with vertices that have no (alternating) path to an unmatched vertex or if there is no unmatched vertex at all (I don't know, if that's possible, though). Could you please elaborate on that? $\endgroup$– NeonitJan 9, 2020 at 14:11