寻找两条3D线段交点的算法

Question

找到两条二维线段的交点很容易； 公式很简单。但恐怕找不到两条 3D 线段的交点。

最好在 C# 中找到两条 3D 线段的交点的算法是什么？

我在这里找到了C++ 实现。但我不信任该解决方案，因为它优先考虑某个平面（看看实现部分下实现 perp 的方式，它假设优先考虑 z 平面）任何通用算法不得假设任何平面方向或偏好）。

有更好的解决方案吗？

Answer 1

大多数 3D 线不相交。一种可靠的方法是找到两条 3D 线之间的最短线。如果最短线的长度为零（或距离小于您指定的任何容差），那么您就知道两条原始线相交。

一种查找两条 3D 线之间最短线的方法，由 Paul Bourke 编写< /a> 总结/解释如下：

接下来，一条线将由位于其上的两个点定义，一个
由点 P1 和 P2 定义的直线“a”上的点有一个方程

Pa = P1 + mua (P2 - P1)

类似地，由点 P3 和 P4 定义的第二条线“b”上的点
将写为

Pb = P3 + mub (P4 - P3)

mua 和 mub 的值范围从负无穷大到正无穷大。
P1 P2 和 P3 P4 之间的线段有其对应的 mu
0 到 1 之间。

有两种方法可以找到之间的最短线段
行“a”和“b”。

方法一：

首先是记下该行的长度
将两条线段连接起来，然后找到最小值。那是，
最小化以下内容

<前><代码>|| Pb - Pa ||^2

代入直线方程可得

<前><代码>|| P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ||^2

然后可以在 (x,y,z) 分量中展开上述内容。

至少要满足一些条件，导数为
mua 和 mub 的尊重必须为零。 ...上面的函数只有
一个最小值，没有其他最小值或最大值。然后这两个方程可以
求解 mua 和 mub，实际的交点由
将 mu 的值代入直线的原始方程中。

方法二：

另一种方法但给出完全相同的方程是
意识到两条线之间的最短线段将
垂直于两条线。这允许我们写两个
点积方程为

(Pa - Pb) 点 (P2 - P1) = 0
(Pa - Pb) 点 (P4 - P3) = 0

根据直线方程展开这些

<代码>( P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ) 点 (P2 - P1) = 0
( P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ) 点 (P4 - P3) = 0

根据坐标 (x,y,z) 展开这些...
结果如下

<前><代码>d1321 + mua d2121 - mub d4321 = 0
d1343 + mua d4321 - mub d4343 = 0

哪里

dmnop = (xm - xn)(xo - xp) + (ym - yn)(yo - yp) + (zm - zn)(zo - zp)

注意 dmnop = dopmn

最后，求解 mua 给出

<预><代码>mua = ( d1343 d4321 - d1321 d4343 ) / ( d2121 d4343 - d4321 d4321 )

回代得到 mub

mub = ( d1343 + mua d4321 ) / d4343

找到了这个方法 Paul Bourke 的网站 这是一个优秀的几何资源。该网站已重新组织，因此请向下滚动以查找主题。

Answer 2

// This code in C++ works for me in 2d and 3d

// assume Coord has members x(), y() and z() and supports arithmetic operations
// that is Coord u + Coord v = u.x() + v.x(), u.y() + v.y(), u.z() + v.z()

inline Point
dot(const Coord& u, const Coord& v) 
{
return u.x() * v.x() + u.y() * v.y() + u.z() * v.z();   
}

inline Point
norm2( const Coord& v )
{
return v.x() * v.x() + v.y() * v.y() + v.z() * v.z();
}

inline Point
norm( const Coord& v ) 
{
return sqrt(norm2(v));
}

inline
Coord
cross( const Coord& b, const Coord& c) // cross product
{
return Coord(b.y() * c.z() - c.y() * b.z(), b.z() * c.x() - c.z() * b.x(), b.x() *  c.y() - c.x() * b.y());
}

bool 
intersection(const Line& a, const Line& b, Coord& ip)
// http://mathworld.wolfram.com/Line-LineIntersection.html
// in 3d; will also work in 2d if z components are 0
{
Coord da = a.second - a.first; 
Coord db = b.second - b.first;
    Coord dc = b.first - a.first;

if (dot(dc, cross(da,db)) != 0.0) // lines are not coplanar
    return false;

Point s = dot(cross(dc,db),cross(da,db)) / norm2(cross(da,db));
if (s >= 0.0 && s <= 1.0)
{
    ip = a.first + da * Coord(s,s,s);
    return true;
}

return false;
}

