I was intrigued by this question on stackoverflow[1] about creating blobby-looking regions based on points. I thought it might work well with the cellular structure I’ve been playing with[2]. (I’m actually working on a tutorial on this topic right now, so this question was right up my alley.) These cells are related to Voronoi, but look much rounder. Voronoi uses the circumcenter of the Delaunay triangles. These cells use the centroid instead.
Click and drag to change the color of a region. (Mouse tracking isn’t exact for this demo, sorry)
Chaikin’s Algorithm#
For the curves, the idea is to start with a convex polygon and change the sharp corners to curves. First find the midpoints of each edge. Then for each segment between the midpoints build a quadratic bezier curve using the original corner as the control point. This is called Chaikin’s Algorithm[3]:
In my problem, I don’t want to turn every section into a curve. I only want the curves in some situations. I draw one wedge at a time from the polygon on the left (marked with ), and consider these four cases:
Compare the owners of the neighboring two regions with the current region (owned by A):
- Case 1: The two neighbors are both owned by us. Draw no border, and use a regular polygon fill.
- Case 2a: The two neighbors have the same owner B, but not owned by us. Draw a curve, and use a curved region fill. This leaves a gap to be filled in with color B.
- Case 2b: One of the neighbors is owned by us, but the other is owned by B. Draw no border, and use a regular polygon fill. The border line and a gap will be handled when drawing region B.
- Case 3: The neighbors aren’t owned by us, and they have different owners B and C. Draw a border with straight lines, and use a regular polygon fill. This will end up drawing each border twice.
I think this curve drawing logic is a little more convoluted than it should be, and I haven’t tested all the cases. I’m not sure what the best thing to do is when there are three different owners meeting at a point. I used a different rule for the demo at the top of the page — I leave a curved gap. On this project I made the curved borders thick enough that they covered the gap. Oskar Stalberg (Bad North) recommends focusing the logic on the triangles formed around each vertex. That triangle can be owned by one of the three neighboring polygons.
Cool: Chaikin’s son has an interactive post about Chaikin’s curve algorithm[4]. Also see Ortho-tiles[5].
Source is in rounded-cell-painter.js but it’s relying on my dual mesh library to calculate the cells, so it’s probably not directly useful.