146

2 つの長方形が交差しているかどうかを検出するアルゴリズムを探しています (1 つは任意の角度、もう 1 つは垂直/水平線のみ)。

一方のコーナーが他方の ALMOST にあるかどうかのテストは機能します。長方形が十字のような形状を形成する場合、失敗します。

垂直線に特殊なケースが必要になるため、線の傾斜を使用しないようにすることをお勧めします。

4

20 に答える 20

164

標準的な方法は、分離軸テストを行うことです (それについて Google 検索を行います)。

要するに：

  • 2 つのオブジェクトを分離する線が見つかった場合、2 つのオブジェクトは交差していません。たとえば、オブジェクト/オブジェクトのすべての点が線の異なる側にあります。

面白いことに、2 つの長方形のすべてのエッジをチェックするだけで十分です。長方形が重ならない場合、エッジの 1 つが分離軸になります。

2D では、勾配を使用せずにこれを行うことができます。エッジは、単純に 2 つの頂点の差として定義されます。

  edge = v(n) - v(n-1)

90°回転させると、これに垂直になります。2D では、これは次のように簡単です。

  rotated.x = -unrotated.y
  rotated.y =  unrotated.x

したがって、三角法や勾配は関係ありません。ベクトルを単位長に正規化する必要もありません。

点が線のどちらか一方の側にあるかどうかをテストしたい場合は、内積を使用できます。サインはあなたがどちら側にいるかを教えてくれます：

  // rotated: your rotated edge
  // v(n-1) any point from the edge.
  // testpoint: the point you want to find out which side it's on.

  side = sign (rotated.x * (testpoint.x - v(n-1).x) + 
               rotated.y * (testpoint.y - v(n-1).y);

ここで、長方形 A のすべての点を長方形 B のエッジに対してテストし、その逆も同様です。分離エッジが見つかった場合、オブジェクトは交差しません (B の他のすべてのポイントがテスト対象のエッジの反対側にある場合 - 下の図を参照)。分離エッジが見つからない場合は、長方形が交差しているか、1 つの長方形が別の長方形に含まれています。

テストは凸多角形で動作します..

修正:分離エッジを識別するには、1 つの長方形のすべてのポイントを他の各エッジに対してテストするだけでは不十分です。候補エッジ E (以下) は、A のすべての点が E の同じ半平面にあるため、分離エッジとして識別されます。ただし、B の頂点 Vb1 と Vb2 は分離エッジではありません。もその半平面にあります。もしそれがなかったら、それは唯一の分離エッジだっただろう http://www.iaassess.com/collision.png

于 2008-09-22T15:28:21.650 に答える
15

基本的に次の図を見てください。


2 つのボックスが衝突すると、線 A と B が重なります。

これは X 軸と Y 軸の両方で行う必要があり、長方形が衝突するには両方が重なる必要があることに注意してください。

質問に答える良い記事がgamasutra.comにあります (写真は記事からのものです)。私は5年前に同様のアルゴリズムを実行しましたが、後でここに投稿するにはコードスニペットを見つける必要があります

修正: 分離軸の定理では、分離軸が存在する場合 (つまり、図示の投影が重ならない軸)、2 つの凸形状は重ならないことが述べられています。したがって、「分離軸が存在します」=>「重なりはありません」。これは双方向の含意ではないため、逆を結論付けることはできません。

于 2008-09-22T15:25:54.727 に答える
4

Cocoa では、selectedArea rect が回転した NSView のフレーム rect と交差するかどうかを簡単に検出できます。ポリゴンや法線などを計算する必要さえありません。これらのメソッドを NSView サブクラスに追加するだけです。たとえば、ユーザーが NSView のスーパービューで領域を選択し、次に、doesThisRectSelectMe メソッドを呼び出して、selectedArea rect を渡します。API convertRect: がその仕事をします。NSView をクリックして選択すると、同じトリックが機能します。その場合は、以下のように hitTest メソッドをオーバーライドするだけです。API convertPoint: その仕事をします;-)

- (BOOL)DoesThisRectSelectMe:(NSRect)selectedArea
{
    NSRect localArea = [self convertRect:selectedArea fromView:self.superview];

    return NSIntersectsRect(localArea, self.bounds);
}


- (NSView *)hitTest:(NSPoint)aPoint
{
    NSPoint localPoint = [self convertPoint:aPoint fromView:self.superview];
    return NSPointInRect(localPoint, self.bounds) ? self : nil;
}
于 2012-12-14T12:19:13.883 に答える
3

m_pGladiator の答えは正しく、私はそれを好みます。 分離軸テストは、長方形の重なりを検出する最も簡単で標準的な方法です。投影間隔が重ならない線を分離軸と呼びます。Nils Pipenbrinck のソリューションは一般的すぎます。内積を使用して、一方の形状が完全に他方のエッジの片側にあるかどうかを確認します。この解決策は、実際には n エッジの凸多角形を引き起こす可能性があります。ただし、2 つの長方形には最適化されていません。

