- Take a set of points
- Generate the voronoi tiles of the points
- Turn the straight-line edges into something wiggly
- Clip or cut the resulting polygons
Clipping and cutting is necessary because voronoi tiles can extend way beyond the initial points if the tile edges are nearly parallel. I implemented four clipping modes:
- No clipping (so you get the full polygons)
- Include polygons that overlap a given boundary polygon
- Clip polygons to given boundary polygon
- Include only polygons completely inside a boundary polygon
Here's my sample data - some points and a blue polygon for clipping:
The wiggling algorithm here may cause lines to cross and overlap. There's no test for that at the moment.
Clipmode 1 only includes polygons that are partly or wholly inside the clip polygon:
Mode 3 only returns polygons wholly inside the clip polygon:
So there it is. I've not polished up the code yet, but it's pretty short and sweet. Interested? Let me know.
Addendum: I promise I'll bundle the code up shortly, but today I've been making tweaks to produce fake river networks:
I tried various weighting schemes for the MST. Using distance means it uses up the small edges before the large edges, which tends to leave those big gaps that could be mountain ridges.
Other ideas welcome!