线段交点

Question

我在 raywenderlich.com 上找到了这个代码片段，但是 link 的解释不再有效。我把答案"translated"改成了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

对于给定的直线，斜率为

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)

这相当于检查分母不为零，

其余代码，请在"Given two points on each line"

下找到wikipedia的解释

Answer 2

这就是代码的作用。

段AB中的每个点P可以描述为：

P = A + u(B - A)

对于某个常量 0 <= u <= 1。事实上，当 u=0 时你得到 P=A，当 u=1. 时你得到 P=B 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。换句话说，您需要在 0 和 1 之间找到 u 和 v，这样：

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，你可以检查它们是否都在 0 和 1 之间，如果是 return有交集。否则没有。

Answer 3

你可以找到详细的段相交算法在书 Computational Geometry in C 中，第二节。 7.7. SegSegInt 那里描述的代码可用 here。我建议避免斜率计算。

有几个 "degenerate" 案例需要注意：共线段重叠与否，一个段端点在其他段的内部，等。我将代码写到 return 这些特殊情况的指示。

线段交点

Line segment intersection

geometry

intersection

lines