For my map generation and some art projects, I want to scatter points around and then run Delaunay/Voronoi on them. Sometimes I want to add some boundary points to surround the scattered points.
I had made a boundary point function for mapgen2 but I had a feeling it had some issues. I reused it for mapgen4 and I still had that feeling. So I decided to look at it more closely:
What don't I like?
- The convex hull clips the corner. I would prefer the convex hull to be a square.
- It only works on square boundaries.
- The triangles along the boundary are smaller than the triangles in the interior.
- The triangles at the corners are even smaller than the triangles along the boundary. They end up too narrow.
The regions usually look ok but occasionally are misshapen.
One thing the old function did right is that it made the boundary slightly convex. What happens if were concave instead?
It's hard to tell what's going on with those thick lines. Let's look close up:
The problem is that the convex hull is … convex. If the points are concave, there have to be lots of narrow triangles to fill in the space to make the hull convex. That leads to lots of weirdly shaped regions:
If they're exactly flat then I might get some of those. To make sure I don't, I make it slightly convex.
I wrote a new boundary point function in 2023 that gives me the things I wanted:
[X]convex - no narrow triangles at the boundary → fixed by generating at 0, 1, 2, 3, …, N-1 instead of 0.5, 1.5, 2.5, 3.5, …, N-0.5[X]no duplicate points → fixed by stopping at N-1 instead of N, and reversing the direction on the south and west sides[X]even spacing at corners → fixed by having one corner point (at 0) instead of two (at 0.5, N-0.5)[X]spacing matches interior points → fixed by changing the spacing to √2 times the poisson min-spacing[X]works on non-square boundaries → fixed by generating horizontal and vertical points in separate loops
Sometimes in the corners a white edge will be marked solid even though it looks like it should be ghost. The reason is that the solid/ghost assignment is based on black edges not white edges. We could avoid these issues by making sure there's a non-boundary point near the corner boundary points. I haven't implemented that.
There's one remaining thing that I'd like but can't easily have, and I'm not even sure would help. I'd like the boundary points to be outside the bounding rectangle. That way none of them show up in the visible map. However, because of the way the Poisson Disc algorithm works, it needs all the points to be inside the bounding rectangle. So I ended up placing these points just barely inside the bounding rectangle.
One additional variant is to have a double boundary. In the previous diagram there were faint triangles connecting the boundary points (blue) to the ghost region (purple). But it might be useful to make those into actual boundary points too.
Although the triangle mesh fits a rectangle, the voronoi regions are polygons that don't fit a rectangle:
We can alter those polygons by clipping the blue points to a rectangle:
Source for diagrams: poisson-with-boundary.js