在2D平面上反转一组矩形

Question

我有一个整数维矩形平面.在这个平面内部,我有一组非交叉矩形(整数维和整数坐标).

我的问题是如何有效地找到该集的逆; 这是平面中未包含在子矩形中的部分.当然,这个点集合形成了一组矩形 - 这些是我感兴趣的.

我当前的天真解决方案使用布尔矩阵(平面的大小),并通过将点i,j设置为0来实现,如果它包含在子矩形内,则为1.然后我遍历矩阵的每个元素,如果它是1(自由),则试图从该点向外"生长"一个矩形.唯一性不是问题(任何合适的矩形都很好).

有没有哪种算法可以更有效地解决这个问题？(即,无需求助于布尔矩阵.

Answer 1

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

无论如何,基本上你可以这样做:

• 从包含单个输出rect的输出列表开始,该输出矩形等于感兴趣的区域(某些任意边界框定义感兴趣的区域并包含所有输入的rects)
• 对于每个输入矩形
  • 如果输入rect与输出列表中的任何rects相交
    • 删除旧的输出rect并生成最多四个新的输出rects,表示交集和原始输出rect之间的差异

可选的最后一步:遍历输出列表,查找可以合并为单个rect的rects对(即,共享公共边的rects对可以组合成单个rect).

Answer 2

好的!第一次实施!(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;
}

可能在这里工作的例子