[GRASS-dev] point cloud analysis: new features

Benjamin Ducke benducke at fastmail.fm
Fri Jan 2 01:08:46 PST 2015

Hi Markus,

On 01/01/15 22:18, Markus Metz wrote:
> Hi all,
> a new spatial index for point data is available in lib/btree2: a
> multidimensional search tree, also known as k-d tree.

Excellent news.

> 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.

I suggest implementing DBSCAN: http://en.wikipedia.org/wiki/DBSCAN
It is density-based and thus produces more useful results than
centroid-based methods (k-means and relatives). It can actually
trace the shapes of spatial clusters (even concave ones) and does
not require a priori knowledge about the number of clusters. It
can also handle noise.

There is a reference implementation (albeit in Java) that you can
use to compare it with other clustering algorithms:


An implementation in C (that I have not tried) is here:


The one drawback of DBSCAN is that it needs an efficient spatial
index to perform well -- and you have just taken care of that!

> - 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.

I would also like to point out that SAGA GIS is moving into
the same direction, i.e. more efficient processing of very
large point clouds. The latest release includes a number
of new point cloud tools. Perhaps it's worth a look.

Most importantly, SAGA GIS has introduced a new file format,
the SAGA Pointcloud (.spc) format. It is compact and yet
flexible enough for a variety of purposes. I recommend to
consider implementing import/export of this format in GRASS 7,
preferably not via v.in.ogr, to avoid the OGR model conversion

If you think this would be an interesting option, then you can
find a summary on our tracker:


(we are going to implement ".spc" in gvSIG CE, as well).

Best wishes,


> 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
> grass-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/grass-dev

Dr. Benjamin Ducke
{*} Geospatial Consultant
{*} GIS Developer

Spatial technology for the masses, not the classes:
experience free and open source GIS at http://gvsigce.org

More information about the grass-dev mailing list