如何檢查2個線段是否相交？我有以下數(shù)據(jù)：Segment1 [ {x1,y1}, {x2,y2} ]Segment2 [ {x1,y1}, {x2,y2} ] 我需要在Python中編寫一個小的算法來檢測2行是否相交。
3 回答
慕村225694
TA貢獻(xiàn)1880條經(jīng)驗 獲得超4個贊
一條線的等式是：
f(x) = A*x + b = y
對于段，除了x包含在間隔I中之外，它完全相同。
如果您有兩個細(xì)分，則定義如下：
Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}
交點（Xa，Ya）的潛在交點Xa必須包含在間隔I1和I2中，定義如下：
I1 = [min(X1,X2), max(X1,X2)]
I2 = [min(X3,X4), max(X3,X4)]
我們可以說Xa包含在：
Ia = [max( min(X1,X2), min(X3,X4) ),
min( max(X1,X2), max(X3,X4) )]
現(xiàn)在，我們需要檢查此間隔Ia是否存在：
if (max(X1,X2) < min(X3,X4))
return false; // There is no mutual abcisses
因此，我們有兩個線公式和一個相互間隔。您的行公式為：
f1(x) = A1*x + b1 = y
f2(x) = A2*x + b2 = y
由于我們按段得到兩個點，因此我們可以確定A1，A2，b1和b2：
A1 = (Y1-Y2)/(X1-X2) // Pay attention to not dividing by zero
A2 = (Y3-Y4)/(X3-X4) // Pay attention to not dividing by zero
b1 = Y1-A1*X1 = Y2-A1*X2
b2 = Y3-A2*X3 = Y4-A2*X4
如果線段是平行的，則A1 == A2：
if (A1 == A2)
return false; // Parallel segments
兩條線上的點（Xa，Ya）必須驗證公式f1和f2：
Ya = A1 * Xa + b1
Ya = A2 * Xa + b2
A1 * Xa + b1 = A2 * Xa + b2
Xa = (b2 - b1) / (A1 - A2) // Once again, pay attention to not dividing by zero
最后要做的是檢查Xa是否包含在Ia中：
if ( (Xa < max( min(X1,X2), min(X3,X4) )) ||
(Xa > min( max(X1,X2), max(X3,X4) )) )
return false; // intersection is out of bound
else
return true;
除此之外，您可以在啟動時檢查所提供的四個點中的兩個不等于以避免所有測試。
jeck貓
TA貢獻(xiàn)1909條經(jīng)驗 獲得超7個贊
用戶@ i_4_got 用Python的高效解決方案指向此頁面。為了方便起見，我在這里復(fù)制它（因為它會讓我很高興在這里擁有它）：
def ccw(A,B,C):
return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)
# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)
慕娘9325324
TA貢獻(xiàn)1783條經(jīng)驗 獲得超4個贊
您不必計算究竟哪里不段相交，但只有了解是否它們相交的。這將簡化解決方案。
想法是將一個片段視為“錨點”，并將第二個片段分為2個點。
現(xiàn)在，您將必須找到每個點與“錨定”線段（OnLeft，OnRight或共線）的相對位置。
對兩個點都這樣做之后，請檢查其中一個點是OnLeft，另一個是OnRight（或者，如果您還希望包括不正確的相交，則包括共線位置）。
然后，您必須使用錨定段和分隔段的角色重復(fù)該過程。
僅當(dāng)其中一個點為OnLeft而另一個為OnRight時，才存在交集。有關(guān)每種可能情況的示例圖像，請參閱此鏈接以獲取更詳細(xì)的說明。
實現(xiàn)這種方法比實際實現(xiàn)找到相交點的方法要容易得多（考慮到很多拐角情況，您也必須處理）。
更新資料
以下函數(shù)應(yīng)說明這一思想（來源：C中的計算幾何）。
備注：此示例假定使用整數(shù)。如果您使用的是浮點表示（顯然會使事情復(fù)雜化），則應(yīng)確定一些epsilon值來表示“相等”（主要用于IsCollinear評估）。
// points "a" and "b" forms the anchored segment.
// point "c" is the evaluated point
bool IsOnLeft(Point a, Point b, Point c)
{
return Area2(a, b, c) > 0;
}
bool IsOnRight(Point a, Point b, Point c)
{
return Area2(a, b, c) < 0;
}
bool IsCollinear(Point a, Point b, Point c)
{
return Area2(a, b, c) == 0;
}
// calculates the triangle's size (formed by the "anchor" segment and additional point)
int Area2(Point a, Point b, Point c)
{
return (b.X - a.X) * (c.Y - a.Y) -
(c.X - a.X) * (b.Y - a.Y);
}
當(dāng)然，使用這些功能時，必須記住檢查每個段是否位于另一個段“之間”（因為這些段是有限段，而不是無限行）。
此外，使用這些功能，您可以了解你是否已經(jīng)有了一個正確或不正確的路口。
正確：沒有共線點。這些段“從一側(cè)到另一側(cè)”彼此交叉。
不正確：一個線段僅“觸摸”另一線段（至少一個點與錨定線段共線）。
添加回答
舉報
0/150
提交
取消