アルゴリズムを検出する交差点の二つの矩形の?

https://stackoverflow.com/questions/115426

02-07-2019
|

質問

ちょっとした用事がある場合のアルゴリズムを検出する場合は二つの矩形が交差する（任意の角度でのみ垂直/水平。

試験場の一角は、他のほとんどです。失敗した場合、矩形のクロスのような形状です。

そうでない方が良いと使用のゲレンデ線を求められる特別な場合にも、垂直ます。

解決

標準の方法であるの 分離軸試験 （googleで検索します。

短:

は、二つのオブジェクトがないの交差点を見つけることができれば回線を離した二つのオブジェクト。例えばのオブジェ/すべてのポイントのオブジェクトとは異なる側面の路線です。

楽しいもので十分だけをチェックすべてのエッジの矩.場合、矩形なが重なり合いのエッジには分離した。

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);

現在の試験すべてのポイントのrectangle Aに対するエッジの矩形をBとします。また、分離端のオブジェなが交差する（他のすべてのポイントBのその他の側端ために開発されている様々な-下図参照)。きない分離端のいずれかの矩形が交差または矩形に多く含まれていると言われる。

試作品と凸多角形ね..

変更: 特定の分離、というだけでは不十分である試験すべてのポイントの一つの矩形の各端します。候補者-edge E（下）など本人を識別することができ、分離端、すべての点で同一の半平面のしかしな分離端の頂点Vb1とVb2Bまたはその半面。うみて分離縁されてこなかった場合 http://www.iassess.com/collision.png

他のヒント

基本的に下記のようなものです写真：

の場合には、箱に衝突し、AとBは重複する。

ることに注意する"について、これはX、Y軸の両方が必要な重なりのための長方形を衝突させる.

あの記事 gamasutra.com るという問いに対する答え（写真はかる。かった類似アルゴリズムは5年前のこととしていますコードスニペットですがこちらの後

改正:の分離軸の定理と両凸形状ない重複した場合の分離軸が存在する(すなわちの見通しとして表示ない重複).では"分離軸が存在する"=>"重複のない".これは二重ことはできませんの締結会話.

m_pGladiatorの答えはまります。分離軸試験 は単純な標準方法を検出す矩形が重なっているのです。ラインに投影間隔で重なり合うわけではないのに対し 分離軸.ニルスPipenbrinckソリューションが一般的です。Itの使用 ドット製品 チェックかつ形状は完全には一面の端ます。このソリューションは実際にもこれを勧誘するn端の凸多角形.しかしなoptmizedのための二つの矩形.

の重要なポイントm_pGladiatorから回答をチェック二四角で見通しの両軸(x、y).ま想に重なってしまえばこれら二つの矩形が重なった.そのコメント上記のm_pGladiatorの答えは間違っています。

のための単純な状況の場合、二つの矩形のない回転させれば、を付けた角を持つ矩形構造:

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

ついに二つの矩形が回転させれば、でニーズの一部を決定するため、見通しにおいて、xおよびy軸.定義構造体RotatedRect、以下のことが明らかとなった。

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

その違いはどのように幅るそうなので、お時間ある方、少し異なる:widthA"をrectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) widthB"をrectB: 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(ゲーム開発会議2007)PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

アできるかどうかを検知にselectedArea rectに交差するご回転NSViewのフレームrect.必要な時に必要なだけ計算アルゴリ以下の二つの条件を考慮する。だけで追加これらの方法をNSViewサブクラス.たとえば、ユーザーを選択するNSViewのsuperview、そのメソッドを呼び出し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;
}

を確認する場合のラインからの矩形が交差する他のラインから。ナイーブラインセグメントの交差点やすいコードです。

が必要な場合は、スピードがあり高度なアルゴリズムのラインセグメント交差点(掃引いただけます。見 http://en.wikipedia.org/wiki/Line_segment_intersection

Oneソリューションは何かという不合多角形を作成します。このポリゴンから算出した二つのポリゴン(概念的にはスライド一周辺のその他）、この領域のポリゴンの重複を相対オフセットされます。一度この雇しだいに有する試験点の相対オフセットのポリゴン.この包接試験、あるいはページをご覧の皆様への雇ます。

て検索なィポリゴンに見つけることができるアルゴリズムの凸多角形(でより複雑な場合は両凹形).ができないかもしれませんので、何メさんのハワード-ドットJ dotがgmailドットコム

ここには何だと思いますのである。次の試験までを実施。

チェックの頂点の矩形の1居住内の矩形の2。いつでも見を頂点とともにその他の矩形すると結論づけることができな交差を停止するように修正しましたこのことに注意の矩形に住む完全に内します。
場合には、試験の度に達した可能性が高見の交差点の各行の1を付けた角を持つ矩形の各線の矩形を塗りつぶします。一回の交差点が見つからチェックが所在すと内部の架空の矩形の対応する4つのポイント。さような点が見つからこれが交差する停止するように修正しました

場合には上述した2つの試験はfalseを返しますそしてこれらの2つの矩形のオーバーラップしません。

を使用している場合、Java、すべての実装のShapeインタフェースを持交差方法をとる矩形を塗りつぶします。

ものづく力の方法は徒歩の端を水平矩形をそれぞれチェックして"エクスポットを端まで又はその他の矩形を塗りつぶします。

数理の答えは、形式を記述する各端の矩.今まで見た場合のラインからの矩形を交差するの線の矩形Bは、単純(快速)線形方程式ソルバー.

-アダム

あらわれることもありますの交差点のそれぞれの側に傾斜を付けた角を持つ矩形の軸に沿った。この方程式の無限にラインをそれぞれの側にある（v1+t(v2-v1)v'1+t'v'2-v'1)基本的に)発見のポイントのラインを満たす方程式を解くことによりtき方程式が等しい場合彼らは並列で試験する)その試験るかどうかその点をとりにあり、ラインセグメント間の頂点、すなわちでは0 <=t <=1と0 <=t' <=1です。

