点在三角形内 [英] point inside a triangle
问题描述
我想问你,是否有人知道如何在空间参考系统上检查点是否在给定三角形内.我知道,就2D系统而言,我可以通过以下过程获得这一点:要确定给定点v是否位于给定三角形内,请考虑单个顶点,表示为v0,v1和v2是来自其他两个顶点v0的向量.用v1和v2表示从v0到v的向量,然后得出
I wanted to ask you if anyone knew how to check if a point was inside a given triangle, on a reference system in space. I am aware that speaking of 2d systems I can obtain this point with the following procedures: To determine if a given point v lies within a given triangle, consider a single vertex, denoted v0, v1 and v2 are the vectors from the other two vertices v0. Expressing the vector from v0 to v in terms of v1 and v2 then gives
v = v0 + av1 + bv2
其中a,b是常数.解决a,b
where a, b are constant. Solve for a, b
a =(det(v v2)-det(v0 v2))/(det(v1 v2))
b =-(det(v v1)-det(v0 v1))/(det(v1 v2))
如果a,b>,则点v在三角形内.0 e a + b <1.我想知道是否有类似的程序.
So the point v is inside the triangle if a, b> 0 e a + b <1. I was wondering if there was a similar procedure or not.
在MBo的建议下,我编写了以下代码:
After MBo's advice I wrote the following code:
def pointLocatedOnTheTriangularFace(self, point):
vertList = list(self.vertices)
system = []
for i in range(4):
p = vertList[1].coords-vertList[0].coords
q = vertList[2].coords-vertList[0].coords
n = np.cross(p,q)
for i in range(3):
system.append([p[i],q[i],n[i]])
try:
solution = list(np.linalg.solve(system,np.array(point-vertList[0].coords)))
if solution[0] > 0 and solution[1] > 0 and solution[0]+solution[1]<1 and solution[2]==0:
return True
except np.linalg.LinAlgError:
print("The system having the floor {0} {1} {2} with the point {3} does not admit solutions.\n".format(vertList[0].coords,vertList[1].coords,vertList[2].coords,point))
v = vertList.pop(0)
vertList.append(v)
return False
我正在使用四面体,而令我感兴趣的三角形是四面体的面.我说这行不通,但我不明白为什么.谁能告诉我我在做什么错?我以以下方式更改了代码,它似乎可以正常工作.
I am working with tetrahedra, and the triangles that interest me are the faces of the tetrahedron. I state that it does not work but I can not understand why. Can anyone tell me what am I doing wrong? I changed the code in the following way and it seems to work.
def pointLocatedOnTheTriangularFace(self, point):
vertList = list(self.vertices)
system = []
for i in range(4):
r = point-vertList[0].coords
p = vertList[1].coords-vertList[0].coords
q = vertList[2].coords-vertList[0].coords
n = np.cross(p,q)
if np.inner(r,n) == 0:
system = [[p[0],q[0]],[p[1],q[1]]]
try:
solution = list(np.linalg.solve(system,np.array([r[0],r[1]])))
if solution[0] > 0 and solution[1] > 0 and solution[0]+solution[1]<1:
return True
except np.linalg.LinAlgError:
print("The system having the floor {0} {1} {2} with the point {3} does not admit solutions.\n".format(vertList[0].coords,vertList[1].coords,vertList[2].coords,point))
v = vertList.pop(0)
vertList.append(v)
return False
通过以下测试:
def test_PointPlacedOnTheTriangularFace(self):
tr1Vertices = [vertex([0,4.32978e-17,0.5],1),vertex([-0.433013,0.25,-0.5],2),vertex([-4.32978e-17,-0.5,-0.5],3),vertex([0.433013,0.25,-0.5],4)]
tr1= tetrahedron(tr1Vertices)
point = vertex([0,0,-0.5],1)
self.assertTrue(tr1.pointLocatedOnTheTriangularFace(point.coords), msg="In this test the point is inside the face")
def test_PointNotPlacedLocatedOnTheTriangularFace(self):
tr1Vertices = [vertex([0,4.32978e-17,0.5],1),vertex([-0.433013,0.25,-0.5],2),vertex([-4.32978e-17,-0.5,-0.5],3),vertex([0.433013,0.25,-0.5],4)]
tr1= tetrahedron(tr1Vertices)
point = vertex([1,0,-0.5],1)
self.assertFalse(tr1.pointLocatedOnTheTriangularFace(point.coords), msg="In this test the point is outside the face")
如果有人对我有任何建议,我一定会珍惜.谢谢.
If anyone has any advice for me I will surely treasure it. Thanks.
推荐答案
描述的2D方法本质上是将矢量 r = v-v0
通过基矢量 p = v1-v0 代码>和
q = v2-v0
.
Described 2D approach is essentially decomposition of vector r = v-v0
by basis vectors p=v1-v0
and q=v2-v0
.
在3D中,您可以通过向量 p
, q
和 n = pxq
(其中 x
表示矢量积运算)
In 3D you can decompose vector r
by vectors p
, q
and n = p x q
(where x
denotes vector product operation)
如果所得系数 a,b,c
满足限制 a,b>0,a + b<1,c = 0
,然后点 v
位于其中的三角形平面中.
If resulting coefficients a,b,c
fulfill limits a, b > 0, a + b < 1, c=0
, then point v
lies in triangle plane inside it.
对于分解,请求解此线性系统以查找未知的 a,b,c
:
For decomposition solve this linear system for unknowns a,b,c
:
rx = a * px + b * qx + c * nx
ry = a * py + b * qy + c * ny
rz = a * pz + b * qz + c * nz
替代方法-检查点积 r.dot.n
为零-在这种情况下,点位于平面上,系数с
为零,则可以求解简化的系统,用于 a
和 b
选择一对方程式,并排除第三被加数(与2D方法相同)
Alternative approach - check that dot product r.dot.n
is zero - in this case point lies in the plane, coefficient с
is zero, and you can solve simplified system for a
and b
choosing a pair of equations and excluding the third summand (same method as in 2D)
这篇关于点在三角形内的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!