# [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
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?

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

```