A museum guide robot turns each laser scan into a few straight walls, so it can compare them with its floor plan. The scan is a list of points in the order the laser swept them (x, y in metres). A wall is a run of consecutive points, given by its first and last index; neighbouring walls share their end point. The list of all those end indices is the scan's breakpoints.
The distance of point k from the chord (i, j) is the perpendicular distance from points[k] to the straight line through points[i] and points[j] (or simply the distance to points[i] if those two points are equal).
Split. Start with the one piece (0, n - 1). For a piece (i, j) with at least one point between its ends, find the point k with i < k < j that is farthest from the chord (i, j) (on a tie, the smallest k). If that distance is greater than threshold, k becomes a breakpoint and the pieces (i, k) and (k, j) are split in the same way. Otherwise the piece is final.
Merge. Sort the breakpoints b_0 < b_1 < ... < b_m from the split. Walk the inner ones, b_1 to b_{m-1}, from left to right, keeping a list that starts with b_0. For each b_t, let a be the last breakpoint kept so far and c = b_{t+1}: if every point strictly between a and c is at most threshold from the chord (a, c), drop b_t; otherwise keep it. Finally keep b_m.
Write split_merge(points, threshold) that returns the kept breakpoints in increasing order.
Examples
Input: points = [(0, 3), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (3, 0)], threshold = 0.1
Output: [0, 3, 6]
Explanation: a corner at (3, 3): two walls, points 0..3 and 3..6.
Input: points = [(0.0, 3.2), (1.1, 3.2), (1.8, 3.1), (3.0, 3.1), (4.2, 3.1), (4.8, 2.8), (4.9, 2.0), (5, 1.2)], threshold = 0.25
Output: [0, 5, 7]
Explanation: point 4 is 1.467 from the chord (0, 7), so it splits first; then point 5 is 0.437
from the chord (4, 7). Breakpoints [0, 4, 5, 7]. In the merge, points 1..4 are all within 0.249
of the chord (0, 5), so 4 is dropped.
Input: points = [(0, 0), (1, 0.5), (2, 0)], threshold = 0.5
Output: [0, 2]
Explanation: point 1 is exactly 0.5 from the chord, which is not greater than the threshold.
Constraints
1 <= len(points) <= 2000;threshold >= 0- the scans in the tests have no distance within
1e-9ofthresholdexcept where it is exact, as in the third example
Goals
- Split an ordered scan where it bends away from the chord between the ends
- Repeat the split on each piece until every piece is straight enough
- Merge neighbouring pieces that turn out to lie on one line