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

Karl Ove Hufthammer karl at huftis.org
Wed Apr 6 09:22:19 CEST 2011

Barry Rowlingson wrote:

> topocolours (I wrote that!) uses the same greedy algorithm once its
> worked out the connectivity. I did make topocolours have the
> flexibility to choose other algorithms but only implemented the greedy
> one. The problem with real world maps is that some features have more
> than one polygon (islands) and if you want them all coloured the same
> you might not be able to do a 4-colour colouring!

Indeed. With multi-polygons you might really have a *non-planar* graph, for 
which the four colour theorem doesn’t apply. (But for polygons that are 
‘real’ islands, i.e., have no neighbouring polygons, this will never be a 

> I also used ColorBrewer colours!

I love ColorBrewer, and wish ‘Set1’ it was the default palette for R … :-)

> It might be worth taking out the construction of the adjacency list
> to another function, since I found recently that poly2nb gave very
> different adjacencies to functions in rgeos.

That’s very surprising, and seems to imply a bug in at least one of the 
functions. Do you have a publically available example showing this?

The ‘poly2nb’ does have a somewhat strange behaviour with polygons with no 
members, BTW. Instead of the corresponding neighbours vector being empty, it 
has one element, namely 0. This means that the length of the neighbour 
vector doesn’t necessarily correspond to the number of neighbours. It’s not 
documented, and can at least be seen as a misfeature.

(It also means that in the last example of my colouring code, which sorts 
the polygons by degree before colouring them, polygons with no neighbours 
are mixed with polygons with one neighbour. This will never have any effect 
on the resulting colouring, though, as the ‘islands’ will automatically get 
colour 1, and don’t influence the colouring of the other polygons.)

Karl Ove Hufthammer

More information about the R-sig-Geo mailing list