Intersection and difference of two rectangles

Question

Searching the internet has not given a satisfactory solution for the following problem. Given a class Rectangle defined as the following:

class Rectangle:

    def __init__(self, x1, y1, x2, y2):
        if x1 > x2 or y1 > y2:
            raise ValueError('coordinates are invalid')
        self.x1, self.y1, self.x2, self.y2 = x1, y1, x2, y2

    @property
    def width(self):
        return self.x2 - self.x1

    @property
    def height(self):
        return self.y2 - self.y1

    def bounds(self, other):
        return Rectangle(min(self.x1, other.x1), min(self.y1, other.y1),
                         max(self.x2, other.x2), max(self.y2, other.y2))

    def intersect(self, other):
        return self.x1 < other.x2 and self.x2 > other.x1 and \
               self.y1 < other.y2 and self.y2 > other.y1

How would you create a method to get the intersection and a generator to get the difference of two rectangles? Presumably, a more complete implementation of the following methods are needed, but it is not clear to me what should be written.

def __and__(self, other):
    if self.intersect(other):
        # return a new rectangle that provides
        # the intersection between self and other
    return None

def __sub__(self, other):
    take_away = self & other
    if take_away is None:
        return self
    if take_away is self:
        return None
    return self.get_partitions(take_away)

def get_partitions(self, take_away):
    # yield 1 or 3 rectangles that are not part of take_away
    # alternative:
    # yield 1 or 2 overlapping rectangles not part of take_away

Does anyone have an elegant implementation for these methods? My hope is to avoid writing code for every conceivable case that might be encountered.

Answer 1

Here is a complete solution for you.
Methods in the class are ordered illogically so that the important parts are visible without scrolling.

import itertools

class Rectangle:
    def intersection(self, other):
        a, b = self, other
        x1 = max(min(a.x1, a.x2), min(b.x1, b.x2))
        y1 = max(min(a.y1, a.y2), min(b.y1, b.y2))
        x2 = min(max(a.x1, a.x2), max(b.x1, b.x2))
        y2 = min(max(a.y1, a.y2), max(b.y1, b.y2))
        if x1<x2 and y1<y2:
            return type(self)(x1, y1, x2, y2)
    __and__ = intersection

    def difference(self, other):
        inter = self&other
        if not inter:
            yield self
            return
        xs = {self.x1, self.x2}
        ys = {self.y1, self.y2}
        if self.x1<other.x1<self.x2: xs.add(other.x1)
        if self.x1<other.x2<self.x2: xs.add(other.x2)
        if self.y1<other.y1<self.y2: ys.add(other.y1)
        if self.y1<other.y2<self.y2: ys.add(other.y2)
        for (x1, x2), (y1, y2) in itertools.product(
            pairwise(sorted(xs)), pairwise(sorted(ys))
        ):
            rect = type(self)(x1, y1, x2, y2)
            if rect!=inter:
                yield rect
    __sub__ = difference

    def __init__(self, x1, y1, x2, y2):
        if x1>x2 or y1>y2:
            raise ValueError("Coordinates are invalid")
        self.x1, self.y1, self.x2, self.y2 = x1, y1, x2, y2

    def __iter__(self):
        yield self.x1
        yield self.y1
        yield self.x2
        yield self.y2

    def __eq__(self, other):
        return isinstance(other, Rectangle) and tuple(self)==tuple(other)
    def __ne__(self, other):
        return not (self==other)

    def __repr__(self):
        return type(self).__name__+repr(tuple(self))


def pairwise(iterable):
    # https://docs.python.org/dev/library/itertools.html#recipes
    a, b = itertools.tee(iterable)
    next(b, None)
    return zip(a, b)


# 1.
a = Rectangle(0, 0, 1, 1)
b = Rectangle(0.5, 0.5, 1.5, 1.5)
print(a&b)
# Rectangle(0.5, 0.5, 1, 1)
print(list(a-b))
# [Rectangle(0, 0, 0.5, 0.5), Rectangle(0, 0.5, 0.5, 1), Rectangle(0.5, 0, 1, 0.5)]

# 2.
b = Rectangle(0.25, 0.25, 1.25, 0.75)
print(a&b)
# Rectangle(0.25, 0.25, 1, 0.75)
print(list(a-b))
# [Rectangle(0, 0, 0.25, 0.25), Rectangle(0, 0.25, 0.25, 0.75), Rectangle(0, 0.75, 0.25, 1), Rectangle(0.25, 0, 1, 0.25), Rectangle(0.25, 0.75, 1, 1)]

