Поиск координат точек из матрицы расстояния

Question

У меня есть набор точек (с неопределенными координатами) и матрицей расстояний. Мне нужно найти координаты этих точек, чтобы построить их и показать решение моего алгоритма.

Я могу установить одну из этих точек в координате (0,0), чтобы упростить и найти другие. Может ли кто-нибудь сказать мне, можно ли найти координаты других точек, и если да, то как?

Заранее благодарен!

РЕДАКТИРОВАТЬ Забыл сказать, что мне нужны координаты на X-Y только

Answer 1

Шаг 1, произвольно присвоить одну точку Р1, как (0,0).

Шаг 2 произвольно назначает одну точку P2 вдоль положительной оси x. (0, Dp1p2)

Шаг 3, найти точку Р3, так что

Dp1p2 ~= Dp1p3+Dp2p3 
Dp1p3 ~= Dp1p2+Dp2p3 
Dp2p3 ~= Dp1p3+Dp1p2 

и установить эту точку в «положительном» у домена (если он соответствует любому из этих критериев, то точка должна быть помещена на оси P1P2).
Используйте закон косинуса для определения расстояния:

cos (A) = (Dp1p2^2 + Dp1p3^2 - Dp2p3^2)/(2*Dp1p2* Dp1p3) 
P3 = (Dp1p3 * cos (A), Dp1p3 * sin(A)) 

Вы успешно построил ортонормированное пространство и размещены три точек в этом пространстве.

Шаг 4: Чтобы определить все остальные точки, повторите шаг 3, чтобы дать вам предварительную координату y. (Xn, Yn).
Сравните расстояние {(Xn, Yn), (X3, Y3)} до Dp3pn в вашей матрице. Если он идентичен, вы успешно определили координату для точки n. В противном случае точка n равна (Xn, -Yn).

Примечания есть альтернатива к шагу 4, но это слишком много математики для субботы дня

Answer 2

Если для точек р, д, г у вас есть рд, ор, и гр в Вашей матрице, у вас есть треугольник.

Если у вас есть треугольник в вашей матрице, вы можете вычислить одно из двух решений для этого треугольника (независимо от евклидова преобразования треугольника на плоскости). То есть для каждого треугольника, который вы вычисляете, зеркальное изображение также является треугольником, который удовлетворяет ограничениям расстояния на p, q и r. Тот факт, что есть два решения даже для треугольника, приводит к проблеме хиральности: вы должны выбрать хиральность (ориентацию) каждого треугольника, и не все варианты могут привести к допустимому решению проблемы.

Тем не менее, у меня есть некоторые предложения. Если числовые записи малы, подумайте об использовании simulated annealing. Вы можете включить хиральность на этап отжига. Это будет медленным для больших систем, и оно может не сходиться к идеальному решению, но для некоторых проблем это лучше всего и вы.

Второе предложение не даст вам идеального решения, но оно распространяет ошибку: method of least squares. В вашем случае целевой функцией будет ошибка между расстояниями в вашей матрице и фактическими расстояниями между вашими точками.

Answer 3

Ответы, основанные на углах, громоздки для реализации и не могут быть легко обобщены на данные в более высоких измерениях.Лучший подход, который упоминается в моих и всем, кого это касается ответов here: даны матрицы расстояний D(i, j), определить

M(i, j) = 0.5*(D(1, j)^2 + D(i, 1)^2 - D(i, j)^2) 

, которая должна быть неотрицателен определенной матрицей с рангом равной минимальных евклидовых размерностей k, в котором точку можно быть встроенным. Координаты точек могут быть затем получена из собственных векторов kv(i) из M, соответствующих ненулевых собственных значений q(i): место векторы sqrt(q(i))*v(i) в виде столбцов в матрице n x kX; то каждая строка X является точкой. Другими словами, sqrt(q(i))*v(i) дает i-й компонент всех точек.

Собственные значения и собственные векторы матрицы могут быть легко получены в большинстве языков программирования (например, с использованием GSL в C/C++, используя встроенную функцию eig в Matlab, используя Numpy в Python и т.д.)

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

Answer 4

Это математическая проблема. Вывести координатную матрицу X только по ее дистанционной матрице.

Однако есть эффективное решение этого - многомерное масштабирование, которое выполняет некоторую линейную алгебру. Проще говоря, для этого требуется парная евклидова матрица расстояний D, а выход - оценочная координата Y (возможно, повернутая), которая является проксимальной связью с X. Для объяснения программирования просто используйте SciKit.manifold.MDS в Python.