A long, snake-like inspection arm curls into tight spaces. Its links are thick bars, so two of them collide when they come too close. The arm is planar with n links, its base at the origin (x right, y up). Link i has length lengths[i] and joint angle angles[i] (radians, counter-clockwise). The angles are relative: angles[0] is measured from the +x axis, every later one from the direction of the link before it.
Model link i as the straight segment from the start of link i to its end (the base is the start of link 0). The distance between two links is the shortest distance between any point of one segment and any point of the other; it is 0 when they cross or touch.
Two links that meet at a joint (i and i + 1) always touch there, so they are never checked. Every other pair i < j with j >= i + 2 collides when its distance is less than clearance.
Write self_hits(lengths, angles, clearance) that returns the list of colliding pairs (i, j), sorted by i and then by j.
Examples
Input: lengths = [2, 1, 2.5], angles = [0, math.pi / 2, math.pi / 2 + 0.6], clearance = 0.1
Output: [(0, 2)]
Explanation: the joints are (0, 0), (2, 0), (2, 1), (-0.06, -0.41).
Link 2 comes back down and crosses link 0.
Input: lengths = [2, 0.6, 1.5], angles = [0, 2.6, 0.4], clearance = 0.25
Output: []
Explanation: link 2 starts at (1.49, 0.31) and runs away from link 0;
the closest the two get is 0.309, at that starting point.
Input: lengths = [2, 0.6, 1.5], angles = [0, 2.6, 0.4], clearance = 0.35
Output: [(0, 2)]
Input: lengths = [1.0, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4], angles = [0, 1.3, 1.3, 1.3, 1.3, 1.3, 1.3],
clearance = 0.3
Output: [(0, 4), (0, 5), (1, 5), (1, 6), (2, 6)]
Constraints
1 <= n <= 60
Goals
- Model each link as a line segment between two joints
- Compute the shortest distance between two segments, crossings included
- Check every pair of non-neighbouring links