On Fri, Jan 2, 2015 at 10:08 AM, Benjamin Ducke <[email protected]> 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 >> [email protected] >> 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 > [email protected] > http://lists.osgeo.org/mailman/listinfo/grass-dev _______________________________________________ grass-dev mailing list [email protected] http://lists.osgeo.org/mailman/listinfo/grass-dev
