Polygon subdivision

[michahell]

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, only the polygon is a rectangle: http://gamedev.stackexchange.com/questions/27055/what-is-an-efficient-packing-algorithm-for-packing-rectangles-into-a-polygon

 

 

I also posted this question on Stack Overflow, so if you want upvotes answer there :

http://stackoverflow.com/questions/19259359/subdividing-a-polygon-into-boxes-of-varying-size

[onefrankguy]

Assuming your Voronoi cells are convex polygons, you should be able to do something like this:

1. Pick a cell

2. Construct two parallel lines through the cell

3. Construct two parallel lines perpendicular to the first two lines where the first two lines intersect the cell

4. You've now inscribed a rectangle in the cell

5. You've also divided the cell into five or fewer pieces

6. Repeat from step 1 for the pieces of the cell that aren't rectangles

7. Stop when the generated rectangles get too small

That'll give you large rectangles in the center of your cells, with smaller rectangles packed around the edges.

[michahell]

Hmm, that's a very nice way to approach this problem indeed, and far easier than i've been finding

 

I will definately use this if i ever get my game big enough to feature cities! I've for now found a different solution,

i changed the concept of cities to towns and i now have a working basic 'town generator'.

 

The 'algorithm' works this way:

 

1. pick a random vertex from all of the voronoi cells

2. check if this vertex has at least 3 outgoing edges that satisfy a length requirement (the edges will become the town streets)

3. designate the random picked vertex as a 'town candidate'.

4. for all 'town candidates', have some requirements to check for and filter for these. (currently i just select randomly for a maximum number of towns :> )

5. populate the town, put houses on each side of the edges (for me this was a shit ton of trigonometry, but still doable apparently haha)

 

Work in progress screenshots: http://d.pr/f/wJxe

 

The working version (no preloading, slow, unoptimized, etc. etc.) can be seen here: http://www.powergeek.nl/proj/mongento/versions/9/

 

 

As for other people running into the same problem: (also on S.O.)

 

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

 

Some more information on these kinds of problems:

 

http://lagrange.ime.usp.br/~lobato/utdc/

http://mathworld.wolfram.com/SquarePacking.html

[Son of Bryce]

I'm not sure if this is even relates, but I've come across this before. Maybe it's helpful:

 

https://code.google.com/p/poly2tri/