How to find coordinates of dot ( x, y, z) if you have only function which returns distance between S-CodePudding

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.