11

我正在寻找一种算法，该算法将确定一个新矩形是否完全被一组现有矩形覆盖。提出问题的另一种方式是，新矩形是否完全存在于现有矩形覆盖的区域中？

似乎有很多算法可以确定矩形重叠等，但我真的找不到任何可以解决这个确切问题的方法。

矩形将使用 x、y 坐标表示。这个问题与地理测绘有关。

编辑- 来自 OP 发表的评论：

矩形在 X/Y 轴上对齐

4

7 回答 7

8

如果矩形对齐很容易：

假设您有矩形 A0 并想知道它是否被 (B1, B2, B3...) = B 完全覆盖

A := (A0)
while P := pop B
  for R in A
    if P fully covers R:
      remove R from A
    else if P and R does overlap:
      remove R from A
      break R in subrentangles S := (S1, S2, S3,...) following the intersections \
                                                     with P edges
      push S into A
if A is empty:
   say B covers A0
else:
   say B does not fully cover A0
于 2010-12-09T10:55:53.713 回答
3

如果矩形都具有相同的角度；那么以下内容可能会让我更高效、更容易编程：

为每个 y 坐标确定哪些矩形覆盖了该 y 坐标（您只需对覆盖变化的 y 坐标执行此操作；即对应于矩形的上限或下限）。一旦你知道了，解决每个这样的 y 坐标的问题（即检查是否所有的 x 值都被那个 Y 坐标“活动”的矩形所覆盖）。

编辑：我认为这是 O(n^2 log(n)^2) 复杂性，因为两种都是你必须做的艰苦工作

于 2010-12-09T10:45:33.420 回答
2

这是我的代码，正如你所要求的：

第一种方法“减去”（返回未覆盖的部分）2 个矩形。

第二种方法从基础矩形中减去一个矩形列表。

在您的案例列表中包含现有的矩形，而新的矩形是基础

要检查是否存在完整的交集，从第二种方法返回的列表应该没有元素。

public static List<Rectangle> SubtractRectangles(Rectangle baseRect, Rectangle splitterRect)
    {
        List<Rectangle> newRectaglesList = new List<Rectangle>();

        Rectangle intersection = Rectangle.Intersect(baseRect, splitterRect);
        if (!intersection.IsEmpty)
        {
            Rectangle topRect = new Rectangle(baseRect.Left, baseRect.Top, baseRect.Width, (intersection.Top - baseRect.Top));
            Rectangle bottomRect = new Rectangle(baseRect.Left, intersection.Bottom, baseRect.Width, (baseRect.Bottom - intersection.Bottom));

            if ((topRect != intersection) && (topRect.Height != 0))
            {
                newRectaglesList.Add(topRect);
            }

            if ((bottomRect != intersection) && (bottomRect.Height != 0))
            {
                newRectaglesList.Add(bottomRect);
            }
        }
        else
        {
            newRectaglesList.Add(baseRect);
        }

        return newRectaglesList;
    }

    public static List<Rectangle> SubtractRectangles(Rectangle baseRect, List<Rectangle> splitterRectList)
    {
        List<Rectangle> fragmentsList = new List<Rectangle>();
        fragmentsList.Add(baseRect);

        foreach (Rectangle splitter in splitterRectList)
        {
            List<Rectangle> toAddList = new List<Rectangle>();

            foreach (Rectangle fragment in fragmentsList)
            {
                List<Rectangle> newFragmentsList = SubtractRectangles(fragment, splitter);
                toAddList.AddRange(newFragmentsList);
            }

            if (toAddList.Count != 0)
            {
                fragmentsList.Clear();
                fragmentsList.AddRange(toAddList);
            }
        }

        return fragmentsList;
    }
于 2010-12-09T12:03:43.710 回答
2

我过去做过类似的事情。想法是将新矩形与现有的每个矩形进行比较（一个接一个）

如果存在交叉点，则丢弃它（相交部分），并将未覆盖的段添加到矩形数组中

接下来，搜索新线段与其他现有（仍未选中）矩形之间的交集。

算法递归地丢弃交叉点，只留下未覆盖的部分。

最后，如果数组中没有矩形，则完全重叠

如果数组中仍有一些矩形，则重叠不完整，因为仍有一些部分。

希望这可以帮助

如果这是您要查找的内容，我可以尝试找到我的代码。我认为它在 C#

另一个想法是将所有现有矩形转换为多边形，然后检查新矩形是否在多边形内，但如果您不使用知道如何使用多边形的语言（或框架），我不建议这样做。

于 2010-12-09T10:39:22.487 回答
2

R-tree可能有用。如果可能有旋转的矩形，您可以将它们括在边界矩形中。

于 2010-12-09T11:03:46.193 回答
1

尝试这个

源矩形：X0、Y0、宽度、高度

// 基本上比较边缘

if(((X0 >= xi) && (X0+breadth <= Xi)) && ((Y0 >= Yi)&&(Y0+height <= Yi)) { //考虑矩形 } else { // 丢弃 }

于 2010-12-09T11:16:41.603 回答
0

您可以使用用于计算矩形联合面积的算法。因为您要检查矩形 a 是否被矩形 B={b_1, b_2, ..., } 覆盖。

首先计算 B 中矩形的并集面积，我们得到 area_1 作为值。

然后计算 B+ {a} 中矩形的并集面积，我们得到 area_2 作为值。
所以如果 area_1 == area_2，那么你确定矩形 A 被矩形 B 覆盖。否则，答案是错误的。

所以主要的问题是如何计算矩形的联合面积。这个问题可以通过现有的优秀算法来解决。该算法可以简单介绍为首先对矩形点的值进行离散化，然后使用Segmentation Tree来加速计算每个块的面积。

于 2015-03-31T08:38:24.083 回答