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)
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.