しかし、これは当てはまりません、場合につrectangleを完全にカバーします。このカバーできる検査によるか否かのすべてのいずれかの矩形の挑その他の矩形を塗りつぶします。

こんに 3D この問題:

モデルは、2つの矩形面として記述する方程式は"P1"、"P2"、---等を書きP1=P2を求めることができるので、線の交差点方程式な存在した場合の飛行機の並列（交差点）、または同一平面の場合、get0=0になります。その場合必要となりまを2次元矩形を交差点アルゴリズムです。

そうだが、平面の矩形パルス両方の矩.そうであるとすればそれはまって交差点の2つの矩形の、それ以外ん(はいけない、[遅発性ジスキネジア、遅発コーナーの場合自分なりました。

見れば回線を通過する矩形が同一平面に、の2点の交差点、線、面、矩形(モデリングを利用してライン方程式）、そのポイントの交差点を付けています。

それが、数学的記述、残念なことにはないコードなのです。

この試験は少しよりも高速に分離軸試験では、使用の巻線数のアルゴリズム（quadrantsみ- ない角度の合計であるhorrifically）各頂点のいずれかの矩形(任意に選ばれた).た場合の頂点としてゼロ以外の巻線数の長方形が重なっているのです。

このアルゴリズムに比冗長による分離軸試験がより速やかだけを必要とした半平面の試験の場合エッジ部は交差二quadrantsではなくて、最大32試験用の分離軸方法)

このアルゴリズムをさらに活用で試験ができるの重なり他のポリゴン(凸型または凹).私がよく知られているようにアルゴリズムにおける2次元空間です。

どちらかい何かが足りないものはなぜこのように複雑?

が(x1,y1)と点(X1,Y1)コーナーの矩形の、その見交差点：

    xIntersect = false;
    yIntersect = false;
    if (!(Math.min(x1, x2, x3, x4) > Math.max(X1, X2, X3, X4) || Math.max(x1, x2, x3, x4) < Math.min(X1, X2, X3, X4))) xIntersect = true;
    if (!(Math.min(y1, y2, y3, y4) > Math.max(Y1, Y2, Y3, Y4) || Math.max(y1, y2, y3, y4) < Math.min(Y1, Y2, Y3, Y4))) yIntersect = true;
    if (xIntersect && yIntersect) {alert("Intersect");}

私は実施までのようになります:

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はアフィン変換マトリクスに変換するポイントにスペースのポイントのスペースです。これに簡単な回転-移動-回転プラススケーリング、アフィン歪な視点での歪.

できない場合がありとして最適です。速度は大きな問題とされている。しかしこうokでした。

こちらはmatlabの実施に受け答え:

function olap_flag = ol(A,B,sub)

%A and B should be 4 x 2 matrices containing the xy coordinates of the corners in clockwise order

if nargin == 2
  olap_flag = ol(A,B,1) && ol(B,A,1);
  return;
end

urdl = diff(A([1:4 1],:));
s = sum(urdl .* A, 2);
sdiff = B * urdl' - repmat(s,[1 4]);

olap_flag = ~any(max(sdiff)<0);

これにより、従来の方法に行く行くかどうかを確かめの線が交差した.このコードMATLAB.

C1 = [0, 0];    % Centre of rectangle 1 (x,y)
C2 = [1, 1];    % Centre of rectangle 2 (x,y)
W1 = 5; W2 = 3; % Widths of rectangles 1 and 2
H1 = 2; H2 = 3; % Heights of rectangles 1 and 2
% Define the corner points of the rectangles using the above
R1 = [C1(1) + [W1; W1; -W1; -W1]/2, C1(2) + [H1; -H1; -H1; H1]/2];
R2 = [C2(1) + [W2; W2; -W2; -W2]/2, C2(2) + [H2; -H2; -H2; H2]/2];

R1 = [R1 ; R1(1,:)] ;
R2 = [R2 ; R2(1,:)] ;

plot(R1(:,1),R1(:,2),'r')
hold on
plot(R2(:,1),R2(:,2),'b')


%% lines of Rectangles 
L1 = [R1(1:end-1,:) R1(2:end,:)] ;
L2 = [R2(1:end-1,:) R2(2:end,:)] ;
%% GEt intersection points
P = zeros(2,[]) ;
count = 0 ;
for i = 1:4
    line1 = reshape(L1(i,:),2,2) ;
    for j = 1:4
        line2 = reshape(L2(j,:),2,2) ;
        point = InterX(line1,line2) ;
        if ~isempty(point)
            count = count+1 ;
            P(:,count) = point ;
        end
    end
end
%%
if ~isempty(P)
    fprintf('Given rectangles intersect at %d points:\n',size(P,2))
    plot(P(1,:),P(2,:),'*k')
end

この機能InterXからダウンロードできます: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

いsimplier方法を自分たのであれば、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)

行うことができるので3次元箱においても、実際にドを動作させることができずがあります。

十分と言われているその他の回答合だけ追加擬似コードワライナー:

!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow