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?

• Comprehensive answer here: stackoverflow.com/questions/5919298/… Oct 11, 2013 at 2:01
• Interesting problem, too, but not the same / my problem :) Oct 12, 2013 at 16:26

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.

I have solved my problem in a different way. As i was looking for my problem, it turned out to be a fairly complex one, both measured in difficulty to implement as algorithm, as algorithm complexity.

If anyone is having a similar problem, these problems are classified as 'packing problems' in general, with specific problems like the 'pallet loading problem'.

The problem i was interested in, is illustrated at the bottom of this page:

https://www.ime.usp.br/~egbirgin/packing/

and a paper about this problem, with algorithm descriptions of how to solve the packing problem for convex polygons and curved shapes:

http://www.ime.usp.br/~egbirgin/publications/bmnr.pdf

• Are you still looking for suggestions? It looks like the links in this answer are about packing a container with shapes of pre-defined sizes (with gaps as necessary), whereas the links in your question are about subdividing the container into mostly-rectangular shapes of arbitrary size, with no gaps. The latter problem seems easier, and might permit different kinds of solutions. Dec 11, 2013 at 17:57
• Hi, you are right, that is what i tried to tell in my own answer by saying "i have solved my problem in a different way" - further on i say that these problems are classified as packing problems which is incorrect, but apparently - i don't remember why i needed it haha - I went with a packing problem solution. Yes, i am still interested in solutions for my original problem! And I would still very much like to know which approaches there are. Even more so since you say that the problem seems to be easier than packing problems! Dec 13, 2013 at 21:25
• Cool. Quick question about constraints then: in the ProcWorld example, all rectangles are required to have some "frontage" - one side is always an edge of the polygon, so there's never a fully-internal rectangle. Do you need the same behaviour? Also, do you have any constraints on the min/max size of the rectangles, or how skinny their aspect ratio can get? Dec 14, 2013 at 18:06
• @DMGregory Hmm, good question. I'd indeed like them to not have an internal rectangle, i.e. all buildings should be accessible by road (that would make sense). Also, they can be roughly square or fully squared (either of last two images of the procworld example are nice). I do not have min max constraints or 'skinnyness' preferences, it would be cool if those could be parameterized though! Dec 29, 2013 at 5:07