Быстрый тест, чтобы увидеть, пересекается ли отрезок 2D линии с треугольником в Python

Question

В 2D-плоскости у меня есть отрезок (P0 и P1) и треугольник, определяемый тремя точками (t0, t1 и t2).

Моя цель - максимально эффективно (с точки зрения вычислительного времени) проверить, касается ли линия, или она прорезает, или перекрывает один из краев треугольника.

Все в 2D! Я надеюсь, что кто-то может помочь мне написать это на python.

Спасибо всем за помощь!

Answer 1

К счастью для меня, отрезок никогда не может начинаться и заканчиваться внутри треугольника, он всегда будет пересекаться. Ниже мой код на Python. Это основано на идее Кевина, что вы просто оцениваете координаты каждого отрезка линии по одной за раз и смотрите, не пересекаются ли они. Если это линия и треугольник, запустите код 3 раза. У кого-нибудь есть проблема? (Реализовано в python):

#Check to see if two lines intersect
# return a 1 if they intersect
# return a 0 if the do not intersect
def line_intersection_test( p0_x, p0_y, p1_x, p1_y, p2_x, p2_y, p3_x,p3_y):


    s1_x = float(p1_x - p0_x)
    s1_y = float(p1_y - p0_y)
    s2_x = float(p3_x - p2_x)
    s2_y = float(p3_y - p2_y)
    outcome = 0

    s = float (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y)
    t = float ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y)

    if (s >= 0 and s <= 1 and t >= 0 and t <= 1):
        outcome = 1

    return outcome

#basically feed line segment and the three lines that form the triangle separately to line_intersect_test to see if they intersect
def triangle_intersection_test(vecX1, vecY1, vecX2, vecY2, triX1, triY1, triX2, triY2,triX3, triY3):

    side_1_test = line_intersection_test(vecX1, vecY1, vecX2, vecY2, triX1, triY1, triX2, triY2)
    side_2_test = line_intersection_test(vecX1, vecY1, vecX2, vecY2, triX2, triY2, triX3, triY3)
    side_3_test = line_intersection_test(vecX1, vecY1, vecX2, vecY2, triX1, triY1, triX3, triY3)

    result = side_1_test + side_2_test + side_3_test

    if result > 0:
    outcome = "motion detected"
    else:
    outcome = "motion not detected"

    return outcome

`

Answer 2

Вы можете черпать вдохновение из алгоритма обрезания линий Коэна-Сазерленда, https://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm,, который обсуждает пересечения на основе "кода региона". В случае треугольника необходимо рассмотреть 7 областей (следовательно, 21 случай, но с большой симметрией), и для выполнения классификации требуется три теста на конечную точку сегмента.

Для некоторых комбинаций кодов регионов вывод является немедленным, а для некоторых других вам потребуется дополнительный тест, чтобы определить, пересекает ли линия поддержки треугольник.

Вы можете (должны) облегчить вычисление путем изменения координат: используя аффинную систему отсчета, определяемую тремя вершинами треугольника, уравнения сторон упрощаются до X = 0, Y = 0, X + Y = 1.

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