如何檢查線段是否與矩形相交？

Question

如果你有兩個點，（x1，y1）和（x2，y2），它們代表一個矩形的兩個對角，以及另外兩個點（x3，y3）和（x4，y4），它們代表兩個端點如何檢查線段是否與矩形相交？

（線段只是包含在給定的端點之間的段，它不是由這兩個點定義的無限長度線。）

Answer 1

一個非常簡單的選擇將是使用a standard algorithm for checking whether two line segments intersect檢查線路是否線段與構成盒子角落的四條線段中的任何線段相交。檢查兩條線段是否相交在計算上非常有效，所以我期望這可以很快運行。

希望這會有所幫助！

Answer 2

用線段的方向向量獲取所有4個頂點（矩形的角）的點積。如果所有4都具有相同符號的值，則所有頂點位於該線的同一側（不是線段，而是無限線），因此該線不與該矩形相交。這種方法僅適用於2D交叉點檢測。這可以用來快速過濾大部分數據（僅使用乘法和加法）。您必須對線段進行更多檢查，而不是線路。

Answer 3

要了解如何導出測試線段是否與矩形相交的公式，請務必記住vector dot product的屬性。

將線段表示爲單位矢量以及線段起點與原點之間的距離。下面是一些C＃代碼來計算從PointF變量a_ptStart和a_ptEnd，使用Vector：

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

您還需要計算垂直向量，它從原點的距離的線段。將單位矢量旋轉90 °爲easy。

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

假設矩形的四個角在Vector變量稱爲vecRect1，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 */; 

我相信這就夠了。