C# 求两条3D线段交点的算法

Question

提问by Graviton

Finding the point of intersection for two 2D line segment is easy; the formula is straight forward. But finding the point of intersection for two 3D line segment is not, I afraid.

找到两条二维线段的交点很容易；公式很简单。但是，我担心找不到两条 3D 线段的交点。

What is the algorithm, in C# preferably that finds the point of intersection of two 3D line segments?

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

I found a C++ implementation here. But I don't trust the solution because it makes preference of a certain plane ( look at the way perpis implemented under the implementation section, it assumes a preference for z plane. Any generic algorithm must not assume any plane orientation or preference).

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

Is there a better solution?

有更好的解决方案吗？

Answer 1

采纳答案by Graviton

I found a solution: it's here.

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

The idea is to make use of vector algebra, to use the dotand crossto simply the question until this stage:

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

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

and calculate the a.

并计算a.

Note that this implementation doesn't need to have any planes or axis as reference.

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

Answer 2

回答by Jens

But finding the point of intersection for two 3D line segment is not, I afraid.

但是，我担心找不到两条 3D 线段的交点。

I think it is. You can find the point of intersection in exactly the same way as in 2d (or any other dimension). The only difference is, that the resulting system of linear equations is more likely to have no solution (meaning the lines do not intersect).

我觉得是这样的。您可以以与在 2d（或任何其他维度）中完全相同的方式找到交点。唯一的区别是，由此产生的线性方程组更有可能没有解（意味着线不相交）。

You can solve the general equations by hand and just use your solution, or solve it programmatically, using e.g. Gaussian elemination.

您可以手动求解一般方程并仅使用您的解，或者使用例如Gaussian elemination 以编程方式求解。

Answer 3

回答by Doug Ferguson

Most 3D lines do not intersect. A reliable method is to find the shortest line between two 3D lines. If the shortest line has a length of zero (or distance less than whatever tolerance you specify) then you know that the two original lines intersect.

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

A method for finding the shortest line between two 3D lines, written by Paul Bourkeis summarized / paraphrased as follows:

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

In what follows a line will be defined by two points lying on it, a point on line "a" defined by points P1 and P2 has an equation
Pa = P1 + mua (P2 - P1)
similarly a point on a second line "b" defined by points P4 and P4 will be written as
Pb = P3 + mub (P4 - P3)
The values of mua and mub range from negative to positive infinity. The line segments between P1 P2 and P3 P4 have their corresponding mu between 0 and 1.
There are two approaches to finding the shortest line segment between lines "a" and "b".

在接下来的一条线将由位于其上的两个点定义，由点 P1 和 P2 定义的线“a”上的点有一个方程
Pa = P1 + mua (P2 - P1)
类似地，由点 P4 和 P4 定义的第二条线“b”上的点将写为
Pb = P3 + mub (P4 - P3)
mua 和 mub 的值范围从负无穷大到正无穷大。P1 P2 和 P3 P4 之间的线段对应的 mu 在 0 和 1 之间。
有两种方法可以找到线“a”和“b”之间的最短线段。

Approach one:

方法一：

The first is to write down the length of the line segment joining the two lines and then find the minimum. That is, minimise the following
|| Pb - Pa ||^2
Substituting the equations of the lines gives
|| P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ||^2
The above can then be expanded out in the (x,y,z) components.
There are conditions to be met at the minimum, the derivative with respect to mua and mub must be zero. ...the above function only has one minima and no other minima or maxima. These two equations can then be solved for mua and mub, the actual intersection points found by substituting the values of mu into the original equations of the line.

首先是记下连接两条线的线段的长度，然后找到最小值。也就是说，最小化以下
|| Pb - Pa ||^2
代入直线方程给出
|| P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ||^2
然后可以在 (x,y,z) 组件中扩展上述内容。
至少要满足一些条件，关于 mua 和 mub 的导数必须为零。...上述函数只有一个最小值，没有其他最小值或最大值。然后可以求解这两个方程的 mua 和 mub，即通过将 mu 的值代入直线的原始方程而找到的实际交点。

Approach two:

方法二：

An alternative approach but one that gives the exact same equations is to realise that the shortest line segment between the two lines will be perpendicular to the two lines. This allows us to write two equations for the dot product as
(Pa - Pb) dot (P2 - P1) = 0
(Pa - Pb) dot (P4 - P3) = 0
Expanding these given the equation of the lines
( P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ) dot (P2 - P1) = 0
( P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ) dot (P4 - P3) = 0
Expanding these in terms of the coordinates (x,y,z) ... the result is as follows
d1321 + mua d2121 - mub d4321 = 0
d1343 + mua d4321 - mub d4343 = 0
where
dmnop = (xm - xn)(xo - xp) + (ym - yn)(yo - yp) + (zm - zn)(zo - zp)
Note that dmnop = dopmn
Finally, solving for mua gives
mua = ( d1343 d4321 - d1321 d4343 ) / ( d2121 d4343 - d4321 d4321 )
and back-substituting gives mub
mub = ( d1343 + mua d4321 ) / d4343

