Постройте географическую карту из точек треугольника в зависимости от расстояния
У меня есть 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} обнаруживаются на основе только информации о расстоянии .
Я попытался построить два возможных треугольника для каждых трех точек треугольника, а затем повернуть их в фиксированной известной точке, чтобы попытаться выровнять их, но я думаю, что этот путь приведет к слишком большому количеству возможностей и ошибок.
В конечном итоге я хотел бы, чтобы каждая точка имела координаты {x, y} каждой другой точки относительно самой себя.
Ответы 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} другой точки.
@billysdomain Симметрия присутствует всегда, пока вы не используете координаты еще двух точек. Это означает, что до тех пор, пока у вас не будет треугольника, координаты которого известны заранее, и вы не используете этот треугольник для решения как симметрии, так и вращения.
Итак, единственный возможный способ решить проблему симметрии - ввести известную точку, любое движение любой из точек в любой последовательности не может помочь?
Любое движение - это просто новые расстояния и, следовательно, новая триангуляция. Вы снова на старте. Без известных точек симметрия сохраняется.
Это здорово, большое спасибо. Если бы одна или несколько точек переместились, а точка P1 оставалась неизменной, смогу ли я определить, какая из двух возможностей верна?