Calculate the intersection area of two rectangles

Question

I want to calculate the intersection of two squares where the coordinates of the input square are given by the bottom left corner and the top right corner. The other square is 6 units wide and has a variable positive integer height h (to make the task simpler).

For that I defined some functions:

The first one is to make sure that the first two coordinates a1, a2 represent the bottom left corner and the two last coordinates represent the top right corner. That way, if someone would type the coordinates the other way around, e.g. the first two numbers being the coordinates of the top left corner and the two last numbers being the coordinates for the bottom right corner, convert_to_standard would switch the coordinates to the right place:

def convert_to_standard(a1,a2,b1,b2):
    if a1 <= b1 and a2 <= b2:
        return (a1,a2,b1,b2)
    elif a1 >= b1 or a2 >= b2:
        a_1 = min(a1,b1)
        b_1 = max(a1,b1)
        a_2 = min(a2,b2)
        b_2 = max(a2,b2)
        return (a_1,a_2,b_1,b_2)

Since I'm quite new to Python I was wondering if there are more elegant ways of making this happen.

I've also written a function to test if the squares even intersect, maybe there is way of making this better too: (The "return "incorrect" bit is for later, get_intersection_area returns the string "incorrect input" if h < 0) (Sorry if I'm overexplainig too much)

def intersects(h,a1,a2,b1,b2):
    if h < 0:
        return "incorrect"
    
    a1,b1,a2,b2 = convert_to_standard(a1,b1,a2,b2)
    
    if a1 > 6: #square is on the right side of R_h
        return False
    
    if b1 < 0: #square is on the left side of R_h
        return False

    if a2 > h: #square is above R_h
        return False

    if b2 < 0: #square is below R_h
        return False

    else:
        return True

What also bothers me is that I'm not sure if the code runs functions needlessly. Specifically the function that calculates the width (get_delta_x1) and height (get_delta_x2) of the resulting square. I would like to only run it when the intersection is not empty and the input is correct (an incorrect input would be a negative value for h). Here is the complete code to check that:

def convert_to_standard(a1,a2,b1,b2):
    if a1 <= b1 and a2 <= b2:
        return (a1,a2,b1,b2)
    elif a1 >= b1 or a2 >= b2:
        a_1 = min(a1,b1)
        b_1 = max(a1,b1)
        a_2 = min(a2,b2)
        b_2 = max(a2,b2)
        return (a_1,a_2,b_1,b_2)

#checks if the input square intersects with the "given" square (whose height h has to be chosen)
def intersects(h,a1,a2,b1,b2):
    if h < 0:
        return "incorrect"
    
    a1,b1,a2,b2 = convert_to_standard(a1,b1,a2,b2)
    
    if a1 > 6: #square is on the right side of R_h
        return False
    
    if b1 < 0: #square is on the left side of R_h
        return False

    if a2 > h: #square is above R_h
        return False

    if b2 < 0: #square is below R_h
        return False

    else:
        return True

#lenght of the resulting intersection square
def get_delta_x1(a1,b1):
        if 0 <= a1 <= 6 and 0 <= b1 <= 6: #square is inside regarding x1
            return b1 - a1
        
        elif a1 < 0: #square sticks out on the left
            return b1

        elif b1 > 6: #square sitcks out on the right
            return 6 - a1
        
#height of the resulting intersection square
def get_delta_x2(h,a2,b2):
        if 0 <= a2 <= h and 0 <= b2 <= h: #square is inside regarding x2
            return b2 - a2

        elif a2 < 0: #square sticks out below
            return b2

        elif b2 > h: #square sticks out above
            return h - a2
#area of the intersection
def get_intersection_area(h,a1,a2,b1,b2):
    if intersects(h,a1,a2,b1,b2) == True:

        A = get_delta_x1(a1,b1) * get_delta_x2(h,a2,b2)

        return "The area of the resulting square is <"+str(A)+"> UA."

    elif intersects(h,a1,a2,b1,b2) == False:

        return "The intersection of the resulting squares is empty"

    elif intersects(h,a1,a2,b1,b2) == "incorrect":
        return "The input is incorrect" 

Since this is a quick program, changes in the code almost won't change runtime. I just want to get more elegant for future projects where runtime will be an issue. I hope this is the right forum for that.

Thank you a lot in advance

Answer 1

Using 4 variables (a1,a2,b1,b2) to define a rectangle is awkward. You need to pass all 4 variables, and remember what the correct order of the variables are.

Consider:

def convert_to_standard(a1,a2,b1,b2):
    ...

def intersects(h,a1,a2,b1,b2):
    if h < 0:
        return "incorrect"

    a1,b1,a2,b2 = convert_to_standard(a1,b1,a2,b2)

    ...

Is this correct? You've passed b1 to a2 and a2 to b1!

As suggested by Sam Stafford, using a tuple of tuples can help.

Rect = Tuple[Tuple[int, int], Tuple[int, int]]

But it still isn't clear if the first coordinate is the lower left, or the upper left. Better would be to use a NamedTuple:

from typing import NamedTuple

class Rectangle(NamedTuple):
    left: float
    bottom: float
    right: float
    top: float

This Rectangle class gives you named members from rect.left through rect.top, which makes it easy to tell what the values represent.

The convert_to_standard() functionality can be added as a @staticmethod to this class, returning a normalized Rectangle regardless of the vertex orientation:

    @staticmethod
    def normalize(x1, y1, x2, y2) -> 'Rectangle':
        return Rectangle(min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2))