另一种方法但给出完全相同的方程是实现两条线之间的最短线段将垂直于两条线。这允许我们将点积的两个方程写为
(Pa - Pb) dot (P2 - P1) = 0
(Pa - Pb) dot (P4 - P3) = 0
扩展这些给定的线方程
( P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ) dot (P2 - P1) = 0
( P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ) dot (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

This method was found on Paul Bourke's websitewhich is an excellent geometry resource. The site has been reorganized, so scroll down to find the topic.

这个方法是在 Paul Bourke 的网站上找到的，这是一个很好的几何资源。该站点已重新组织，因此向下滚动以找到该主题。

Answer 4

回答by Bill

// 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 5

回答by Kapitán Mlíko

I tried @Bill answerand it actually does not work every time, which I can explain. Based on the link in his code.Let's have for example these two line segments ABand CD.

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

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

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

when you try to get the intersection it might tell you It's the point A (incorrect) or there is no intersection (correct). Depending on the order you put those segments in.

当您尝试获得交叉点时，它可能会告诉您这是 A 点（不正确）或没有交叉点（正确）。根据您放置这些段的顺序。

x = A+(B-A)s
x = C+(D-C)t

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

Bill solved for sbut never solved t. And since you want that intersection point to be on both line segments both sand thave to be from interval <0,1>. What actually happens in my example is that only sif from that interval and tis -2. Alies on line defined by Cand D, but not on line segment CD.

Bill 解决了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));

where da is B-A, db is D-C and dc is C-A, I just preserved names provided by Bill.

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

Then as I said you have to check if both sand tare from <0,1>and you can calculate the result. Based on formula above.

然后正如我所说，您必须检查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);
}

Also another problem with Bills answer is when two lines are collinear and there is more than one intersection point. There would be division by zero. You want to avoid that.

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

Answer 6

回答by user1633759

The original source you mention is only for the 2d case. The implementation for perp is fine. The use of x and y are just variables not an indication of preference for a specific plane.

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

The same site has this for the 3d case: "http://geomalgorithms.com/a07-_distance.html"

对于 3d 案例，同一个站点有这个：“ http://geomalgorithms.com/a07-_distance.html”

Looks like Eberly authored a response: "https://www.geometrictools.com/Documentation/DistanceLine3Line3.pdf"

看起来 Eberly 撰写了一个回复：“ https://www.geometrictools.com/Documentation/DistanceLine3Line3.pdf”

Putting this stuff here because google points to geomalgorithms and to this post.

把这些东西放在这里是因为 google 指向 geomalgorithms 和这篇文章。

Answer 7

回答by GMan3000

I found an answer!

我找到了答案！

in an answer from above, I found these equations:

在上面的回答中，我找到了这些等式：

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

等式#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));

等式#2： var t = Vector3.Dot(Vector3.Cross(dc, da), Vector3.Cross(da, db)) / Norm2(Vector3.Cross(da, db));

Then I modified #3rd Equation:

然后我修改了#3rd等式：

Eq#3:

等式#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);
}

And while keeping Eq#1 and Eq#2 just the same, I created this equations:

在保持 Eq#1 和 Eq#2 相同的同时，我创建了以下等式：

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

我的等式#1：我的Vector3f p0 = da.mul(s).add(A<vector>);等式#2：Vector3f p1 = db.mul(t).add(C<vector>);

then I took a wild guess at creating these three more equations:

然后我在创建这三个方程时进行了疯狂的猜测：

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

我的等式#3：我的Vector3f p0z = projUV(da, p0).add(A<vector>);等式#4：Vector3f p1z = projUV(db, p1).add(C<vector>);

and finally to get the subtraction of the two magnitudes of the projUV(1, 2) gives you the margin of the error between 0 and 0.001f to find whether the two lines intersect.

最后得到 projUV(1, 2) 的两个量级的减法，给出 0 到 0.001f 之间的误差幅度，以确定两条线是否相交。

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

我的方程式#5： var m = p0z.magnitude() - p1z.magnitude();

Now I mind you, this was done in Java. This explanation is not java convention ready. Just put it to work from the above equations. (Tip: Don't transform to World Space yet so that both projection of UV equations fall exactly where you want them).

现在我提醒你，这是用 Java 完成的。这个解释不是java约定准备的。只需将其从上述等式中发挥作用即可。（提示：先不要转换到世界空间，以便 UV 方程的两个投影都准确地落在您想要的位置）。

And these equations are visually correct in my program.

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

C# 求两条3D线段交点的算法

提问by Graviton

采纳答案by Graviton

回答by Jens

回答by Doug Ferguson

回答by Bill

回答by Kapitán Mlíko

回答by user1633759

回答by GMan3000

相关推荐

最近更新

标签

C# 求两条3D线段交点的算法

提问by Graviton

采纳答案by Graviton

回答by Jens

回答by Doug Ferguson

回答by Bill

回答by Kapitán Mlíko

回答by user1633759

回答by GMan3000

相关推荐

C# 提供了 XmlNamespaceManager，但仍然得到“需要命名空间管理器或 XsltContext”

Linux 在shell中，用点作为分隔符分割字符串的一部分

C# Request["key"] vs Request.Params["key"] vs Request.QueryString["key"]

Linux sysconf(_SC_CLK_TCK) 它返回什么？

相关推荐

最近更新

标签