Какой алгоритм использовать для нахождения точки?

Question

[DashaPoliazzz]

Вам необходимо найти некоторую неизвестную, заранее заданную точку в трехмерном пространстве,
наименьшее количество попыток, используя только функцию, которая может вернуть расстояние от
любой передаваемой вами к ней точки к искомой неизвестной точке.

Для решения задачи сначала реализуйте функцию f, которая, принимая координаты любой
какой точки s(x, y, z), возвращает расстояние между этой точкой и условно неизвестной, заранее

произвольно сгенерированной вами точкой r(x, y, z), где x, y, z могут быть целыми числами между
0 и 100.
Например, для произвольно сгенерированной точки r(0, 0, 10) и переданной в функцию точки
s(0, 0, 0), результат работы функции будет следующим:
f(s) = 10 // расстояние между s(0, 0, 0) и r(0, 0, 10) равно 10
Далее имплементируйте сам алгоритм для задания. Алгоритм должен находить координаты
произвольно сгенерированной точки при наименьшем количестве вызовов функции f.

У меня вместо алгоритма рандомизатор, это все до чего я додумался. Помогите.

const pointToFound = {
  x: 12,
  y: 9,
  z: 76,
};

let attemts = 0;
let isXFound = false;
let isYFound = false;
let isZFound = false;

const pointHistory = [];

const getRandomPoint = () => {
  return {
    x: isXFound ? isXFound : Math.floor(Math.random() * 101), 
    y: isYFound ? isYFound : Math.floor(Math.random() * 101),
    z: isZFound ? isZFound : Math.floor(Math.random() * 101),
  };
};

const getDifference = (point, pointToCompare) => {
  return {
    x:
      Math.max(point.x, pointToCompare.x) - Math.min(point.x, pointToCompare.x),
    y:
      Math.max(point.y, pointToCompare.y) - Math.min(point.y, pointToCompare.y),
    z:
      Math.max(point.z, pointToCompare.z) - Math.min(point.z, pointToCompare.z),
  };
};

const condition = !isXFound && !isYFound && !isZFound;

while (condition) {
  const point = getRandomPoint();

  const difference = getDifference(point, pointToFound);
  pointHistory.push(point);

  attemts += 1;

  if (isXFound && isYFound && isZFound) {
    console.log("Total attempts: ", attemts);
    console.log(point);
    break;
  }

  if (difference.x === 0 && !isXFound) {
    isXFound = point.x;
  }

  if (difference.y === 0 && !isYFound) {
    isYFound = point.y;
  }

  if (difference.z === 0 && !isZFound) {
    isZFound = point.z;
  }
}

console.log(pointHistory);

Comments

[Василий Банников]

Вам необходимо найти некоторую неизвестную, заранее заданную точку в трехмерном пространстве,
наименьшее количество попыток, используя только функцию, которая может вернуть расстояние от
любой передаваемой вами к ней точки к искомой неизвестной точке.

Самое очевидное - триангуляция. Гарантированно за 4 измерения найдёшь искомую точку

[Akina]

Вульгарнейшая задачка на решение системы из трёх квадратных уравнений с тремя неизвестными. Стыдно должно быть...

Отойди от компа. Возьми бумагу и карандаш. И реши задачу аналитически. И только потом - запрограммируй полученное решение.

[DashaPoliazzz]

Akina, да стыдно не то слово

[mayton2019]

Эту задачу решает GPS приемник несколько раз в минуту.

[Сергей П]

mayton2019, у GPS чуть более сложная задача. Там не известны абсолютные расстояния от спутников до приёмника, приёмнику приходится учитывать эффекты, связанные с терией относительности, вычислять координаты спутников по элементам орбиты...
А тут всё просто.

Answer 1

[Wataru]

Вам уже подсказали: Триангуляция по 4 точкам.

При чем не надо решать систему в общем виде. Если вы возьмете ваши 4 точки как (0,0,0) и (0,0,1), (0,1,0) и (1, 0, 0) то вы уже можете найти координаты искомой точки, не решая даже квадратных уравнений или систем.

Например, для первых двух точек:

x^2+y^2+z^2 = d1^2
x^2+y^2+(z-1)^2 = d2^2

Вычтите одно уравнение из другого, сократите все сокращаемое, поделите на 2 и в одно арифмитическое действие найдете z.

Точно также можно найти x и y, рассматривая другие пары уравнений.