Distance to the nearest waypoint along a route

Split the problem into two independent steps, because they need different data structures:

1. Where am I after travelling d? Walk the polyline to find the segment that contains distance d, then interpolate along it.
2. How far is that point from the closest waypoint? A nearest-neighbour query over all waypoints, not just the two ends of the current segment. A route can double back, so the closest waypoint can be one you passed long ago (or one still ahead).

Brute force. For each query, walk the segments from the start, adding up lengths until the running total passes d (O(n)). Then compare the point against every waypoint (O(n)). That is O(n·q) overall. It is correct and worth stating first, but slow when both n and q are large.

Locating the position: prefix sums + binary search. Precompute prefix[i], the distance travelled on reaching waypoint i. prefix is non-decreasing, so i = bisect_right(prefix, d) - 1 is the segment start. With t = (d - prefix[i]) / (prefix[i+1] - prefix[i]) the position is p[i] + t·(p[i+1] - p[i]). Using bisect_right means a run of repeated waypoints (zero-length segments) is skipped automatically, so we never divide by zero. Distances at or beyond the route length clamp to the last waypoint. Negative distances are rejected.

Nearest waypoint: sorted-by-x sweep with pruning. Sort the waypoints by x once. For a query point, binary-search its x and expand left and right at the same time. A side stops as soon as its horizontal gap alone is at least the best distance found so far, since every point further out on that side is at least that far away. On real routes this touches only a few waypoints per query. The worst case is still O(n) (all waypoints share one x). A k-d tree or uniform grid gives the same answer with better guarantees; see Follow-ups.

Invariants.

• prefix[0] = 0 and prefix is non-decreasing. prefix[-1] is the route length.
• For 0 ≤ d < length, prefix[i] ≤ d < prefix[i+1] with prefix[i+1] > prefix[i], so 0 ≤ t < 1.
• In the sweep, best only decreases, and a side is closed only when its next x-gap is ≥ best.

from bisect import bisect_left, bisect_right
from math import hypot

Point = tuple[float, float]


class Route:
    def __init__(self, coordinates: list[Point]) -> None:
        if not coordinates:
            raise ValueError("route needs at least one waypoint")
        self.points = coordinates
        # prefix[i] = distance travelled when reaching waypoint i
        self.prefix = [0.0]
        for (x1, y1), (x2, y2) in zip(coordinates, coordinates[1:]):
            self.prefix.append(self.prefix[-1] + hypot(x2 - x1, y2 - y1))
        # waypoints sorted by x for the nearest-neighbour sweep
        self.by_x = sorted(coordinates)
        self.xs = [p[0] for p in self.by_x]

    @property
    def length(self) -> float:
        return self.prefix[-1]

    def position_at(self, d: float) -> Point:
        if d < 0:
            raise ValueError("distance must be non-negative")
        if d >= self.length:
            return self.points[-1]
        # last waypoint whose prefix <= d; skips zero-length segments
        i = bisect_right(self.prefix, d) - 1
        seg = self.prefix[i + 1] - self.prefix[i]
        t = (d - self.prefix[i]) / seg
        (x1, y1), (x2, y2) = self.points[i], self.points[i + 1]
        return (x1 + t * (x2 - x1), y1 + t * (y2 - y1))

    def nearest_waypoint_distance(self, p: Point) -> float:
        px, py = p
        k = bisect_left(self.xs, px)
        best = float("inf")
        lo, hi = k - 1, k
        # expand outward in x; stop a side once its x-gap alone exceeds best
        while lo >= 0 or hi < len(self.xs):
            if hi < len(self.xs):
                if self.xs[hi] - px >= best:
                    hi = len(self.xs)
                else:
                    qx, qy = self.by_x[hi]
                    best = min(best, hypot(qx - px, qy - py))
                    hi += 1
            if lo >= 0:
                if px - self.xs[lo] >= best:
                    lo = -1
                else:
                    qx, qy = self.by_x[lo]
                    best = min(best, hypot(qx - px, qy - py))
                    lo -= 1
        return best


def nearest_checkpoint_distances(
    coordinates: list[Point], distances: list[float]
) -> list[float]:
    route = Route(coordinates)
    return [
        route.nearest_waypoint_distance(route.position_at(d)) for d in distances
    ]

