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$
$\endgroup$
3
-
$\begingroup$ What specific quantity are you trying to minimize? Total number of polygons? $\endgroup$– S. Carnahan ♦Commented 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$– SandeepJCommented Jun 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'RourkeCommented Jun 16, 2010 at 0:51
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
I'm not sure what you mean about the triangles, but if a polygon has all its sides axis-parallel, 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 axis-parallel 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 axis-parallel 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 two-dimensional 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.
answered Jun 16, 2010 at 4:44
-
$\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$– NeonitCommented Jan 9, 2020 at 14:11
-
$\begingroup$ Do you know of any information on the 3d version of this problem? $\endgroup$– AedoroCommented Jan 18 at 9:36