Efficient Way To Get Voronoi Polygons and Matched Points

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Efficient Way To Get Voronoi Polygons and Matched Points

Gerard LYNCH

Hello,

 

I'm using postgis2.3 and ST_VoronoiPolygons.

 

I would like to know the best way to do a reverse lookup of sorts to find out which Voronoi polygon maps to which point(s) used in ST_Collect.

 

Currently I'm looping through each of the input points and doing a ST_Within on each of the Voronoi polygons until I get a match. This can be time consuming when there are 1000 points and 1000 voronoi polygons. I could also do the reverse and loop through each of the Voronoi polygons and fetch points within the polygon but I am wondering if there is a more efficient approach.

 

Ideally an object that returned something like "Polygon1 => [pointa, pointb], Polygon2 => [pointc]" etc would be preferable.

 

My use case is when someone clicks on a Voronoi polygon in my GUI I would like to be able to provide the user with information on the points used to create that polygon.

 

Cheers,

Gerard

 

 


_______________________________________________
postgis-users mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-users
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Way To Get Voronoi Polygons and Matched Points

Tom van Tilburg-2
Hi Gerard,

Considering that your points will always be in the heart of your polygons, an ST_Intersects would be faster than ST_Within. 1000 points x 1000 polygons should not be a problem at all in this matter, but you might consider adding a spatial index to the polygons.
On a side note: if your GUI is a web-site, you may consider using D3 voronoi: https://github.com/d3/d3-voronoi It does exactly what you describe.

Best, 
  Tom

On Thu, 2 Mar 2017 at 04:28 Gerard LYNCH <[hidden email]> wrote:

Hello,

 

I'm using postgis2.3 and ST_VoronoiPolygons.

 

I would like to know the best way to do a reverse lookup of sorts to find out which Voronoi polygon maps to which point(s) used in ST_Collect.

 

Currently I'm looping through each of the input points and doing a ST_Within on each of the Voronoi polygons until I get a match. This can be time consuming when there are 1000 points and 1000 voronoi polygons. I could also do the reverse and loop through each of the Voronoi polygons and fetch points within the polygon but I am wondering if there is a more efficient approach.

 

Ideally an object that returned something like "Polygon1 => [pointa, pointb], Polygon2 => [pointc]" etc would be preferable.

 

My use case is when someone clicks on a Voronoi polygon in my GUI I would like to be able to provide the user with information on the points used to create that polygon.

 

Cheers,

Gerard

 

 

_______________________________________________
postgis-users mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-users

_______________________________________________
postgis-users mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-users
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Way To Get Voronoi Polygons and Matched Points

Gerard LYNCH

Hi Tom,

 

The d3 library is exactly what I needed. Although d3v4 removed the polygon clipping function, so I am using d3v3.

 

Cheers,

Gerard

 

From: postgis-users [mailto:[hidden email]] On Behalf Of Tom van Tilburg
Sent: 07 March, 2017 8:14 AM
To: [hidden email]
Subject: Re: [postgis-users] Efficient Way To Get Voronoi Polygons and Matched Points

 

Hi Gerard,

 

Considering that your points will always be in the heart of your polygons, an ST_Intersects would be faster than ST_Within. 1000 points x 1000 polygons should not be a problem at all in this matter, but you might consider adding a spatial index to the polygons.

On a side note: if your GUI is a web-site, you may consider using D3 voronoi: https://github.com/d3/d3-voronoi It does exactly what you describe.

 

Best, 

  Tom

 

On Thu, 2 Mar 2017 at 04:28 Gerard LYNCH <[hidden email]> wrote:

Hello,

 

I'm using postgis2.3 and ST_VoronoiPolygons.

 

I would like to know the best way to do a reverse lookup of sorts to find out which Voronoi polygon maps to which point(s) used in ST_Collect.

 

Currently I'm looping through each of the input points and doing a ST_Within on each of the Voronoi polygons until I get a match. This can be time consuming when there are 1000 points and 1000 voronoi polygons. I could also do the reverse and loop through each of the Voronoi polygons and fetch points within the polygon but I am wondering if there is a more efficient approach.

 

Ideally an object that returned something like "Polygon1 => [pointa, pointb], Polygon2 => [pointc]" etc would be preferable.

 

My use case is when someone clicks on a Voronoi polygon in my GUI I would like to be able to provide the user with information on the points used to create that polygon.

 

Cheers,

Gerard

 

 

_______________________________________________
postgis-users mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-users


_______________________________________________
postgis-users mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-users