Hi everyone!

Say I have this rectangle with a size of say 4096x1024 length units, how can I split this into a list of polygons? This is for random map generation. I tried googling for "cell generation" and "cell algorithms" but have so far come up empty.

I want to split the map into n (doesn't have to be exact) polygons with different sizes, shapes, number of edges and number of neighbours. I also want some limits on sizes and angles.

Any ideas? Google keywords? Articles/tutorials?

I'm posting this in the Math forum since I'm guessing this will be quite math-intensive.

[Edit] Polyons does not have to be convex, in fact, I'm not sure I want them to be.

The algorithm doesn't have to be fast, if possible, I want it to run at load-time, but I'm also ok with offline generation.

My idea is to place tons of points/vertices and then try to connect them somehow.

[Edited by - DvDmanDT on August 26, 2010 8:38:54 PM]

Voronoi Regions? You can generate them by placing N points into the rectangle then running the algorithm. They'll be convex. However you can generate more regions with more points then randomly remove edges to generate more random regions.

I have a similar suggestion: Compute the Delaunay triangulation of a set of random points and join some triangles with adjacent triangles to form more complex polygons. Make sure to pick some points along the edges of the rectangle so you don't end up with very long skinny triangles at the edges.

Thanks alot! Those Voronoi things look great, I think that's pretty much what I'm looking for. Now I just have to implement it too.