1

x1、y1、x2、y2座標を含む構造で表される2つの長方形があります。1つの長方形は親、別の長方形は子と見なすことができます。

子の長方形が親の長方形内にあるかどうかを検出する方法はすでに知っています。私が今理解しようとしているのは、子の長方形と重なっていない親内の長方形の領域を決定するための最も簡単で最速の方法です。

たとえば、100x100の親の長方形と、親の真ん中に配置された50x50の子の長方形について考えてみます。これは、子がオーバーラップしていない親長方形の4つの領域を表す4つの長方形があることを意味します。

もちろん、子供は左上、右上、左下、右下隅、または少し左、少し右などにいる可能性があります... 1、2、3、または4つある可能性があります重ならない領域を表す長方形。

これを理解するための実装についていくつかのアイデアがありましたが、すべてが非常に複雑に見えます。これを理解するための簡単で迅速な方法はありますか？

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 が交差する可能性のある部分を削除することです。toprect からそのセクションをトリムするための中間ステップとして「trimmedparent」を使用しました。

于 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

これは基本的なアルゴリズムです:

子の各点が親の内側にある場合、対応する子と親の点は対角線の長方形を形成します。ここで、子の各辺について、2 つの点が親にある場合、それらの 2 つの点と親の端にある一致する点は長方形を形成します。子のエッジ上のポイントの 1 つだけが親にある場合、このポイントと、親にない子のエッジ ポイントに対応する親ポイントは、長方形の対角線を形成します。これらの長方形を返します。

最大 8 つの長方形が得られます (各コーナーに 1 つ、各エッジに 1 つ)。最小限の長方形が必要な場合は、それらがエッジを共有しているかどうかを確認し、共有している場合はそれらを結合します。

于 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 に答える