Underground there is no satellite signal, so a mine's inspection robot finds itself with three radio beacons fixed at known places beacons = [(x1, y1), (x2, y2), (x3, y3)] (metres, x to the right, y up). Timing each beacon's reply gives the robot's distance to it: ranges = [r1, r2, r3]. Finding a position from distances is trilateration.
Each range says the robot is on a circle: (x - x_i)^2 + (y - y_i)^2 = r_i^2. With perfect ranges the three circles meet in exactly one point. Real ranges are a little off and the circles miss each other, so the robot uses this definition instead: its position is the point P where the three quantities
are all equal. (With perfect ranges they are all 0, at the true position.)
Write trilaterate(beacons, ranges) that returns that point (x, y). If the three beacons lie on one straight line, no such single point exists in general: return None. Beacon coordinates are whole numbers, so this test can be exact.
Examples
Input: beacons = [(0, 0), (10, 0), (0, 8)], ranges = [5, math.sqrt(65), 5]
Output: (3.000000000000001, 4.0)
Explanation: (3, 4) is 5 m from (0, 0), sqrt(49 + 16) m from (10, 0) and 5 m from (0, 8).
Input: beacons = [(0, 0), (10, 0), (0, 8)], ranges = [5.1, 8.0, 4.9]
Output: (3.1005, 4.125)
Explanation: at (3.1005, 4.125) each squared distance minus its squared range is 0.61873.
Input: beacons = [(0, 0), (5, 5), (10, 10)], ranges = [3, 4, 9]
Output: None
Constraints
- answers are compared with a tolerance of
1e-6; do not round
Goals
- Write a range measurement as the equation of a circle
- Turn three circle equations into two linear equations and solve them
- Detect beacons on one line, where the position cannot be fixed