1

我有两个由包含 x1、y1、x2、y2 坐标的结构表示的矩形。一个矩形可以被认为是父母，另一个是孩子。

我已经知道如何检测子矩形是否在父矩形内；我现在要弄清楚的是最简单，最快的方法来确定父级中未被子矩形重叠的矩形区域。

例如，考虑一个 100x100 的父矩形和一个 50x50 的子矩形，正好位于父矩形的中心。这意味着将有四个矩形代表父矩形中未被子矩形重叠的四个区域。

当然，孩子可能在左上角、右上角、左下角、右下角，或者向左一点、向右一点等等……可能有一个、两个、三个或四个表示非重叠区域的矩形。

我有一些实现的想法来解决这个问题，但似乎都过于复杂。有没有一种简单、快速的方法来解决这个问题？

4

5 回答 5

1

所以最多可以有 4 个矩形的非重叠区域。让我们列出它们。

leftrect = rightrect = toprect = bottomrect = None
trimmedparent = duplicate(parent)

if parent.x1 < child.x1:
    leftrect = duplicate(parent)
    leftrect.x2 = child.x1
    trimmedparent.x1 = child.x1

if parent.x2 > child.x2:
    rightrect = duplicate(parent)
    rightrect.x1 = child.x2
    trimmedparent.x2 = child.x2

if parent.y1 < child.y1:
    toprect = duplicate(trimmedparent)
    toprect.y2 = child.y1

if parent.y2 > child.y2:
    bottomrect = duplicate(trimmedparent)
    bottomrect.y1 = child.y2

唯一棘手的部分是消除leftrect 和toprect 可能相交的部分。我使用 'trimmedparent' 作为中间步骤从 toprect 修剪该部分。

于 2009-06-02T22:19:57.150 回答
0 
parent = Rectangle.new(x1,y1,mx1,my1)
child = Rectangle.new(x2,y2,mx2,my2)

rects = []
if (parent.contains(child))
  rects.push Rectangle.new(parent.x, parent.y, parent.mx, child.y) if child.y>parent.y
  rects.push Rectangle.new(parent.x, child.my, parent.mx, parent.my) if child.my<parent.my
  rects.push Rectangle.new(parent.x, parent.y, child.x, pareny.my) if child.x>parent.x
  rects.push Rectangle.new(child.mx, parent.y, parent.mx, parent.my) if child.mx<parent.mx
end
于 2009-06-02T22:12:49.927 回答
0

这是基本算法：

对于子节点中的每个点，如果它在父节点内部，则对应的子节点和父节点组成对角线一个矩形。现在，对于子节点的每一侧，如果两个点在父节点中，则这两个点和父节点边缘上的匹配点形成一个矩形。如果子节点边缘上只有一个点在父节点中，则该点与子节点边缘点对应的父节点不在父节点中，形成一个矩形的对角线。返回这些矩形。

您将获得最多八个矩形（每个角一个，每个边一个）。如果您想要尽可能少的矩形，请查看它们是否共享边缘，如果共享，则将它们组合起来。

于 2009-06-02T22:15:57.783 回答
0

这是计算父项非重叠区域的另一种方法：

Function max(ByVal v1 As Double, ByVal v2 As Double) As Double
    If v1 > v2 Then
        Return v1
    Else
        Return v2
    End If
End Function

Function min(ByVal v1 As Double, ByVal v2 As Double) As Double
    If v1 > v2 Then
        Return v2
    Else
        Return v1
    End If
End Function

Function IntervalOverLap(ByVal p1 As Double, ByVal p2 As Double, ByVal c1 As Double, ByVal c2 As Double) As Double
    'determine how much of the parent(p1 to p2) segment '
    ' is overlapped by the child(c1 to c2) segment      '

    'sort to standard direction  '
    Dim ph As Double = max(p1, p2)
    Dim pl As Double = min(p1, p2)
    Dim ch As Double = max(c1, c2)
    Dim cl As Double = min(c1, c2)

    'restrict the child to within the parent '
    ch = min(ph, max(pl, ch))
    cl = max(pl, min(cl, ph))

    'return the overlapped length  '
    Return (ch - cl)
End Function

Function NonOverLappedArea(ByVal parent As Rectangle, ByVal child As Rectangle) As Double
    'return the area of the parent        '
    ' that is not overlapped by the child '
    Return IntervalOverLap(parent.X1, parent.X2, child.X1, child.X2) _
        * IntervalOverLap(parent.Y1, parent.Y2, child.Y1, child.Y2)
End Function
于 2009-06-02T23:50:14.033 回答
0

根据您的描述，孩子总是完全被父母所包含。所以非重叠区域总是一个矩形甜甜圈，尽管它可能在 4 个边中的任何一个上退化，因为子边可能与父边相邻，完全退化的情况是子边与父边相同.

甜甜圈可以分解成4个矩形。分解可能不是唯一的，这意味着您可以根据执行分解的方式获得不同的矩形。在 4 个矩形中，丢弃退化的（面积为 0 的），就完成了。

这是一个垂直偏向的分解

// assume the child is known to be in the parent bounds at this point
// assume parent and child are normalized
std::vector<CRect> rects;
CRect rect( parent.x1(), parent.y1(), child.x1(), parent.y2() ); // left
if ( rect.area() > 0.0 ) rects.push_back(rect);
rect.set( child.x1(), parent.y1(), child.x2(), child.y1() ); // bottom
if ( rect.area() > 0.0 ) rects.push_back(rect);
rect.set( child.x1(), child.y2(), child.x2(), parent.y2() ) ); // top
if ( rect.area() > 0.0 ) rects.push_back(rect);
rect.set( child.x2(), parent.y1(), parent.x2(), parent.y2() ) ); // right
if ( rect.area() > 0.0 ) rects.push_back(rect);

// yes, this could be written without all the code replication... :)
于 2009-06-02T23:56:54.990 回答