[GRASS-dev] point cloud analysis: new features

Markus Metz markus.metz.giswork at gmail.com
Sun Jan 4 12:02:37 PST 2015

On Fri, Jan 2, 2015 at 10:08 AM, Benjamin Ducke <benducke at fastmail.fm> wrote:
> 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.

Done in trunk r63952 as v.cluster. It is not a GRASS7 addon because it
does not work with G7.0. At the moment it only identifies and labels
clusters. Connectivity graphs and cluster shapes are not implemented.
In future, I would like to add OPTICS because OPTICS can better handle
different clusters with different densities.

Markus M

> There is a reference implementation (albeit in Java) that you can
> use to compare it with other clustering algorithms:
>   http://elki.dbs.ifi.lmu.de/
> An implementation in C (that I have not tried) is here:
>   https://github.com/siddharth950/DBSCAN
> 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
> overhead.
> If you think this would be an interesting option, then you can
> find a summary on our tracker:
>   http://gvsigce.sourceforge.net/mantis/view.php?id=595
> (we are going to implement ".spc" in gvSIG CE, as well).
> Best wishes,
> Ben
>> 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
> _______________________________________________
> grass-dev mailing list
> grass-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/grass-dev

More information about the grass-dev mailing list