# Rectangle to irregular polygon list?

This topic is 3032 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.

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

 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]

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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.

1. 1
2. 2
Rutin
21
3. 3
4. 4
5. 5
A4L
14

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633736
• Total Posts
3013603
×