estimates and plots parquet for a given room plan

parquet.py

import itertools
import matplotlib.pyplot as plt
from descartes.patch import PolygonPatch
from shapely.geometry import Polygon
from shapely import affinity, ops

#room = Polygon([[0, 0], [5, 0], [5, 5], [10, 5], [10, 10], [0, 10]])
room = Polygon([[0, 0], [4, 0], [4, 4], [0, 4]])

board_width = 2.2
board_height = 0.18
start_pos = [0, 0]
offset = 0.4
board = Polygon([[0, 0], [board_width, 0], [board_width, board_height], [0, board_height]])

for offset in [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.8, 0.9, 1.0, 1.1]:
    epsilon = 1e-4
    next_start_pos = start_pos[:]
    row = 0
    boards = []
    while True:
        fit = False
        pos = next_start_pos[:]
        while True:
            pos[0] -= board_width
            new_board = affinity.translate(board, pos[0], pos[1])
            if new_board.intersection(room).area < epsilon:
                break
            fit = True
            boards.append(pos[:])
        pos = next_start_pos[:]
        while True:
            new_board = affinity.translate(board, pos[0], pos[1])
            if new_board.intersection(room).area < epsilon:
                break
            fit = True
            boards.append(pos[:])
            pos[0] += board_width
        if not fit:
            break
        row += 1
        next_start_pos[0] = start_pos[0] + (offset * row) % board_width
        next_start_pos[1] += board_height

    numbers = []
    parts = []
    for b in boards:
        new_board = affinity.translate(board, b[0], b[1])
        number_parts = []
        for r in ops.split(new_board, room.boundary):
            inter = r.intersection(room).area
            if r.intersection(room).area > epsilon:
                centroid = r.centroid
                number_parts.append(centroid)
                if inter < board.area:
                    r = affinity.translate(r, -b[0], -b[1])
                    parts.append((r, centroid, number_parts))
        numbers.append(number_parts)

    rest = 0
    while True:
        min_area = board.area
        min_pair = None
        for a, b in itertools.combinations(parts, 2):
            intersection = a[0].intersection(b[0])
            if intersection.area > epsilon:
                continue
            if intersection.area < min_area:
                min_area = intersection.area
                min_pair = (a, b)
        if min_pair is None:
            break
        parts.remove(min_pair[0])
        parts.remove(min_pair[1])
        min_pair[0][2].append(min_pair[1][1])
        min_pair[1][2].remove(min_pair[1][1])
        rest += board.area - min_pair[0][0].area - min_pair[1][0].area
    numbers = [n for n in numbers if len(n) > 0]
    for p in parts:
        rest += board.area - p[0].area
    print(offset, rest)

"""
fig, ax = plt.subplots()
ax.add_patch(PolygonPatch(room, fc='red'))
for b in boards:
    new_board = affinity.translate(board, b[0], b[1])
    ax.add_patch(PolygonPatch(new_board, fc='blue', alpha=0.3))
for i, cs in enumerate(numbers):
    for c in cs:
        ax.text(c.x, c.y, str(i))
plt.autoscale()
plt.show()
"""