Compute nearest index within threshold after walking distances

You are given: (1) points: a list of N 2D coordinates in miles, points[i] = [x_i, y_i], ordered; (2) distances: a list of M nonnegative floats (miles); and (3) a threshold t > 0 (miles). Starting at points[0], walk along the polyline connecting points[0] -> points[1] -> ... -> points[N-1]. For each step value d in distances, advance exactly d miles along this polyline from the current position, continuing across segments as needed; if the step would pass the final vertex, clamp the position to points[N-1]. After each step, determine whether there exists any index j such that the Euclidean distance between the current position and points[j] is <= t. If such points exist, output the index j of the nearest point (break ties by choosing the smallest index); otherwise output None. Return a list of length M with these results. Implement an efficient NumPy-based solution that handles large N and M (e.g., up to 1e 5), using cumulative segment lengths and within-segment interpolation; avoid naive O(N*M) scanning when possible. Specify time and space complexity and include tests for edge cases (d = 0, repeated points, zero-length segments, empty distances).

Nearest polyline vertex after walking step distances with threshold

You are given two tables:

1. points: an ordered list of 2D coordinates (in miles) that define a polyline.
2. distances: an ordered list of nonnegative step distances (in miles).

The polyline is defined by walking from the smallest point_idx to the largest: points[0] -> points[1] -> ... -> points[N-1]. Consecutive points are connected by straight-line segments.

You start at points[0]. For each row in the distances table, ordered by step_id, you:

• Move forward along the polyline by exactly step_distance miles from your current position.
• If this movement would go past the final point, clamp your position to the last point in the polyline.
• After moving, compute the Euclidean distance from your current position to every point in the points table.
• If there is at least one point whose distance is less than or equal to a threshold t = 1.5 miles, choose the nearest such point; if there is a tie, choose the smallest point_idx. Otherwise, return NULL for that step.

Write a single SQL query that returns, for each step_id, the index of the nearest point within the threshold or NULL if no point is within 1.5 miles. Use window functions and set-based operations (no procedural loops).

Assume point_idx values are consecutive integers starting at 0 and define the walking order along the polyline.

Table points

column	type	constraints
point_idx	INT	PRIMARY KEY
x	DECIMAL(10,2)	NOT NULL
y	DECIMAL(10,2)	NOT NULL

Sample data:

point_idx	x	y
0	0	0
1	3	0
2	3	4
3	8	4

Table distances

column	type	constraints
step_id	INT	PRIMARY KEY
step_distance	DECIMAL(10,2)	NOT NULL

Sample data:

step_distance	step_id
2	1
4	2
3	3
5	4

Expected output

For each step_id, after walking cumulatively along the polyline by the given step distances (clamped at the final point), return the index of the nearest point within 1.5 miles. If no point is within 1.5 miles of the current position, return NULL. For the sample data, the positions after each step are approximately (2,0), (3,3), (5,4), and (8,4), leading to nearest points 1, 2, NULL, and 3 respectively.

nearest_point_idx	step_id
1	1
2	2
NULL	3
3	4

Hints

1. First compute segment lengths and cumulative distances along the polyline using window functions so you can map each cumulative walked distance to a specific segment and an offset within it.
2. Interpolate the (x, y) position for each step on the appropriate segment, then cross join to points and use a window function to pick the nearest point within the threshold for each step.