Poisson With Boundary

 from Red Blob Games
9 Apr 2023

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 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:

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

Email me , or tweet @redblobgames, or comment: