Как получить координаты точки, зная координаты других 3-х, и расстояние между ними?

Question

[lundoger]

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

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

Например, для произвольно сгенерированной точки a(10, 6, 19) и переданной в функцию точки
b(10, 6, 9), результат работы функции будет следующим: f(a, b) = 10
Далее имплементируйте сам алгоритм для задания. Алгоритм должен находить координаты
произвольно сгенерированной точки при наименьшем количестве вызовов функции f.

Я читал про триангуляцию по 4 точкам, про решение системы уровнений, про поиск растояния между точками по функции (x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2 = d^2, это я в функцию добавил, но что мне с решениями этих уровнений я немогу понять, помогите...

const MAX_NUMBER = 100
const MIN_NUMBER = 0
let probes = []

export const getRandomNumber = (min, max) => {
	return Math.floor(Math.random() * (max - min + 1)) + min;
};

export const getRandomCoordinates = () => {
	return {
		x: getRandomNumber(MIN_NUMBER, MAX_NUMBER),
		y: getRandomNumber(MIN_NUMBER, MAX_NUMBER),
		z: getRandomNumber(MIN_NUMBER, MAX_NUMBER),
	}
};

export const createAsteroid = () => {
	return getRandomCoordinates()
};

export const getDistanceBetweenPoints = (point1, point2) => {
	const { x: x1, y: y1, z: z1 } = point1;
	const { x: x2, y: y2, z: z2 } = point2;

	const distance = Math.sqrt(
		Math.pow(x2 - x1, 2) +
		Math.pow(y2 - y1, 2) +
		Math.pow(z2 - z1, 2)
	);

	return distance;
}

const addProbeAndGetDistance = (probe, asteroid) => {
	probes.push(probe)
	return getDistanceBetweenPoints(probe, asteroid)
}

export const findAsteroidLocation = () => {
	const asteroid = createAsteroid()

	const d1 = addProbeAndGetDistance({ x: 0, y: 0, z: 0 }, asteroid)
	const d2 = addProbeAndGetDistance({ x: 0, y: 0, z: 1 }, asteroid)
	const d3 = addProbeAndGetDistance({ x: 0, y: 1, z: 0 }, asteroid)
	const d4 = addProbeAndGetDistance({ x: 1, y: 0, z: 0 }, asteroid)
}

Comments

[Adamos]

Если задача стоит так, как сформулировано в заголовке (то есть даны координаты трех точек, и нужно найти координаты четвертой, зная расстояния от нее до этих точек), то это задача пересечения трех сфер (трилатерация).
Триангуляция - это если знаешь углы, а не расстояния.

[ksnk]

Ну, тупо же. Задача решается почти на коленке, без функции расстояния.
Мат. рассуждения:
Берем 2 точки, рисуем вокруг них сферу с указанным расстоянием между этими точками и нужной нам. Пересекаются сферы в окружности. Ее формула выводится на бумажке. - тоже формула.
Проектируем перепендикулярно плоскости третью точку в плоскость , в которой располагается окружность, пересчитываем расстояние и получаем плоскую картинку про пересечение 2-х окружностей. Не более 2х ответов.

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

[lundoger]

Adamos, теперь буду знать, благодарю!

Answer 1

[Rsa97]

Первую тестовую точку берём (0, 0, 0)
Получаем расстояние d₀
[1] (x - 0)² + (y - 0)² + (z - 0)² = x² + y² + z² = d₀²
Возьмём вторую точку (1, 0, 0)
Получаем расстояние d₁
[2] (x - 1)² + (y - 0)² + (z - 0)² = x² - 2x + 1 + y² + z² = d₁²
2x - 1 = d₀² - d₁²
x = (d₀² - d₁² + 1) / 2
Аналогично, по точкам (0, 1, 0) и (0, 0, 1) получаем координаты y и z.

Comments

[lundoger]

то-есть сейчас у меня функция подсчета длинны неправильно считает, так как раскрывает (x - число)^2 не по формуле а просто считает? И еще вопрос, если d0 и d1 я могу использовать для получения x, то для y - d1 и d2, z - d2 и d3? И для получения правильной координаты нужно правильно написать функцию и вычесть от первой длинны вторую?

[lundoger]

спустя часов 6 беспрерывных попыток сделать эту задачу я ее закончил наконец-то, хотя я все еще не совсем понял почему она так решается.
Спасибо большое за то что помог, попробую еще чуть лучше понять почему все именно так, но теперь хотя бы спать лягу спокойно

[Алексей Ярков]

lundoger, ты хоть выложи рабочий код ))

[Rsa97]

