[FEA]Point-to-polyline nearest neighbor distance

[EmilioZhao]

1. Is your feature request related to a problem? Please describe.
    Sure. In autonomous driving, we heavily used GPU to accelerate computation. One typical scenario is: self-driving car needs to know the relative position of every obstacle that might affects its path planning. To get obstacle's relative position, we need to transform obstacles' coordinates from X/Y axis to S/L axis (Frenet-frame coordinate) , in other words, to see the obstacles from car's perspective not the bird view. To do the transformation, we calculated the distance of every obstacle's bounding box points (4 vertices) to the reference line (a polyline, usually the central line of a lane) on which the car is currently driving. We did this in a brute force way by breaking the polyline into pieces of segments and calculating the distance from the point to every segment to find the closest segment to the point. Obstacle's lateral and longitudinal relative offset to the car can be described by the relative position of all points to their closest segments.
However, there're probably a more efficient way to implement the Point to Polyline nearest neighbor distance algorithm, so we resort to cuSpatial.

2. Describe the solution you'd like

• You might use Matrix Multiplication to implement Point to Polyline distance and use advanced GPU acceleration techniques as long as your solution is better than the naive point-to-segment way:)
• In practice, we will iterate multiple points to do Point-to-Polyline distance, so a multiple points version of point to polyline is very welcomed and it's obviously more efficient, widely used and user-friendly.
• One more thing, for car driver, it's critical to know if the obstacle is on the left side or the right side of the car.”For lateral distance, left is positive and right negative" is a Frenet-frame coordinate convention, we will highly appreciate your efforts if you follow this convention.

    Actually, I was very excited to see this feature (Point-to-polyline nearest neighbor distance) in your future plan.
Manageable latency is critical to autonomous driving and if cuSpatial could boost the performance, a lot of people would benefit from this. So please re-prioritize your feature plan and bring this forward.

Thanks a lot!

[KirkDybvik]

I am interested in this as well. In the past I have done a similar brute force method like you describe and agree that there are a lot of computations.

A few questions/comments that may or may not apply (or may be out of scope for initial consideration):

• possibly consider 2 methods for point-to-polyline. One for "local" distances (like items within sensor range of a car) and one that uses "great circle" distance (like features near the route an airplane would fly).
• would cuSpatial require a specified coordinate system in either case?
• any special consideration for crossing the +/- 180 degree longitude line? any limitations for accepted northernmost/southernmost latitudes?

[EmilioZhao]

@KirkDybvik Thanks for your attention, Kirk :)

For your questions, here is my opinions:

• possibly consider 2 methods for point-to-polyline. One for "local" distances (like items within sensor range of a car) and one that uses "great circle" distance (like features near the route an airplane would fly).

A: This is a brilliant idea. Actually, the reference line (polyline) is around 500 meters long, and the sensor range of car is about 120 meters. However, we only care about items within sensor range, so it's okay to just calculate a "local" distances as long as it's fast enough to satisfy the real-time needs.

• would cuSpatial require a specified coordinate system in either case?

A: Frenet's frame coordinate is preferred. It has S/L axies, S is the longitude distance from the polyline start point and L is the shortest lateral distance to polyline.

• any special consideration for crossing the +/- 180 degree longitude line? any limitations for accepted northernmost/southernmost latitudes?

A: For lateral distance, left is positive and right negative in the convention of Frenet's frame.

[github-actions]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

[trxcllnt]

Hi @KirkDybvik and @EmilioZhao! We have this implemented as point_to_nearest_polyline, one of the quadtree-based spatial joins. We're working on a version with performance improvements for certain cases, but the current version is fully supported.

As for coordinates and reference frames, the quadtree is agnostic to the coordinate system and supports scaling in construction/querying. I believe this should allow you to transform the results to your desired the coordinate system, but I'm not an expert in this area.

[github-actions]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

[github-actions]

This issue has been labeled inactive-90d due to no recent activity in the past 90 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed.

[harrism]

@EmilioZhao have you tried the cuSpatial quadtree_point_to_nearest_polyline API in cuSpatial?

Does it satisfy this feature request?

[github-actions]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

[harrism]

@KirkDybvik have you tried the cuSpatial quadtree_point_to_nearest_polyline API in cuSpatial?

Does it satisfy this feature request for you?

Reading above, perhaps we need to add ability to change the distance metric and/or coordinate systems used.

[github-actions]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

[github-actions]

This issue has been labeled inactive-90d due to no recent activity in the past 90 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed.

[isVoid]

@EmilioZhao Recently pairwise_point_in_linestring_distance is implemented in 22.10 release. It's underlying algorithm is similar to your "brute force" algorithm description. We might differ in the way how you launch the kernels, though. If possible, perhaps give it a try.

You might use Matrix Multiplication to implement Point to Polyline distance and use advanced GPU acceleration techniques as long as your solution is better than the naive point-to-segment way:)

I'm interested in this way of implementing point-polyline distance. Would you like to elaborate a bit or point us to some readings? Thanks!