用矩形填充直角多边形

Question

给定一个由矩形完全构成的多边形，由点数组定义，其中边始终与轴对齐：

我正在尝试确定一个快速算法，以找到一小部分可以填满这个形状的矩形。这是我用手做的示例，展示了我所描述的矩形集合：

编辑： 这里有一些简单的processing代码来创建这个形状（嗯，接近它）。

float[] xpts = {0,    50,  50,  100, 100, 150, 150, 250, 250, 300, 300, 325, 325, 300, 300, 250, 250, 210, 210, 250, 250, 125, 125, 25, 25,   50,  50,  0 };
float[] ypts = {100, 100,  80,   80, 10,   10,  80, 80,  75,  75, 80,   80,  200, 200, 300, 300, 275, 275, 260, 260, 200, 200, 270, 270, 165, 165, 125, 125};


void setup( )
{
  size( 350, 350 );
}

void draw( )
{

stroke( 0 );
strokeWeight( 1.5 );

float px = xpts[0];
float py = ypts[0];
for (int i=1; i < xpts.length; i++)
{
  float nx = xpts[i];
  float ny = ypts[i];
  line( px, py, nx, ny );


  px = xpts[i];
  py = ypts[i];
}
float nx = xpts[0];
float ny = ypts[0];

line( px, py, nx, ny );
}

- jedierikb

---

边缘是否总是与轴对齐？如果是，您可以使用扫描线轻松找到最大区域。 - Flexo

是的，边缘始终是轴对齐的（我会更新帖子）。您能详细介绍一下扫描线方法吗？谢谢。 - jedierikb

@finnw - 我认为这个问题与那个问题足够不同 - 这里的输入是一个边缘列表。 - Flexo

请查看覆盖一组矩形所需最少矩形的算法。 - Gareth Rees

Answer 1

使用现有的边作为分裂平面来构建KD树，并在递归过程中忽略完全位于多边形外部的区域。叶节点将组成矩形分解。

获得良好的分解只是在递归的每个步骤中选择哪个分裂器的问题。您可以使用简单的启发式算法，每一步将剩余区域减半。如果需要，您也可以尝试几种不同的分裂器！

以下是一些伪代码：

function makeRects(Rect r, Polygon p)

  if p is empty
    if r is inside your original polygon
      add r to results

  else
    choose good splitter s

    makeRects(left part of r relative to s, left part of p relative to s)
    makeRects(right part of r relative to s, right part of p relative to s)

- ltjax

---

你能给个例子吗？我不是很清楚每个分割的子节点是如何定义的。 - Null Set

每个分裂的子空间都是剩余的子空间。也就是说，分裂平面的两半与父节点关联的子空间相交。 - ltjax

一些伪代码（可以是非常高级的）将有助于理解如何操作化您的建议。非常感谢。 - jedierikb

根据您的要求，我添加了一些伪代码。它留下了很多自由度。例如，您实际上不需要显式测试r是否在原始多边形内部以打破递归：通常可以从上一级的分裂平面推导出来！ - ltjax

我明白了，谢谢。但是，“相对于s的p的左部分”不是一项相当昂贵的操作吗？我知道如果p被修剪得越多，它会变得更便宜，但这仍然需要进行大量的点检查，不是吗？ - jedierikb

如果你以天真的方式实现它，那么它应该是线性的。但即便如此，它应该还是相当快的，所以不用过于担心。 - ltjax

Answer 2

听起来很像一个NP问题。这意味着，如果矩形的数量对你不是很重要，那么肯定有一些算法可以快速地填充你的形状，但是如果你坚持要求最小数量，那么你最好忘记“快”这个词。实际上，你甚至应该忘记“最小”这个词，而改用“小”，因为确定集合是否最小已经是算法的一个巨大问题了。

- Mecki

---

最小的改为小的。谢谢！ - jedierikb

你能画一个证明为什么这是 NP 问题吗？ - citykid

@citykid 现在问题说得很小，它不再是一个 NP 问题了，但最初它是说最小的。请给我展示一个数学测试来验证一个解决方案是“最小的”，并且可以在多项式时间内运行。我不知道有任何这样的测试，因此验证一个解决方案是否最小已经成为 NP 问题，因此找到最小的解决方案也是 NP 问题。这类似于旅行商或背包问题 - 在短时间内找到一个好的解决方案是可能的，但找到完美的解决方案是 NP 问题。 - Mecki

干得好，同意，这确实是一个很棘手的问题。 - citykid

嗨，感谢您的提问。 我使用Hopcroft和Karp算法制作了图形顶点并将其缩小。 您甚至可以通过仅绘制切割线来快捷完成此步骤，以将多边形（正交）转换为一组矩形。结果可能会得到比最少矩形数量更多的矩形，但通常不会是一个大问题。好吧，如果您在奇怪的应用程序中处理数千个小正交图形，那可能就是问题了。现在我的问题是，一旦我画出这些矩形，我就无法填充它们。 我很难理解所提议的算法。 有没有示例？谢谢。 - Jean-Yves DANIEL

您的假设是错误的。参见“如果一个多边形的所有边都是轴向平行的，则可以在多项式时间内找到将其分割为尽可能少的矩形”的分割方法（https://mathoverflow.net/questions/28303/split-polygon-into-minimum-amount-of-rectangles-and-triangles/28350#28350）。 - arkon