Вопрос, возможно, простой, но я что-то туплю и не нахожу внятного решения.
Есть некий набор удаленных точек на карте с известными координатами и количественным показателем удаления от места "Х". Нужно по этим данным рассчитать приблизительное место той самой точки "Х".
- Можно найти центр масс многоугольника, образованного этими точками, но там не учитывается количественый показатель удаления, так что рассчет будет даже приблизительно не верный.
- Можно найти область пересечения двух окружностей, образованных двумя точками на карте и количественным показателем удаления как радиусом каждой из окружностей. Это справедливо для вух точек, а нужно для большего кол-ва.
Помню такое слово как "триангуляция", но что-то не нашел толковго алгоритма для рассчета. Может кто подскажет в какую сторону копать? Интересует алгоритм, а не конечный код.
Предполагаем координаты точки равными (X, Y). Строим выражение разности расстояния от этой точки до имеющейся в массиве и заданного в массиве расстояния (delta = sqrt((Xi-X)^2+(Yi-Y)^2))-L). Суммируем по модулю (или, скажем, квадраты) для всех точек. Получаем уравнение поверхности. Находим глобальный минимум любым методом. Всё.
В общем, обычный поиск минимума функции двух переменных.
Можно найти центр масс многоугольника, образованного этими точками, но там не учитывается количественый показатель удаления, так что рассчет будет даже приблизительно не верный.
Почему? Центр масс многоугольника не зависит от других показателей.
Прошу прощения, но не совсем догнал мысль. От пересечения двух окружностей получаем 2 точки. Далее, без учета этих окружностей, сравниваем полученные точки с оставшимися окружностями... как?
Леха, Вам нужна точка, которая лежит на всех окружностях. Фактически, у вас n уравнений. Но уже двух уравнений достаточно, чтобы найти 1-2 кандидата. Поэтому достаточно взять эти 2 точки кандидата и просто подставить их в оставшиеся n-2 уравнения.
Ну просто проверяйте, что точка лежит на окружности, т.е. растсояние от нее до центра равно заданному радиусу.
Wataru, а поскольку он будет работать с вещественными числами [ограниченной точности], то ему нужно не точное попадание одной из двух точек на 3-ю, 4-.ю и т.д. окружности, а минимальное среди двух точек расстояние до 3-й, 4-й и т.д. окружности.
А ещё лучше для минимизации погрешности проделать эти вычисления n*(n-1) раз, выбирая в качесве 1-й и 2-й окружности всевозможные пары, а затем взять центр масс от полученных n*(n-1) точек.
Ну это если отвлечься от геометрически точного решения, а решать численно.
Простой
Средний
