最小面积包围矩形？

Question

最小面积包围矩形？

algorithmmatrixcomputational-geometrygeometry-surface

4

我需要一个算法来解决以下问题（我已经尝试过一些个人解决方案，但它们似乎不是最优的）

如果给定一个带有标记和未标记区域的表面（以矩阵形式），以及可以以任何形式或位置操作的两个矩形，请找到可能的矩形形状和位置，使其覆盖所有标记区域的同时保持最小的表面积。

- Silviu

你可以尝试所有的矩形：O(n^8)。虽然不是很高效，但也没关系。 - user1035652

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- orlp · Accepted Answer

本答案假设您无法旋转矩形，且边始终平行于x和y轴。

首先，找到包含整个区域的矩形。一个实现该算法的方法如下（假设原点在左上角）:

For each marked spot in the matrix:
    if spot.x < rectangle.left:
        rectangle.left = spot.x
    if spot.x > rectangle.right:
        rectangle.left = spot.x
    if spot.y < rectangle.top:
        rectangle.left = spot.x
    if spot.y < rectangle.bottom:
        rectangle.left = spot.x

然后，像这样找到最大的水平间隔：

largest_gap = -1
For each column in matrix:
     last_marked_spot = 0, 0
     For each spot in column:
         if spot.marked:
             if spot.x - last_marked_spot.x > largest_gap:
                 largest_gap = spot.x - last_marked_spot.x
             last_marked_spot = spot

同样，对于垂直间隔也是如此。然后检查哪个间隔最大。接下来使用最大的间隔将包含所有内容的矩形分成两部分。最后一步是折叠这两个矩形（使用顶部算法的相反操作）。