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

Roger Bivand Roger.Bivand at nhh.no
Wed Apr 6 09:38:58 CEST 2011

On Wed, 6 Apr 2011, Karl Ove Hufthammer wrote:

> 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 
> problem.)
>> 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?

I've asked Barry off-list about this, there was a case a little while ago 
with unexpected results because of inserted sliver polygons causing 
apparently separate observations to be neighbours (the slivers were only 
visible when zooming right in). There are also differences in the way 
software may handle precision (snapping). More will follow ...

> 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.

This is a feature of nb objects - card(nb) returns the number of 
neighbours, and should always be used. This is documented in ASDAR (p. 
240), and at length in Bivand & Portnov (2004). I'll add to the 
documentation in the package. If you use card(), you get the outcomes you 

Hope this helps,


> (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
> _______________________________________________
> R-sig-Geo mailing list
> R-sig-Geo at r-project.org
> https://stat.ethz.ch/mailman/listinfo/r-sig-geo

Roger Bivand
Economic Geography Section, Department of Economics, Norwegian School of
Economics and Business Administration, Helleveien 30, N-5045 Bergen,
Norway. voice: +47 55 95 93 55; fax +47 55 95 95 43
e-mail: Roger.Bivand at nhh.no

More information about the R-sig-Geo mailing list