Нахождение координат точек из матрицы расстояний

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

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

Заранее спасибо!

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

 Oliver Charlesworth09 июн. 2012 г., 19:28
Рассмотрим три точки (треугольник). Есть две ориентации и бесконечное число вращений, которые дают одинаковую матрицу расстояний.
 Rasman09 июн. 2012 г., 19:32
Еще один шаг, мы говорим об одномерном пространстве, или двух, или трех, или четырех ... Ответ будет меняться в каждом случае. По (0,0), должны ли мы принять его двумерное?
 Ignacio Vazquez-Abrams09 июн. 2012 г., 19:28
Это ... понадобится много грубого принуждения ...
 Daniel Fischer09 июн. 2012 г., 20:08
@KevinReid В общем да. Но если первые три точки лежат на одной прямой линии, у вас есть два варианта (полученных друг от друга путем отражения в линии), пока вы не выберете первую точку, которая не лежит на этой линии.
 Kevin Reid09 июн. 2012 г., 19:33
Как только вы определите ориентацию и угол, не все ли точки после третьего будут однозначными? (В двумерном пространстве, поскольку ОП дало двумерный ноль.)

Ответы на вопрос(4)

основанные на ракурсах, являются громоздкими для реализации и не могут быть легко обобщены для данных в более высоких измерениях. Лучший подход - это тот, который упомянут в моих ответах и ответах 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) изM соответствует ненулевым собственным значениямq(i): разместите векторыsqrt(q(i))*v(i) как столбцы вn x k матрицаX; тогда каждый рядX это точка. Другими словами,sqrt(q(i))*v(i) даетiй компонент всех точек.

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

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

 13 янв. 2015 г., 22:55
Это должно быть ответом. Нет необходимости кодировать его самостоятельно, хотя функции многомерного масштабирования можно найти в Python или R.

по ее матрице расстояний.

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

q и r в вашей матрице есть pq, qr и rp, у вас есть треугольник.

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

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

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

 BrunoB09 июн. 2012 г., 23:02
Спасибо за ответ. Я не знаю, является ли это наилучшим подходом, потому что в некоторых кинариях у меня много точек, и метаэвристика не всегда возвращает оптимальное решение или, в данном случае, реальное решение. Так что я мог бы провести с ним много времени и до сих пор не получил реальный ответ.
 10 июн. 2012 г., 03:29
@DeepYellow: Мне нравится ваш ответ частично, потому что он может помочь ответить на другой, более сложный вопрос, опубликованный вчера другим пользователем. Я попытался ответить на этот другой вопрос и потерпел неудачу. Если задача вас интересует, вот URL:stackoverflow.com/questions/10957359/…
 11 июн. 2012 г., 11:43
@thb: Спасибо за указание на этот вопрос. Я опубликовал то, что я считаю правильным решением, дайте мне знать, что вы думаете.
Решение Вопроса

Шаг 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, но это слишком много математики для субботнего дня

 09 июн. 2012 г., 23:12
@BrunoBruck закон косинуса дает угол (первое уравнение) между P1P2 и P1P3. Следующая часть - получить проекцию P3 на ось P1P2. Зная расстояние P1P3 и устанавливая его в качестве гипотенузы треугольника, значения X и Y - это просто cos и sine умноженные на гипотенузу соответственно.
 BrunoB10 июн. 2012 г., 00:10
Хорошо, я думаю, что понял. Сначала мы притворяемся, что P3 находится в оси Y, чтобы получить прямоугольный треугольник, и в этом случае мы можем создать уравнения для координат. Но мы знаем реальное расстояние между P3 и P2, поэтому мы можем получить реальный угол между P1P2 и P1P3, и, используя его в уравнениях для координат, мы можем получить реальные значения для Xp3 и Yp3. Я правильно понял?
 BrunoB09 июн. 2012 г., 23:40
То, что вы сделали с P2, в порядке, но в случае с P3 я не могу выбрать точку моего набора, которая не находится на одной линии с P1 и P2, и точно сказать, что она на оси y.
 10 июн. 2012 г., 02:02
@ BrunoBruck, извините за путаницу, P3 не должен быть на оси Y, скорее он находится в полуплоскости, где y положительно. Другими словами, построите второе измерение так, чтобы третья точка имела положительное значение y. Я изменил текст на этот счет.
 BrunoB10 июн. 2012 г., 02:54
О, теперь это имеет смысл и решает мою проблему. Спасибо за ответ!

Ваш ответ на вопрос