Map coloring algorithm

[MiklerGM]

Develop or extend existing algorithm suitable for assigning color id to a PoliticalEntity (PE).

• Color assigned to PE can not be changed during it's existence.
• All neighbors must have different colors.
• Number of different colors for each level can be limited by reasonable amount

PE is an organization that has claimed some land in special time period
PoliticalEntities has different admin levels it means that country (lvl 2) have some regions (lvl3, lvl4, ...etc) and are part of larger group (lvl1) or groups

PE can be formed out of the existing PE: predecessor of Russain Empire was Tsardom of Russia.

Proposal for MVP:

• Separate 3 color schemes
  • Countries (LvL2)
    • 13 different colors
  • Regions (LvL3-6?)
    • color scheme limited to 6, related to the country color
  • Groups (LvL1)
    • Separate color scheme (?)

@ataalik mentioned the graph coloring algorithm

[amaury1093]

I think we can split this algorithm into smaller steps:

Preliminaries:

• Let's set k=13, and take a preset of k colors, call them c(1)..c(k).
• For each TE, we have a wish color (inputted by the mappers), that defines what color each TE ideally has. This mapping is called W, so that W(te) is the wish color of TE te. Of course, two neighbor TEs can have identical or similar wish colors, that's why we need an algorithm to make sure this never happens.

for D=1..N, do

1. get from DB all the SpacetimeVolumes at date D, and their respective TE owner.
2. Using PostGIS, create a graph so that nodes are TEs, and vertices define the relationship these 2 TEs are neighbors at date D. The graph will likely be represented as an adjacency list.
3. Color the nodes into k colors, with the most equal distribution of colors possible. See here for a more formal problem statement.
4. We have now a key/value mapping M between TE and [1..k], so that M(te) is a number between 1 and k that represents the color_id assigned by the algorithm in step 3. Now the last step is to assign each color_id to one of the c(j)s, so that we have the maximum wished color for TEs. More formally, find a permutation sigma of [1..k], to minimize the distance

sum( d( W(te) - c(sigma(M(te)) ) ), summing over all the TEs

where d represents the color difference. A bruteforce approach can be used here, if k is kept small.

od

Notes:

• We do not use predecessors here. This algorithm does not guarantee that if France is blue at date D, it will be blue at date D+1. However, our historical data shows that neighbors don't change that much between D and D+1, so the distance minimization algorithm should make sure that most of the time, France will keep the same color between D and D+1, assuming France has the same wish color between D and D+1. (stuff in italic are my gut feeling, they might be contested).
• If anyone wants to re-define the problem using the predecessors constraint, feel free to do so.
• 1 is straight-forward. 4 is easy enough. 2 is non-trivial. 3 is non-trivial. Overall this is a complicated problem.

[MiklerGM]

This algorithm does not guarantee that if France is blue at date D, it will be blue at date D+1.

That is strange, this feature has more priority than wish color, I think.

However, our historical data shows that neighbors don't change that much between D and D+1

We have great examples like Ottoman Empire, Holy Roman Empire, Germany, Mongol Empire they conquered almost half of the world. They are the hardest one to color, I think.

You are also ignoring the admin level during coloring.

My proposal:

Step 1 - collect all neighbors, 1-year representation

I prefer to use trees instead of graph for 1-year representation.
TE -> Year -> [Neighbor TEs]
It's does not matter, if it's a graph or tree, on this step. Trees are easier for imagination IMO
Disputed should not be counted as neighbors.

Step 2 - build range of unchanged neighbors for each TE

TE -> [Start_Year, End_Year] -> [Neighbor TSs]

Step 3 - Build META_TE by using predecessor field.

Possibly would cause some problems, because of m2m relationship. If Admin Level changes TE should be colored in a different way.

Admin_level -> META_TE -> [TEs] -> [Start_Year, End_Year] -> [Neighbor TSs]

Step 4 - Grade TE's based on their Admin Level and maximum neighbors.

Finding the most easiest and hardest one for coloring.

Step 5 - assign color_ids for TEs with largest neighborhood base

Step 6 - build color scheme

[KevinTyrrell]

Generate n evenly spaced color hues where n is the number of countries on the map. A naive approach to this would be to calculate the number of possible RGB colors (255³ => 16581375). Divide that value by n which is going to be the spacing between color hues. For example if there are 4 countries total, 16581375 / 4 => 4145343. Start an incremental value, x, at 0. To convert that value back to RGB, perform RGB((x - 255¹) % 255, (x - 255²) % 255, (x - 255³) % 255). Note % differs from Mod with negative values. Increment x by 255³ / n after each color is generated.

From there, simply color each country with the RGB generated from the above algorithm.

[MiklerGM]

For me as a partially color blind person this seems logical but not right. There are around 200 countries in the world (right now), so basically it's easier to take at least 256 color scheme.

Sample image taken from https://misc.flogisoft.com/bash/tip_colors_and_formatting

As you can see they are not so unique after all. For example 106, 142, 136, 172 are almost the same for me.

Additionally map color scheme usually matches the brand book of the project

UPD:
The picture itself is not perfect. Main idea: it's obvious from every 8-bit pallet, that neighbor colors should not be placed together.

[v1kun]

Accidentaly overheard about https://en.wikipedia.org/wiki/Four_color_theorem
Might be usefull

[MiklerGM]

From discussion on discord

TurntSnacko

anyway mikler you can see what i was reffering to by the shading in the upper right here and switzerland

MiklerGM
@turntsnacko correct me if I am wrong, you are proposing the light-grey color for really deep admin_levels?
TurntSnacko
yes the lowest level