I have a test task. It sounds like this. Write 2 functions. The first function must contain a secret point, let's say [ 12, 45, 99 ]. This point is in 3D space and its coordinates can only take integer values from 0 to 100. This function takes an arbitrary point as an argument and calculates the distance from the secret point to the given one.
const secretPoint = [12, 45, 99];
export default function getDistance(manualPoint) {
if (manualPoint.length !== 3) {
console.error("Wrong manualPoint!");
}
let sum = 0;
for (let i = 0; i < manualPoint.length; i ) {
const difference = secretPoint[i] - manualPoint[i];
sum = Math.pow(difference, 2);
}
const result = Math.sqrt(sum);
return result;
}
The second function must find the coordinates of the SECRET point in the least number of calls to the first function.
And here's the problem, because I don't know how to do it right. It is logical to assume that the fastest search on a sorted array of data is a binary search. In our case, this is suitable, because. we are looking for 3 coordinates ranging from 0 to 100.
In order not to complicate my task, I decided to first write a function that would search for a coordinate in only 1 plane.
Here is how I tried to do it. I have a minimum value - 0 and a maximum value - 100.
So we call the first function with the given values [0 0 0] / [0 0 100]
And we compare the result. If in the first case the distance to the secret point is greater than in the second case. So the desired coordinate 0 0 Z lies in the range from 50 to 100. And we continue in the same way to reduce the search area for the point.
This function is incorrect, I know. But somehow sometimes it gives me correct values, but sometimes there is an error by 1 or 2.
const secretPoint = [12, 45, 99];
function binarySearch() {
let left = 0;
let right = 100;
let mid;
while (left <= right) {
mid = (right - left) / 2 left;
if (getDistance([0, 0, left]) < getDistance([0, 0, right])) {
console.log(Math.floor(mid));
right = mid - 1;
} else {
console.log(Math.floor(mid));
left = mid 1;
}
}
return -1;
}
binarySearch();
Output is like this: 50 75 88 94 97 99
So now it works fine somehow, but let's change secretPoint to
const searchPoint = [12, 45, 28];
and Output is like this: 50 24 37 30 27 29
So it's wrong.
CodePudding user response:
The points at a given distance from a center lie on a sphere with that radius. Two centers define two spheres, which intersect on a circle. A third sphere determines two points on the circle. And finally, a fourth point is necessary to discriminate between these two.
So you essentially need to implement an algorithm for the intersections of three spheres.
The equation of a sphere is quadratic in X, Y, Z with a special form. By subtracting two pairs of equations, you obtain two linear equations which are those of two planes. The intersection of these planes is a straight line. By writing the parametric equation of the line, it is easy to obtain the intersection points with one of the spheres.