What are good algorithms to generate borders / state areas on 2d star maps?

Question

I'm trying to generate a fairly large two-dimensional star map that shows different factions / states, each owning one or more star systems. I'd like to automatically create borders / areas for the factions.

The idea is to essentially go from something like this (the dots represent star systems on a 2d plane, colors are faction affiliations)

to this

Generating maps like this seems like a fairly common requirement, so my actual question is this: Are there standard algorithms for generating state areas as shown? If so, could you point them out to me? If not, can you think of a good algorithm (basic idea or pseudo code are fine)?

The algorithm's performance is not a primary concern to me, so I'd rather have a "prettier" map than a faster-to-generate one. This similar question offers an approach that is probably applicable to my problem, albeit with some "prettification" needed: How to create a map from graph

Let me explain what I mean when I say prettier: At the bottom of the linked question, the asker presents her end result after implementing the accepted answer. My first issue here: The areas for nodes #6, #9 and #12 are very small and oddly shaped. Also, instead of the sharp edges, I would prefer a smoother, curved look.

My own ideas so far, including the respective drawbacks / questions I see with them:

• Generate a "convex hull" polygon for each faction, then expand outwards a bit. Problems: No concave features. Also, how do you deal with overlaps?
• Generate a voronoi graph for the dots, then use the voronoi polygon edges between neighboring systems of different factions as borders. Problem: Large polygons at the map edges - how do I identify and fix those?
• Generate a fixed-size polygon for each dot, union all polygons for a single faction (resulting in one large, potentially complex "faction polygon"). Then do something to reconcile overlapping areas between two factions. Problems: How would I do this exactly? Not exactly a trivial process. What if there is overlap between more than two factions?

Your help is appreciated.

---

Addendum: After thinking about the first two answers and their respective approaches to solving the problem, I've realized that my requirements above are incomplete.

I have to add that the map can have sparsely populated areas, meaning that there may be an isolated star or cluster of stars. I'd like to display each of those clusters with their own contiguous colored area. Something like this:

I realize that this might necessitate a first step which identifies clusters, and then running the actual algorithm for each of the clusters.

Answer 1

I think the Voronoi idea is a good one. Each star becomes a seed point for Voronoi, and then the Voronoi regions show the areas owned by each faction. However, there are some changes that will make it work better:

1. As you mentioned, there are empty areas that shouldn't be assigned to a faction. Voronoi will create large polygons that extend out to areas where the faction shouldn't reach. To fix this, use a blue noise algorithm like poisson disc to fill the unoccupied space with "owned by no one" stars. Blue noise is random but evenly distributed (it might also be useful for generating your star locations).
2. Voronoi produces blocky regions. To produce rounder cells, replace Voronoi's circumcenter calculation with a centroid calculation. I've written a little about this here with some comparison images.
3. Voronoi produces polygons, but you want round areas. At each corner, there are three polygons. When all three are the same faction, you can leave it alone. When two are the same faction, introduce a quadratic bezier curve that shifts the boundary towards the other faction. When all three factions are different, you can either leave the corner alone, or you can introduce three bezier curves to move all of the boundaries away from one another. I'm not sure which looks better.

Here's the output:

I also wrote a page which lets you paint the regions to see what they'd look like.

Answer 2

One of many methods is an influence map. You can search for specific code implementations, but the basic algorithm is fairly simple.

For each faction object (e.g. star system), assign a positive (hot) value. For all other factions' objects assign a negative (cold) value. The magnitude of hot or cold should be based on how much influence you think the object exerts on its surroundings and neighbors. These values do not have to be proportional if you ultimately want to keep a "dmz" between factions.

Use these details to create a temporary grid (e.g. array) that approximates your map's pixels. You can build such a grid to the resolution you desire including 1:1.

Next, use the heat/field transfer equation to iterate and propagate the faction objects' strengths (heat) against the adversaries' objects' strengths (cold) for each neighbor cell in the grid.

Rinse and repeat for each Faction on your map by creating separate faction grids for each.

Finally, interpolate the faction grids together to produce a contour of influence for each faction. Then transfer that grid back onto your pixel map given the resolution that you used for the grid (adding any faction specific colors, etc).

The art in this process is to determine how much influence each object should have and what game elements you use to quantify that value.

As an aside, the products of this method can be used for all kinds of other things, like your ai decision-making.

---

Additional reference: discussion thread on origins of influence mapping.

Answer 3

You should look into Voronoi diagrams. Here is the definition on wikipedia:

In mathematics, a Voronoi diagram is a partitioning of a plane into regions based on distance to points in a specific subset of the plane.

The basic points are usually randomly generated and are often called nodes. In your case, each node could be your stars. That way, the faction associated with the stars can be associated with the voronoi cell surrounding the star and when every cell has been calculated, you join those with the same faction together and you should have a pretty neat border around your stars.

FastNoise library has support for Voronoi Diagrams, so maybe you should look at it.

• Voronoi Diagrams on Wikipedia
• FastNoise library on GitHub

Smoothing of the regions

Keep your stars in a « safe array » and use a copy of it where you actually add more points via interpolation of the nearest neighbors and generate the diagram from those points. It should give you smoother regions.

Other ideas The fortune algorithm is based on a straight line that sweeps the cartesian plane. An interesting idea would be to use a circle to sweep the plane from the center of your galaxy/space instead, maybe that could lead to some interesting shapes too.

Geometry manipulation

Your last idea of combining smaller polygons into bigger ones and then fixing the edges will require advanced spline algorithms to modify the shapes. Not sure if that would make it efficient or good looking. I’m pretty sure that the voronoi diagram with extra tessellation is the way to go as it fixes the edge problem by itself and can even offer some extra data by itself like the distance from the borders (which could be used to determine the zones of conflict between the different factions, the probability of encountering different kinds of ships, etc.)