Hi all, a new spatial index for point data is available in lib/btree2: a multidimensional search tree, also known as k-d tree.
What is it good for: - nearest neighbor statistics: test if points are randomly distributed. The current GRASS addon v.nnstat uses an external k-d tree from PCL (which in turn uses flann) which finds the approximate, not the exact nearest neighbor. The new GRASS-native k-d tree always finds the real nearest neighbor. - spatial cluster analysis: a point cloud can be partitioned into separate clusters where points within each cluster are closer to each other than to points of another cluster. To be implemented. - point cloud thinning: a sample can be generated from a large point cloud by specifying a minimum distance between sample points. To be implemented. The new k-d tree is now used by v.clean tool=snap (Vect_snap_lines()), reducing both memory consumption and processing time. More technical: the new k-d tree finds the exact nearest neighbor(s), not some approximation. It supports up to 255 dimensions. It is dynamic, i.e. points can be inserted and removed at any time. It is balanced to improve search performance. It provides k nearest neighbor search (find k neighbors to a given coordinate) as well as radius or distance search (find all neighbors within radius, i.e. not farther away than radius to a given coordinate). Markus M _______________________________________________ grass-dev mailing list [email protected] http://lists.osgeo.org/mailman/listinfo/grass-dev
