2d - Subdividing a polygon into boxes of varying size

I would like to be pointed to information / resources for creating algorithms like the one illustrated on this blog, which is a subdivision of a polygon (in my case a voronoi cell) into several boxes of varying size:

http://procworld.blogspot.nl/2011/07/city-lots.html

In the comments a paper by among others the author of the blog can be found, however the only formula listed is about candidate location suitability:

http://www.groenewegen.de/delft/thesis-final/ProceduralCityLayoutGeneration-Preprint.pdf

Any language will do, but if examples can be given Javascript is preferred (as it is the language i am currently working with)

A similar question is this one: What is an efficient packing algorithm for packing rectangles into a polygon?

Answer

Sorry for the long delay since my comment. I'd been trying to reverse-engineer the ProcWorld example and couldn't work out why the algorithm was making some of the choices it did.

In any case though, here's my best idea so far, using the center block from the ProcWorld example as a guide:

Start by finding an oriented bounding rectangle of the polygon. (For this example it happens to be aligned with the grid, which made these diagrams a bit easier) This rectangle defines the axes for the partition inside (you may want to transform all of your vertices into this new coordinate space to make the math simpler)

Next, split the polygon along one of these axes, from one vertex all the way to the far side. (I'm not sure how this vertex is chosen. Most of the time, it looks like it's the one that gives the longest cut, but not always. It might be chosen to roughly equalize the areas on each side of the cut, or to ensure that the max distance on one side does not exceed a maximum building depth constraint)

For each sub-polygon formed, select another vertex from the original polygon boundary and cut across to the previous cut. (This vertex may be chosen as the one furthest from the previous cut - which I assume here - or again in an area-balancing fashion)

Continue until the remaining polygon is a quadrilateral, or the next cut would exceed a maximum-skinniness constraint (eg. the cut shown in green).

Split the remaining polygons into quadrilaterals by cutting parallel to the previous successful cut.

If cutting at a vertex would result in an excessively skinny building, discard it.

Finally, we have a set of quadrilaterals. Several will be bounded by cuts on three sides - cap them off at their obtuse angle to make them rectangular. For quads that are bounded by cuts on only two edges, find the largest rectangle that fits inside.

If ever the next proposed cut would go outside the polygon (shouldn't happen with Voronoi cells since they're always convex), generate a new oriented bounding box for that sub-polygon and start cutting its remaining boundary vertices as though you were starting from scratch. (That's the best way I can think of to explain how the alignment axis changes in places like the one pictured - I think it's because the algorithm wanted to connect the bottom-right vertex to the bold blue cut, and couldn't because of the concavity in-between)

I hope that may be of some use, even if you don't use this algorithm exactly. Thinking about the problem in terms of cutting rather than filling certainly seems to make it easier to get a clean, tightly-packed result.