作为对上述答案的轻微修正,使用 3D 叉积来计算 2D 线交点几乎是效率最低的。跨产品根本不进行 SIMD 优化(除非您竭尽全力使用 SOA 数据结构,但即使它是一种极其浪费的方法)。最好的方法是使用良好的旧联立方程。
从定义线的输入点开始:
line1: [(x1, y1), (x2, y2)]
line2: [(x3, y3), (x4, y4)]
计算一些方向向量:
// 1st direction
u1 = x2 - x1
v1 = y2 - y1
D1 = [u1, v1]
// 2nd direction
u2 = x4 - x3
v2 = y4 - y3
D2 = [u2, v2]
现在让我们将线方程重新表述为射线,并为这些射线上的任何点得出一个方程:
// coords of a point 'd1' distance along the 1st ray
Px = x1 + d1*u1
Py = y1 + d1*v1
// coords of a point 'd2' distance along the 2nd ray
Px = x3 + d2*u2
Py = y3 + d2*v2
让我们假设线相交,这意味着两个 P 将是相同的,允许我们声明:
x1 + d1*u1 = x3 + d2*u2
y1 + d1*v1 = y3 + d2*v2
我不会遍历每一步,而是根据 d1 重新排列两个方程,我们得到:
d1 = x3 + d2*u2 - x1
---------------
u1
d1 = y3 + d2*v2 - y1
---------------
v1
现在我们有 d1 的两个方程,所以让我们做另一个联立方程来获得 d2 的值:
x3 + d2*u2 - x1 y3 + d2*v2 - y1
--------------- = ---------------
u1 v1
重新排列以隔离 d2:
d2 = u1(y3 - y1) - v1(x3 - x1)
-------------------------
v1*u2 - u1*v2
如果 (v1*u2 - u1*v2) 恰好为零,则该方程没有解(我们称其为行列式,因为它就是这样!)。如果行列式不为零,则只需使用上述等式计算 d2,然后返回到我们之前的等式之一以找到点值:
Px = x3 + d2*u2
Py = y3 + d2*v2
一些未经测试的 C++ 代码:
bool computeIntersectPoint(
float x1, float y1,
float x2, float y2,
float x3, float y3,
float x4, float y4,
float outPoint[2])
{
// compute direction vectors
// in some cases, it can be worth
// storing the lines as rays as an
// optimisation. (avoids 4 subs)
const float u1 = x2 - x1;
const float v1 = y2 - x1;
const float u2 = x4 - x3;
const float v2 = y4 - x3;
// check to see if we have a solution
// 1 mul, 1 fmsub
float determinant = v1*u2 - u1*v1;
if(determinant == 0)
return false;
// 2 sub, 1 mul, 1 fmsub
float temp = u1 * (y3 - y1) - v1 * (x3 - x1);
// 1 div
float intersectDistance = temp / determinant;
// 2 fma
outPoint[0] = intersectDistance * u2 + x3;
outPoint[1] = intersectDistance * v2 + y3;
return true;
}
快速desmos证明:https ://www.desmos.com/calculator/gtlmnmzn6l
此时值得比较两种方法之间的指令数。3d 叉积需要 3 个 mult 和 3 个 fmsub 指令(如果 FMA 不可用,则需要 6 mul + 3 sub)。由于我们有 3 个,我们最多:9 个 mul 和 9 个 fmsub 操作。加上 2 个部门,我们得到:
9 mul
9 fmsub
2 div
我发布的方法需要:
1 div
6 sub
4 fma
2 mul
尽管如果您可以将线存储为射线,则可以保存其中的 4 个。