線段交點

Question

我在raywenderlich.com上發現了這段代碼片段，但是解釋的鏈接無效。我把答案翻譯成Swift，希望你能理解，即使不知道語言，它實際上也很容易。任何人都可以解釋這裏究竟發生了什麼？謝謝你的幫助。

class func linesCross(#line1: Line, line2: Line) -> Bool { 
    let denominator = (line1.end.y - line1.start.y) * (line2.end.x - line2.start.x) - 
     (line1.end.x - line1.start.x) * (line2.end.y - line2.start.y) 

    if denominator == 0 { return false } //lines are parallel 

    let ua = ((line1.end.x - line1.start.x) * (line2.start.y - line1.start.y) - 
     (line1.end.y - line1.start.y) * (line2.start.x - line1.start.x))/denominator 
    let ub = ((line2.end.x - line2.start.x) * (line2.start.y - line1.start.y) - 
     (line2.end.y - line2.start.y) * (line2.start.x - line1.start.x))/denominator 

    //lines may touch each other - no test for equality here 
    return ua > 0 && ua < 1 && ub > 0 && ub < 1 
} 

Answer 1

這就是代碼所做的事情。對於某一常數0 <= u <= 1

P = A + u(B - A) 

：

每一點P在段AB可謂。實際上，當u=0您獲得P=A，並且您獲得P=B時u=1.u的中間值會給您段中的中間值P。例如，當u = 0.5你會得到中間的點。通常，您可以將參數u視爲AP和AB的長度之間的比率。現在

，如果你有另一段CD你可以描述點Q它以同樣的方式，但有不同的u，我會打電話給v：

Q = C + v(D - C) 

再次請記住Q位於C和D之間，並且只有在0 <= v <= 1（與上面的P相同）時。

要找到兩個部分之間的交點，您必須等於P=Q。換句話說，你需要找到u和v，兩者之間0和1這樣的：

A + u(B - A) = C + v(D - C) 

所以，你有這個公式，你必須看到，如果它是u和v在給定的約束之內可解。

鑑於A，B，C和D與兩個座標x,y每個點，你可以打開上面的等式分爲兩個方程式：

ax + u(bx - ax) = cx + v(dx - cx) 
ay + u(by - ay) = cy + v(dy - cy) 

其中ax = A.x，ay = A.y，等等，都是座標點。

現在我們剩下一個2x2線性系統。在矩陣形式：

|bx-ax cx-dx| |u| = |cx-ax| 
|by-ay cy-dy| |v| |cy-ay| 

的矩陣的行列式是

det = (bx-ax)(cy-dy) - (by-ay)(cx-dx) 

該量對應於所述代碼段的denominator（請檢查）。

現在，輔因子矩陣兩邊乘以：（！檢查這太）

|cy-dy dx-cx| 
|ay-by bx-ax| 

我們得到

det*u = (cy-dy)(cx-ax) + (dx-cx)(cy-ay) 
det*v = (ay-by)(cx-ax) + (bx-ax)(cy-ay) 

對應於在代碼中定義的變量ua和ub

最後，一旦你有u和v你可以檢查它們是否在之間和1，並在那種情況下返回有交集。否則，沒有。

Answer 2

對於給定的線的斜率是

m=(y_end-y_start)/(x_end-x_start) 

如果兩個斜率相等，則線平行

m1=m1 

(y1_end-y_start)/(x1_end-x1_start)=(y2_end-y2_start)/(x2_end-x2_start) 

而且該分母不爲零這等同於檢查，

關於其他代碼，請查看wikipedia的解釋nder「給定每行兩個點」

Answer 3

你可以在書Computational Geometry in C第2節中找到詳細的段交集算法 。 7.7。 SegSegInt這裏描述的代碼可用here。 我建議避免斜率計算。

有需要照顧幾個「退化」的情況：共線區段 重疊與否，在其他部分的內部一個段終點， 等我寫的代碼，返回的這些特殊情況的指示。