3
$\begingroup$

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?

$\endgroup$
3
  • $\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$
    – SandeepJ
    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$ Jun 16, 2010 at 0:51

1 Answer 1

15
$\begingroup$

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.

$\endgroup$
2
  • $\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$
    – Neonit
    Jan 9, 2020 at 14:11
  • $\begingroup$ Do you know of any information on the 3d version of this problem? $\endgroup$
    – Aedoro
    Jan 18 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.