# 3.
b = Rectangle(0.25, 0.25, 0.75, 0.75)
print(a&b)
# Rectangle(0.25, 0.25, 0.75, 0.75)
print(list(a-b))
# [Rectangle(0, 0, 0.25, 0.25), Rectangle(0, 0.25, 0.25, 0.75), Rectangle(0, 0.75, 0.25, 1), Rectangle(0.25, 0, 0.75, 0.25), Rectangle(0.25, 0.75, 0.75, 1), Rectangle(0.75, 0, 1, 0.25), Rectangle(0.75, 0.25, 1, 0.75), Rectangle(0.75, 0.75, 1, 1)]

# 4.
b = Rectangle(5, 5, 10, 10)
print(a&b)
# None
print(list(a-b))
# [Rectangle(0, 0, 1, 1)]

# 5.
b = Rectangle(-5, -5, 10, 10)
print(a&b)
# Rectangle(0, 0, 1, 1)
print(list(a-b))
# []

Intersection is based on SFML's implementation. It is proven correct and is not interesting to explain.

The difference, however, was a lot of fun to make.

Consider the following cases and compare them with corresponding examples at the bottom of the code. The method may return from 0 to 8 rectangles!

It works by finding all the vertical (xs) and horizontal (ys) lines that go through our rectangle (all the black and grey lines on the picture).

The coordinate sets are turned into sorted lists and taken pairwise ([a, b, c] becomes [(a, b), (b, c)]).

The product of such horizontal and vertical segments gives us all the rectangles that we divided the original one into by these lines.

All that remains is to yield all of these rectangles except the intersection.

Answer 2

Oleh Prypin was extremely helpful with the provided code. The following is a refactored version of the same.

from itertools import product, tee

def test():
    print('Example 1:')
    a = Rectangle(1, 1, 5, 5)
    b = Rectangle(3, 3, 7, 7)
    print(a & b)
    print(list(a - b))
    ##########################
    print('Example 2:')
    b = Rectangle(3, 2, 7, 4)
    print(a & b)
    print(list(a - b))
    ##########################
    print('Example 3:')
    b = Rectangle(2, 2, 4, 4)
    print(a & b)
    print(list(a - b))
    ##########################
    print('Example 4:')
    b = Rectangle(6, 2, 10, 6)
    print(a & b)
    print(list(a - b))
    ##########################
    print('Example 5:')
    b = Rectangle(0, 0, 6, 6)
    print(a & b)
    print(list(a - b))
    ##########################
    print('Example 6:')
    b = Rectangle(2, 0, 4, 6)
    print(a & b)
    print(list(a - b))

def pairwise(iterable):
    "s -> (s0, s1), (s1, s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

class Rectangle:

    __slots__ = '__x1', '__y1', '__x2', '__y2'

    def __init__(self, x1, y1, x2, y2):
        self.__setstate__((min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2)))

    def __repr__(self):
        return '{}({})'.format(type(self).__name__, ', '.join(map(repr, self)))

    def __eq__(self, other):
        return self.data == other.data

    def __ne__(self, other):
        return self.data != other.data

    def __hash__(self):
        return hash(self.data)

    def __len__(self):
        return 4

    def __getitem__(self, key):
        return self.data[key]

    def __iter__(self):
        return iter(self.data)

    def __and__(self, other):
        x1, y1, x2, y2 = max(self.x1, other.x1), max(self.y1, other.y1), \
                         min(self.x2, other.x2), min(self.y2, other.y2)
        if x1 < x2 and y1 < y2:
            return type(self)(x1, y1, x2, y2)

    def __sub__(self, other):
        intersection = self & other
        if intersection is None:
            yield self
        else:
            x, y = {self.x1, self.x2}, {self.y1, self.y2}
            if self.x1 < other.x1 < self.x2:
                x.add(other.x1)
            if self.y1 < other.y1 < self.y2:
                y.add(other.y1)
            if self.x1 < other.x2 < self.x2:
                x.add(other.x2)
            if self.y1 < other.y2 < self.y2:
                y.add(other.y2)
            for (x1, x2), (y1, y2) in product(pairwise(sorted(x)),
                                              pairwise(sorted(y))):
                instance = type(self)(x1, y1, x2, y2)
                if instance != intersection:
                    yield instance

    def __getstate__(self):
        return self.x1, self.y1, self.x2, self.y2

    def __setstate__(self, state):
        self.__x1, self.__y1, self.__x2, self.__y2 = state

    @property
    def x1(self):
        return self.__x1

    @property
    def y1(self):
        return self.__y1

    @property
    def x2(self):
        return self.__x2

    @property
    def y2(self):
        return self.__y2

    @property
    def width(self):
        return self.x2 - self.x1

    @property
    def height(self):
        return self.y2 - self.y1

    intersection = __and__

    difference = __sub__

    data = property(__getstate__)

