我有两个线段,在开始/结束点用3D点表示 .
线:
class Line
{
public string Name { get; set; }
public Point3D Start { get; set; } = new Point3D();
public Point3D End { get; set; } = new Point3D();
}
坐标X,Y和Z的3D点数仅为3倍 .
3DPoint:
class Point3D
{
public double X { get; set; }
public double Y { get; set; }
public double Z { get; set; }
}
The Question:
我可以找到两个'Lines'与该距离'Line'的 endpoints 之间的距离 . [
1
What I have:
目前,我可以使用此代码成功获取两行之间的距离(Adapted From Here使用段到段的部分):
public double lineNearLine(Line l1, Line l2)
{
Vector3D uS = new Vector3D { X = l1.Start.X, Y = l1.Start.Y, Z = l1.Start.Z };
Vector3D uE = new Vector3D { X = l1.End.X, Y = l1.End.Y, Z = l1.End.Z };
Vector3D vS = new Vector3D { X = l2.Start.X, Y = l2.Start.Y, Z = l2.Start.Z };
Vector3D vE = new Vector3D { X = l2.End.X, Y = l2.End.Y, Z = l2.End.Z };
Vector3D w1 = new Vector3D { X = l1.Start.X, Y = l1.Start.Y, Z = l1.Start.Z };
Vector3D w2 = new Vector3D { X = l2.Start.X, Y = l2.Start.Y, Z = l2.Start.Z };
Vector3D u = uE - uS;
Vector3D v = vE - vS;
Vector3D w = w1 - w2;
double a = Vector3D.DotProduct(u, u);
double b = Vector3D.DotProduct(u, v);
double c = Vector3D.DotProduct(v, v);
double d = Vector3D.DotProduct(u, w);
double e = Vector3D.DotProduct(v, w);
double D = a * c - b * b;
double sc, sN, sD = D;
double tc, tN, tD = D;
if (D < 0.01)
{
sN = 0;
sD = 1;
tN = e;
tD = c;
}
else
{
sN = (b * e - c * d);
tN = (a * e - b * d);
if (sN < 0)
{
sN = 0;
tN = e;
tD = c;
}
else if (sN > sD)
{
sN = sD;
tN = e + b;
tD = c;
}
}
if (tN < 0)
{
tN = 0;
if (-d < 0)
{
sN = 0;
}
else if (-d > a)
{
sN = sD;
}
else
{
sN = -d;
sD = a;
}
}
else if (tN > tD)
{
tN = tD;
if ((-d + b) < 0)
{
sN = 0;
}
else if ((-d + b) > a)
{
sN = sD;
}
else
{
sN = (-d + b);
sD = a;
}
}
if (Math.Abs(sN) < 0.01)
{
sc = 0;
}
else
{
sc = sN / sD;
}
if (Math.Abs(tN) < 0.01)
{
tc = 0;
}
else
{
tc = tN / tD;
}
Vector3D dP = w + (sc * u) - (tc * v);
double distance1 = Math.Sqrt(Vector3D.DotProduct(dP, dP));
return distance1;
}
What I Need:
有没有办法从上面的代码确定位移矢量'dP'的 endpoints ?如果没有,有人能建议一种更好的方法来找到最小距离和该距离的终点吗?
Thank you for Reading, and Thanks in advance for any suggestions!
An Enormous Thank You to @Isaac van Bakel for the theory behind this Solution
这是我的代码完成:两条线之间的最短距离由在最短距离处连接它们的线表示 .
Classes:
-
Sharp3D.Math:我将此参考用于Vector3D,但实际上任何3D矢量类都可以使用 . 最重要的是,如果按元素执行减法元素,则甚至不需要向量 .
-
Point3D:我的个人Point3D类 . 您可以根据需要随意使用 .
class Point3D
{
public double X { get; set; }
public double Y { get; set; }
public double Z { get; set; }
public Vector3D getVector()
{
return new Vector3D { X = this.X, Y = this.Y, Z = this.Z };
}
}
- 专线:我的个人专线课程 . 您可以根据需要随意使用 .
class Line
{
public string Name { get; set; }
public Point3D Start { get; set; } = new Point3D();
public Point3D End { get; set; } = new Point3D();
public double Length
{
get
{
return Math.Sqrt(Math.Pow((End.X - Start.X), 2) + Math.Pow((End.Y - Start.Y), 2));
}
}
}
Functions:
- ClampPointToLine:我写的夹紧功能是将一个点夹到一条线上 .
public Point3D ClampPointToLine(Point3D pointToClamp, Line lineToClampTo)
{
Point3D clampedPoint = new Point3D();
double minX, minY, minZ, maxX, maxY, maxZ;
if(lineToClampTo.Start.X <= lineToClampTo.End.X)
{
minX = lineToClampTo.Start.X;
maxX = lineToClampTo.End.X;
}
else
{
minX = lineToClampTo.End.X;
maxX = lineToClampTo.Start.X;
}
if (lineToClampTo.Start.Y <= lineToClampTo.End.Y)
{
minY = lineToClampTo.Start.Y;
maxY = lineToClampTo.End.Y;
}
else
{
minY = lineToClampTo.End.Y;
maxY = lineToClampTo.Start.Y;
}
if (lineToClampTo.Start.Z <= lineToClampTo.End.Z)
{
minZ = lineToClampTo.Start.Z;
maxZ = lineToClampTo.End.Z;
}
else
{
minZ = lineToClampTo.End.Z;
maxZ = lineToClampTo.Start.Z;
}
clampedPoint.X = (pointToClamp.X < minX) ? minX : (pointToClamp.X > maxX) ? maxX : pointToClamp.X;
clampedPoint.Y = (pointToClamp.Y < minY) ? minY : (pointToClamp.Y > maxY) ? maxY : pointToClamp.Y;
clampedPoint.Z = (pointToClamp.Z < minZ) ? minZ : (pointToClamp.Z > maxZ) ? maxZ : pointToClamp.Z;
return clampedPoint;
}
- distanceBetweenLines:返回表示两条线之间最短距离的线的函数 . 如果不可解析则返回null .
public Line distBetweenLines(Line l1, Line l2)
{
Vector3D p1, p2, p3, p4, d1, d2;
p1 = l1.Start.getVector();
p2 = l1.End.getVector();
p3 = l2.Start.getVector();
p4 = l2.End.getVector();
d1 = p2 - p1;
d2 = p4 - p3;
double eq1nCoeff = (d1.X * d2.X) + (d1.Y * d2.Y) + (d1.Z * d2.Z);
double eq1mCoeff = (-(Math.Pow(d1.X, 2)) - (Math.Pow(d1.Y, 2)) - (Math.Pow(d1.Z, 2)));
double eq1Const = ((d1.X * p3.X) - (d1.X * p1.X) + (d1.Y * p3.Y) - (d1.Y * p1.Y) + (d1.Z * p3.Z) - (d1.Z * p1.Z));
double eq2nCoeff = ((Math.Pow(d2.X, 2)) + (Math.Pow(d2.Y, 2)) + (Math.Pow(d2.Z, 2)));
double eq2mCoeff = -(d1.X * d2.X) - (d1.Y * d2.Y) - (d1.Z * d2.Z);
double eq2Const = ((d2.X * p3.X) - (d2.X * p1.X) + (d2.Y * p3.Y) - (d2.Y * p2.Y) + (d2.Z * p3.Z) - (d2.Z * p1.Z));
double[,] M = new double[,] { { eq1nCoeff, eq1mCoeff, -eq1Const }, { eq2nCoeff, eq2mCoeff, -eq2Const } };
int rowCount = M.GetUpperBound(0) + 1;
// pivoting
for (int col = 0; col + 1 < rowCount; col++) if (M[col, col] == 0)
// check for zero coefficients
{
// find non-zero coefficient
int swapRow = col + 1;
for (; swapRow < rowCount; swapRow++) if (M[swapRow, col] != 0) break;
if (M[swapRow, col] != 0) // found a non-zero coefficient?
{
// yes, then swap it with the above
double[] tmp = new double[rowCount + 1];
for (int i = 0; i < rowCount + 1; i++)
{ tmp[i] = M[swapRow, i]; M[swapRow, i] = M[col, i]; M[col, i] = tmp[i]; }
}
else return null; // no, then the matrix has no unique solution
}
// elimination
for (int sourceRow = 0; sourceRow + 1 < rowCount; sourceRow++)
{
for (int destRow = sourceRow + 1; destRow < rowCount; destRow++)
{
double df = M[sourceRow, sourceRow];
double sf = M[destRow, sourceRow];
for (int i = 0; i < rowCount + 1; i++)
M[destRow, i] = M[destRow, i] * df - M[sourceRow, i] * sf;
}
}
// back-insertion
for (int row = rowCount - 1; row >= 0; row--)
{
double f = M[row, row];
if (f == 0) return null;
for (int i = 0; i < rowCount + 1; i++) M[row, i] /= f;
for (int destRow = 0; destRow < row; destRow++)
{ M[destRow, rowCount] -= M[destRow, row] * M[row, rowCount]; M[destRow, row] = 0; }
}
double n = M[0, 2];
double m = M[1, 2];
Point3D i1 = new Point3D { X = p1.X + (m * d1.X), Y = p1.Y + (m * d1.Y), Z = p1.Z + (m * d1.Z) };
Point3D i2 = new Point3D { X = p3.X + (n * d2.X), Y = p3.Y + (n * d2.Y), Z = p3.Z + (n * d2.Z) };
Point3D i1Clamped = ClampPointToLine(i1, l1);
Point3D i2Clamped = ClampPointToLine(i2, l2);
return new Line { Start = i1Clamped, End = i2Clamped };
}
Implementation:
Line shortestDistanceLine = distBetweenLines(l1, l2);
Results:
到目前为止,这在我的测试中是准确的 . 如果传递两条相同的行,则返回null . 我感谢任何反馈!
1 回答
两条歪斜线(不相交的线)之间的最短距离是垂直于它们两者的线的距离 .
如果我们有一条带有已知点p1和p2的线l1,一条带有已知点p3和p4的线l2:
因此,我们知道我们正在寻找的向量v垂直于这两个方向向量:
或者,如果您愿意:
对于d2也一样 .
让我们在线l1,l2上取点,其中v实际上垂直于方向 . 我们将分别称为i1和i2这两点 .
由于v是i1和i2之间的向量(根据定义),我们得到v = i2 - i1 .
这给出了v的x,y,z向量的替换:
等等 .
您现在可以将其替换为您的点积方程式:
这使得我们的方程数减少到2(两个点积方程),有两个未知数(m和n),所以你现在可以解决它们!
一旦你有m和n,你可以通过回到i1和i2的原始计算找到坐标 .
如果您只想要在p1-p2和p3-p4之间的段上的点的最短距离,则可以在这些坐标范围之间夹紧i1和i2,因为最短距离将始终尽可能接近垂线 .