2 minute read

Intersecting Rectangles - Elements of Programming Interviews (EPI)

Problem:

Write a program which tests if 2 rectangles have a nonempty intersection. If the intersection is nonempty, return the rectangle formed by their intersection.

Solution:

We can start off by considering how to determine if the rectangles intersect. It helps to consider the \(x\) and \(y\) axes separately and determine if there is any overlap. This is just simple arithmetic with starting and end points of the lines and some comparisons to see if there is any overlap. If both \(x\) and \(y\) overlap then we simply return the region formed by this intersection.

Rect = collections.namedtuple('Rect', ('x', 'y', 'width', 'height'))
Line = collections.namedtuple('Line', ('x', 'length'))

def intersect_rectangle(r1: Rect, r2: Rect) -> Rect:
    """Function to return the intersection region of 2
    rectangles. Assuming a rectange to be defined by its
    lower left coordinates (X,Y) and its width and height.
    """
    def intersecting_line(l1: Line, l2: Line) -> Line:
        """Function to return the overlapping line of 2
        lines. Defined by starting position x and length
        """
        # Find which line starts first:
        if l1.x == l2.x:
            # If they both start at same position:
            first, second = (l1, l2) if l1.length <= l2.length else (l2, l1)
            return first
        else:
            first, second = (l1, l2) if (l1.x < l2.x) else (l2, l1)
            # Find if there is any overlap by comparing end points:
            first_end, second_end = (first.x + first.length, second.x + second.length)
            if first_end > second.x:
                if first_end >= second_end:
                    return second
                else:
                    return Line(second.x, first_end - second.x)
        return Line(0, 0)
    x_overlap = intersecting_line(Line(r1.x, r1.width), Line(r2.x, r2.width))
    y_overlap = intersecting_line(Line(r1.y, r1.height), Line(r2.y, r2.height))
    if x_overlap.length and y_overlap.length:
        return Rect(x_overlap.x, y_overlap.x, x_overlap.length, y_overlap.length)

    return Rect(0, 0, -1, -1)

We came up with a wrong solution for this because we didnt consider the case of common borders as being an intersection with width 0 or height 0. We thought it was a reasonable assumption since Lines arent exactly rectangles… Anyway, the correct solution is as follows which also considers the case of 0 area lines as rectangles.

def intersect_rectangle(R1, R2):
    def is_intersect(R1, R2):
        return (R1.x <= R2.x + R2.width and R1.x + R1.width >= R2.x
                and R1.y <= R2.y + R2.height and R1.y + R1.height >= R2.y)

    if not is_intersect(R1, R2):
        return Rect(0, 0, -1 , -1) # No intersection.
    return Rect(
        max(R1.x, R2.x),
        max(R1.y, R2.y),
        min(R1.x + R1.width, R2.x + R2.width) - max(R1.x, R2.x),
        min(R1.y + R1.height, R2.y + R2.height) - max(R1.y, R2.y))