Fast test to see if a 2D line segment intersects a triangle in python

Question

In a 2D plane, I have a line segment (P0 and P1) and a triangle, defined by three points (t0, t1 and t2).

My goal is to test, as efficiently as possible ( in terms of computational time), whether the line touches, or cuts through, or overlaps with one of the edge of the triangle.

Everything is in 2D! I hope that someone can help me write this in python.

Thanks everyone for the help!

Probably can't do much better than performing a [line segment intersection test](https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect) against all three sides. — Kevin, May 07 '18 at 16:07
For efficiency, a preliminary bounding box test can be useful, depending on your configurations. — , May 08 '18 at 10:21

score 0 · Answer 1 · 2018-05-08T10:47:43.043

You can take inspiration from the Cohen-Sutherland line clipping algorithm, https://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm, which discusses the intersections based on a "region code". In the case of a triangle, there are 7 regions to be considered (hence 21 cases, but much symmetry), and it takes three tests per segment endpoint to perform the classification.

For some combinations of the region codes, the conclusion is immediate, and for some others, you will need an extra test to tell if the supporting line crosses the triangle.

You can (should) ease the computation by means of a change of coordinates: by using an affine frame defined by the three triangle vertices, the equations of the sides simplify to X=0, Y=0, X+Y=1.

Depending on the exact distribution of the triangles and segments, a bounding box test can be useful of not.

Joel Persinger · Answer 2 · 2018-05-08T13:43:24.463

Lucky for me the line segment can never start and end inside the triangle, it will always intersect. Below is my code in python. It is based on Kevin's idea that you just evaluate each line segment coordinates one at a time and see if they intersect. If it is a line and a triangle, run the code 3 times. Anyone have issue?(implemented in 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

`

The fact about ends of segments might significantly change problem statement and possible approaches. How do you expect effective solutions with incomplete problem definition??? — MBo, May 09 '18 at 01:27

Fast test to see if a 2D line segment intersects a triangle in python

2 Answers2