m_pGladiator の回答の重要な点は、2 つの長方形の投影を両方の軸 (x と y) で確認する必要があるということです。2 つの投影が重なっている場合、これら 2 つの長方形が重なっていると言えます。したがって、m_pGladiator の回答に対する上記のコメントは間違っています。

単純な状況として、2 つの長方形が回転されていない場合、構造を持つ長方形を提示します。

struct Rect {
    x, // the center in x axis
    y, // the center in y axis
    width,
    height
}

長方形 A、B を rectA、rectB と名付けます。

    if Math.abs(rectA.x - rectB.x) < (Math.abs(rectA.width + rectB.width) / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(rectA.height + rectB.height) / 2))
    then
        // A and B collide
    end if

2 つの長方形のいずれかが回転している場合は、x 軸と y 軸でのそれらの投影を決定するために何らかの努力が必要になる場合があります。RotatedRect 構造体を次のように定義します。

struct RotatedRect : Rect {
    double angle; // the rotating angle oriented to its center
}

違いは、width' が少し異なっていることです: rectA の場合は widthA': Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) rectB の場合は widthB':Math.sqrt(rectB.width*rectB.width + rectB.height*rectB.height) * Math.cos(rectB.angle)

    if Math.abs(rectA.x - rectB.x) < (Math.abs(widthA' + widthB') / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(heightA' + heightB') / 2))
    then
        // A and B collide
    end if

GDC (Game Development Conference 2007) PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.pptを参照できます。

于 2012-11-25T11:53:13.813 に答える
2

1 つの長方形の線が他の長方形の線と交差するかどうかを確認します。単純な線分の交点は、コーディングが簡単です。

さらに速度が必要な場合は、線分交差 (スイープライン) の高度なアルゴリズムがあります。http://en.wikipedia.org/wiki/Line_segment_intersectionを参照

于 2008-09-22T15:23:28.383 に答える
2

1 つの解決策は、No Fit Polygon と呼ばれるものを使用することです。このポリゴンは 2 つのポリゴンから計算され (概念的には、一方を他方の周りにスライドさせることによって)、相対オフセットを指定してポリゴンがオーバーラップする領域を定義します。この NFP を取得したら、2 つのポリゴンの相対オフセットによって指定されたポイントを使用して包含テストを実行するだけです。この包含テストは迅速かつ簡単ですが、最初に NFP を作成する必要があります。

Web で No Fit Polygon を検索して、凸多角形のアルゴリズムを見つけられるかどうかを確認してください (凹多角形の場合はさらに複雑になります)。何も見つからない場合は、howard dot J dot may gmail dot com にメールしてください。

于 2008-10-15T11:56:24.963 に答える
0

分離軸テストを使用するよりもわずかに高速なテストを実行する別の方法は、いずれかの長方形 (任意に選択) の各頂点で (象限のみ - 恐ろしく遅い角度の合計ではなく) 巻き数アルゴリズムを使用することです。いずれかの頂点の巻き数が 0 でない場合、2 つの長方形が重なります。

このアルゴリズムは、分離軸テストよりもやや長くなりますが、エッジが 2 つの象限を横切る場合に半平面テストのみを必要とするため (分離軸法を使用した最大 32 テストとは対照的に) 高速です。

このアルゴリズムには、任意の多角形 (凸面または凹面)のオーバーラップをテストするために使用できるというさらなる利点があります。私の知る限り、このアルゴリズムは 2D 空間でのみ機能します。

于 2011-03-26T16:43:35.090 に答える
0

Java を使用している場合、Shape インターフェースのすべての実装には、長方形を取るintersectsメソッドがあります。

于 2008-09-22T15:22:10.430 に答える
0

強引な方法は、水平方向の長方形の端をたどり、端に沿った各点をチェックして、それが他の長方形の上にあるかどうかを確認することです。

数学的な答えは、両方の長方形の各エッジを記述する方程式を形成することです。これで、四角形 A の 4 本の線のいずれかが四角形 B のいずれかの線と交差するかどうかを簡単に見つけることができます。これは単純な (高速な) 線形方程式ソルバーである必要があります。

-アダム

于 2008-09-22T15:23:25.530 に答える
0

角度の付いた長方形の各辺と、軸に沿った長方形の各辺の交点を見つけることができます。これを行うには、各辺が存在する無限直線の方程式 (つまり、基本的に v1 + t(v2-v1) と v'1 + t'(v'2-v'1)) を見つけ、これらの 2 つの方程式が等しい場合に t を解くことによって線が交わり (それらが平行である場合、それをテストできます)、その点が 2 つの頂点間の線分上にあるかどうか、つまり 0 <= t が真かどうかをテストします。 <= 1 および 0 <= t' <= 1。

ただし、一方の長方形がもう一方の長方形を完全に覆っている場合は、この限りではありません。いずれかの長方形の 4 つの点すべてがもう一方の長方形の内側にあるかどうかをテストすることでカバーできます。

于 2008-09-22T15:25:37.990 に答える
0

これは、この問題の3Dバージョンに対して、私が行うことです。

