In uk.transport.london message ,
Mon, 29 Oct 2007 11:04:56, Clive D. W. Feather clive@on-the-
train.demon.co.uk posted:
In article , Tom
Anderson writes
I'm trying to figure out how to program a computer to find these
automatically.

The approach I've taken in the past is very simple. Start with a grid
representing the entire area (to make it easy, say 1000 x 1000 with one
unit on the grid being 100 metres). Set up a list of locations of all
the stations. Then:
for each grid cell
best := infinity
for each station on the list
d := (distance from station to cell) squared
if d best then best := d
cell value := sqrt (best)

You can optimize things slightly by using a lookup table for the square
roots rather than calculating them each time.

Square root is an FPU operation nowadays, so minimising them is only of
minor importance. But there's no need to store distance in each cell
while finding the best; store the square, and root only for display.


A quick test in Javascript shows that the language can calculate a
million distance^2 in five seconds (P4 3GHz); so for N stations the
distances^2 would need 5N seconds; double that for details, and divide
it by a fairly large number if using a compiled language. N is under
1000, IIRC.

The conclusion seems to be that there's no point, for a one-off
calculation (stations don't move about much), in doing other than simple
reliable brute force, testing of course with subset data first; if one
cannot do the final full run over dinner at home, one needs a better
cook. Unless, of course, one has an already-developed more subtly
algorithm to hand and knows how to use it.

If course, that's just for distances. The nearest station to Ham House
must be Twickenham or St Margarets; but the nearest by foot alone is
probably Richmond, possibly Teddington.

--
(c) John Stockton, Surrey, UK. Turnpike v6.05 MIME.
Web URL:http://www.merlyn.demon.co.uk/ - FAQish topics, acronyms, & links.
Proper = 4-line sig. separator as above, a line exactly "-- " (SonOfRFC1036)
Do not Mail News to me. Before a reply, quote with "" or " " (SonOfRFC1036)