Territory outline

from Red Blob Games
02 Nov 2017

In a polygon mesh where each polygon represents a map region, it is sometimes useful to paint an overlay showing some properties of the regions. For example, here I want to show which empire controls each region.

This is roughly the same approach as on this page, but for polygons instead of hexagons, but the algorithms are a little more complicated:

  1. Identify the boundaries. Visit all edges between polygons. Whenever you find an edge that has different owners for the two polygons, try to make a loop. As you follow the edge, choose one of the two successor edges each step. Only one of the two will share exactly one owner with the current edge, so follow that one. Keep going until you get back to the first edge. This forms a loop. There can be “holes” from smaller loops inside the big one; these holes will go in the opposite direction (counterclockwise instead of clockwise).
  2. Draw the boundaries. I’m using a clip-region and a blurry line. This keeps the blurry part inside the empire.
  3. Choose a color for each empire. The colors are chosen from the Lab color space. It’s non-rectangular but I picked evenly spaced points from a grid that overlapped with the valid colors from the space.

Code is here but it’s quick & dirty and won’t be easy to read.

Email me at , or tweet to @redblobgames, or post a public comment: