Алгоритм трилатерации для n очков

27

Мне нужно найти алгоритм, который может рассчитать центроид A (он же центр тяжести, геометрический центр, центр масс) по фигуре, где окружности T1, T2, T3, T4, T5, .., Tn пересекаются и длина линии R от центроида до дальний угол упомянутой фигуры

Предоставляется следующая информация:

  • Широта T1 = 56,999883 Долгота = 24,144473 Радиус = 943
  • Широта T2 = 57.005352 Долгота = 24.151168 Радиус = 857
  • T3 Широта = 57.005352 Долгота = 24.163356 Радиус = 714
  • Широта T4 = 56.999042 Долгота = 24.168506 Радиус = 714
  • T5 Широта = 56.994226 Долгота = 24.15709 Радиус = 771

Результат должен выглядеть следующим образом: A Широта = XX.XXXXXXX Долгота = XX.XXXXXXX Радиус = XX

введите описание изображения здесь

Как вы, наверное, уже поняли, я работаю над программным обеспечением, которое может определять местоположение устройства по ближайшим точкам доступа Wi-Fi или мобильным базовым станциям, так как количество точек доступа или базовых станций может измениться, мне нужен алгоритм, который может адаптироваться к неопределенному количеству точек ,

Есть некоторые подобные вопросы здесь и здесь , но ни один из них точно не отвечает на мой вопрос.

Карлис Бауманис
источник
на каком языке вы работаете?
WolfOdrade
В основном PHP, немного JavaScript. Я думаю, что я должен был упомянуть об этом раньше, но я веб-разработчик, и чтобы понять ответ Уубер, мне нужно будет найти математика.
Карлис Бауманис
Радиусы получены из относительных уровней сигнала?
Кирк Куйкендалл
Да! На самом деле Радиусы находятся в дБм
Карлис Бауманис
1
@ Редокс, частично - мне удалось рассчитать его с помощью php_exec (), используя mathematica на стороне сервера.
Карлис Бауманис

Ответы:

29

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

Это стандартный материал доступен в (среди прочего) Python, R, Mathematica , и многие полнофункциональные статистические пакеты, так что я просто проиллюстрировать. Вот некоторые данные, полученные путем измерения расстояний с относительной погрешностью 10% до пяти точек произвольного доступа, расположенных вокруг устройства:

Таблица данных

Mathematica требуется всего одна строка кода и не измеримое время процессора для вычисления соответствия:

fit = NonlinearModelFit[data, Norm[{x, y} - {x0, y0}], {x0, y0}, {x, y}, Weights -> 1/observations^2]

Редактировать--

Для больших радиусов более точные (сферические или эллипсоидальные) решения можно найти, просто заменив евклидово расстояние Norm[{x, y} - {x0, y0}]на функцию для вычисления сферического или эллипсоидального расстояния. В Mathematica это можно сделать, например , с помощью

fit = NonlinearModelFit[data, GeoDistance[{x, y}, {x0, y0}], {x0, y0}, {x, y}, 
        Weights -> 1/observations^2]

- конец редактирования

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

ellipsoid = fit["ParameterConfidenceRegion", ConfidenceLevel -> 0.95];
fit["ParameterConfidenceIntervalTable", ConfidenceLevel -> 0.95]

Таблица доверительных интервалов

Поучительно представить данные и решение:

Graphics[{Opacity[0.2], EdgeForm[Opacity[0.75]], White, Disk[Most[#], Last[#]] & /@ data, 
  Opacity[1], Red, ellipsoid, 
  PointSize[0.0125], Blue, Point[source], Red, Point[solution],
  PointSize[0.0083], White, Point @ points}, 
  Background -> Black, ImageSize -> 600]

карта

  • Белые точки - это (известные) точки доступа.

  • Большая синяя точка - это истинное местоположение устройства.

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

  • Большая красная точка - приблизительное местоположение устройства.

  • Красный эллипс определяет 95% доверительную область для местоположения устройства.

Форма эллипса в этом случае представляет интерес: локальная неопределенность является наибольшей вдоль линии NW-SE. Здесь расстояния до трех точек доступа (до NE и SW) практически не меняются, и существует компромисс между ошибками между расстояниями до двух других точек доступа (к северу и юго-востоку).

(Более точная доверительная область может быть получена в некоторых системах в виде контура функции правдоподобия; этот эллипс является лишь приближением второго порядка к такому контуру.)

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

Этот метод работает с двумя или более точками доступа. Три или более необходимы для получения доверительных интервалов. Когда доступно только два, он находит одну из точек пересечения (если они существуют); в противном случае он выбирает подходящее место между двумя точками доступа.

Whuber
источник
3
Молодец, Билл!
1
@Reddox В принципе, да: любой язык, полный тьюринга, может выполнять буквально любые вычисления. Но PHP будет далеко внизу списка вариантов выбора в качестве целевого языка. Даже руководство по PHP признает то же самое: «PHP, вероятно, не самый лучший язык для создания настольных приложений с графическим интерфейсом пользователя, но если вы очень хорошо знаете PHP и хотели бы использовать некоторые расширенные функции PHP на вашей стороне клиента приложения вы также можете использовать PHP-GTK для написания таких программ. "
whuber
1
@Reddox Спасибо за ссылку. Я вижу, как это обеспечивает расчеты геометрии. В этом случае они действительно не нужны: единственное такое вычисление - это применение теоремы Пифагора для получения расстояний в виде корневых сумм квадратов (вызов Normв моем коде). Вся работа связана с подгонкой взвешенных нелинейных наименьших квадратов, но я не верю, что библиотека GEOS предоставляет такую ​​возможность. Возможно, GEOS может оказать некоторую помощь, когда необходимы точные эллипсоидальные расстояния.
whuber
2
Если я правильно читаю, @BenR, похоже, вы взвешиваете данные пропорционально квадратам радиусов, а не обратно пропорционально им. Что происходит , когда вы разделить на square(data[2])вместо умножения на него?
whuber
1

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

Сначала определите все n * (n-1) точек пересечения. Назовем множество этих точек пересечения I . Возьмите список точек T, который содержит самые внутренние точки. Затем для каждой точки p в I проверьте, находится ли p внутри каждого круга. Если р находится внутри каждого круга, то это точка на самом внутреннем пересечении. Добавьте такую точку в списке T .

Теперь у вас есть нужные координаты пересечения. Я могу придумать как минимум два способа предсказать местоположение:

  1. Просто вычислите центроид (использовать расстояние как вес?) Многоугольника, образованного буквой Т, и центроид - это желаемое место.
  2. Вычислить минимальный круг , который содержит каждую точку Т . Тогда центр этого круга - желаемое место. После этого вычисление R должно быть простым.

Еще одно примечание: сначала преобразуйте силу сигнала в расстояние, используя модель пути в свободном пространстве (или вариации). Мое мнение таково: у вас есть какой-либо обучающий набор данных, вы должны попытаться найти показатель потери пути, используя некоторую технику обучения вместо использования n = 2 или n = 2.2 в качестве фиксированного значения.

Масум Биллал
источник
что такое T ... "самые внутренние точки" - если у меня 5 узлов ... сколько "внутренних точек" я должен проверять?
Ewizard