How to draw a border line around adjacent shapes?

Question

Algorithms

I have a field of irregular hexagons. Each of which is painted over with one of several colors.
I draw each of them by vertex coordinates.

I need to draw a line that will outline all the hexagons of the same color, standing next to each other. As a result, it should turn out like this:

Tell me the algorithm with which you can implement this.
This is implemented in various strategy games, for example in civilization:

Answer 1

Everything is well described here https://habrahabr.ru/post/144921/
It is not problematic to compose a set of vertices of polygons of the same color.
UPD. The first solution that came to mind:
We take the set of all faces of these hexagons. Next, we go through it and delete everything that lies between the hexagons of the same color. As a result, we have many faces necessary to build the necessary figure.
You can even abstract from hexagons and do this for any shapes.

Answer 2

It is difficult to say something concrete without seeing how exactly the structure describing the field is implemented from the inside.
I will assume that you have the opportunity for any cell to know all six of its neighbors. If such a method exists, then everything is easy.
Start with any one cell.
Create two empty sets - let's call them 'currents' and 'visited'.
In currents, put the cell you start with.
Next, loop while there is at least one cell in currents:
1. Remove the first cell that comes across from currents (hereinafter, I call it the "current cell").
2. For this current cell, find all of its neighbors.
3. For each neighbor:
3.1. If it is the same color as the current one and is not in the visited set, add it to currents
3.2. If it is of a different color, draw a border between this neighbor and the current cell.
4. Add current cell to visited
5. Repeat until currents runs out.
The border has been drawn!

Answer 3

This is a Voronoi diagram, if you were able to implement it in some language, then it should not be difficult for you to color it. In JS , d3js can do this , here is the module code .

Answer 4

Slow, but fairly easy to implement algorithm.
To draw, you will most likely need a "polygon with holes" entity. It should store separately a large outer polygon and a list of hole polygons. The polyline can be stored as a sorted list of vertices. If we consider the hexagons as a regular grid and index all the vertices, then we can subsequently complete the contour by increasing or decreasing the colored area.