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 _______________________________________________ grass-dev mailing list [email protected] http://lists.osgeo.org/mailman/listinfo/grass-dev