Let n be the number of waypoints and q the number of queries.

• Build: O(n log n) time (prefix sums are O(n); sorting by x is O(n log n)). O(n) space.
• position_at: O(log n) time, O(1) extra space.
• nearest_waypoint_distance: O(log n + k) time, where k is the number of waypoints inside the x-window that the pruning cannot rule out. This is small on typical routes and O(n) in the worst case.
• All queries: O(n log n + q·(log n + k)) time. O(n + q) space, counting the output.
• Brute force for comparison: O(n·q) time, O(1) extra space.

• coordinates = [(0,0), (4,0), (4,3)], distances = [0, 1, 2, 5, 7, 100] → [0, 1, 2, 1, 0, 0]. At d = 5 you are at (4, 1), which is 1 from (4,0). d = 100 clamps to the end.
• Single waypoint [(5,5)], distances = [0, 3] → [0, 0]. The route has length 0, so every query sits on the only waypoint.
• Route that doubles back: [(0,0), (10,0), (10,1), (-10,1)], d = 21 → position (0, 1). The answer is 1, from (0,0). The current segment's ends are 10 away, so an endpoints-only check gives the wrong answer.
• Repeated waypoint (zero-length segment): [(0,0), (0,0), (2,0)], d = 1 → position (1, 0), answer 1, no division by zero.
• Exactly on a waypoint: [(0,0), (3,4)], d = 5 → 0.
• Midpoint of a diagonal: [(0,0), (3,4)], d = 2.5 → position (1.5, 2), answer 2.5.
• Negative distance → ValueError.
• Randomised check: compare against a brute-force minimum over all waypoints for random routes and distances.

1. Distances arrive sorted (a car streaming its odometer). Replace the binary search with a pointer that only moves forward. Locating becomes amortised O(1) per query, O(n + q) in total. Mention that this assumes monotone input and fall back to bisect otherwise.
2. Guaranteed fast nearest-waypoint queries. Build a k-d tree (O(log n) expected per query) or a uniform grid with cell size near the typical waypoint spacing. With a grid you search rings of cells outward until the ring's minimum distance exceeds the best found. Discuss build cost, memory, and what happens when waypoints are very unevenly spaced.
3. Real GPS coordinates (lat/lon). Segment lengths use haversine (or an equirectangular approximation over short segments). Interpolation along a short segment can stay linear in lat/lon. For the nearest-waypoint search, project to a local metric frame first, or use a spatial index that works on the sphere (S2/H3 cells).
4. Closest point on the route, not the closest waypoint. The question flips to "given a GPS fix, where am I on the route?". Project the point onto each segment (clamp t to [0, 1]) and keep the minimum. Index the segments by bounding box in a grid or R-tree. The along-route distance is prefix[i] + t·len_i. This is map matching, and the natural next step for a navigation team.
5. The route changes on the fly (reroute, appended waypoints). Appending only extends prefix and inserts into the spatial index. A change in the middle invalidates every later prefix value. A Fenwick tree over segment lengths gives O(log n) updates and O(log² n) or O(log n) position lookups.

Mid-level (L4)

• Gets a correct brute force: walks the segments, interpolates, and checks every waypoint.
• Handles distance 0, distances past the end, and a single-waypoint route without crashing.
• Moves to prefix sums + binary search for locating the position once prompted, and states the complexity correctly.

Senior (L5)

• Separates "locate on polyline" from "nearest waypoint" without prompting, and notices that a route that doubles back makes endpoints-only checks wrong.
• Handles zero-length segments and float boundaries carefully, and asks how out-of-range or negative distances should behave.
• Proposes a spatial index (sorted sweep, grid, or k-d tree), explains why its pruning is correct, and gives honest worst-case bounds.

Staff (L6+)

• Connects the problem to real navigation concerns: geodesic distance vs. planar, GPS noise, map matching to the closest point on a segment, and streaming odometer input.
• Weighs index choices for an in-car system (memory, rebuild cost on reroute, uneven waypoint density) and picks one with a reason.
• Discusses incremental updates when the route changes, numeric stability over long routes, and how to test (randomised comparison against brute force, property tests on monotonicity).