8

我有一个整数维度的矩形平面。在这个平面内部，我有一组不相交的矩形（整数维度和整数坐标）。

我的问题是如何有效地找到这个集合的倒数；即不包含在子矩形中的平面部分。自然地，这些点的集合形成了一组矩形——我感兴趣的正是这些。

我当前的、幼稚的解决方案使用布尔矩阵（平面的大小）并通过将点 i,j 设置为 0（如果它包含在子矩形内）来工作，否则设置为 1。然后我遍历矩阵的每个元素，如果它是 1（自由）尝试从该点向外“增长”一个矩形。唯一性不是问题（任何合适的矩形集都可以）。

有没有算法可以更有效地解决这样的问题？（即，无需求助于布尔矩阵。

4

5 回答 5

7

是的，这很简单。我以前在 SO 上回答过一个几乎相同的问题，但还没有找到。

无论如何，基本上你可以这样做：

  • 从一个输出列表开始，其中包含一个等于感兴趣区域的输出矩形（一些任意边界框，它定义了感兴趣区域并包含所有输入矩形）
  • 对于每个输入矩形
    • 如果输入矩形与输出列表中的任何矩形相交
      • 删除旧的输出矩形并生成最多四个新的输出矩形，它们表示交集与原始输出矩形之间的差异

可选的最后一步：遍历输出列表，寻找可以合并为单个矩形的矩形对（即，共享公共边的矩形对可以合并为单个矩形）。

于 2010-11-21T19:10:25.330 回答
5

好吧！首次实施！(java)，基于@Paul 的 回答：

List<Rectangle> slice(Rectangle r, Rectangle mask)
{
        List<Rectangle> rects = new ArrayList();

        mask = mask.intersection(r);

        if(!mask.isEmpty())
        {
                rects.add(new Rectangle(r.x, r.y, r.width, mask.y - r.y));
                rects.add(new Rectangle(r.x, mask.y + mask.height, r.width, (r.y + r.height) - (mask.y + mask.height)));
                rects.add(new Rectangle(r.x, mask.y, mask.x - r.x, mask.height));
                rects.add(new Rectangle(mask.x + mask.width, mask.y, (r.x + r.width) - (mask.x + mask.width), mask.height));

                for (Iterator<Rectangle> iter = rects.iterator(); iter.hasNext();)
                        if(iter.next().isEmpty())
                                iter.remove();
        }
        else rects.add(r);

        return rects;
}

List<Rectangle> inverse(Rectangle base, List<Rectangle> rects)
{
        List<Rectangle> outputs = new ArrayList();
        outputs.add(base);

        for(Rectangle r : rects)
        {
                List<Rectangle> newOutputs = new ArrayList();

                for(Rectangle output : outputs)
                {
                        newOutputs.addAll(slice(output, r));
                }

                outputs = newOutputs;
        }
        return outputs;
}

可能在这里工作的例子

于 2010-11-21T20:21:22.057 回答
2

你应该看看空间填充算法。这些算法正在努力用一些几何图形填充给定的空间。根据您的需要修改此类算法应该不难。

这种算法是从头开始（空白），所以首先你用你已经在 2D 平面上拥有的框填充他的内部数据。然后你让算法来做剩下的事情——用另一个盒子填满剩余的空间。这些盒子正在列出你飞机的倒置空间块。

您将这些框保留在某个列表中，然后检查一个点是否在倒置平面上非常容易。您只需遍历您的列表并检查点是否位于框内。

这是一个包含大量算法的站点，可能会有所帮助。

于 2010-11-21T19:16:36.663 回答
0

这相对简单，因为您的矩形不相交。目标基本上是一组完全覆盖平面的不相交矩形，一些标记为原始矩形，一些标记为“反向”。

考虑自上而下（或左右或其他）扫描。你有一个当前的“潮汐线”位置。确定您将遇到的下一条水平线的位置不在潮线上。这将为您提供下一条潮汐线的高度。

在这些潮汐线之间，您有一条带，其中每条垂直线从一条潮汐线延伸到另一条潮汐线（可能在两个方向上都超出）。您可以对这些垂直线的水平位置进行排序，并使用它将条带划分为矩形，并将它们识别为原始矩形的（部分）或反向矩形的（部分）。

进行到最后，你会得到（可能太多太小的）矩形，并且可以选择你想要的。您还可以选择（在每个步骤中）将当前条带中的小矩形与之前的一组潜在可扩展矩形组合起来。

即使您的原始矩形可能相交，您也可以这样做，但这有点繁琐。

留给读者练习的细节;-)

于 2010-11-21T19:14:56.623 回答
0

我怀疑您可以通过按 y 坐标对矩形进行排序并采用扫描线方法来到达某个地方。我可能会也可能不会真正构建一个实现。

于 2010-11-21T19:09:23.947 回答