Tried it out, and it works like a charm, great! One question/request, would it be terribly difficult to add an option to compute an user-defined number of clusters of equal size?
On Sun, Jan 4, 2015 at 9:02 PM, Markus Metz <[email protected]> wrote: > 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 >
_______________________________________________ grass-dev mailing list [email protected] http://lists.osgeo.org/mailman/listinfo/grass-dev
