Jump to content
  • Advertisement
Sign in to follow this  
DvDmanDT

Rectangle to irregular polygon list?

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

If you intended to correct an error in the post then please contact us.

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.

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]

Share this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!