[GRASS-dev] About v.distance, v.what.vect (wrt "count points within...").

[Markus Metz]

Moritz Lennert wrote:
> Markus Metz wrote:
>>
>> OK, here comes (soon) a speed-up for v.distance
>
> [...]
>
>> Results for the 10000 points are identical (distance to nearest area
>> and category of nearest area).
>> The code is now a bit more complicated, but reducing processing time
>> for distance calculations from over 6m down to 2s might justify some
>> code complexity.
>
> Wow !
>
> Could you explain (briefly) what you did ?

This all assumes dmax unset or dmax > 0

Original: for each point, the distances to all areas in the To-vector
are calculated with dmax unset

Experimental: the search box is stepwise increased up to the extends
of the To vector. The search stops as soon as an area overlapping with
the current search box is found. A check is included if the area's
bbox overlaps with the search box, but the area itself is outside the
search box, does really happen regularly (e.g. halfmoon area). The
trick is how the search box is increased, in the first few iterations
the search box is very small, only getting larger if really necessary.
With this method, only few areas (the nearest areas) are selected and
distances to these areas are calculated.

For a To vector with many areas and a From vector with many points,
the original amount of distance calculations with dmax unset is n
points x n areas. Now it's only a bit larger than n points, I guess
maximum 4 x n points. Thus this experimental modification really pays
off with many areas. The test vector I used, boundary_municp in the NC
dataset, has 3579 areas, that's not that much, but I observed the
speed increase mentioned above. Now the slow part of v.distance is
updating the attribute table.

Markus M