Answer 3

我尝试了@Bill回答，但实际上并不是每次都有效，我可以解释一下。基于他的代码中的链接。让我们以这两条线段为例 AB和CD。

A=(2,1,5)、B=(1,2,5) 和 C=(2,1,3) 和 D=(2,1,2)

当您尝试获得交集时，它可能会告诉您是 A 点（错误）或者没有交点（正确）。取决于您放置这些段的顺序。

x = A+(BA)s
x = C+(DC)t

比尔解出了s，但从未解出t。由于您希望交点位于两条线段上，因此 s 和 t 都必须来自区间 <0,1>。在我的示例中实际发生的情况是，只有 s 如果来自该间隔且 t 为 -2。 A 位于由 C 和 D 定义的直线上，但不在线段 CD 上。

var s = Vector3.Dot(Vector3.Cross(dc, db), Vector3.Cross(da, db)) / Norm2(Vector3.Cross(da, db));

var t = Vector3.Dot(Vector3.Cross(dc, da), Vector3.Cross(da, db)) / Norm2(Vector3.Cross(da, db));

其中da是BA，db是DC，dc是CA，我只是保留了Bill提供的名称。

然后正如我所说，你必须检查 s 和 t 是否都来自 <0,1> 并且你可以计算结果。根据上面的公式。

if ((s >= 0 && s <= 1) && (k >= 0 && k <= 1))
{
   Vector3 res = new Vector3(this.A.x + da.x * s, this.A.y + da.y * s, this.A.z + da.z * s);
}

比尔答案的另一个问题是当两条线共线并且有多个交点时。将会被零除。你想避免这种情况。

Answer 4

我找到了一个解决方案：它是在这里。

这个想法是利用向量代数，使用dot和cross来简化这个阶段的问题：

a (V1 X V2) = (P2 - P1) X V2

并计算a。

请注意，此实现不需要任何平面或轴作为参考。

Answer 5

您提到的原始来源仅适用于二维案例。 perp 的实现很好。 x 和 y 的使用只是变量，并不表示对特定平面的偏好。

同一个网站有 3d 案例：
“http://geomalgorithms.com/a07-_distance.html”

看起来 Eberly 创作了回复：
“https://www.geometrictools.com/Documentation/DistanceLine3Line3.pdf”

放置这些东西放在这里是因为谷歌指向了地理算法和这篇文章。

Answer 6

但恐怕找不到两条 3D 线段的交点。

我认为是的。您可以按照与二维（或任何其他维度）完全相同的方式找到交点。唯一的区别是，所得的线性方程组更有可能无解（意味着直线不相交）。

您可以手动求解一般方程，然后使用您的解决方案，或者以编程方式求解，例如使用

Answer 7

我找到了答案！

在上面的答案中，我找到了这些方程：

Eq#1: var s = Vector3.Dot(Vector3.Cross(dc, db), Vector3.Cross(da, db)) / Norm2(Vector3.Cross( da, db));

Eq#2: var t = Vector3.Dot(Vector3.Cross(dc, da), Vector3.Cross(da, db)) / Norm2(Vector3.Cross(da) , db));

然后我修改了 #3rd 方程：

Eq#3：

if ((s >= 0 && s <= 1) && (k >= 0 && k <= 1))
{
   Vector3 res = new Vector3(this.A.x + da.x * s, this.A.y + da.y * s, this.A.z + da.z * s);
}

在保持 Eq#1 和 Eq#2 相同的同时，我创建了这个方程：

MyEq#1: Vector3f p0 = da .mul(s).add(A<向量>);
MyEq#2: Vector3f p1 = db.mul(t).add(C);

然后我疯狂猜测创建这三个方程：

MyEq#3: Vector3f p0z = projUV(da, p0).add(A<向量>);
MyEq#4: Vector3f p1z = projUV(db, p1).add(C);

最后将 projUV(1, 2) 的两个幅度相减，得到： 0 到 0.001f 之间的误差幅度来查找两条线是否相交。

MyEq#5: var m = p0z.magnitude() - p1z.magnitude();

