Check if two triangles intersect

Question

Problem statement: Write a function which checks if two triangles intersect or not. Complete containment or tangential contact is not considered intersection.

Approach: I have considered each triangle as collection of three line segments. And then checked if any of the line segment from first triangle intersects segments from segments second triangle. To check line segment intersection, I have used rotation direction of one segment endpoint with respect to another. Assertion is that in case of intersection rotation direction will change( from clockwise to anticlockwise or vice versa). Rotation direction is computed using cross product.

Review ask: Do you see functional glitches? Missing boundary or error cases? Input around use of python

import operator

def compute_direction(common_point, first_endpoint, second_endpoint):
    first_vector = tuple(map(operator.sub, first_endpoint, common_point))
    second_vector = tuple(map(operator.sub, second_endpoint, common_point))
    return first_vector[0]*second_vector[1] - first_vector[1]*second_vector[0]
    

def does_line_segments_intersect(first_segment, second_segment):
    d1 = compute_direction(first_segment[0], first_segment[1], second_segment[0])
    d2 = compute_direction(first_segment[0], first_segment[1], second_segment[1])
    d3 = compute_direction(second_segment[0], second_segment[1], first_segment[0])
    d4 = compute_direction(second_segment[0], second_segment[1], first_segment[1])
    
    if d1*d2 < 0 and d3*d4 < 0:
        return True
    
    pass

def does_triangles_intersect(first_triangle, second_triangle):    
    for first_triangle_side in range(3):
        first_side = [first_triangle[first_triangle_side], first_triangle[(first_triangle_side+1)%3]]
        for second_triangle_side in range(3):
            second_side =  [second_triangle[second_triangle_side], second_triangle[(second_triangle_side+1)%3]]
            if does_line_segments_intersect(first_side, second_side):
                return True
    return False
   

print(does_triangles_intersect([(0, 0), (8, 0), (4, 4)], [(0, 0), (8, 0), (8, 4)]))

Answer 1

Your code looks mostly good to me. Here are a few comments

Style details

• Invisible details but there are a few trailing whitespaces that should be cleaned up
• Probably a matter of personal preference but I think that ordinal ("first", "second") lead to variables names which are pretty long and could make things harder to understand at first glance. My suggestion would to be use number as suffixes: "segment1", "segment2", etc.
• Each function implemented is non-trivial and deserves a bit of explanation regarding what it does, the expected inputs, the algorithm used.
• The code seems to follow PEP 8 pretty well except for this particular point:

Be consistent in return statements. Either all return statements in a function should return an expression, or none of them should. If any return statement returns an expression, any return statements where no value is returned should explicitly state this as return None, and an explicit return statement should be present at the end of the function (if reachable)

Indeed, does_line_segments_intersect returns either True (explicitly) or None (implicitly). It would be better to returns either True or False (explicitly).

if d1*d2 < 0 and d3*d4 < 0:
        return True
return False

Then, it is a bit clearer that we can have a single return statement:

return d1*d2 < 0 and d3*d4 < 0

More tests

Unit-tests could help to:

• explain your code
• check that it works as expected on various cases, in particular edge-cases

Here is what I wrote using the assert statement but this should probably be done using a proper unit-test framework.

# Tests about compute_direction
###############################

# An endpoint is the origin
assert compute_direction((1, 2), (3, 4), (1, 2)) == 0
# Two endpoints are similar
assert compute_direction((1, 2), (3, 4), (3, 4)) == 0
# Two endpoints in the exact same direction
assert compute_direction((0, 0), (1, 2), (3, 6)) == 0

# More interesting cases
assert compute_direction((4, 4), (0, 0), (8, 4)) > 0
assert compute_direction((8, 0), (8, 4), (4, 4)) > 0
assert compute_direction((8, 0), (4, 4), (8, 4)) < 0
assert compute_direction((8, 4), (0, 0), (4, 4)) < 0
assert compute_direction((0, 0), (8, 0), (4, 4)) > 0
assert compute_direction((0, 0), (8, 0), (8, 4)) > 0
assert compute_direction((4, 4), (0, 0), (8, 0)) > 0
assert compute_direction((8, 0), (4, 4), (0, 0)) > 0
assert compute_direction((8, 0), (8, 4), (0, 0)) > 0
assert compute_direction((8, 4), (0, 0), (8, 0)) > 0

# Tests about triangles_intersect
#################################

# Example provided
assert triangles_intersect([(0, 0), (8, 0), (4, 4)], [(0, 0), (8, 0), (8, 4)])

# No intersection, similar triangle
assert not triangles_intersect([(0, 0), (1, 0), (0, 1)], [(0, 0), (1, 0), (0, 1)])
# No intersection, one common point
assert not triangles_intersect([(0, 0), (1, 0), (0, 1)], [(1, 0), (2, 0), (2, 1)])
# No intersection, two common points
assert not triangles_intersect([(0, 0), (1, 0), (0, 1)], [(1, 1), (1, 0), (0, 1)])

# Intersection, one point in other triangle
assert triangles_intersect([(0, 0), (3, 0), (0, 3)], [(1, 1), (1, 3), (3, 1)])
# Intersection, two points in other triangle
assert triangles_intersect([(0, 0), (4, 0), (0, 4)], [(1, 2), (2, 1), (3, 3)])
# Intersection, three points in other triangle
# assert triangles_intersect([(0, 0), (4, 0), (0, 4)], [(1, 1), (2, 1), (1, 2)])  # WRONG
# Intersection but not point in other triangle
assert triangles_intersect([(0, 1), (4, 1), (2, 3)], [(0, 2), (4, 2), (2, 0)])

# Intersection, two common points, one on side
# assert triangles_intersect([(0, 0), (2, 0), (1, 1)], [(1, 0), (2, 0), (1, 1)])  # WRONG
# Intersection, two common points, one inside
# assert triangles_intersect([(0, 0), (3, 0), (0, 3)], [(1, 1), (3, 0), (0, 3)])  # WRONG
# Intersection, two common points, one outside
assert triangles_intersect([(0, 0), (1, 1), (1, 0)], [(0, 1), (1, 1), (1, 0)])

From what I understand, a few cases are not handled properly (flagged "WRONG" above). However, I am not too sure if the code is incorrect or if my understanding is incorrect.

My understanding is that 2 triangle intersects if there are points which are (strictly) inside the 2 triangles but it looks like the code expects triangles to intersect if and only if they have sides that intersect.

I'll let you see if this if what you want.

Edit: a value was wrong in one of my examples. I noticed this (and fixed this) by using some code to generate the corresponding graph. See:

Second edit:

Now that I understand better the expected behavior, let's continue the review.

The logic to iterate over the different sides of the triangle is a bit cumbersome. For a start, we could extract it in a function on its own. Also, we could easily write it in a very generic way so that it gives the different sides of any polygon. Using generator, we could have something like:

def get_sides(polygon):
    last_point = polygon[-1]
    for point in polygon:
        yield (last_point, point)
        last_point = point

def triangles_intersect(triangle1, triangle2):
    for side1 in get_sides(triangle1):
        for side2 in get_sides(triangle2):
            if segments_intersect(side1, side2):
                return True
    return False

Going further, we could use itertools.product and any.

def triangles_intersect(triangle1, triangle2):
    return any(segments_intersect(side1, side2)
               for side1, side2 in itertools.product(get_sides(triangle1), get_sides(triangle2)))