Articles tagged: gis

Fast Interception of a Path of Geodesic Segments on the Earth Spheroid

Here I describe a fast filter-and-refine algorithm for finding interceptions of a sequence of Earth geodesic segments by a set of points, such as between a GPX file’s route and waypoints, which I developed last year for my open source project CoursePointer. [1] Combining this filter with Karney’s geodesic interception algorithm [9] yields precise points of interception while being simpler to implement than an R-tree—and probably more efficient for some common use cases, at the tradeoff of order of growth.

I’ve been unable to find this exact approach documented elsewhere, including by asking AI to help me search for prior art. If you’re aware of an earlier description that I’ve missed please email me and I’ll update this post!

Problem Statement and Background

Given a path as a sequence of geodesic segments on the WGS84 spheroid Earth model, plus a set of points on the spheroid, how can we quickly find where any of the points “intercept” the path within some threshold distance? [2]

Concretely, I wrote CoursePointer to convert GPX routes/tracks and waypoints into Garmin FIT course files and course points. [3] Waypoints and course points have different semantics: A waypoint is just a point somewhere on the spheroid, given as a latitude and longitude, which may or may not be located along a route or track in the same GPX file. A course point, on the other hand, is specifically associated with—and located at a certain distance along—a course. That distance is needed as part of its FIT representation.

So to generate course points, my program must answer the question: “Does this route ever get within e.g. 35 m of that waypoint? And if so, how far along the overall route does that happen?”

A 2D projection of a route alongside two waypoints in the vicinity. A dashed line is drawn between the points and the nearest position along the route. Point A is pictured close to the route, while point B is much farther away.

Figure 1: A route made of multiple segments, and some waypoints. Waypoint A is near to the route, so it should be interpreted as a course point along it; Waypoint B is far from the route and should not be considered a course point.

Read more…

Pagination