现在我要提醒你，这是用 Java 完成的。这个解释还没有准备好java约定。只需根据上面的方程式将其发挥作用即可。 （提示：暂时不要变换到世界空间，以便 UV 方程的两个投影完全落在您想要的位置）。

这些方程在我的程序中在视觉上是正确的。

Answer 8

除了鲍勃的回答之外：

我在测试中发现所编写的 junction() 函数解决了原始问题的一半，这是一种查找两个 3D 线段交点的算法。

假设这些线是共面的，这个问题有 5 种可能的结果：

1. 线段是平行的，所以它们不相交，或者，

2. 线段不平行，并且它们所在的无限长线确实相交，但交点不在任一线段的边界内，或者，

3. 线相交且交点在a 行但不是 b 行，或者，

4. 线相交，并且交点位于线 b 的边界内，但不在线 a 的范围内，或者，

5. 线相交，且交点位于两条线段的边界内。

当直线相交且交点位于直线 a 的边界内时，Bob 的 junction() 函数返回 true，但如果直线相交且交点仅位于直线 b 的边界内，则返回 false。

但是，如果您调用 intersect() 两次，首先使用线 a，然后使用线 b，然后第二次使用线 b 和 a（交换第一个和第二个参数），那么如果两次调用都返回 true，则交集包含在两个线段内（情况5）。如果两个调用都返回 false，则两个线段都不包含相交（情况 2）。如果只有一个调用返回 true，则作为该调用的第一个参数传递的段包含交点（情况 3 或 4）。

另外，如果调用norm2(cross(da,db)) 的返回值等于0.0，则线段是平行的（情况1）。

我在测试中注意到的另一件事是，对于经常实现的那种代码的固定精度浮点数， dot(dc, cross(da,db)) 返回 0.0 可能很不寻常，因此当其返回 false 时不是这样的可能不是你想要的。您可能想要引入一个阈值，低于该阈值代码将继续执行而不是返回 false。这表明线段在 3D 中倾斜，但根据您的应用程序，您可能希望容忍少量倾斜。

我注意到的最后一件事是 Bill 代码中的这条语句：

ip = a.first + da * Coord(s,s,s);

da * Coord(s,s,s) 看起来是向量乘以向量乘法。当我用 da * 的标量倍数替换它时，我发现它工作得很好。

但无论如何，非常感谢鲍勃。他明白了最困难的部分。

Answer 9

https://bloodstrawberry.tistory.com/1037
本博客是用Unity c#实现的。

Vector3 getContactPoint(Vector3 normal, Vector3 planeDot, Vector3 A, Vector3 B)
{
    Vector3 nAB = (B - A).normalized;

    return A + nAB * Vector3.Dot(normal, planeDot - A) / Vector3.Dot(normal, nAB);
}

(Vector3 point1, Vector3 point2) getShortestPath(Vector3 A, Vector3 B, Vector3 C, Vector3 D)
{
    Vector3 AB = A - B;
    Vector3 CD = C - D;
    Vector3 line = Vector3.Cross(AB, CD);
    Vector3 crossLineAB = Vector3.Cross(line, AB);
    Vector3 crossLineCD = Vector3.Cross(line, CD);

    return (getContactPoint(crossLineAB, A, C, D), getContactPoint(crossLineCD, C, A, B));
}

Answer 10

我将从处理相应的线-线相交问题开始。假设第一条线经过点 p1 并平行于向量 v1，而第二条线经过点 p2 并平行于向量 v2。正如一些人已经指出的，在 3D 中两条线很少相交。但如果我们假设它们是这样，那么交点 q 可以写为

q = p2 + t * v2

其中

t = dot(p1 - p2, v3) / dot(v2, v3)

且其中

v3 = cross(cross( v1、v2)、v1)。

由于我们假设两条线相交，因此它们位于同一平面内。通过 v1 和 v2 的叉积找到的向量与该平面正交。与 v1 进行下一个叉积将 v3 放回到平面中，但也与 v1 正交。然后可以将 3D 问题视为 2D 问题，从而得到 t 的表达式。

有了直线-直线相交问题的解决方案，线段-线段相交问题现在只需检查 q 是否位于两条线段上即可。这应该只是比较点积来判断 q 是否位于第一段的问题。第二段更容易检查，因为上面的 q 表达式总是将 q 放在第二行，即我们只需要检查 t 的值。