Какой самый эффективный способ обнаружить пересечение треугольника с треугольником?

Один из способов - проверить, пересекаются ли две стороны треугольника A с любой стороной треугольника B, а затем проверьте все шесть возможностей точки A внутри B или точки B внутри A.

Для точки внутри треугольника см., Например: Точка в тесте треугольника.

Когда мы тестируем столкновения на полигонах, у нас также есть окружающий прямоугольник для наших полигонов. Итак, сначала мы проверяем на предмет столкновений прямоугольников, и если есть попадание, мы переходим к обнаружению столкновений многоугольников.

Реализация 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

Вот моя попытка решить проблему столкновения треугольника с треугольником (реализована на 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

Отсортируйте вершины обоих треугольников по убыванию ординаты. Для этого требуется не более трех сравнений на треугольник. Затем объедините две последовательности. Думаю, для этого потребуется не более пяти сравнений.

Теперь для каждой ординаты рассмотрим горизонтальную линию. Он пересекает оба треугольника не более чем в одном линейном сегменте, и легко проверить, действительно ли сегменты перекрываются. Если это так или если они меняют порядок между двумя линиями, то треугольники пересекаются.

Как уже говорилось, вам нужно убедиться, что точка находится внутри треугольника. Самый простой способ проверить, находится ли точка внутри замкнутого многоугольника, - провести прямую линию в любом направлении от точки и посчитать, сколько раз линия пересекает вершину. Если ответ нечетный, то точка находится в многоугольнике, четный - снаружи.

Простейшая прямая линия для проверки - это линия, проходящая горизонтально справа от точки (или в другом перпендикулярном направлении). Это делает проверку пересечения вершин почти тривиальной. Следующих проверок должно хватить:

• Находится ли y-координата точки между y-координатами двух конечных точек вершины? Нет, тогда не переходит.

• Координата x точки больше самой дальней правой конечной точки вершины? Да тогда не переступает.

• Координата x точки меньше самой дальней левой конечной точки вершины? Да, значит, крест.

• Если вышеперечисленные случаи терпят неудачу, вы можете использовать перекрестное произведение вектора, представляющего вершину, и вектора, образованного от конца вершины до точки. Отрицательный ответ будет означать, что точка лежит по одну сторону от вершины, положительный ответ - по другую сторону от вершины, а нулевой ответ - по вершине. Это работает, потому что кросс-произведение включает в себя синус двух векторов.

На самом деле вам нужен алгоритм «Точка в многоугольнике». Если какая-либо из точек одного треугольника находится в другом, они пересекаются. Вот хороший вопрос, чтобы проверить.

Как определить, находится ли 2D-точка в пределах многоугольника?