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 回答