Draw random squares in a rectangle

lace.py

from collections import namedtuple
from random import randrange

Point = namedtuple('Point', 'x y')
Part = namedtuple('Part', 'inf sup subpart area')

def mincoord(point, other):
    return Point(min(point.x, other.x), min(point.y, other.y))

def maxcoord(point, other):
    return Point(max(point.x, other.x), max(point.y, other.y))

def rectarea(point, other):
    return max(0, other.x - point.x) * max(0, other.y - point.y)

class Lace:
    def __init__(self, root=None):
        self.root = root

    def punch(self, inf, sup):
        if self.root is None:
            return
        else:
            inf = maxcoord(inf, self.root.inf)
            sup = mincoord(sup, self.root.sup)
            if rectarea(inf, sup):
                self.root = punch(self.root, inf, sup)
                
    def find_random_point(self):
        if self.root is None:
            raise RuntimeError("Empty lace")
        n = randrange(self.root.area)
        return find_point(self.root, n)

def find_point(part, n):
    if part.subpart:
        for p in part.subpart:
            if n < p.area:
                return find_point(p, n)
            n -= p.area
        raise ValueError('Invalid value')
    else:
        w = part.sup.x - part.inf.x
        q, r = divmod(n, w)
        return Point(part.inf.x + r, part.inf.y + q)
    
def punch(part, inf, sup):
    res = []
    if part.subpart:
        for p in part.subpart:
            i, s = maxcoord(inf, p.inf), mincoord(sup, p.sup)
            if rectarea(i, s):
                q = punch(p, i, s)
                if q:
                    res.append(q)
            else:
                res.append(p)
    else: # part is a rectangle
        ix, iy = inf
        sx, sy = sup
        if part.inf.x < ix:
            p = Point(ix, part.sup.y)
            r = rectarea(part.inf, p)
            if r:
                res.append(Part(part.inf, p, None, r))
        if part.inf.y < iy:
            p = Point(ix, part.inf.y)
            q = Point(part.sup.x, iy)
            r = rectarea(p, q)
            if r:
                res.append(Part(p, q, None, r))
        if sx < part.sup.x:
            p = Point(sx, iy)
            q = Point(part.sup.x, part.sup.y)
            r = rectarea(p, q)
            if r:
                res.append(Part(p, q, None, r))
        if sy < part.sup.y:
            p = Point(ix, sy)
            q = Point(sx, part.sup.y)
            r = rectarea(p, q)
            if r:
                res.append(Part(p, q, None, r))
    if not res:
        return None
    elif len(res) == 1:
        return res[0]
    else:
        ix = min(r.inf.x for r in res)
        iy = min(r.inf.y for r in res)
        sx = max(r.sup.x for r in res)
        sy = max(r.sup.y for r in res)
        a = sum(r.area for r in res)
        return Part(
            Point(ix, iy), Point(sx, sy), tuple(res), a)

def main():
    r = 3
    W, H = 10, 15
    p0, q0 = Point(0, 0), Point(W - r + 1, H - r + 1)
    lace = Lace(Part(p0, q0, None, rectarea(p0, q0)))
    irect = []
    for i in range(10):
        try:
            p = lace.find_random_point()
        except RuntimeError:
            break
        print(p)
        lace.punch(Point(p.x-r, p.y-r), Point(p.x + r + 1, p.y + r + 1))
        irect.append((p, Point(p.x+r, p.y+r)))
    draw_rects(Point(0, 0), Point(W, H), irect)
    
def draw_rects(p0, q0, irect):
    import matplotlib.pyplot as plt
    import matplotlib.patches as patches
    #import numpy as np

    # Create figure and axes
    fig,ax = plt.subplots(1)
    
    for p, q in irect:
        # Create a Rectangle patch
        w, h = q.x - p.x, q.y - p.y
        print(p, w, h)
        rect = patches.Rectangle(
            (p.x, p.y), w, h,
            linewidth=1, edgecolor='black',facecolor='none')

        # Add the patch to the Axes
        ax.add_patch(rect)
    ax.set(xlim=(p0.x, q0.x), ylim=(p0.y, q0.y), aspect='equal')
    plt.savefig('rect.pdf')
    # plt.show()

if __name__ == '__main__':
    main()