if __name__ == '__main__':
    test()

Answer 3

For the complete program the Rectangle class was used in and as a practical example of its usage:

# The robots have requested your help setting up a new base on the
# island. They need you to define the visibility of a building from the
# southern edge of the base. To help you out, you have been given a map
# of the buildings in the complex. The map is an orthogonal projection
# of each of the buildings onto a horizontal plane. It is oriented on a
# rectangular coordinate system so that the positive x-axis points east
# and the positive y-axis points north. No two buildings in the map
# overlap or touch. Each of the buildings have perfectly rectangular
# sides and are aligned from north to south and from east to west. The
# map is a list of buildings. Every building is presented as the list
# with coordinate of south-west corner, coordinate of north-east corner
# and height - [Xsw, Ysw, Xne, Yne, height]. We need to determinate how
# many of the buildings are visible from the area just south of the base
# (excluding the angle of vision, just using projection.) See the
# illustration below.

# Input: Building coordinates and heights as a list of lists. The
# coordinates are integers. The heights are integers or floats.

# Output:The quantity of visible buildings as an integer.

# Example:
# checkio([
#     [1, 1, 4, 5, 3.5],
#     [2, 6, 4, 8, 5],
#     [5, 1, 9, 3, 6],
#     [5, 5, 6, 6, 8],
#     [7, 4, 10, 6, 4],
#     [5, 7, 10, 8, 3]
# ]) == 5 #"First"
# checkio([
#     [1, 1, 11, 2, 2],
#     [2, 3, 10, 4, 1],
#     [3, 5, 9, 6, 3],
#     [4, 7, 8, 8, 2]
# ]) == 2 #"Second"
# assert checkio([
#     [1, 1, 3, 3, 6],
#     [5, 1, 7, 3, 6],
#     [9, 1, 11, 3, 6],
#     [1, 4, 3, 6, 6],
#     [5, 4, 7, 6, 6],
#     [9, 4, 11, 6, 6],
#     [1, 7, 11, 8, 3.25]
# ]) == 4 #"Third"

# How it is used: This concept is useful for image recognition systems
# and graphical systems. When rendering of 3D model you should determine
# the visibility of the surfaces. This concept also can be applied in
# architecture and city planning, allowing you to plan out which sides
# of a building will receive sunlight, or if a building will block
# natural light in another building.

# Precondition: 0 < |buildings| < 10> 10
# ∀ x ∈ coordinate : x is an integer; 0 ≤ x ≤10
# ∀ h ∈ heights : x is an integer or a float; 0 < h ≤20

################################################################################

from itertools import combinations, product, starmap, tee
from pprint import pprint
from random import randint

################################################################################

TESTS = {
    "0. Basics": [
        #First
        {
            "input":
                [
                    [1, 1, 4, 5, 3.5],
                    [2, 6, 4, 8, 5],
                    [5, 1, 9, 3, 6],
                    [5, 5, 6, 6, 8],
                    [7, 4, 10, 6, 4],
                    [5, 7, 10, 8, 3]
                ],
            "answer": 5,
            "explanation": [5, 1, 3, 4, 0, 2]
        },
        #Second
        {
            "input":
                [
                    [1, 1, 11, 2, 2],
                    [2, 3, 10, 4, 1],
                    [3, 5, 9, 6, 3],
                    [4, 7, 8, 8, 2]
                ],
            "answer": 2
        },
        #Third
        {
            "input":
                [
                    [1, 1, 3, 3, 6],
                    [5, 1, 7, 3, 6],
                    [9, 1, 11, 3, 6],
                    [1, 4, 3, 6, 6],
                    [5, 4, 7, 6, 6],
                    [9, 4, 11, 6, 6],
                    [1, 7, 11, 8, 3.25]
                ],
            "answer": 4
        },
        #Alone
        {
            "input":
                [
                    [0, 0, 1, 1, 10]
                ],
            "answer": 1
        },
        #Shadow
        {
            "input":
                [
                    [2, 2, 3, 3, 4],
                    [2, 5, 3, 6, 4]
                ],
            "answer": 1
        },
    ],
    "1. Extra": [
        #H1
        {
            "input":
                [
                    [1, 1, 3, 3, 20],
                    [3, 4, 5, 6, 10],
                    [5, 1, 7, 3, 20],
                    [1, 7, 7, 9, 20]
                ],
            "answer": 4
        },
        #H2
        {
            "input":
                [
                    [1, 1, 3, 3, 20],
                    [3, 4, 5, 6, 20],
                    [5, 1, 7, 3, 20],
                    [1, 7, 7, 9, 20]

                ],
            "answer": 3
        },
        #H3
        {
            "input":
                [
                    [0, 1, 1, 2, 2.5],
                    [0, 3, 1, 4, 3.5],
                    [0, 5, 1, 6, 1.5],
                    [3, 0, 4, 2, 30],
                    [5, 0, 6, 2, 2],
                    [7, 0, 8, 2, 2],
                    [4, 3, 8, 4, 2],
                    [4, 5, 5, 6, 1],
                    [7, 5, 8, 6, 3]
                ],
            "answer": 7
        },
        #H4
        {
            "input":
                [
                    [0, 0, 10, 1, 10],
                    [3, 3, 4, 4, 1],
                    [5, 5, 6, 6, 1],
                    [7, 7, 8, 8, 1]
                ],
            "answer": 1
        },
    ],
    "2. Random": [
        #Half-Random
        {
            "input":
                [
                    [0, 0, 10, 1, 10],
                    [3, 3, 4, 4, randint(1, 9)],
                    [5, 5, 6, 6, randint(1, 9)],
                ],
            "answer": 1
        },

        #Half-Random
        {
            "input":
                [
                    [1, 1, 2, 2, 1],
                    [randint(3, 5), randint(3, 5), randint(6, 8), randint(6, 8), 1]
                ],
            "answer": 2
        },
    ]
}

