I am working with spherical coordinates (lon/lat, haversine metric) and am trying to find an efficient way to find all points that are both close to a geodetic line and their projection w.r.t the line is on the line. I have seen several libraries which can do spatial indexing or perform actions on geometries such as calculating intersection and whether a geometry contains another geometry but I did not find a library which can do spatial indexing and actions on geometry in spherical coordinates. Therefore, I tried something by myself. Using scikit-learn's BallTree for spatial indexing and querying of points with the haversine metric, I did the following:
- Inputs: points, line_point1, line_point2, distance_threshold
- Perform spatial indexing on points
- find points on line in intervals of at most distance_threshold by SLERPing between line_point1 and line_point2
- for each interpolated point including line_point1 and line_point2 do a radius query of sqrt(2)*distance_threshold (in order to promise no false negatives). Remove duplicates and obtain result in query_points
- remove all points in query_points that are either farther than distance_threshold from the line or their projection w.r.t the line is not on the line. Can be done by simple closed-form solutions.
I would like to know if there exists a more efficient and simple solution that does not require re-inventing the wheel.
I tested my implementation on 10000 coordinates uniformly distributed around the equator between both lon/lat -1 to 1. I attached an image of the output I received. In cyan is the line itself, in blue are points close to the line and in orange-brown are the points which are not close to the line.
