<br><font size=2 face="sans-serif">I have used a program to "four-colour" a map. You need to be a bit careful. The State of New South Wales in Australia has about 7500 parishes (for land administration purposes), and I wanted to colour a GIS data set representing them. The program I used first does a swift greedy pass generating an approximate solution (this took about 30 seconds on a Sun Ultra 2 with 167 MHz processor, showing how long ago I tried this). I thought I'd see how long it would take to generate the full four-colour solution - in the end, I killed the process after about 3 weeks :-)</font>
<br>
<br><font size=2 face="sans-serif">Camden, you're right about needing a table showing which polygons border each other. My base data set was in an ESRI Arc coverage format, which meant I could generate and unload the Polygon Adjacency information (using the "palinfo" command). I had to sort and remove duplicates and adjust polygon numbers to eliminate the universal polygon. I ran this through the four-colouring program, and ended up with a table listing polygon numbers with a colour for each polygon (as an integer). I then joined this back to the original coverage's attribute data.</font>
<br>
<br><font size=2 face="sans-serif">For the four-colouring program, I used Michael Trick's "trick.c" program from </font>
<br>
<br><font size=2 face="sans-serif">http://mat.gsia.cmu.edu/COLOR/solvers/ .</font>
<br>
<br><font size=2 face="sans-serif">(Professor Trick is at Carnegie Mellon University. For further information, I'd suggest having a look at his home page (http://mat.gsia.cmu.edu/trick/), and at the operations research site (www.informs.org) .)</font>
<br>
<br><font size=2 face="sans-serif">You might also like to look at Professor Joseph Culberson's page at the University of Alberta (http://www.cs.ualberta.ca/~joe/).</font>
<br>
<br><font size=2 face="sans-serif">In summary, I wouldn't try doing this for large data sets, and I would not do it dynamically - add the colouring beforehand via an attribute. And consider just doing the initial swift greedy pass to get an approximate solution - it might be good enough for your purposes.</font>
<br>
<br><font size=2 face="sans-serif">Finally, does anyone have a program to compute the polygon adjacency information for polygons in a shapefile ?</font>
<br>
<br><font size=2 face="sans-serif">Cheers</font>
<br>
<br><font size=2 face="sans-serif">Richard E. Roger</font>
<br>
<br>
<br><font size=2 face="sans-serif">Dr. R. E. Roger NSW Department of <br>
Primary Industries<br>
Spatial Information Officer Systems 161 Kite St<br>
Resource Information Unit Locked Bag 21<br>
ORANGE NSW 2800<br>
ph: (02) 6391 3697 fax: (02) 6391 3740</font>
<br>
<br><font size=2 face="Courier New">------------------------------<br>
<br>
Date: Thu, 6 Jan 2005 10:52:55 -0800<br>
From: Paul Ramsey <pramsey@REFRACTIONS.NET><br>
Subject: Re: Four Color Theorem<br>
<br>
Google gives a pretty good answer right away, and even an algorithm.<br>
<br>
http://www.math.gatech.edu/~thomas/FC/fourcolor.html<br>
<br>
Sadly, it is quadratic.<br>
<br>
P<br>
<br>
Camden Daily wrote:<br>
<br>
> Does anyone have any experience in dynamically coloring a map with<br>
> only 4 colors? I know that it would be easier to just pick out the<br>
> colors myself, but I thought perhaps someone out there might have come<br>
> up with a good mapscript algorithm to do this.<br>
><br>
> I'd imagine the first step would be constructing a table defining<br>
> which polygons on the map border each other. Anyone have a good<br>
> method of doing that?<br>
><br>
> -Camden Daily</font><font size=2 face="sans-serif"><br>
<br>
This message is intended for the addressee named and may contain confidential information. If you are not the intended recipient or received it in error, please delete the message and notify sender. Views expressed are those of the individual sender and are not necessarily the views of their organisation.</font>