erfaniaa / map-coloring

Map coloring, using four colors

map-coloring

Map coloring, using four colors

This program gets a map image as an input and produces all possible valid colorings of that map using backtracking.

The input image background and borders should be white.

Some Basic Stuff to Know

1. Map coloring
2. Four color theorem

Algorithm

1. Detecting all non-white regions (eg. provinces or states).
2. Converting the input map to a simple planar graph: There will be a node for each region. Two nodes will be adjacent, if and only if their corresponding regions have a common border on the map.
3. Using backtracking for coloring that graph (it's a recursive function that produces all valid colorings).
4. Displaying all produced colorings on the given map.

Dependencies

Install numpy, matplotlib and opencv using pip.

pip install -r requirements.txt

Run

python3 map_coloring.py map_image_file_name

Samples

python3 map_coloring.py iran.jpg

The original image:

A part of the program output:

python3 map_coloring.py tehran_province.jpg

The original image:

A part of the program output:

python3 map_coloring.py usa.png

The original image:

A part of the program output:

Notes

It runs slowly on large images. It can be improved by changing the second part of its algorithm (about setting the graph edges). Some computational geometry knowledge about polygons may be needed for this part.

Any contributions are welcomed.

map-coloring's Issues

No module named 'resource'

  File "C:\Users\Smkgames\Desktop\map-coloring-master\map_coloring.py", line 3, in <module>
    import resource, sys
ModuleNotFoundError: No module named 'resource'```

Making The Used Algorithm Faster #hacktoberfest

As it's noted on the README page:
It runs slowly on large images. It can be improved by changing the second part of its algorithm (about setting the graph edges). Some computational geometry knowledge about polygons may be needed for this part.

The second part of the algorithm is converting the input map to a simple planar graph: There will be a node for each region. Two nodes will be adjacent, if and only if their corresponding regions have a common border on the map.

If two regions like A and B have N and M vertices respectively, checking whether their corresponding graph nodes should have an edge between them or not takes O(N * M) time complexity. If anyone reduces this complexity by changing the used algorithm, he/she will gain some #hacktoberfest credits.