On Sat, 3 Nov 2007, Tim Woodall wrote:

On Mon, 29 Oct 2007 11:04:56 +0000,
Clive D. W. Feather wrote:
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.

Possibly. This is not as sure-fire a trick as it once was - you're saving
arithmetic operations, but giving your data cache a rough ride.

I'd have thought a more useful optimization would be:
If D(x,y) = x^2 + y^2

then D(x+1, y) = D(x, y) + 2x + 1
D(x, y+1) = D(x, y) + 2y + 1
D(x-1, y) = D(x, y) - 2x + 1
D(x, y-1) = D(x, y) - 2y + 1

This would only work if you inverted the loops, though, so you iterated
over stations on the outside, and grid cells on the inside. If you did
that, though, yes, this would be what we call 'strength reduction', a
venerable optimisation trick. Very well spotted that it can be applied
here!

A better optimisation, though, would be to start off by putting the
stations in a quadtree or some other spatial data structure (something
clever involving the Voronoi diagram?), so that you can find the nearest
station (or at least a small number of candidates) to each grid cell with
a fast lookup, rather than having to grind through every station in the
list.

Or at least, this would be true if there were a million stations. If there
are only a few hundred, brute force might still be quicker. Most
unsatisfying.

tom

--
Science which is distinguishable from magic is insufficiently advanced

On Mon, 29 Oct 2007, Mr Thant wrote:

On 29 Oct, 11:04, "Clive D. W. Feather" cl...@on-the-
train.demon.co.uk wrote:

When you've finished, the grid holds the distance to the nearest
station. Convert it to a GIF and fiddle with the colour map and, for
example, you can have a map where places within 1km of a station are
green, within 2km are yellow, and more than 2km are red.

I actually did a map like this on Friday:
http://londonconnections.blogspot.co...ndon-gaps.html

I posted a similar, but much less pretty, map, a few months ago. Can't
find it now - i think i must have deleted it. Oh well.

But i want an actual readout of polygons, with lists of bounding stations
and exact areas. My OCD requires this. Then i need a map and/or dataset
showing the population density across London.

If you did want to do it with pure graphics, the best way i can think of
would be to do a Voronoi tesselation (using some code off the internet or
something [1]), split the regions into triangles centred on the stations,
then make postscript of the triangles with a graduated fill getting
darker/redder/etc as it goes out from the station [2]. That would look
pretty sweet.

I loaded all the station locations into a MySQL database, then wrote a
PHP script to generate an SVG file. I didn't bother calculating
distances - it just does separate passes to make the quarter mile discs
appear on top of the half mile discs, which achieves a similar effect.

The thing that excites me most is that you have the coordinates of all the
stations from Google Earth dudes - i've been using Clive's grid references
for tube stations and manually adding them for railway stations, which is
very tedious. I will be obtaining the dataset you used forthwith!

tom

[1] Such as:

http://www.qhull.org/

[2] Like so:

http://redgrittybrick.org/postscript/gradient.html

--
Science which is distinguishable from magic is insufficiently advanced

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)