lundoger, 1. Перед тем, как программировать, стоит разобраться с формулами. Часто бывает так, что час-другой аналитических преобразований превращают трёхэтажную формулу с циклическим элементом в пару линейных действий или сразу в константу.
2. В данном случае решение строится на том, что из равенства [2] вычитается равенство [1]. В результате, если контрольная точка смещалась только по одной координате, то только эта координата и остаётся в результирующем равенстве.
3. В целом, алгоритм выглядит примерно так (псевдокод):

function distance(p1, p2) {
    return sqrt((p1.x - p2.x)^2 + (p1.y - p2.y)^2 + (p1.z - p2.z)^2)
}
d0 := distance(target, {x: 0, y: 0, z: 0})
dx := distance(target, {x: 1, y: 0, z: 0})
dy := distance(target, {x: 0, y: 1, z: 0})
dz := distance(target, {x: 0, y: 0, z: 1})
x := (d0^2 - dx^2 + 1) / 2
y := (d0^2 - dy^2 + 1) / 2
z := (d0^2 - dz^2 + 1) / 2
locatedTarget := {x: x, y: y, z: z}

[lundoger]

Алексей Ярков, Да, забыл ночью добавить, я немножко ее облагородил так как ночью я такого понаписовал в попытках заставить функцию работать)

const MAX_NUMBER = 100
const MIN_NUMBER = 0
let probes = []

export const getRandomNumber = (min, max) => {
	return Math.floor(Math.random() * (max - min + 1)) + min;
};

export const getRandomCoordinates = () => {
	return {
		x: getRandomNumber(MIN_NUMBER, MAX_NUMBER),
		y: getRandomNumber(MIN_NUMBER, MAX_NUMBER),
		z: getRandomNumber(MIN_NUMBER, MAX_NUMBER),
	}
};

export const createAsteroid = () => {
	return getRandomCoordinates()
};

export const getDistanceBetweenPoints = (point1, point2) => {
	const { x: x1, y: y1, z: z1 } = point1;
	const { x: x2, y: y2, z: z2 } = point2;

	//Я просто оставлю эту формулу тут что бы кто-то немножко повеcелел от увиденного
	// Что бы долго не вникать я расписал формулу (a- b)^2 как a^2 - 2ab + b^2 
	// const distance = Math.pow(x1, 2) - 2 * x1 * x2 + Math.pow(x2, 2) + Math.pow(y1, 2) - 2 * y1 * y2 + Math.pow(y2, 2) + Math.pow(z1, 2) - 2 * z1 * z2 + Math.pow(z2, 2)


	const distance = Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2) + Math.pow(z1 - z2, 2)

	return Math.sqrt(distance);
}

const addProbeAndGetDistance = (probe, asteroid) => {
	probes.push(probe)
	return getDistanceBetweenPoints(asteroid, probe)
}


export const findAsteroidLocation = () => {
	const asteroid = createAsteroid()

	const d0 = addProbeAndGetDistance({ x: 0, y: 0, z: 0 }, asteroid)
	const dx = addProbeAndGetDistance({ x: 1, y: 0, z: 0 }, asteroid)
	const dy = addProbeAndGetDistance({ x: 0, y: 1, z: 0 }, asteroid)
	const dz = addProbeAndGetDistance({ x: 0, y: 0, z: 1 }, asteroid)

        //Тут так как у меня вернулись не квадраты расстояния, я рассписал d0 ^2- dn^2 как (d0 - dn) * (d0 + dn)
	const asteroid_x = Math.round(((d0 - dx) * (d0 + dx) + 1) / 2)
	const asteroid_y = Math.round(((d0 - dy) * (d0 + dy) + 1) / 2)
	const asteroid_z = Math.round(((d0 - dz) * (d0 + dz) + 1) / 2)

	console.log(asteroid);
	console.log(`x: ${asteroid_x}, y: ${asteroid_y}, z: ${asteroid_z}`);

	const result = { x: asteroid_x, y: asteroid_y, z: asteroid_z }

	return { probes, location: result }
}

[lundoger]

Rsa97, Спасибо большое за объяснения, теперь намного понятнее стало, я в итоге сделал все почти так как ты и написал вот только формулу по получению расстояния расписывал в ручную как a^2 - 2ab + b^2) потому что с ее изначальным видом у меня что то неполучалось, сегодня переписал все более просто так как в твоем примере. Очень благодарен

[Adamos]

lundoger, раскрывать бином Ньютона, собственно, незачем, только ухудшает читаемость.
Math.pow для степени 2 - просто смешно.
(a - b) * (a - b) компьютеру не сложно посчитать, а человеку - прочитать.

[lundoger]

Adamos, а почему Math.pow() тебе не понравился, интересно узнать

[Adamos]

lundoger, я "крестовик" и не вызываю функции, если в этом нет необходимости.
А уж функцию, которая внутри себя определяет, что ее вызвали зря - и возвращает то же самое умножение...