Если отрезок пересекает треугольник в пространстве

Question

Прежде чем перейти к флажку и пометить его как дурака, пожалуйста, подтвердите, что у меня небольшой опыт c ++ , и я не совсем понимаю ответы на некоторые вопросы, касающиеся матрицы или выше математика.

У меня есть треугольник, определяемый 3 точками, A (0,0,0), B (1,0,0), C (0,1, 1)

У меня есть отрезок, определяемый двумя точками, D (0,1 / 2,0) и E (1,1 / 2,1)

Теперь,Что касается первой ссылки, я понимаю, что если объемы тетры ABCD = 0 или тетры ABCE = 0, то есть точка внутри грани треугольников.Но когда упоминаются отрицательные объемы:

Вот один из способов решения вашей проблемы.Вычислить объем тетраэдра Td = (a, b, c, d) и Te = (a, b, c, e).Если объем Td или Te равен нулю, то одна конечная точка сегмента de лежит на плоскости, содержащей треугольник (a, b, c).Если объемы Td и Te имеют один и тот же знак, то де лежит строго в одну сторону, и пересечения нет. Если Td и Te имеют противоположные знаки, то де пересекает плоскость, содержащую (a, b, c) .

Как объем может быть отрицательным?Я что-то упустил?

У меня есть этот код для 2d треугольника, но я не могу найти в Интернете ничего для 3d треугольника, который понятен / легко переводится в код,

def areaOfTri(x1, y1, x2, y2, x3, y3): 
    return abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0) 


def pointIn2dTri(x1, y1, x2, y2, x3, y3, x, y): 
    # Calculate area of triangle ABC 
    A = areaOfTri (x1, y1, x2, y2, x3, y3)

    # Calculate area of triangle PBC  
    A1 = areaOfTri (x, y, x2, y2, x3, y3) 

    # Calculate area of triangle PAC
    A2 = areaOfTri (x1, y1, x, y, x3, y3) 

    # Calculate area of triangle PAB  
    A3 = areaOfTri (x1, y1, x2, y2, x, y) 

    # Check if sum of A1, A2 and A3  
    # is same as A 
    if(A == A1 + A2 + A3): 
        return True
    else: 
        return False

Некоторые случайные ссылки, которые я нашел: здесь , здесь и здесь

Answer 1

Пусть сегмент описывается параметрическим уравнением

P(t) = D + (E-D)*t

, а треугольник определяет двухпараметрическую систему координат в его плоскости

F(u,v) = A + u*(B-A) + v*(C-A)

Составьте систему из трех линейных уравнений для точки сегмента, принадлежащую так:Самолет

D.X + (E.X - D.X) * t  = A.X + u*(B.X-A.X) + v*(C.X-A.X)
similar for y,z

решите это за неизвестные t,u,v (это должно быть легко с NumPy).

Сегмент пересекает треугольник, если решение существует, и

t is in range 0..1
u ~ 0..1
v ~ 0..1
u+v ~ 0..1

В случае успеха подставьте t в первое уравнение, чтобы получить точку пересечения

Answer 2

В этом случае линия пересекает плоскость, содержащую (a, b, c).

Доказательство:

abcd = np.array([[0, 0, 0, 1],
                 [1, 0, 0, 1],
                 [0, 1, 1, 1],
                 [0, 0.5, 0, 1]])

abce = np.array([[0, 0, 0, 1],
                 [1, 0, 0, 1],
                 [0, 1, 1, 1],
                 [1, 0.5, 1, 1]])

print(np.sign(np.linalg.det(abcd)))
print(np.sign(np.linalg.det(abce)))

Вывод:

1.0
-1.0

Интерпретация отрицательный объем , вероятно, не по теме для этого сайта, но см. этот ответ .

Вкратце, векторы имеют направление, представляющее, откуда вы идете, а не то, куда вы идете, что представлено их знаком.

Мы можем расширить эту концепцию до объемов, признав, что объемограничен определенными векторами, которые сами имеют направления.