[GRASS-dev] point cloud analysis: new features

[Benjamin Ducke]

On 04/01/15 23:00, Paulo van Breugel wrote:
> 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?
> 

I think you are looking for a completely different algorithm
there. There are many clustering methods that will produce
exactly k clusters. But what do you mean by size: number of
points per cluster or spatial extent/area?

In both cases, I am not sure how you would reconcile the
two opposing goals: (A) find the actual cluster shapes,
(B) make the cluster shapes so that all clusters are of
equal size.

(please see also my comment to Markus below).

> 
> 
> On Sun, Jan 4, 2015 at 9:02 PM, Markus Metz
> <markus.metz.giswork at gmail.com <mailto:markus.metz.giswork at gmail.com>>
> wrote:
> 
> 
>     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.
>

Thanks Markus, this is excellent progress.
It seems to me that the approximation of cluster shapes from grouped
points is a generic problem that would best be solved with a separate
module. As long as the shapes are roughly convex, the existing v.hull
should work fine. For concave shapes, AFAIK things become messy because
common methods such as alpha shapes require the user to provide
threshold values.

Cheers,

Ben

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