michahell Posted October 10, 2013 Share Posted October 10, 2013 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.htmlIn 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.pdfAny 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 Quote Link to comment Share on other sites More sharing options...

onefrankguy Posted October 12, 2013 Share Posted October 12, 2013 Assuming your Voronoi cells are convex polygons, you should be able to do something like this:1. Pick a cell2. Construct two parallel lines through the cell3. Construct two parallel lines perpendicular to the first two lines where the first two lines intersect the cell4. You've now inscribed a rectangle in the cell5. You've also divided the cell into five or fewer pieces6. Repeat from step 1 for the pieces of the cell that aren't rectangles7. Stop when the generated rectangles get too smallThat'll give you large rectangles in the center of your cells, with smaller rectangles packed around the edges. Quote Link to comment Share on other sites More sharing options...

michahell Posted October 12, 2013 Author Share Posted October 12, 2013 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 cells2. 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 Quote Link to comment Share on other sites More sharing options...

Son of Bryce Posted October 21, 2013 Share Posted October 21, 2013 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/ Quote Link to comment Share on other sites More sharing options...

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Note:Your post will require moderator approval before it will be visible.