2 つの長方形を方程式 P1 と P2 で記述される平面としてモデル化し、P1=P2 と書き、そこから交線方程式を導出します。平面が平行である (交差がない) 場合、または同じ平面内にある場合は存在しません。この場合、0=0 になります。その場合、2D 長方形交差アルゴリズムを使用する必要があります。

次に、両方の長方形の平面にあるその線が両方の長方形を通過するかどうかを確認します。もしそうなら、あなたは2つの長方形の交点を持っています。

線が同じ平面内の長方形を通過するかどうかを確認するには、線と長方形の辺の 2 つの交点を見つけ (線の方程式を使用してそれらをモデル化)、交点が次のようになっていることを確認します。範囲。

それは数学的な説明です。残念ながら、上記を実行するコードはありません。

于 2008-09-22T15:27:00.747 に答える
0

他の回答で十分なことが述べられているので、疑似コードのワンライナーを追加します。

!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);
于 2018-06-18T23:05:51.367 に答える
0

2 つの長方形がある場合、私自身のより簡単な方法があります。

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

次の場合にのみ重複します。

オーバーラップ = (max_x1 > min_x2) および (max_x2 > min_x1) および (max_y1 > min_y2) および (max_y2 > min_y1)

3D ボックスに対しても実行できます。実際には、任意の数の次元に対して機能します。

于 2017-06-15T21:38:27.507 に答える
0

私は次のように実装しました：

bool rectCollision(const CGRect &boundsA, const Matrix3x3 &mB, const CGRect &boundsB)
{
    float Axmin = boundsA.origin.x;
    float Axmax = Axmin + boundsA.size.width;
    float Aymin = boundsA.origin.y;
    float Aymax = Aymin + boundsA.size.height;

    float Bxmin = boundsB.origin.x;
    float Bxmax = Bxmin + boundsB.size.width;
    float Bymin = boundsB.origin.y;
    float Bymax = Bymin + boundsB.size.height;

    // find location of B corners in A space
    float B0x = mB(0,0) * Bxmin + mB(0,1) * Bymin + mB(0,2);
    float B0y = mB(1,0) * Bxmin + mB(1,1) * Bymin + mB(1,2);

    float B1x = mB(0,0) * Bxmax + mB(0,1) * Bymin + mB(0,2);
    float B1y = mB(1,0) * Bxmax + mB(1,1) * Bymin + mB(1,2);

    float B2x = mB(0,0) * Bxmin + mB(0,1) * Bymax + mB(0,2);
    float B2y = mB(1,0) * Bxmin + mB(1,1) * Bymax + mB(1,2);

    float B3x = mB(0,0) * Bxmax + mB(0,1) * Bymax + mB(0,2);
    float B3y = mB(1,0) * Bxmax + mB(1,1) * Bymax + mB(1,2);

    if(B0x<Axmin && B1x<Axmin && B2x<Axmin && B3x<Axmin)
        return false;
    if(B0x>Axmax && B1x>Axmax && B2x>Axmax && B3x>Axmax)
        return false;
    if(B0y<Aymin && B1y<Aymin && B2y<Aymin && B3y<Aymin)
        return false;
    if(B0y>Aymax && B1y>Aymax && B2y>Aymax && B3y>Aymax)
        return false;

    float det = mB(0,0)*mB(1,1) - mB(0,1)*mB(1,0);
    float dx = mB(1,2)*mB(0,1) - mB(0,2)*mB(1,1);
    float dy = mB(0,2)*mB(1,0) - mB(1,2)*mB(0,0);

    // find location of A corners in B space
    float A0x = (mB(1,1) * Axmin - mB(0,1) * Aymin + dx)/det;
    float A0y = (-mB(1,0) * Axmin + mB(0,0) * Aymin + dy)/det;

    float A1x = (mB(1,1) * Axmax - mB(0,1) * Aymin + dx)/det;
    float A1y = (-mB(1,0) * Axmax + mB(0,0) * Aymin + dy)/det;

    float A2x = (mB(1,1) * Axmin - mB(0,1) * Aymax + dx)/det;
    float A2y = (-mB(1,0) * Axmin + mB(0,0) * Aymax + dy)/det;

    float A3x = (mB(1,1) * Axmax - mB(0,1) * Aymax + dx)/det;
    float A3y = (-mB(1,0) * Axmax + mB(0,0) * Aymax + dy)/det;

    if(A0x<Bxmin && A1x<Bxmin && A2x<Bxmin && A3x<Bxmin)
        return false;
    if(A0x>Bxmax && A1x>Bxmax && A2x>Bxmax && A3x>Bxmax)
        return false;
    if(A0y<Bymin && A1y<Bymin && A2y<Bymin && A3y<Bymin)
        return false;
    if(A0y>Bymax && A1y>Bymax && A2y>Bymax && A3y>Bymax)
        return false;

    return true;
}

行列 mB は、B 空間の点を A 空間の点に変換する任意のアフィン変換行列です。これには、単純な回転と移動、回転とスケーリング、完全なアフィン ワープが含まれますが、遠近法ワープは含まれません。

可能な限り最適ではない場合があります。速度は大きな問題ではありませんでした。しかし、それは私にとってはうまくいくようです。

于 2013-03-16T00:34:12.717 に答える