[GRASSLIST:8909] Re: distance algorithim

[Michael Barton]

Doesn't r.distance already do this?

Michael
__________________________________________
Michael Barton, Professor of Anthropology
School of Human Evolution and Social Change
Arizona State University
Tempe, AZ 85287-2402

phone: 480-965-6213
fax: 480-965-7671
www: http://www.public.asu.edu/~cmbarton



> From: Joel Peter William Pitt <joel.pitt at gmail.com>
> Date: Mon, 7 Nov 2005 15:30:19 +1300
> To: <grasslist at baylor.edu>
> Subject: [GRASSLIST:8906] distance algorithim
> 
> Hi all,
> 
> I'm trying to optimise a grass module that takes two maps of a
> phenomenon at different times. It calculates the distance between the
> raster cells in the later map to the nearest cell in the earlier map.
> 
> Obviously when the earlier map has alot of cells present it takes a
> while to find the closest.
> 
> Currently I'm optimising it by making a list of cell coordinates for
> the cells in the earlier map. I only add cells to the list that are
> not surrounded by other cells - ie I'm only adding cells from the
> outlines of contiguous areas. Each cell present in the later map is
> compared to the earlier map to check if the same raster cell is
> present, if so the distance is 0.
> 
> I also split this list into a grid. The grid is basically a lower
> resolution raster of the same map, but contains a list in each cell of
> the coordinates that fall within the grid position.
> 
> e.g
> 
> Say the raster region is 100,100 and the grid spacing is 16
> 
> This gives a grid size of 7 rounding up from 6.25.
> 
> Say we have a coordinate in the later map: 34,50. This evaluates to
> grid position (3, 4). Because 34/16 = 2.125 and 50/16=3.125, and each
> is rounded up.
> To find the nearest cell in the past map we compare distances to all
> the coords associated with grid position (3,4) - we also compare the
> distances to the 8 surrounding grid positions in case coords in one of
> these is closer. If no coords are found then the grid positions
> surrounding the surrounding positions are searched, etc.
> 
> The grid spacing has some effect on performance - and for my purposes
> it seems like 16 does alright.
> 
> ----
> 
> So, the point of this post is:
> 
> Is this the best way to be doing this? Does anyone know of a better
> algorithm? I know for linear 1 dimensional data I could be using a
> range of structures to find the closest, but for two dimensional data
> I don't know any.
> 
> Alternatively, if my current method is reasonable are there any
> additional things I could do to speed it up?
> 
> Note, I am doing stochastic dispersal simulations, and although this
> does run a 25 timestep simulation within half an hour, I need to do as
> many replications as possible. The major hold up at the moment is this
> distance evaluation. Part of the problem is that the present cells are
> very scattered, so only adding the boundary cells to the lists doesn't
> have as great an impact as it usually would.
> 
> Any suggestions or comment appreciated, thanks!
> 
> Joel