给定两个点和两个向量，找到它们的交点。

Question

可能重复：
如何检测两条线段的交点？ 给定两个点a和b以及两个向量v和u，我想以以下方式找到第三个点c，即交点：

vector2 intersection(vector2 a, vector2 v, vector2 b, vector2 u)
{
    float r, s;

    a + r * v = b + s * u;
    r * v - s * u = b - a

    r * v.x - s * u.x = b.x - a.x
    r * v.y - s * u.y = b.y - a.y
}

有没有比使用高斯消元更好的方法来解决这个系统？或者说，这是处理这个问题的最佳（或至少是可接受的）方法吗？

编辑： vector2 的定义。

typedef union vector2
{
    float v[2];
    struct { float x, y; };
} vector2;

a 和 b 也属于类型为 vector2，因为点和向量之间唯一的区别就在于它们被仿射变换转换的方式。

- 0xbadf00d

---

vector2 是如何定义的？为什么 points a 和 b 也是 vector2 类型？ - Paul R

我已经在下面解释了。但不管怎样，为什么向量不仅仅是一个结构体？为什么需要联合和"数组"？ - Roee Gavirel

这个问题被 Gareth Rees、Paul R、Mark Dickinson和0xbadf00d 标记为重复，因为“这个问题已经被问过并且已经有了答案”。但是截至本文撰写时，那个问题还没有被接受的答案。我认为只有在引用的问题有被接受的答案时，才应该将一个问题标记为重复。 - user316117

Answer 1

这看起来像是一个作业问题。以下逻辑将帮助您编写代码。

让我们称第一个射线为R0。
R0上的点的轨迹被定义为P：

P = P0 + alpha x V0

对于第二条射线R1：

P = P1 + beta x V1

由于它们应该相交：

P0 + alpha x V0 = P1 + beta x V1

alpha和beta是未知数，我们有两个关于x和y的方程。

解出未知数并返回交点。

i.e.,

P0.x + alpha * V0.x = P1.x + beta * V1.x
P0.y + alpha * V0.y = P1.y + beta * V1.y

解出 alpha 和 beta。

如果 alpha 和 beta 都有一个正实数解，那么射线相交。
如果 alpha 和 beta 至少有一个负实数解，那么延长射线相交。

- Ram

Answer 2

这是简单的数学。

但首先，请检查您是否有交集。如果两个向量是平行的，则无法解决：

// Edit this line to protect from division by 0 
if (Vy == 0 && Uy == 0) || ((Vy != 0 && Uy != 0 && (Vx/Vy == Ux/Uy)) // => Fail.

然后（我不会展示计算过程，因为它们很长，但结果是）：

R = (AxUy - AyUx + ByUx - BxUy) / (VyUx - VxUy)  
S = (Ax - Bx + RVx) / Ux  

希望这对您有所帮助。

- Roee Gavirel

---

如果你将 (a.x - b.x + r * v.x) / u 相除，假设 u 是一个向量，(a.x - b.x + r * v.x) 是一个标量，那么结果是什么？ - 0xbadf00d

@0xbadf00d，你是正确的，这是一个打字错误。我想说的是Ux... - Roee Gavirel

如果 Ux=0 怎么办？例如：*v1=(0,1)，v2=(2,0)，p1=(-4,2)，p2=(3,5)*？ - Konrad Viltersten