I like your idea very much, especially since something I did not say is that the points have a range attribute which determines how far they can interact with other points. So the circle buffer you talk about would have a diameter equals to the range of each point.
What would be fastest as the last step : bounding box, minimum bounding circle or minimum convex hull ? I am guessing the BB, but is the difference significant enough that one should be chosen over another ? Sébastien On Tue, Dec 7, 2010 at 13:42, Emilie Laffray <emilie.laff...@gmail.com>wrote: > > > On 7 December 2010 17:01, Sébastien Lorion <s...@thestrangefactory.com>wrote: > >> Hello, >> >> I am trying to find an efficient way to find clusters of points as shown >> in the attached image. The only clustering criteria is the distance between >> the points. The dataset can be very large (millions of points) and point >> distribution is mostly clustered with some sparse points in the gaps. >> >> I searched the net and this mailing list and found two promising solution >> paths: >> >> - use a statistical tools such as R with a density function ( >> http://www.r-project.org) >> - use a clustering algorithm like those explained here >> http://www.med.nyu.edu/biostatistics/people/Ilana%20Belitskaya-Levy/Courses/MAS/Handouts/clustering.pdf >> (agnes >> seems the most promising for my purposes) >> >> >> <http://www.med.nyu.edu/biostatistics/people/Ilana%20Belitskaya-Levy/Courses/MAS/Handouts/clustering.pdf>I >> would like your advice to help me find which approach would be best suited >> with PostGIS (maybe there is even something already made that I can use?). >> Whatever solution I pick, it must be efficient and the workload must be able >> to be distributed on a cluster of commodity hardware. >> >> I am new to GIS and this mailing list, so please excuse me if I am not >> using the right vocabulary. >> >> Thank you very much! >> >> > Hello, > > Some time ago I have worked on something similar, except that I was using > circles instead of boxes which should not be a problem. I am just giving the > logic as I don't have access to the code right now. > You can start by creating a buffer around each of your points of the > distance you want. > The next step is to create an UNION of all the buffers that intersect. > You get the list of points included in each of the resulting polygons and > then you create either a bounding box around them or use a minimum bounding > circle (Postgis 1.5 and above). > > Emily Laffray > > _______________________________________________ > postgis-users mailing list > postgis-users@postgis.refractions.net > http://postgis.refractions.net/mailman/listinfo/postgis-users > >
_______________________________________________ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users