如何判断两个三角形在二维欧几里得空间中是否相交？（即经典的 2D 几何）给定每个三角形中每个顶点的 (X,Y) 坐标。
问问题
22222 次
6 回答
4
def line_intersect2(v1,v2,v3,v4):
'''
judge if line (v1,v2) intersects with line(v3,v4)
'''
d = (v4[1]-v3[1])*(v2[0]-v1[0])-(v4[0]-v3[0])*(v2[1]-v1[1])
u = (v4[0]-v3[0])*(v1[1]-v3[1])-(v4[1]-v3[1])*(v1[0]-v3[0])
v = (v2[0]-v1[0])*(v1[1]-v3[1])-(v2[1]-v1[1])*(v1[0]-v3[0])
if d<0:
u,v,d= -u,-v,-d
return (0<=u<=d) and (0<=v<=d)
def point_in_triangle2(A,B,C,P):
v0 = [C[0]-A[0], C[1]-A[1]]
v1 = [B[0]-A[0], B[1]-A[1]]
v2 = [P[0]-A[0], P[1]-A[1]]
cross = lambda u,v: u[0]*v[1]-u[1]*v[0]
u = cross(v2,v0)
v = cross(v1,v2)
d = cross(v1,v0)
if d<0:
u,v,d = -u,-v,-d
return u>=0 and v>=0 and (u+v) <= d
def tri_intersect2(t1, t2):
'''
judge if two triangles in a plane intersect
'''
if line_intersect2(t1[0],t1[1],t2[0],t2[1]): return True
if line_intersect2(t1[0],t1[1],t2[0],t2[2]): return True
if line_intersect2(t1[0],t1[1],t2[1],t2[2]): return True
if line_intersect2(t1[0],t1[2],t2[0],t2[1]): return True
if line_intersect2(t1[0],t1[2],t2[0],t2[2]): return True
if line_intersect2(t1[0],t1[2],t2[1],t2[2]): return True
if line_intersect2(t1[1],t1[2],t2[0],t2[1]): return True
if line_intersect2(t1[1],t1[2],t2[0],t2[2]): return True
if line_intersect2(t1[1],t1[2],t2[1],t2[2]): return True
inTri = True
inTri = inTri and point_in_triangle2(t1[0],t1[1],t1[2], t2[0])
inTri = inTri and point_in_triangle2(t1[0],t1[1],t1[2], t2[1])
inTri = inTri and point_in_triangle2(t1[0],t1[1],t1[2], t2[2])
if inTri == True: return True
inTri = True
inTri = inTri and point_in_triangle2(t2[0],t2[1],t2[2], t1[0])
inTri = inTri and point_in_triangle2(t2[0],t2[1],t2[2], t1[1])
inTri = inTri and point_in_triangle2(t2[0],t2[1],t2[2], t1[2])
if inTri == True: return True
return False
于 2014-04-29T05:34:18.063 回答
1
通过减少纵坐标对两个三角形的顶点进行排序。每个三角形最多需要三个比较。然后合并两个序列。我想这最多需要五次比较。
现在对于每个纵坐标，考虑一条水平线。它最多在一条线段中与两个三角形相交，很容易检查线段是否重叠。如果他们这样做了，或者如果他们改变了两条线之间的顺序，那么三角形相交。
更新：
有一个仿射变换可以将其中一个三角形归一化为 (0, 0)-(1, 0)-(0, 1)。将其应用于另一个，许多计算将简化。
于 2021-04-21T15:08:20.210 回答
0
这是我对三角形-三角形碰撞问题的尝试（在 python 中实现）：
#2D Triangle-Triangle collisions in python
#Release by Tim Sheerman-Chase 2016 under CC0
import numpy as np
def CheckTriWinding(tri, allowReversed):
trisq = np.ones((3,3))
trisq[:,0:2] = np.array(tri)
detTri = np.linalg.det(trisq)
if detTri < 0.0:
if allowReversed:
a = trisq[2,:].copy()
trisq[2,:] = trisq[1,:]
trisq[1,:] = a
else: raise ValueError("triangle has wrong winding direction")
return trisq
def TriTri2D(t1, t2, eps = 0.0, allowReversed = False, onBoundary = True):
#Trangles must be expressed anti-clockwise
t1s = CheckTriWinding(t1, allowReversed)
t2s = CheckTriWinding(t2, allowReversed)
if onBoundary:
#Points on the boundary are considered as colliding
chkEdge = lambda x: np.linalg.det(x) < eps
else:
#Points on the boundary are not considered as colliding
chkEdge = lambda x: np.linalg.det(x) <= eps
#For edge E of trangle 1,
for i in range(3):
edge = np.roll(t1s, i, axis=0)[:2,:]
#Check all points of trangle 2 lay on the external side of the edge E. If
#they do, the triangles do not collide.
if (chkEdge(np.vstack((edge, t2s[0]))) and
chkEdge(np.vstack((edge, t2s[1]))) and
chkEdge(np.vstack((edge, t2s[2])))):
return False
#For edge E of trangle 2,
for i in range(3):
edge = np.roll(t2s, i, axis=0)[:2,:]
#Check all points of trangle 1 lay on the external side of the edge E. If
#they do, the triangles do not collide.
if (chkEdge(np.vstack((edge, t1s[0]))) and
chkEdge(np.vstack((edge, t1s[1]))) and
chkEdge(np.vstack((edge, t1s[2])))):
return False
#The triangles collide
return True
if __name__=="__main__":
t1 = [[0,0],[5,0],[0,5]]
t2 = [[0,0],[5,0],[0,6]]
print (TriTri2D(t1, t2), True)
t1 = [[0,0],[0,5],[5,0]]
t2 = [[0,0],[0,6],[5,0]]
print (TriTri2D(t1, t2, allowReversed = True), True)
t1 = [[0,0],[5,0],[0,5]]
t2 = [[-10,0],[-5,0],[-1,6]]
print (TriTri2D(t1, t2), False)
t1 = [[0,0],[5,0],[2.5,5]]
t2 = [[0,4],[2.5,-1],[5,4]]
print (TriTri2D(t1, t2), True)
t1 = [[0,0],[1,1],[0,2]]
t2 = [[2,1],[3,0],[3,2]]
print (TriTri2D(t1, t2), False)
t1 = [[0,0],[1,1],[0,2]]
t2 = [[2,1],[3,-2],[3,4]]
print (TriTri2D(t1, t2), False)
#Barely touching
t1 = [[0,0],[1,0],[0,1]]
t2 = [[1,0],[2,0],[1,1]]
print (TriTri2D(t1, t2, onBoundary = True), True)
#Barely touching
t1 = [[0,0],[1,0],[0,1]]
t2 = [[1,0],[2,0],[1,1]]
print (TriTri2D(t1, t2, onBoundary = False), False)
它的工作基于这样一个事实，即如果三角形 1 的所有点都在三角形 2 的至少一条边的外侧（反之亦然），则三角形不重叠。当然，三角形永远不是凹的。
我不知道这种方法是否比其他方法更有效。
奖励：我将它移植到 C++ https://gist.github.com/TimSC/5ba18ae21c4459275f90
于 2016-03-27T17:38:29.020 回答
-3
如前所述，您需要检查一个点是否在三角形内。检查一个点是否在封闭多边形内的最简单方法是从该点向任意方向绘制一条直线，并计算该线与顶点相交的次数。如果答案是奇数，则该点在多边形内，偶数，则在多边形外。
要检查的最简单的直线是水平到点右侧（或其他垂直方向）的直线。这使得检查顶点交叉几乎是微不足道的。以下检查就足够了：
该点的y坐标是否在顶点的两个端点的y坐标之间？不，然后不交叉。
该点的 x 坐标是否大于顶点的最右端点？是的，然后不交叉。
该点的 x 坐标是否小于顶点的最左端点？是的，然后确实交叉。
如果上述情况失败，那么您可以使用表示顶点的向量与从顶点末端到该点形成的向量的叉积。否定答案将表明该点位于顶点的一侧，肯定答案位于顶点的另一侧，而顶点的答案为零。这是有效的，因为叉积涉及取两个向量的正弦。
于 2009-10-26T15:41:51.103 回答
-5
What you're really looking for is a "Point in Polygon" algorithm. If any of the points of one triangle are in the other, they are intersecting. Here is a good question to check out.
于 2009-10-18T17:56:50.137 回答