2つの三角形が2Dユークリッド空間で交差するかどうかをどのように判断できますか？（つまり、古典的な2Dジオメトリ）各三角形の各頂点の（X、Y）座標が与えられます。
22222 次
6 に答える
18
1つの方法は、三角形Aの2つの辺が三角形Bのいずれかの辺と交差するかどうかを確認してから、Bの内側のAの点またはAの内側のBの点の6つの可能性すべてを確認することです。
三角形の内側の点については、たとえば、「三角形の点のテスト」を参照してください。
ポリゴンの衝突をテストするとき、ポリゴンの周囲の長方形もあります。したがって、最初に長方形の衝突をテストし、ヒットがあった場合はポリゴンの衝突検出に進みます。
于 2009-10-18T17:26:58.413 に答える
4
少し変更を加えた、三角形テストの線交差と点のPython実装。
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
縦座標を減らして、両方の三角形の頂点を並べ替えます。これには、三角形ごとに最大3つの比較が必要です。次に、2つのシーケンスをマージします。これにはせいぜい5回の比較が必要だと思います。
ここで、すべての縦座標について、水平線について考えます。最大で1つの線分で両方の三角形と交差し、セグメントが重なっていることを確認するのは簡単です。もしそうなら、あるいはそれらが2本の線の間で順序を変えるなら、三角形は交差します。
アップデート：
三角形の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のエッジの少なくとも1つの外側にある場合（またはその逆の場合）、三角形が重ならないという事実に基づいて機能します。もちろん、三角形は決して凹面ではありません。
このアプローチが他のアプローチよりも効率的かどうかはわかりません。
ボーナス：C++に移植しましたhttps://gist.github.com/TimSC/5ba18ae21c4459275f90
于 2016-03-27T17:38:29.020 に答える
-3
前述のように、ポイントが三角形の内側にあることを確認する必要があります。ポイントが閉じたポリゴンの内側にあるかどうかを確認する最も簡単な方法は、ポイントから任意の方向に直線を描き、その線が頂点と交差する回数を数えることです。答えが奇数の場合、ポイントはポリゴン内にあり、偶数の場合は外側にあります。
チェックする最も簡単な直線は、ポイントの右側（または他の垂直方向）に水平に伸びる直線です。これにより、頂点の交差のチェックはほとんど簡単になります。次のチェックで十分です。
ポイントのy座標は、頂点の2つの端点のy座標の間にありますか？いいえ、交差しません。
ポイントのx座標は、頂点の最も右端のエンドポイントよりも大きいですか？はい、交差しません。
ポイントのx座標は、頂点の左端のエンドポイントよりも小さいですか？はい、それから交差します。
上記のケースが失敗した場合は、頂点を表すベクトルと頂点の端から点までに形成されたベクトルの外積を使用できます。否定的な答えは、ポイントが頂点の片側にあり、肯定的な答えが頂点の反対側にあり、ゼロの答えが頂点にあることを示します。これは、外積が2つのベクトルの正弦を取ることを伴うために機能します。
于 2009-10-26T15:41:51.103 に答える
-5
あなたが本当に探しているのは「ポリゴンの点」アルゴリズムです。一方の三角形のいずれかの点がもう一方の点にある場合、それらは交差しています。ここにチェックアウトするための良い質問があります。
于 2009-10-18T17:56:50.137 に答える