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

Question

找到两条二维线段的交点很容易； the formula is straight forward .但是，恐怕不是找到两条 3D 线段的交点。

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

我找到了一个 C++ implementation here .但我不相信这个解决方案，因为它偏爱某个平面(查看 perp 在实现部分下的实现方式，它假定偏爱 z plane . 任何通用算法都不能假定任何平面方向或偏好)。

有没有更好的解决方案？

Answer 1

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

一种查找the shortest line between two 3D lines, written by 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".

方法一:

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.

方法二:

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

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