Мне нужно найти алгоритм, который может рассчитать центроид 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 или мобильным базовым станциям, так как количество точек доступа или базовых станций может измениться, мне нужен алгоритм, который может адаптироваться к неопределенному количеству точек ,
Есть некоторые подобные вопросы здесь и здесь , но ни один из них точно не отвечает на мой вопрос.
источник
Ответы:
Измерения радиуса, безусловно, подвержены некоторой ошибке. Я ожидаю, что количество ошибок будет пропорционально самим радиусам. Давайте предположим, что измерения в противном случае беспристрастны. Разумное решение тогда использует взвешенную нелинейную аппроксимацию по методу наименьших квадратов с весами, обратно пропорциональными квадратам радиусов.
Это стандартный материал доступен в (среди прочего) Python,
R
, Mathematica , и многие полнофункциональные статистические пакеты, так что я просто проиллюстрировать. Вот некоторые данные, полученные путем измерения расстояний с относительной погрешностью 10% до пяти точек произвольного доступа, расположенных вокруг устройства:Mathematica требуется всего одна строка кода и не измеримое время процессора для вычисления соответствия:
Редактировать--
Для больших радиусов более точные (сферические или эллипсоидальные) решения можно найти, просто заменив евклидово расстояние
Norm[{x, y} - {x0, y0}]
на функцию для вычисления сферического или эллипсоидального расстояния. В Mathematica это можно сделать, например , с помощью- конец редактирования
Одно из преимуществ использования статистического метода, подобного этому, заключается в том, что он может создавать доверительные интервалы для параметров (которые являются координатами устройства) и даже одновременный доверительный эллипс для местоположения устройства.
Поучительно представить данные и решение:
Белые точки - это (известные) точки доступа.
Большая синяя точка - это истинное местоположение устройства.
Серые кружки представляют измеренные радиусы. В идеале они все должны пересекаться в истинном местоположении устройства - но, очевидно, нет, из-за ошибки измерения.
Большая красная точка - приблизительное местоположение устройства.
Красный эллипс определяет 95% доверительную область для местоположения устройства.
Форма эллипса в этом случае представляет интерес: локальная неопределенность является наибольшей вдоль линии NW-SE. Здесь расстояния до трех точек доступа (до NE и SW) практически не меняются, и существует компромисс между ошибками между расстояниями до двух других точек доступа (к северу и юго-востоку).
(Более точная доверительная область может быть получена в некоторых системах в виде контура функции правдоподобия; этот эллипс является лишь приближением второго порядка к такому контуру.)
Когда радиусы измерены без ошибок, все окружности будут иметь хотя бы одну точку взаимного пересечения и - если эта точка является уникальной - это будет уникальное решение.
Этот метод работает с двумя или более точками доступа. Три или более необходимы для получения доверительных интервалов. Когда доступно только два, он находит одну из точек пересечения (если они существуют); в противном случае он выбирает подходящее место между двумя точками доступа.
источник
Norm
в моем коде). Вся работа связана с подгонкой взвешенных нелинейных наименьших квадратов, но я не верю, что библиотека GEOS предоставляет такую возможность. Возможно, GEOS может оказать некоторую помощь, когда необходимы точные эллипсоидальные расстояния.square(data[2])
вместо умножения на него?В этом случае каждый круг пересекает все остальные круги, поэтому мы можем определить точки пересечения следующим образом:
Сначала определите все n * (n-1) точек пересечения. Назовем множество этих точек пересечения I . Возьмите список точек T, который содержит самые внутренние точки. Затем для каждой точки p в I проверьте, находится ли p внутри каждого круга. Если р находится внутри каждого круга, то это точка на самом внутреннем пересечении. Добавьте такую точку в списке T .
Теперь у вас есть нужные координаты пересечения. Я могу придумать как минимум два способа предсказать местоположение:
Еще одно примечание: сначала преобразуйте силу сигнала в расстояние, используя модель пути в свободном пространстве (или вариации). Мое мнение таково: у вас есть какой-либо обучающий набор данных, вы должны попытаться найти показатель потери пути, используя некоторую технику обучения вместо использования n = 2 или n = 2.2 в качестве фиксированного значения.
источник