Check if two rectangles overlap

Question

Suppose rectangles are parallel to x-axis/y-axis. Check if two rectangles overlap or not and if they do, output the overlap area.

Here is my code and I track min/max x-coordinate and min/max y-coordinate for each rectangle. Using Python 2.7.

Any comments on code bugs, code style and performance improvements in terms of algorithm time complexity are appreciated.

class Rectangle:
    def __init__(self, min_x, max_x, min_y, max_y):
        self.min_x = min_x
        self.max_x = max_x
        self.min_y = min_y
        self.max_y = max_y

    def is_intersect(self, other):
        if self.min_x > other.max_x or self.max_x < other.min_x:
            return False
        if self.min_y > other.max_y or self.max_y < other.min_y:
            return False
        return True

    def get_insersec_region(self, other):
        if not self.is_intersect(other):
            return None
        min_x = max(self.min_x, other.min_x)
        max_x = min(self.max_x, other.max_x)
        min_y = max(self.min_y, other.min_y)
        max_y = min(self.max_y, other.max_y)

        return Rectangle(min_x, max_x, min_y, max_y)

    def __str__(self):
        return str(self.min_x) + '\t' + str(self.max_x) + '\t' + str(self.min_y) + '\t' + str(self.max_y)

if __name__ == "__main__":
    r1 = Rectangle(0,10,0,10)
    r2 = Rectangle(5,15,5,15)
    print r1.is_intersect(r2)
    print r1.get_insersec_region(r2)

Answer 1

Instead of get_insersec_region, I would call this method __and__. This way you can use overlap = r1 & r2, just like for set intersection.

You can add intersect = __and__ if you also want the expressiveness of overlap = r1.intersect(r2).

Instead of returning None, I would consider returning an empty Rectangle. This way you don't need any special code to handle e.g. (r1&r2).area. For this, I would set default values for the coordinates, all 0.

Incidentally, I would add an area method and make it a property:

@property
def area(self):
    return (self.max_x - self.min_x) * (self.max_y - self.min_y)

The reason it should be a property is maintainability. If you decide at some point that you only want to compute the area at creation time because a Rectangle is not allowed to change size anymore, you could remove this function and just store self.area = ... in the constructor. Also it is evidently true that the area of a rectangle is a property of that particular rectangle.

And an __or__ method to get the bounding rectangle. You might need this if you want a GUI and update only the region where things changed but still want to do only one update. Then you need to find a rectangular area which includes all objects, which you can then just get by |ing all rectangles.

Your __str__ method can be simplified using map and str.join:

def __str__(self):
    return '\t'.join(map(str, (self.min_x, self.max_x, self.min_y, self.max_y)))

Alternatively, you can use str.format:

def __str__(self):
    return '{self.min_x}\t{self.max_x}\t{self.min_y}\t{self.max_y}'.format(self=self)

The latter slightly more future proof, because you can replace it with this in Python 3.6, using f-strings:

def __str__(self):
    return f'{self.min_x}\t{self.max_x}\t{self.min_y}\t{self.max_y}'

Final code:

class Rectangle:
    def __init__(self, min_x=0, max_x=0, min_y=0, max_y=0):
        self.min_x = min_x
        self.max_x = max_x
        self.min_y = min_y
        self.max_y = max_y

    def is_intersect(self, other):
        if self.min_x > other.max_x or self.max_x < other.min_x:
            return False
        if self.min_y > other.max_y or self.max_y < other.min_y:
            return False
        return True

    def __and__(self, other):
        if not self.is_intersect(other):
            return Rectangle()
        min_x = max(self.min_x, other.min_x)
        max_x = min(self.max_x, other.max_x)
        min_y = max(self.min_y, other.min_y)
        max_y = min(self.max_y, other.max_y)
        return Rectangle(min_x, max_x, min_y, max_y)

    intersect = __and__

    def __or__(self, other):
        min_x = min(self.min_x, other.min_x)
        max_x = max(self.max_x, other.max_x)
        min_y = min(self.min_y, other.min_y)
        max_y = max(self.max_y, other.max_y)
        return Rectangle(min_x, max_x, min_y, max_y)

    union = __or__

    def __str__(self):
        return 'Rectangle({self.min_x},{self.max_x},{self.min_y},{self.max_y})'.format(self=self)

    @property
    def area(self):
        return (self.max_x - self.min_x) * (self.max_y - self.min_y)