[R-sig-Geo] Colouring maps so that adjacent polygons differ in colour

Karl Ove Hufthammer karl at huftis.org
Wed Apr 6 11:11:57 CEST 2011

Rainer M Krug wrote:

> I think the idea is really great. I couldn't try it out yet, but if it
> is working, I think it should be added to one of the spatial packages -
> maybe sp?

If anyone is interested, feel free to add the function to any of the spatial 
packages, under a suitable free license (at least GPL2+ is OK).

I hope to some time in the future also implement one of the linear 5-
colouring algorithms. It annoys me somewhat that the greedy algorithm only 
manages a 6-colouring on one of my map data sets … :-)

(The ‘gcolor’ algorithm gives nice results, but is *extremely* slow for 
large maps. It has been trying to colour the ‘world’ map for over two hours 
now, and is still not finished …)

One final thought: For creating beautiful maps other criteria than 
minimising the number of colours may be useful. One example is balancing the 
number of polygons using each of the colours. The greedy algorithm naturally 
tends to use most of the low colours. For instance, on a map of 500 
polygons, 470 may be coloured with colours 1–3, 29 by colour 4 and only 1 by 
colour 5. Colours 4 and (especially) 5 may therefor look ‘out of place’. If 
the algorithms only manges a 5-colouring, it could at least use equal 
amounts of each colour (here one might also want to take into account the 
area of the various polygons). On the other hand, a map using all colours 
equally often will tend to look more ‘busy’, so perhaps a greedy colouring 
gives the nicest maps after all … ?

Karl Ove Hufthammer

More information about the R-sig-Geo mailing list