2009-10-18 46 views
6

Làm cách nào để biết liệu hai tam giác giao nhau trong không gian Euclide 2D? (tức là hình học 2D cổ điển) cho tọa độ (X, Y) của mỗi đỉnh trong mỗi tam giác.Cách hiệu quả nhất để phát hiện giao lộ tam giác-tam giác là gì?

+0

Re thuật toán thực sự hiệu quả nhất, đó vẫn chưa được nhiều công việc được thực hiện trên câu hỏi đó - không ai đã dứt khoát thể hiện mà biến thể là nhanh nhất. Một vấn đề là rất nhiều cuộc thảo luận liên quan đến tris trong không gian 3D. Ví dụ: realtimecollisiondetection.net/blog/?p=29 PS Các sự cố như vậy thường được tính theo các điểm nằm ở "mặt chính xác" của một đoạn đường. Ví dụ: http://www.mochima.com/articles/cuj_geometry_article/cuj_geometry_article.html Như Nick đã chỉ ra trong đoạn cuối cùng của mình, trong thực tế, đó là tất cả về cách tốt bạn làm tiêu hủy. – Fattie

Trả lời

16

Một cách là để kiểm tra xem hai cạnh của tam giác Một intersect với bất kỳ bên của tam giác B, và sau đó kiểm tra tất cả sáu khả năng của một điểm A B bên trong hoặc một điểm B bên A.

Đối với một điểm bên trong một hình tam giác, ví dụ: Point in triangle test.

Khi chúng tôi kiểm tra va chạm trên đa giác, chúng tôi cũng có hình chữ nhật xung quanh cho đa giác của chúng tôi. Vì vậy, chúng tôi đầu tiên thử nghiệm cho va chạm hình chữ nhật và nếu có một nhấn chúng tôi tiến hành dò ​​tìm xung đột đa giác.

+0

hi @Joe. Đúng là chúng ta nên kiểm tra tất cả 3 mặt của A chống lại cả 3 mặt của B. Nhưng vì chúng ta sẽ kiểm tra xem các góc của A có ở trong B hay không - sau khi kiểm tra giao cắt đoạn đường - toàn bộ quy trình vẫn hoạt động . Đó là bởi vì nếu chúng ta phát hiện bất kỳ góc nào trong tam giác khác, chúng ta có một va chạm. –

+0

vâng, giờ đây chính xác hơn nhiều. Cảm ơn @Joe. Chúc mừng! –

+1

Chỉ cần 4 điểm trong thử nghiệm tam giác. https://jsfiddle.net/eyal/gxw3632c/ Đây không phải là thuật toán nhanh cho giao điểm tam giác-tam giác – Eyal

-4

Điều bạn đang thực sự tìm kiếm là thuật toán "Điểm trong đa giác". Nếu bất kỳ điểm nào của một hình tam giác nằm ở điểm kia, chúng sẽ giao nhau. Đây là một câu hỏi hay để kiểm tra.

How can I determine whether a 2D Point is within a Polygon?

+17

Điều này sẽ không đưa ra giải pháp * chung * vì có thể hai hình tam giác chồng lên nhau mà không có một trong hai đỉnh của chúng ở trong cai khac. – gnovice

+0

nếu chỉ có một điểm chồng chéo nhỏ, thật khó để biết điểm nào để chọn cho thử nghiệm –

-2

Như đã trình bày, bạn sẽ cần phải kiểm tra xem một điểm nằm bên trong một hình tam giác. Cách đơn giản nhất để kiểm tra xem một điểm có nằm trong một đa giác khép kín hay không là vẽ một đường thẳng theo bất kỳ hướng nào từ điểm và đếm số lần đường đi qua một đỉnh. Nếu câu trả lời là lẻ thì điểm đó nằm trong đa giác, ngay cả khi nó ở bên ngoài.

Đường thẳng đơn giản nhất để kiểm tra là đường thẳng nằm ở bên phải của điểm (hoặc một số hướng vuông góc khác). Điều này làm cho việc kiểm tra đỉnh vượt qua gần như tầm thường. Các kiểm tra sau đây là đủ:

  • Sản phẩm của điểm y phối hợp giữa y tọa độ của hai cuối điểm của đỉnh? Không, sau đó không giao nhau.

  • Tọa độ x của điểm lớn hơn điểm cuối bên phải xa nhất của đỉnh? Có, sau đó không vượt qua.

  • Tọa độ x của điểm có nhỏ hơn điểm cuối cùng bên trái của đỉnh không? Có, sau đó vượt qua.

  • Nếu các trường hợp trên không, sau đó bạn có thể sử dụng sản phẩm chéo của vector đại diện cho đỉnh và một vector hình thành từ sự kết thúc của đỉnh để điểm. Một câu trả lời tiêu cực sẽ cho biết điểm nằm ở một bên của đỉnh, một câu trả lời tích cực ở phía bên kia của đỉnh, và một số không trả lời trên đỉnh. Điều này hoạt động bởi vì một sản phẩm chéo liên quan đến việc lấy sin của hai vectơ.

+0

Điều này sẽ không cho bạn biết nếu hai tam giác cắt nhau, đó là câu hỏi. Bạn không thể chỉ kiểm tra một đỉnh của tam giác, vì hình tam giác có thể giao nhau mà không có bất kỳ đỉnh nào nằm trong nhau (ví dụ: ngôi sao của david). – Ergwun

2

Triển khai Python cho line intersectionpoint in triangle test, với một chút sửa đổi.

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 

Có một tương tác đầy đủ demo.

+0

Điều này nhận được câu trả lời sai trong trường hợp này: 't1 = [[0,0], [5,0], [0,5]]; t2 = [[-10,0], [- 5,0], [- 1,6]]; in (tri_intersect2 (t1, t2), Sai) ' – TimSC

+1

@TimSC Có, nó không phát hiện giao lộ cho hai đường song song. Bạn có thể thực thi điều đó | d | lớn hơn một số ít positve trong hàm 'line_intersect2'. –

+1

Bạn không cần phải làm tất cả các giao lộ 9 dòng, bạn có thể làm chỉ 8. Bởi vì nếu một trong các hình tam giác đi qua trong khác, nó cũng phải vượt qua trở lại. Vì vậy, nếu có 1 giao lộ, phải có hai giao lộ. Ngoài ra, bạn không cần tất cả các điểm trong thử nghiệm tam giác bởi vì, nếu không có nút giao, thì tất cả các điểm đều nằm trong hoặc không có điểm nào. Vì vậy, bạn có thể làm 8 line_intersect và 2 điểm trong Triangle. Hoặc làm 6 line_intersect và sau đó 6 điểm trong Triangle. Phụ thuộc vào những gì nhanh hơn cho bạn. – Eyal

0

Đây là nỗ lực của tôi vào vấn đề tam giác tam giác va chạm (thực hiện trong 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) 

Nó hoạt động dựa trên cơ sở thực tế là các tam giác không chồng chéo lên nhau nếu tất cả các điểm của tam giác 1 là trên mặt ngoài của ít nhất một trong các cạnh của tam giác 2 (hoặc ngược lại là đúng). Tất nhiên, hình tam giác không bao giờ lõm.

Tôi không biết liệu phương pháp này hiệu quả hơn hay ít hơn các phương pháp khác.

Bonus: Tôi chuyển nó vào C++ https://gist.github.com/TimSC/5ba18ae21c4459275f90

Các vấn đề liên quan