Трехмерная трилатерация с использованием заданных расстояний до неизвестных фиксированных точек

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

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

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

P1-P2-Расстояние

  • 1-2-30
  • 2-3-40
  • 1-3-50
  • 1-4-60
  • 2-4-60
  • 3-4-60

Шаг 1: Теперь, как мне рассчитать относительные координаты этих точек?
Я решил, что первая точка идет на 0,0,0, а вторая - на 30,0,0. < br> После этого можно вычислить третьи точки, найдя пересечение двух окружностей из точек 1 и 2 с их расстояниями до точки 3 (50 и 40 соответственно). Как мне сделать это математически? (хотя я взял эти простые числа, чтобы наглядно представить ситуацию). Кроме того, я не знаю, как найти ответ математическим путем. Третья точка находится на отметке 30,40,0 (или 30,0,40, но я проигнорирую это).
Но получение четвертой точки - это не так. так просто. Я думал, что мне нужно использовать 3 сферы для расчета пересечения, чтобы получить точку, но как мне это сделать?

Шаг 2. После того, как я выяснил, как рассчитать этот "простой" пример, я хочу использовать больше неизвестных точек ... Для каждой точки существует минимум 1 заданное расстояние до другой точки, чтобы "связать" ее с другие. Если координаты не могут быть вычислены из-за его степеней свободы, я хочу игнорировать все возможности, кроме одной, которую я выбираю случайным образом, но с учетом известных расстояний.

Шаг 3: Последний этап должен быть таким: каждое измеренное расстояние немного неверно из-за реальной жизненной ситуации. Таким образом, если для данной пары точек существует более 1 расстояния, расстояния усредняются. Но из-за неточных расстояний могут возникнуть трудности с определением точного (относительного) местоположения точки. Поэтому я хочу усреднить различные возможные местоположения до «оптимального».

Можете ли вы помочь мне шаг за шагом решить мою задачу?


3d math euclidean-distance triangulation trilateration
person JStaxton    schedule 10.02.2011    source источник
comment
У вас есть расстояния между всеми парами точек? То есть, предположим, у вас есть 4 точки A, B, C и D, гарантированно ли у вас есть расстояния AB, BC, CD, DA, AC, BD?   -  person Jacob    schedule 11.02.2011
comment
нет, это не гарантируется. Когда точки не могут быть определены (из-за отсутствия одного или нескольких расстояний), я хочу выбрать координаты случайным образом, но с учетом заданных расстояний (гарантируется минимум одно расстояние.   -  person JStaxton    schedule 11.02.2011

Ответы (3)


arrow_upward
1
arrow_downward

Вам необходимо использовать тригонометрию, а именно «правило косинусов». Это даст вам углы треугольника, что позволит вам решить 3-ю и 4-ю точки.

Правила гласят, что

c^2 = a^2 + b^2 - 2abCosC

где a, b и c - длины сторон, а C - угол, противоположный стороне c.

В вашем случае нам нужен угол между 1-2 и 1-3 - угол между двумя линиями, пересекающимися в точке (0,0,0). Это будет 90 градусов, потому что у вас треугольник 3-4-5, но давайте докажем:

50^2 = 30^2 + 40^2 - 2*30*40*CosC
CosC = 0
C = 90 degrees

Это угол между линиями (0,0,0) - (30,0,0) и (0,0,0) - точка 3; протяните вдоль этой линии длину стороны 1-3 (то есть 50), и вы получите вторую точку (0,50,0).

Найти свою 4-ю точку немного сложнее. Самый простой алгоритм, который я могу придумать, - это сначала найти компонент (x, y) точки, а оттуда компонент z просто использовать Пифагора.

Учтите, что на плоскости (x, y, 0) есть точка, которая находится прямо «под» вашей точкой 4 - назовите эту точку 5. Теперь вы можете создать 3 прямоугольных треугольника 1-5-4, 2-5- 4 и 3-5-4.

Вам известны длины 1-4, 2-4 и 3-4. Поскольку это прямоугольные треугольники, отношение 1-4 : 2-4 : 3-4 равно 1-5 : 2-5 : 3-5. Найдите точку 5, используя тригонометрические методы - «правило синуса» даст вам углы между 1-2 и 1-4, 2-1 и 2-4 и т. Д.

«Правило синуса» гласит, что (в прямоугольном треугольнике)

a / SinA = b / SinB = c / SinC

Итак, для треугольника 1-2-4, хотя вы не знаете длины 1-4 и 2-4, вы знаете соотношение 1-4 : 2-4. Точно так же вы знаете отношения 2-4 : 3-4 и 1-4 : 3-4 в других треугольниках.

Я оставлю вас решать пункт 4. Как только у вас будет эта точка, вы можете легко решить компонент z 4 с помощью пифагора - у вас будут стороны 1-4, 1-5, а длина 4-5 будет равна компонент z.

person Kirk Broadhurst    schedule 11.02.2011

arrow_upward
1
arrow_downward

Сначала я предполагаю, что вы знаете расстояния между всеми парами точек.

Как вы говорите, вы можете выбрать одну точку (A) в качестве начала координат, сориентировать вторую точку (B) вдоль оси x и разместить третью точку (C) вдоль плоскости xy. Вы можете найти координаты C следующим образом:

given: distances ab, ac, bc
assume
A = (0,0)
B = (ab,0)
C = (x,y)  <- solve for x and y, where:
  ac^2 = (A-C)^2 = (0-x)^2 + (0-y)^2 = x^2 + y^2
  bc^2 = (B-C)^2 = (ab-x)^2 + (0-y)^2 = ab^2 - 2*ab*x + x^2 + y^2

-> bc^2 - ac^2 = ab^2 - 2*ab*x
-> x = (ab^2 + ac^2 - bc^2)/2*ab
-> y = +/- sqrt(ac^2 - x^2)

Чтобы это работало точно, вам следует избегать случаев, когда точки {A,B,C} находятся на прямой линии или близко к ней.

Решение для дополнительных точек в 3-м пространстве аналогично - вы можете расширить формулу Пифагора для расстояния, отменить квадратичные элементы и решить полученную линейную систему. Однако это не поможет вам напрямую с шагами 2 и 3 ...

К сожалению, я также не знаю точного решения для шагов 2 и 3. Ваша общая проблема, как правило, будет как чрезмерно ограниченной (из-за конфликтующих зашумленных расстояний), так и недостаточно ограниченной (из-за пропущенных расстояний).

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

person comingstorm    schedule 14.02.2011

arrow_upward
0
arrow_downward

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

Я сделал это с помощью радиомодулей Nanotron, у которых есть возможность определения дальности.

С Уважением

person Stefan    schedule 13.02.2011