段路段交叉点 [英] Segment Segment intersection
问题描述
让我们进一步假设该段与三角形相交。
现在，我需要找出线段与边界处的三角形相交的地方。
所以我的想法是采取三角形（AB，BC和CA）的每个边缘并测试其中一个与DE段相交。问题是我没有找到段/段交叉的解决方案。我找到了这，但它不起作用。
编辑
基于MBo的回答，我实现了一个C＃方法：
// return：0 - >段平行于平面
//返回：1 - >段与面的边相交
// return：-1 - >分段与内部或三角形相交或根本不相交
public static int SegmentTriangleIntersection（Vector3D a，Vector3D b，Vector3D c，Vector3D d，Vector3D e）
{
var ed = e - d ;
var ba = b - a;
var ca = c - a;
var ad = a - d;
var det =（ed.X * -ba.Y * -ca.Z）+（-ba.X * -ca.Y * ed.Z）+（-ca.X * ed .Y * -ba.Z） - （ed.Z * -ba.Y * -ca.X） - （--ba.Z * -ca.Y * ed.X） -
（-ca.Z * * ed.Y -ba.X）;
if（Vector3D.IsNearlyEqual（det，0））//与三角形并行的段
return 0;
var det_t =（ad.X * -ba.Y * -ca.Z）+（-ba.X * -ca.Y * ad.Z）+（-ca.X * ad .Y * -ba.Z） - （ad.Z * -ba.Y * -ca.X） - （--ba.Z * -ca.Y * ad.X） -
（-ca.Z * ad.Y * -ba.X）;
var t = det_t / det;
if（t> = 0& t< = 1）//段与三角形平面相交
{
var det_u =（ed.X * ad.Y * -ca。 Z）+（ad.X * -ca.Y * ed.Z）+（-ca.X * ed.Y * ad.Z） - （ed.Z * ad.Y * -ca.X） - （ad .Z * -ca.Y * ed.X） -
（-ca.Z * ed.Y * ad.X）;
var u = det_u / det;
var det_v =（ed.X * -ba.Y * ad.Z）+（-ba.X * ad.Y * ed.Z）+（ad.X * ed.Y * -ba.Z ） - （ed.Z * -ba.Y * ad.X） -
（-ba.Z * ad.Y * ed.X） - （ad.Z * ed.Y * -ba.X） ;
var v = det_v / det;
$ b $ if（Vector3D.IsNearlyEqual（u，0）& v> = 0&& v< = 1）
return 1;
if（Vector3D.IsNearlyEqual（v，0）&& u> = 0&& u< = 1）
return 1;
if（Vector3D.IsNearlyEqual（v + u，1）&& u> = 0&& v> = 0）
return 1;
}
返回-1;
}
让我们使用参数方程（以粗体显示）：
段DE：
sDE （t）= D + t *（ E - D ）= D + t * ED
// ED = E - D
AB：
sAB （u）= A + u *（ B - A ）= + u * BA
细分受众群：
sAC ）= A + v *（ C - A ）= A b
$ b
ABC三角形平面用双参数方程描述：b
pABC v（u，v）= A + u * BA + v CA
坐标（u，v ）位于三角形内，如果
u范围[0..1]
和
v in范围[0..1]
和
u + v的范围是[0..1]
如果 [边界条件]
u = 0和v范围[0..1] //在AC边缘
或
v = 0和u在范围[0..1] // AC边缘
或
v + u = 1，u在范围内（0..1）和v在范围内（0..1）//在BC边缘
现在让我们来写一下DE段和ABC平面相交的方程式吧！
sDE < （t）= pABC （u，v）
D + t * ED = A + u * BA + v CA
我们可以解出最后一个方程对于每个坐标，都有3个线性方程式），并找到 t，u，v
DX + t * ED.X = AX + u * BA.X + v * CA.X
DY + t * ED.Y = AY + u * BA.Y + v * CA.Y
DZ + t * ED.Z = AZ + u * BA.Z + v * CA.Z
t * ED.X - u * BA.X - v * CA.X = AX - DX
t * ED.Y - u * BA.Y - v * CA.Y = AY - DY
t * ED.Z - u * BA.Z - v * CA.Z = AZ - DZ
首先找到这个系统的行列式 - 如果它是零，那么segment与飞机平行。
如果不是，请检查参数t。如果 t 在范围[0..1]中，则分段与飞机相交
如果是，请检查 u，v 参数符合上面的边缘条件
Let's suppose I have a triangle defined by three coordinates A, B and C and a line segment defined by two coordinates D and E in 3D euclidean space. Let's further suppose that the segment is intersecting the triangle. Now, I need to find out wether the line segment intersects the triangle at its "border". So my idea was to take each edge of the triangle (AB, BC and CA) and test wether one of them intersects with the segment DE. The problem is that I haven't found a solution for segment/segment intersection. I have found this one but it doesn't work. Help very appreciated.
Edit Based on MBo's answer, I have implemented a C# method:
// return: 0 -> segment parallel to plane
// return: 1 -> segment intersects an edge of the face
// return: -1 -> segments intersects the interior or the triangle or not at all
public static int SegmentTriangleIntersection(Vector3D a, Vector3D b, Vector3D c, Vector3D d, Vector3D e)
{
var ed = e - d;
var ba = b - a;
var ca = c - a;
var ad = a - d;
var det = (ed.X*-ba.Y*-ca.Z) + (-ba.X*-ca.Y*ed.Z) + (-ca.X*ed.Y*-ba.Z) - (ed.Z*-ba.Y*-ca.X) - (-ba.Z*-ca.Y*ed.X) -
(-ca.Z*ed.Y*-ba.X);
if (Vector3D.IsNearlyEqual(det, 0)) // segment parallel to triangle
return 0;
var det_t = (ad.X * -ba.Y * -ca.Z) + (-ba.X * -ca.Y * ad.Z) + (-ca.X * ad.Y * -ba.Z) - (ad.Z * -ba.Y * -ca.X) - (-ba.Z * -ca.Y * ad.X) -
(-ca.Z * ad.Y * -ba.X);
var t = det_t/det;
if (t >= 0 & t <= 1) // segment intersects plane of triangle
{
var det_u = (ed.X*ad.Y*-ca.Z) + (ad.X*-ca.Y*ed.Z) + (-ca.X*ed.Y*ad.Z) - (ed.Z*ad.Y*-ca.X) - (ad.Z*-ca.Y*ed.X) -
(-ca.Z*ed.Y*ad.X);
var u = det_u/det;
var det_v = (ed.X*-ba.Y*ad.Z) + (-ba.X*ad.Y*ed.Z) + (ad.X*ed.Y*-ba.Z) - (ed.Z*-ba.Y*ad.X) -
(-ba.Z*ad.Y*ed.X)-(ad.Z*ed.Y*-ba.X);
var v = det_v/det;
if (Vector3D.IsNearlyEqual(u, 0) && v >= 0 && v <= 1)
return 1;
if (Vector3D.IsNearlyEqual(v, 0) && u >= 0 && u <= 1)
return 1;
if (Vector3D.IsNearlyEqual(v + u, 1) && u >= 0 && v >= 0)
return 1;
}
return -1;
}
Let's use parametric equations for coordinates (vectors in bold):
Segment DE:
sDE(t) = D + t * (E - D) = D + t * ED
//ED = E - D
Segment AB:
sAB(u) = A + u * (B - A) = A + u * BA
Segment AC:
sAC(v) = A + v * (C - A) = A + u * CA
Plane of ABC triangle is described by bi-parametric equation:
pABC(u,v) = A + u * BA + v * CA
Point in the plane with coordinates (u,v) lies inside the triangle, if
u in range [0..1]
and
v in range [0..1]
and
u+v is in range [0..1]
Point with coordinates (u,v) lies at the triangle edge, if [edge condition]
u = 0 and v in range [0..1] //at AC edge
or
v = 0 and u in range [0..1] //at AC edge
or
v + u = 1 and u in range (0..1) and v in range (0..1) //at BC edge
Now let's write equation for intersection of DE segment and ABC plane
sDE(t) = pABC(u,v)
D + t * ED = A + u * BA + v * CA
We can solve the last equation (system of 3 linear equations for every coordinate) and find parameters t,u,v
D.X + t * ED.X = A.X + u * BA.X + v * CA.X
D.Y + t * ED.Y = A.Y + u * BA.Y + v * CA.Y
D.Z + t * ED.Z = A.Z + u * BA.Z + v * CA.Z
t * ED.X - u * BA.X - v * CA.X = A.X - D.X
t * ED.Y - u * BA.Y - v * CA.Y = A.Y - D.Y
t * ED.Z - u * BA.Z - v * CA.Z = A.Z - D.Z
At first find determinant of this system - if it is zero, segment is parallel to the plane.
If not, check for parameter t. Segment intersects the plane if t is in range [0..1]
If yes, check whether u, v parameters comply to edge condition above
这篇关于段路段交叉点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
