У меня есть набор точек (с неопределенными координатами) и матрицей расстояний. Мне нужно найти координаты этих точек, чтобы построить их и показать решение моего алгоритма.
Я могу установить одну из этих точек в координате (0,0), чтобы упростить и найти другие. Может ли кто-нибудь сказать мне, можно ли найти координаты других точек, и если да, то как?
Спасибо заранее!
ИЗМЕНИТЬ Забыл сказать, что мне нужны координаты только на x-y
Шаг 1, произвольно назначить одну точку P1 как (0,0).
Шаг 2 произвольно назначает одну точку P2 вдоль положительной оси x. (0, Dp1p2)
Шаг 3, найдем точку P3 такую, что
Dp1p2 ~= Dp1p3+Dp2p3
Dp1p3 ~= Dp1p2+Dp2p3
Dp2p3 ~= Dp1p3+Dp1p2
и установите эту точку в "положительной" y-области (если она соответствует любому из этих критериев, точка должна быть помещена на ось 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, но это слишком большая математика для субботнего дня.
Ответы, основанные на углах, громоздки для реализации и не могут быть легко обобщены на данные в более высоких измерениях. Лучший подход заключается в том, что упомянутые в my и WimC ответы здесь: если задана матрица расстояний D(i, j), определите
M(i, j) = 0.5*(D(1, j)^2 + D(i, 1)^2 - D(i, j)^2)
которая должна быть положительной полуопределенной матрицей с рангом, равным минимальной евклидовой размерности k, в которую могут быть вложены точки. Координаты точек можно затем получить из k собственных векторов v(i) of M, соответствующих ненулевым собственным значениям q(i): поместите векторы sqrt(q(i))*v(i) в виде столбцов в матрице n x k X; то каждая строка X является точкой. Другими словами, sqrt(q(i))*v(i) дает i -й компонент всех точек.
Собственные значения и собственные векторы матрицы можно легко получить в большинстве языков программирования (например, используя GSL в C/С++, используя встроенную функцию eig в Matlab, используя Numpy в Python и т.д.)
Обратите внимание, что этот конкретный метод всегда помещает первую точку в начало координат, но любое вращение, отражение или перевод точек также будет удовлетворять исходной матрице расстояния.
Если для точек p, q и r в вашей матрице есть pq, qr и rp, у вас есть треугольник.
Везде, где у вас есть треугольник в вашей матрице, вы можете вычислить одно из двух решений для этого треугольника (не зависящего от евклидова преобразования треугольника на плоскости). То есть для каждого треугольника, который вы вычисляете, это зеркальное изображение также является треугольником, который удовлетворяет ограничениям расстояния на p, q и r. Тот факт, что есть два решения даже для треугольника, приводит к проблеме хиральности: вам нужно выбрать хиральность (ориентацию) каждого треугольника, и не все варианты могут привести к возможному решению проблемы.
Тем не менее, у меня есть некоторые предложения. Если числовые записи малы, рассмотрите использование имитационного отжига. Вы можете включить хиральность на этап отжига. Это будет медленным для больших систем, и оно может не сходиться к идеальному решению, но для некоторых проблем это лучше всего и вы.
Второе предложение не даст вам идеального решения, но оно будет распространять ошибку: метод наименьших квадратов. В вашем случае объектная функция будет ошибкой между расстояниями в вашей матрице и фактическими расстояниями между вашими точками.
Это математическая проблема. Вывести координатную матрицу X только по ее дистанционной матрице.
Однако для этого существует эффективное решение - многомерное масштабирование, которое выполняет некоторую линейную алгебру. Проще говоря, для этого требуется парная евклидова матрица расстояний D, а выход - оценочная координата Y (возможно, повернутая), которая является проксимальной связью с X. Для объяснения программирования просто используйте SciKit.manifold.MDS в Python.