[postgis-users] Voronoi polygons for large dataset

[Giuseppe Broccolo]

Hi Nathan,

2018-06-07 16:15 GMT+01:00 Nathan Einstein <njeinstein at gmail.com>:

> Hi all,
>
> I’d like to create Voronoi polygons for a set of about 11 million points.
> ST_VoronoiPolygons works fine for a subset of ~3 million of these points,
> though the function’s processing speed seems to scale non-linearly in the
> number of points. I therefore haven’t been able to get it to work for the
> entire dataset, even when left running overnight (but notably, ArcGIS
> completes it in under an hour).
>
> Unfortunately, it doesn’t seem like there’s any simple
> “divide-and-conquer”-type solution; because the Voronoi polygons on the
> edges will be irregularly shaped, I haven’t been able to come up with a
> clean way to combine the results from subsets of the full dataset.
>
> Does anyone have any suggestions?
>

As you said, there is not a trivial way to make work Voronoi polygons
creation in subsets of data, for then being put together. You can do this
just in case you can accept irregularities at the edges of each subset.
Though it is normal that processing speed doesn't scale linearly (the
complexity of the algorithm should be ~O(N logN) in the best case), it is
strange that ArcGIS performs with a so large difference, being based both
ArcGIS and ST_VoronoiPolygons functions on triangulation. Could check if
both processing are performed with the same tollerance (i.e. the distance
below which two points are considered as one)? In really dense datasets
different tollerance could bring to different starting points in input to
the algorithm.

Anyway, I'd be happy to know more from anyone has a good answer to this
question.

All the best,
Giuseppe.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20180609/1ecfc8ea/attachment.html>