線分が矩形と交差するかどうかを確認する方法は？

Question

長方形の2つの反対側のコーナーを表す（x1、y1）と（x2、y2）、および2つの端点を表す（x3、y3）および（x4、y4）線分の長方形と交差するかどうかを確認するにはどうすればよいですか？

（線分が所定のエンドポイント間で含まれるだけセグメントである。それは、これら二つの点によって定義される無限長線路ではない。）

Answer 1

1つの非常に単純なオプションは、行かどうかをチェックするa standard algorithm for checking whether two line segments intersectを使用することであろうセグメントは、ボックスのコーナーを構成する4つの線分のいずれかと交差します。 2つの線分が交差しているかどうかを確認するのは計算上非常に効率的です。そのため、これは非常に迅速に実行できることが期待されます。

希望すると便利です。

Answer 2

4つの頂点（矩形の角）の内積を、線分の方向ベクトルで求めます。すべての4つの値が同じ符号を持つ場合、すべての頂点は線の同じ側（線分ではなく無限線）にあり、線は矩形と交差しません。このアプローチは、2D交差検出にのみ有効です。これは、大部分を素早く（乗算と加算のみを使用して）フィルタリングするために使用できます。線の代わりに線分をさらにチェックする必要があります。

Answer 3

線分が矩形と交差するかどうかをテストする式を導出する方法を理解するには、vector dot productのプロパティを覚えておくことが重要です。

線分を単位ベクトルとし、線分の始点と原点間の距離を表す。あなたはまた、垂直ベクトルを計算する必要があります

Vector vecLine = new Vector(a_ptEnd.X - a_ptStart.X, a_ptEnd.Y - a_ptStart.Y); 
double dLengthLine = vecLine.Length; 
vecLine /= dLengthLine; 
double dDistLine = Vector.Multiply(vecLine, new Vector(a_ptStart.X, a_ptStart.Y)); 

、線分の原点からの距離、：ここでVector使用して、PointF変数a_ptStartとa_ptEndからそれを計算するために、いくつかのC＃コードです。単位ベクトルを90 °で回転すると、easyとなります。

：矩形の四隅を仮定

Vector vecPerpLine = new Vector(-vecLine.Y, vecLine.X); 
double dDistPerpLine = Vector.Multiply(vecPerpLine, new Vector(a_ptStart.X, a_ptStart.Y)); 

がVectorvecRect1と呼ばれる変数、vecRect2、vecRect3、及びvecRect4であり、線分とターゲットの外接矩形の四隅の間distanceを計算します

double dPerpLineDist1 = Vector.Multiply(vecPerpLine, vecRect1) - dDistPerpLine; 
double dPerpLineDist2 = Vector.Multiply(vecPerpLine, vecRect2) - dDistPerpLine; 
double dPerpLineDist3 = Vector.Multiply(vecPerpLine, vecRect3) - dDistPerpLine; 
double dPerpLineDist4 = Vector.Multiply(vecPerpLine, vecRect4) - dDistPerpLine; 
double dMinPerpLineDist = Math.Min(dPerpLineDist1, Math.Min(dPerpLineDist2, 
    Math.Min(dPerpLineDist3, dPerpLineDist4))); 
double dMaxPerpLineDist = Math.Max(dPerpLineDist1, Math.Max(dPerpLineDist2, 
    Math.Max(dPerpLineDist3, dPerpLineDist4))); 

すべての距離が正の場合、またはすべての距離が負の場合、長方形は線の片側にあります。したがって、交点はありません。 （ゼロ程度の長方形は、任意の線分と交差しないと考えられる。）

if (dMinPerpLineDist <= 0.0 && dMaxPerpLineDist <= 0.0 
     || dMinPerpLineDist >= 0.0 && dMaxPerpLineDist >= 0.0) 
    /* no intersection */; 

次に、プロジェクト線分上に対象の境界の矩形の四隅。これは、ラインの原点とそのライン上の長方形コーナーの投影との間の距離を与える。

double dDistLine1 = Vector.Multiply(vecLine, vecRect1) - dDistLine; 
double dDistLine2 = Vector.Multiply(vecLine, vecRect2) - dDistLine; 
double dDistLine3 = Vector.Multiply(vecLine, vecRect3) - dDistLine; 
double dDistLine4 = Vector.Multiply(vecLine, vecRect4) - dDistLine; 
double dMinLineDist = Math.Min(dDistLine1, Math.Min(dDistLine2, 
    Math.Min(dDistLine3, dDistLine4))); 
double dMaxLineDist = Math.Max(dDistLine1, Math.Max(dDistLine2, 
    Math.Max(dDistLine3, dDistLine4))); 

矩形の点が線分の範囲内にない場合、交差点はありません。

if (dMaxLineDist <= 0.0 || dMinLineDist >= dLengthLine) 
    /* no intersection */; 

私はそれで十分だと思います。