<div dir="ltr"><div>Tried it out, and it works like a charm, great! <br><br></div>One question/request, would it be terribly difficult to add an option to compute an user-defined number of clusters of equal size?<br><br><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Jan 4, 2015 at 9:02 PM, Markus Metz <span dir="ltr"><<a href="mailto:markus.metz.giswork@gmail.com" target="_blank">markus.metz.giswork@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Fri, Jan 2, 2015 at 10:08 AM, Benjamin Ducke <<a href="mailto:benducke@fastmail.fm">benducke@fastmail.fm</a>> wrote:<br>
> Hi Markus,<br>
><br>
> On 01/01/15 22:18, Markus Metz wrote:<br>
>> Hi all,<br>
>><br>
>> a new spatial index for point data is available in lib/btree2: a<br>
>> multidimensional search tree, also known as k-d tree.<br>
>><br>
><br>
> Excellent news.<br>
><br>
>> What is it good for:<br>
>><br>
>> - nearest neighbor statistics: test if points are randomly<br>
>> distributed. The current GRASS addon v.nnstat uses an external k-d<br>
>> tree from PCL (which in turn uses flann) which finds the approximate,<br>
>> not the exact nearest neighbor. The new GRASS-native k-d tree always<br>
>> finds the real nearest neighbor.<br>
>><br>
>> - spatial cluster analysis: a point cloud can be partitioned into<br>
>> separate clusters where points within each cluster are closer to each<br>
>> other than to points of another cluster. To be implemented.<br>
>><br>
><br>
> I suggest implementing DBSCAN: <a href="http://en.wikipedia.org/wiki/DBSCAN" target="_blank">http://en.wikipedia.org/wiki/DBSCAN</a><br>
> It is density-based and thus produces more useful results than<br>
> centroid-based methods (k-means and relatives). It can actually<br>
> trace the shapes of spatial clusters (even concave ones) and does<br>
> not require a priori knowledge about the number of clusters. It<br>
> can also handle noise.<br>
<br>
</span>Done in trunk r63952 as v.cluster. It is not a GRASS7 addon because it<br>
does not work with G7.0. At the moment it only identifies and labels<br>
clusters. Connectivity graphs and cluster shapes are not implemented.<br>
In future, I would like to add OPTICS because OPTICS can better handle<br>
different clusters with different densities.<br>
<br>
Markus M<br>
<div class="HOEnZb"><div class="h5"><br>
><br>
> There is a reference implementation (albeit in Java) that you can<br>
> use to compare it with other clustering algorithms:<br>
><br>
>   <a href="http://elki.dbs.ifi.lmu.de/" target="_blank">http://elki.dbs.ifi.lmu.de/</a><br>
><br>
> An implementation in C (that I have not tried) is here:<br>
><br>
>   <a href="https://github.com/siddharth950/DBSCAN" target="_blank">https://github.com/siddharth950/DBSCAN</a><br>
><br>
> The one drawback of DBSCAN is that it needs an efficient spatial<br>
> index to perform well -- and you have just taken care of that!<br>
><br>
>> - point cloud thinning: a sample can be generated from a large point<br>
>> cloud by specifying a minimum distance between sample points. To be<br>
>> implemented.<br>
>><br>
>> The new k-d tree is now used by v.clean tool=snap (Vect_snap_lines()),<br>
>> reducing both memory consumption and processing time.<br>
>><br>
><br>
> I would also like to point out that SAGA GIS is moving into<br>
> the same direction, i.e. more efficient processing of very<br>
> large point clouds. The latest release includes a number<br>
> of new point cloud tools. Perhaps it's worth a look.<br>
><br>
> Most importantly, SAGA GIS has introduced a new file format,<br>
> the SAGA Pointcloud (.spc) format. It is compact and yet<br>
> flexible enough for a variety of purposes. I recommend to<br>
> consider implementing import/export of this format in GRASS 7,<br>
> preferably not via v.in.ogr, to avoid the OGR model conversion<br>
> overhead.<br>
><br>
> If you think this would be an interesting option, then you can<br>
> find a summary on our tracker:<br>
><br>
>   <a href="http://gvsigce.sourceforge.net/mantis/view.php?id=595" target="_blank">http://gvsigce.sourceforge.net/mantis/view.php?id=595</a><br>
><br>
> (we are going to implement ".spc" in gvSIG CE, as well).<br>
><br>
> Best wishes,<br>
><br>
> Ben<br>
><br>
>><br>
>> More technical:<br>
>> the new k-d tree finds the exact nearest neighbor(s), not some<br>
>> approximation. It supports up to 255 dimensions. It is dynamic, i.e.<br>
>> points can be inserted and removed at any time. It is balanced to<br>
>> improve search performance. It provides k nearest neighbor search<br>
>> (find k neighbors to a given coordinate) as well as radius or distance<br>
>> search (find all neighbors within radius, i.e. not farther away than<br>
>> radius to a given coordinate).<br>
>><br>
>> Markus M<br>
>> _______________________________________________<br>
>> grass-dev mailing list<br>
>> <a href="mailto:grass-dev@lists.osgeo.org">grass-dev@lists.osgeo.org</a><br>
>> <a href="http://lists.osgeo.org/mailman/listinfo/grass-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/grass-dev</a><br>
>><br>
><br>
><br>
><br>
> --<br>
> Dr. Benjamin Ducke<br>
> {*} Geospatial Consultant<br>
> {*} GIS Developer<br>
><br>
> Spatial technology for the masses, not the classes:<br>
> experience free and open source GIS at <a href="http://gvsigce.org" target="_blank">http://gvsigce.org</a><br>
> _______________________________________________<br>
> grass-dev mailing list<br>
> <a href="mailto:grass-dev@lists.osgeo.org">grass-dev@lists.osgeo.org</a><br>
> <a href="http://lists.osgeo.org/mailman/listinfo/grass-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/grass-dev</a><br>
_______________________________________________<br>
grass-dev mailing list<br>
<a href="mailto:grass-dev@lists.osgeo.org">grass-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/grass-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/grass-dev</a><br>
</div></div></blockquote></div><br></div>