Note: the /x/ series of posts on my site are mostly unpolished mini posts. The polished version of this will come later, maybe in a few months.
When I think back on my polygon map generator project from 2010, the word I associate most with it is voronoi. I used Voronoi diagrams in two places:
- I selected a nice “blue noise” distribution of points
- I constructed polygons around those points and assigned biomes
The even distribution of points can be implemented in other ways, such as poisson disc sampling. The polygons were the main thing I wanted. I used both the Voronoi polygons and the Delaunay triangulation for different parts of the map generator. The Voronoi polygons and Delaunay triangulations are “duals” of each other. Each Voronoi polygon (white edges, blue vertices) corresponds to one red point; each Delaunay triangle (black edges, red vertices) corresponds to one blue point. I used the red points for biomes, quests, roads; I used the blue points for rivers, ridges, valleys.
Although the parts all connect and correspond, three things were tricky to handle in the map generator:
- The blue points might not be inside the Delaunay triangles.
- Although the red (seed) points are nicely spaced, the blue points are sometimes right on top of each other. When the blue points are close to each other, the Voronoi edges are too short.
- Each Voronoi edge (white) is perpendicular to the corresponding Delaunay edge (black) but they may not actually cross.
Voronoi diagrams offer lots of nice properties. The polygons are convex. The edges are perpendicular to the Delaunay triangle edges. Any point is associated with the closest seed point. However it turns out I didn’t really need these properties for the procedural map generator, and I had to work around the issues I listed above. Are there other irregular polygon divisions that would’ve worked better for me? I wanted to satisfy these constraints:
- The red points must always be inside the polygons. The blue points must always be inside the triangles.
- The black edges must have reasonable length, so the red points will be nicely spaced out. The white edges must also have reasonable length, so the blue points will also be nicely spaced out.
- The white edges and the black edges must cross.
I was pretty happy with the Voronoi+Delaunay combination except for the locations of the blue points. Voronoi starts with the red seed points, constructs the white edges to be perpendicular to the black edges, and then places the blue points where the white edges intersect. If I moved the blue points, I could solve all three of my problems.
Voronoi places the blue points at the circumcenters of the Delaunay triangles. The circumcenters and orthocenters are not guaranteed to be inside the triangles, but incenters and centroids always are. I constructed my own non-Voronoi polygons by placing the blue points at the centroids. The resulting polygons have the same number of vertices and edges as the Voronoi polygons, but the vertices are placed differently. On the left, polygons constructed with Voronoi; on the right, polygons constructed from the Delaunay centroids:
Notice in particular how every blue point is contained within its corresponding triangle, by construction. The blue points are spaced evenly. The white edges and black edges always cross, but aren’t perpendicular. I wasn’t sure whether the polygons would always be convex; AegisToast on Reddit shows that they are.
Here’s how they look at a larger scale, with ~600 points. The voronoi-based polygons look more “boxy” whereas the centroid-based polygons look more “rounder” and “cellular”, but they have less consistent sizes:
I generated some much larger polygon networks too, using ~6000 points. Click to see the large version; I suggest loading both in separate tabs, then flipping back and forth to compare.
I’m pretty happy with this! I think Delaunay centroid polygons will be a better match for my future procedural map generation projects, but I won’t know until I hook up the rest of the map generator to this.
More ideas to try: instead of always using centroids, what if we used centroids only when the circumcenter (from voronoi) falls outside the triangle (idea from FacitiusVir on reddit)? What if we picked a random point inside the triangle?
I’m a novice at math and computational geometry, so I’m only touching the basics here. Other things I found, mostly after writing this blog post:
- After posting this blog entry, I learned that this is called the barycentric dual mesh. The primal mesh is the triangles (red dots, black lines) and the dual mesh is the polygons (blue dots, white lines). Voronoi is the circumcentric dual mesh and what I’m using is the barycenter (centroid) dual mesh. These types of meshes show up in 3d modeling and also in scientific calculations like fluid simulations.
- HOT: Hodge-Optimized Triangulations [PDF] has a nice overview in its introduction, including mentioning a hybrid between barycentric and circumcentric dual meshes. The paper proposes an even better approach that keeps both the red and blue points in good positions.
- This page is about discrete exterior calculus, which is a type of calculus that works on this type of mesh. .
- “Optimal Delaunay triangulations” are Delaunay triangulations with better mesh properties, either by moving vertices around, or by adding Steiner vertices at “bad” points. This might let me skip the Poisson Disc step. These slides have a different algorithm for picking good points based on Delaunay triangulation.
- Centroidal Voronoi tesselations places the seeds for Voronoi in the center of the mass of the Voronoi polygons; I believe this is related to Lloyd’s method for constructing blue noise points.
- Triangulated irregular networks are often used for map representation.
- Pitteway triangulations ensures that the white edges (Voronoi) and black edges (Delaunay) cross
- Gabriel graphs
- Urquhart graphs
- Relative neighborhood graphs
- Plateau’s Laws describe the structure of soap bubbles; also see this discussion on stack exchange.
- Triangles have many different types of center: circumcenter, centroid, incenter, orthocenter, and more. The incenter and centroid are always inside the triangle; I tried both and found the centroid looked a little better for my use. There are at least 13240 different types of triangles centers! Clark Kimberling has been compiling a list.