You can add a @property for the rectangle's width and height, ensuring the width and height are never negative:

    @property
    def width(self) -> float:
        return max(self.right - self.left, 0)

    @property
    def height(self) -> float:
        return max(self.top - self.bottom, 0)

As well as a @property for the rectangle's area:

    @property
    def area(self) -> float:
        return self.width * self.height

You can add a method to determine if a rectangle is valid or not, based on this area. if rect will return True only for valid rectangles, which have a positive area, so must have a top coordinate larger than the bottom, and a right coordinate larger than the left:

    def __bool__(self):
        return self.area > 0

Finally, we can define a method which returns the intersection of two Rectangle objects:

    def intersect(self, other):
       if not isinstance(other, Rectangle):
           raise TypeError("Not a rectangle")
       return Rectangle(max(self.left, other.left), max(self.bottom, other.bottom),
                        min(self.right, other.right), min(self.top, other.top))

And we can write some code to quickly exercise this class, based on the diagram given at the top. (Also, notice the use of f"..." strings for formatted output):

if __name__ == '__main__':
    h = 5
    rh = Rectangle(0, 0, 6, h)
    r1 = Rectangle.normalize(-6, -4, 2, 1)
    r2 = Rectangle.normalize(-3, 7, 3, 5)   # flipped top-bottom
    r3 = Rectangle.normalize(9, 2, 5, 4)    # flipped left-right

    for rect in (r1, r2, r3):
        intersection = rh.intersect(rect)
        if intersection:
            print(f"{rect} intersection area = {intersection.area}")
        else:
            print(f"{rect} No intersection")

Output:

Rectangle(left=-6, bottom=-4, right=2, top=1) intersection area = 2
Rectangle(left=-3, bottom=5, right=3, top=7) No intersection
Rectangle(left=5, bottom=2, right=9, top=4) intersection area = 2

PEP-8

PEP-8 is a style guide for Python. It defines certain conventions to improve conformity and readability amongst Python programs. Things like:

• All commas (such as in function parameters and arguments) must be followed by one space.
• Variables must be snake_case, which you follow except for A for area.

Consistent Return Types

What does intersects(h,a1,a2,b1,b2) return? A bool? If so, you can test it like:

if intersect(h, a1, a2, b1, b2):
    ...
else:
    ...

Except, it can also return the string "incorrect", which is treated as True in all conditionals. So instead you must test the return value as is True, is False and == "incorrect", and hope you don't accidentally write == "Incorrect" or == "invalid".

It is much better to raise an exception when incorrect arguments are passed to the function, such as intersect() raising a TypeError when not given a Rectangle argument.

Also, you are doing the computation up to 3 times! This is inefficient; you should store the return value from intersect(h, a1, a2, b1, b2) in a local variable, and then test that value, instead of doing the intersection calculations repeatedly.

Answer 2

My main piece of advice is to think in terms of general solutions rather than trying to handle each case separately. For example, taking this function:

def convert_to_standard(a1,a2,b1,b2):
    if a1 <= b1 and a2 <= b2:
        return (a1,a2,b1,b2)
    elif a1 >= b1 or a2 >= b2:
        a_1 = min(a1,b1)
        b_1 = max(a1,b1)
        a_2 = min(a2,b2)
        b_2 = max(a2,b2)
        return (a_1,a_2,b_1,b_2)

If a1 <= b1 then min(a1, b1) is the same as a1, right? And so on for the other values in your if statements. This can in fact be written as:

def convert_to_standard(a1, a2, b1, b2):
    return (
        min(a1, b1),
        min(a2, b2),
        max(a1, b1),
        max(a2, b2),
    )

Because it's hard to keep track of which value is which, I'd personally want to express this as two coordinate pairs rather than a single 4-tuple. I'd also use the name "normalize" for this operation:

from typing import Optional, Tuple

Rect = Tuple[Tuple[int, int], Tuple[int, int]]

def normalize(rect: Rect) -> Rect:
    """
    Given a rectangle specified as a pair of arbitrary opposite corners,
    normalize to a pair where the first is the lower left and second is upper right.
    """
    (ax, ay), (bx, by) = rect
    return (
        (min(ax, bx), min(ay, by)),
        (max(ax, bx), max(ay, by)),
    )

In your problem description:

The other square is 6 units wide and has a variable positive integer height h (to make the task simpler).

this does not actually make the task simpler, it makes it harder, because now you have to deal with different formats of input. It would be simpler IMO to write a function that takes two rectangles in a standardized format and returns a rectangle representing their intersection, since it's easier to reason about that sort of straightforward geometric problem than to solve a particular special case subset of it.

def bottom(rect: Rect) -> int:
    return rect[0][1]

def top(rect: Rect) -> int:
    return rect[1][1]

def left(rect: Rect) -> int:
    return rect[0][0]

def right(rect: Rect) -> int:
    return rect[1][0]

def overlaps(a: Rect, b: Rect) -> bool:
    """
    Computes whether two normalized rectangles have a non-zero overlap.
    """
    return (
        top(a) > bottom(b)      # top of a is not below b
        and top(b) > bottom(a)  # top of b is not below a
        and right(a) > left(b)  # right of a is not left of b
        and right(b) > left(a)  # right of b is not left of a
    )

etc.

If your input is in a specialized format, I think it's still better to write the general-purpose rectangle code and then add a bit of code to translate the input into a normalized rectangle.