[FEA]: Allow to find the K nearest points to a polygon (using quadtree)

[fpenarruApr]

Is this a new feature, an improvement, or a change to existing functionality?

Improvement to existing functionality

How would you describe the priority of this feature request

Low priority, just an improvement

Please provide a clear description of problem you would like to solve.

Right now, cuspatial.quadtree_point_to_nearest_linestring allows to find the nearest point. It will be useful to find the N closest points to a feature (point, polygon or linestring) Something similar to this article with Postgis:

https://www.crunchydata.com/blog/a-deep-dive-into-postgis-nearest-neighbor-search

SELECT loc.*, t.name, t.geom
  FROM locations loc
  JOIN LATERAL (SELECT name, geom FROM geonames gn
      ORDER BY loc.geom <-> gn.geom LIMIT 10) AS t ON true;

Describe any alternatives you have considered

No response

Additional context

No response

[GPUtester]

Hi @fpenarruApr!

Thanks for submitting this issue - our team has been notified and we'll get back to you as soon as we can! In the mean time, feel free to add any relevant information to this issue.

[jarmak-nv]

Hey @fpenarruApr - Thanks for taking the time for a feature req here on cuSpatial!

quadtree_point_to_nearest_linestring() might do what you need already, just want to check to see if you've tried this out for your needs.

The function returns a cuDF dataframe with 3 columns:

1. point_index - this is the index of your input points that the distance calc corresponds to
2. linestring_index - the index of your input lines that the distance calc corresponds to
3. distance - the distance itself in whatever your projection units are (side note, check out cuProj if you need to accelerate WGS84 <-> UTM!)

I think you can replicate

SELECT loc.*, t.name, t.geom
  FROM locations loc
  JOIN LATERAL (SELECT name, geom FROM geonames gn
      ORDER BY loc.geom <-> gn.geom LIMIT 10) AS t ON true;

With something similar to

distances = cuspatial.quadtree_point_to_nearest_linestring(linestring_quad_pairs, 
                                                           quadtree,
                                                           point_indices, 
                                                           points, 
                                                           linestrings)
top_n_distances = distances.sort(distances.distance)[:n]

That assumes the input points, or input linestrings are static (ie you're comparing a single point to a lot of different linestrings)

For any given point I think you'd need to do something similar to:

index_of_point_p = point_p_idx
top_n_distances_for_point_p = distances[distances.point_index == index_of_point_p].sort(distances.distance)[:n]

[fpenarruApr]

Hi @jarmak-nv

Thanks for your help. I think your suggestions are not going to solve my problem. top_n_distances will have the minimum distances between different points and polygons, and this is not what I want. Let me clarify my problem. Suppose points representing hospitals, and polygons representing buildings. A typical Facility Problem will be to find the 3 or 4 closest hospitals to each building. So, the solution can be a dataframe with the same number of rows that buildings, and some fields like

id_building, id_hospital1, dist_hospital1, id_hospital2, dist_hospital2, id_hospital3, dist_hospital3

Later, we can assign colors to each polygon according to distances or some coefficients and see which areas could be with a bad service. I hope now my problem is more clear. Thank you very much for your help! :-)

[harrism]

Thanks for the great example!

[jarmak-nv]

@fpenarruApr Yeah I see that now! Definitely will leave this feature request open since it's not something we directly support.

We'll have to get creative here, I'll test a few things out this week and post some ideas 🌐