8
\$\begingroup\$

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)
\$\endgroup\$
  • 2
    \$\begingroup\$ What do you mean by insersec? ;) \$\endgroup\$ – Roland Illig Dec 31 '16 at 8:58
  • 1
    \$\begingroup\$ If you’re using Python 2.7, custom classes should subclass from object; see stackoverflow.com/q/2588628/1558022 for more background. I’d also recommend adding a __repr__ for easy debuggability. \$\endgroup\$ – alexwlchan Jan 1 '17 at 18:49
  • 1
    \$\begingroup\$ @LinMa what I really wanted to ask is: why do you write insersec (2 typos) when the correct spelling is intersect? \$\endgroup\$ – Roland Illig Jan 3 '17 at 7:57
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Peilonrayz Jan 4 '17 at 7:57
  • 2
    \$\begingroup\$ @RolandIllig: A line segment is an ordered pair of numbers, start and end. A rectangle r is a pair of line segments, call them top and left. Two rectangles r1 and r2 overlap iff r1.top overlaps r2.top and r1.left overlaps r2.left. So you only have to solve the problem on line segments. \$\endgroup\$ – Eric Lippert Jan 4 '17 at 21:53
9
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks Graipher, love all of your comments, however have two different options, (1) your implementation of or has issues, suppose two rectangles do not overlap at all, return or of them is unclear what it means (in your implementation, your returned areas of or will contain area not in ether rectangle if they are not overlapping) (2) what is the benefit of making it a property in my problem? \$\endgroup\$ – Lin Ma Jan 3 '17 at 7:52
  • 1
    \$\begingroup\$ @LinMa Yes, __or__ is not a very clear concept. It returns a rectangle which bounds the two rectangles. You would need this if you want a GUI and update only the region where things changed but still want to do o Lynn one update. Then you need to find a rectangular area which includes all objects. You probably don't need it. \$\endgroup\$ – Graipher Jan 3 '17 at 7:54
  • 1
    \$\begingroup\$ @LinMa it is a property for 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, you could remove this function and just store self.area = ... in the constructor. In your particular problem I don't know if this has any advantage. But that is due to the fact that you did not tell us about the problem these Rectangles are supposed to solve. \$\endgroup\$ – Graipher Jan 3 '17 at 8:03
  • \$\begingroup\$ Thanks Graipher, your comments making it clear. Do you think there might be a more efficient solution to check if rectangle overlap? More efficient I mean from algorithm time complexity perspective. \$\endgroup\$ – Lin Ma Jan 4 '17 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.