Friday, May 12, 2017

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:


Boundig Box


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)



First Cut


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)


Second Order Cuts


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)


Cut that's too skinny Keep Cutting


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


Quadrilateralifying


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.


Tadah! Rectangles! Partition Alone



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.


weird case - change of axes


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.


No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...