[GRASS-dev] point cloud analysis: new features

[Markus Metz]

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