Trying to combine nearby points into a polygon

Question

We have collected millions of cell phone strength readings. I am trying to group points of the same strenght that are within a distance of each other in to a polygon. I asked on the postgis mailing list but didn't get a response.

To make the process simpler, I already extracted all the point of the same strength to one table. So I have a table of 1.5 million rows. It has a gist index on the geom field and btree indexes on the uniqueid of each row and on the 'clusterid' which is supposed to be the same for all points that are in the same 'cluster' (ie point a which is within distance of point c which is within distance of point z would all be the same cluster).

How would you accomplish this task???

I did wonder whether it might be worth trying to load the geometries in to memory and use JTS to process them? Although I doubt that would be any better.

Thanks - Bryan.

Answer 1

I would not use a conventional point->polygon process because that expects your points to define the boundary of a polygon and it doesn't sound like yours do. It sounds like yours are hotspots that are somehow related.

However, there are lots of ways to create polygons for this sort of situation depending on what is sensitive in your data. Here's a few quick ideas (one or more of which might be appropriate to your use-case):

• Buffer your points by your cluster distance and then dissolve the buffers based on the clusterid
• Create a convex hull of your points, one per clusterid
• Convert the points to a raster with a resolution of half your distance. Perhaps using the hexagonal cell raster available in QGIS would be good, you can the convert the raster to polygons
• Interpolate a raster from the points using a finer resolution than the option above, but your interpolation method will need to be chosen based on what is appropriate to your use case.

Answer 2

So, after looking at kmeans and some further research, I ended up using a function similar to those mentioned in the thread at http://www.mail-archive.com/[email protected]/msg12453.html

I haven't had a chance to fully analyze and test what I did, so there may well be some bugs in it. Basically, I buffered my points then used st_intersects and then assigned each row a 'cluster id' that matched those circles that formed one contiguous polygon. To try and keep the transactions down in size, I wrote a simple python script that ran a batch of records through. Once all records had a clusterid I then did a union to create a polygon for all rows with the same clusterid.

Most of the code is at http://pastebin.com/H7gQxEm8 for those interested.

Answer 3

If you're interested in the simple hexagon cartogram approach, Hexer is available. I use it for generating density and boundary maps of large LiDAR point sets (millions). It can read OGR point data sources in addition to ASPRS LAS data if you set the CMake config -DWITH_GDAL=ON when configuring.