################################################################################

def test():
    for category, tests in sorted(TESTS.items()):
        for test in tests:
            i, a = test['input'], test['answer']
            o = checkio(i)
            if o != a:
                print('Category:', category)
                print('  Input:')
                pprint(i, indent=8)
                print('  Output:', o)
                print('  Answer:', a)

def checkio(buildings):
    buildings = sorted(starmap(Building, buildings), key=lambda b: b.z)
    for a, b in combinations(buildings, 2):
        if a.seen:
            a.cover(b)
    return sum(b.seen for b in buildings)

################################################################################

class Building:

    def __init__(self, x1, y1, x2, y2, height):
        self.rect = [Rectangle(x1, 0, x2, height)]
        self.z = min(y1, y2)

    def __str__(self):
        return 'Z = {}; {}'.format(self.z, self.rect)

    def cover(self, other):
        for s in self.rect:
            other.rect = list(flatten(o - s for o in other.rect))

    @property
    def seen(self):
        return bool(self.rect)

def flatten(iterable):
    if isinstance(iterable, Rectangle):
        raise TypeError()
    for item in iterable:
        try:
            yield from flatten(item)
        except TypeError:
            yield item

################################################################################

class Rectangle:

    __slots__ = '__x1', '__y1', '__x2', '__y2'

    def __init__(self, x1, y1, x2, y2):
        self.__setstate__((min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2)))

    def __repr__(self):
        return '{}({})'.format(type(self).__name__, ', '.join(map(repr, self)))

    def __eq__(self, other):
        return self.data == other.data

    def __ne__(self, other):
        return self.data != other.data

    def __hash__(self):
        return hash(self.data)

    def __len__(self):
        return 4

    def __getitem__(self, key):
        return self.data[key]

    def __iter__(self):
        return iter(self.data)

    def __and__(self, other):
        x1, y1, x2, y2 = max(self.x1, other.x1), max(self.y1, other.y1), \
                         min(self.x2, other.x2), min(self.y2, other.y2)
        if x1 < x2 and y1 < y2:
            return type(self)(x1, y1, x2, y2)

    def __sub__(self, other):
        intersection = self & other
        if intersection is None:
            yield self
        else:
            x, y = {self.x1, self.x2}, {self.y1, self.y2}
            if self.x1 < other.x1 < self.x2:
                x.add(other.x1)
            if self.y1 < other.y1 < self.y2:
                y.add(other.y1)
            if self.x1 < other.x2 < self.x2:
                x.add(other.x2)
            if self.y1 < other.y2 < self.y2:
                y.add(other.y2)
            for (x1, x2), (y1, y2) in product(pairwise(sorted(x)),
                                              pairwise(sorted(y))):
                instance = type(self)(x1, y1, x2, y2)
                if instance != intersection:
                    yield instance

    def __getstate__(self):
        return self.x1, self.y1, self.x2, self.y2

    def __setstate__(self, state):
        self.__x1, self.__y1, self.__x2, self.__y2 = state

    @property
    def x1(self):
        return self.__x1

    @property
    def y1(self):
        return self.__y1

    @property
    def x2(self):
        return self.__x2

    @property
    def y2(self):
        return self.__y2

    @property
    def width(self):
        return self.x2 - self.x1

    @property
    def height(self):
        return self.y2 - self.y1

    intersection = __and__

    difference = __sub__

    data = property(__getstate__)

def pairwise(iterable):
    "s -> (s0, s1), (s1, s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

################################################################################

if __name__ == '__main__':
    test()