Построить географическую карту из треугольных точек на основе расстояния

Question

У меня есть 5 {x, y} точек, случайно расположенных на сетке

Каждая из точек не знает {x, y} координаты других точек

Каждая из точек знает расстояние каждой из других точек от их позиции {x, y}

Каждая из точек обменивается этой информацией о расстоянии с каждой другой точкой

Таким образом, каждая точка знает каждое расстояние каждой другой точки

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

Например, точка 1 может вычислить следующие треугольники: 1-2-3, 1-2-4, 1-2-5, 1-3-4, 1-3-5, 1-4-5 и используяданные о расстоянии, полученные из других точек, могут также рассчитываться 2-3-4, 2-3-5, 2-4-5, 3-4-5

Я хотел бы построить картурасположение каждой другой точки относительно одной точки

Как мне поступить так?Я предполагаю, что это будет какой-то алгоритм триангуляции, но в основном он вычисляет местоположение точки из трех других точек, а не наоборот, где обнаруживаются координаты других точек {x, y}, основываясь только на информации о расстоянии..

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

В конечном итоге я хотел бы, чтобы каждая точка заканчивалась координатами {x, y} каждой другой точки относительно себя

Answer 1

Вы знаете расстояние от одной точки до другой, dij.Таким образом, точка 2 лежит в окружности центральной точки 1 и радиус = d12.Точка 3 лежит в окружности центральной точки 1 и R = d13, а также в другой окружности центральной точки 2 и R = d23.

См. Эту картинку:

Для простоты я установил точку 2 на оси X.

Как видите, точка 3 находится на пересечении двух кумуляций, центрированных в P1 и P2.Есть второе пересечение, P3a.Давайте выберем ту, которая идет вверх, и продолжим.

Для P4 мы можем использовать три окружности, центрированные в P1, P2 и P3.Мы снова получаем два решения.

Тот же процесс можно проделать с остальными пунктами.Для Pn у вас есть n-1 окружностей.
Я уверен, что вы можете найти математику для пересечения окружности с окружностью.

Необходимо отметить некоторые замечания:
1) Построение проще, если вы сначала отсортируете точки по расстояниюдо P1.
2) Не все расстояния порождают решение.Например, увеличьте d13 и нет пересечения между двумя окружностями для P3.Или увеличьте d14, и теперь три окружности не пересекаются только в двух ожидаемых точках 4 и 4a.
3) Этот факт можно переоценить, учитывая среднее значение пересечений и расстояние от каждого решения до этого среднего.Вы можете установить допуск на этих расстояниях и сказать, является ли среднее значение решением, а некоторые dij неверны.Поскольку возможны два решения, вы должны рассмотреть два средних.
4) Две возможные триангуляции симметричны по оси X в случае, который я нарисовал.

Реальное решение получается вращением вокруг P1.Для расчета угла поворота вам понадобятся {x,y} координаты другой точки.