What You're Looking At

This interactive 3D model generates every permutation of the minimum rectangular tiling for a given orthogonal polygon. You’ll find a fuller description of the model below.

Description

The input for this model can be x-convex, y-convex, both, or neither and may contain any number of orthogonal, polygonal holes. The model outputs every permutation of rectangular tiles that minimally partition the input shape. Tiling refers to the composition of a complex shape from basic building blocks whereas partitioning refers to the decomposition of a complex shape into basic building blocks. In this case, we can use the two terms interchangeably because the building blocks are the same.

To find the minimum partitioning, I adapted a graph-based decomposition algorithm. The first part of this algorithm performs degenerate decomposition and works as follows. Every pair of co-grid concave vertices (vertices having an inner angle of 270° and sharing a horizontal or vertical coordinate) is compiled into a list. The idea here is to construct chords between co-grid vertices that partition the input polygon into non-degenerate subpolygons (i.e., polygons containing no co-grid vertices). L. Ferrari et al. proved that the optimal selection of co-grid pairs is that which maximizes the number of nonintersecting chords.

In practice, this is most easily accomplished by transforming the decomposition problem into a graph partitioning problem. My implementation here uses the NetworkX python package to construct a bipartite graph where nodes represent either horizontal or vertical chords and edges represent intersections. The algorithm then searches for every maximal independent set. Each of these sets contains the same maximum number of disconnected nodes but represents a unique arrangement of non-degenerate subpolygons.

The second part of the algorithm loops through each concave vertex within a maximal set (now non-degenerate by preparation) and further subdivides the polygon by drawing either a horizontal or a vertical chord between that vertex and the polygon’s boundary. This process is sequential, every concave vertex within a single partitioning is visited once. The number of permutations is equal to $2^n$ where $n$ is the number of concave vertices remaining after degenerate decomposition.

At the end, I generate a graph for each partition where nodes represent tiles and edges are drawn between adjacent tiles. To display the partitions in a legible way, I use a greedy coloring algorithm to ensure that no neighboring rectangles are rendered with the same color.

Context

I happened upon this problem while working at a furniture company in Chicago where my role was to help transition the firm from building furniture to building cross-laminated timber (CLT) housing.

While much of my time there was spent working on the manufacturing floor as a woodworker, I also was tasked with coding a parametric model for a CLT housing typology. The specific typology I used was based on a floor-cassette system developed by Paul Mayencourt ,who was consulting on the CLT (non)transition. I began coding the model and got it to a presentable place before the end of my stint at the company. As I continued to work on that CLT model to expand its capabilities, I conceptualized the separate model above as a floorplan designer.

The basic floor-cassette system was designed to be laid out in a simple grid on a rectangular floorplan, which might not project neatly on more complex shapes—an ‘L’ or a building with an interior courtyard. For the sake of this model, I decided that I did not want to compromise on material usage by padding grids nor constrain input dimensions to multiples of a predetermined cassette dimension. As a result, I accepted the possibility of misaligned grids. While there are some creative methods to handle these misalignments with built-ins, windows, or concealing walls, I recognized that the starting point would be to minimize the number of common edges where these methods are employed.

To develop the model presented above, I ultimately had to read and adapt algorithms from papers dealing with image compression and integrated circuit design. In a nod to its original purpose of generating architectural floorplans, I intentionally designed the model's output to block out volumes, allowing partitions to be evaluated from various angles.

How It Works

Input and output data are both handled in Three.js. When the user applies a partitioning to an input shape, the data is processed by Python scripts running on AWS Lambda with layer dependencies. Everything is contained to the Lambda function apart from one call which is made to a Rhino.Compute server hosted on a virtual machine (AWS EC2 instance) to compute input area properties.

Next Steps

I am currently working on integrating this model as a floorplan designer for my own CLT building model.

While researching minimum partitioning, I devised a new minimum $k$ partitioning algorithm. Minimum $k$ partitioning is the extension of the special case above where $k=4$ to cases where $k$ can be any even number of vertices. I still need to test the algorithm, but so far it has outperformed other popular algorithms on time complexity.