Матрица расстояний -> координаты на плоскости

@nicolaus2 · Регистрация: 11.07.2010

Студворк — интернет-сервис помощи студентам

Здравствуйте.

Имея координаты на плоскости мы с легкостью можем построить матрицу расстояний между всеми координатами.

Но как сделать обратное(с матрицы расстояний получить координаты на плоскости)? Что-то ничего в голову не приходит.

Евгений М. · 14.02.2011, 06:33

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

silent_1991 · 14.02.2011, 09:56

Евгений М., речь идёт не обязательно о трёх точках. Но, возьми мы любые три точки из набора, они будут удовлетворять неравенству треугольника, поэтому предложенный способ справедлив для всего набора, и формально вы правы, из них можно сделать треугольник))).

@Ирэнка · 04.06.2011, 21:16

а как программу записать для нахождения этой матрицы?

@ColdDeath · 19.01.2014, 01:47

Так и не понял, как преобразовать матрицу расстояний в координатыточек.
Напишите, пожалуйста, более подробно про преобрахование с помощью уравнения окружности. Лучше всего подкрепить теорию примером.
Например, имеем матрицу расстояний:
0 2 5 7
2 0 5 4
5 5 0 6
7 4 6 0

silent_1991 · 19.01.2014, 23:12

ColdDeath, для начала надо учесть, что матрица расстояний может быть вообще невалидной (т.е. таких расстояний между точками на обычной евклидовой плоскости быть не может). Это легко учесть, если на каком-либо шаге вычислений получилось уравнение, не имеющее действительных корней. Например, ваша матрица смежности невалидна, и дальше я покажу, почему.
Давайте попробуем восстановить координаты точек по вашей матрице смежности.
Мы сразу можем найти две точки - первую и вторую.
Координаты первой точки - P1=(0, 0) (просто поместили её в начало координат).
Координаты второй - P2=(0, 2) (отодвинули вторую точку от первой на нужное расстояние - 2 - по оси абсцисс).
Теперь найдём координаты третьей точки.
Сначала найдём общий вид нужного нам уравнения. Имеем общее уравнение окружности с произвольным центром:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{{(x-{x}_{0})}^{2}+{(y-{y}_{0})}^{2}}=R$
Возведём обе части в квадрат:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{(x-{x}_{0})}^{2}+{(y-{y}_{0})}^{2}={R}^{2}$
Перенесём член с иксом в правую часть:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{(y-{y}_{0})}^{2}={R}^{2}-{(x-{x}_{0})}^{2}$
Извлечём квадратный корень из обеих частей.
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y-{y}_{0}=\sqrt{{R}^{2}-{(x-{x}_{0})}^{2}}$
Ну и перенесём $https://www.cyberforum.ru/cgi-bin/latex.cgi?{y}_{0}$ в правую часть:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{{R}^{2}-{(x-{x}_{0})}^{2}}+{y}_{0}$
Таким образом, нам удалось выразить y из общего уравнения окружности. Это нам понадобится для того, чтобы найти точки пересечения пары окружностей. Для чего нам эти две окружности - дальше.
Если нам требуется найти для известной (с заданными координатами) точки другую точку, расположенную от первой на заданном расстоянии, нам достаточно построить окружность с центром в первой точке радиуса, равного этому заданному расстоянию. Всё множество точек, составляющее полученную окружность, будет удовлетворять заданному условию: любая точка на окружности будет находиться на заданном расстоянии от первой точки.
Однако если нам нужно найти точку, расположенную на заданных расстояниях от двух точек, нам нужно построить уже две окружности: одна окружность строится с центром в первой точке радиуса, равного расстоянию от этой первой точки до искомой, вторая - радиуса, равного расстоянию от второй точки до искомой с центром во второй точке. Точки пересечения этих двух окружностей и дадут искомую точку (на самом деле этих точек может быть две - по обе стороны от отрезка, соединяющего две исходные точки; одна (окружности соприкасаются, но не пересекаются) - точка лежит ровно на середине отрезка, соединяющего исходные; ни одной - точка, лежащая одновременно на обоих заданных расстояниях от двух исходных точек, не существует). Именно это мы и будем делать.
Поскольку нам известны координаты первых двух точек, мы будем искать расстояния до остальных точек на основе первых двух. При этом надо учитывать следующие случаи: 1) очередная точка не может лежать одновременно на заданных расстояниях от двух первых точек; 2) очередная точка успешно найдена, она действительно лежит на нужных расстояниях от обеих первых точек, т.е. составляет с ними треугольник, но не может лежать на заданном расстоянии от одной или нескольких других точек, найденных в процессе работы алгоритма. В обоих этих случаях можно считать, что исходная матрица расстояний была некорректна. При этом для проверки второго случая необходимо искать расстояния от найденной точки до всех других уже найденных точек и смотреть, возможно ли его найти вообще (уравнение имеет действительные корни) и совпадает ли оно с указанным в матрице расстояний.
Попробуем же найти третью точку. Для этого используем ранее найденное уравнение окружности.
Построим окружность с центром в точке P1=(0, 0) радиуса 5:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{{5}^{2}-{(x-0)}^{2}}+2=\sqrt{25-{x}^{2}}+2$
Теперь построим вторую окружность - с центром в точке P2 радиуса 5 (радиус совпал, потому что у вас такая матрица смежности, в общем случае он, конечно, может быть разным):
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{{5}^{2}-{(x-0)}^{2}}+2=\sqrt{25-{x}^{2}}+2$
Найдём точки пересечения этих двух окружностей. Для этого приравняем правые части полученных уравнений:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{25-{x}^{2}}=\sqrt{25-{x}^{2}}+2$
Возведём обе части в квадрат:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?25-{x}^{2}=25-{x}^{2}+4\sqrt{25-{x}^{2}}+4$
Приведём подобные и попутно выделим квадратный корень в одну часть, всё остальное - в другую:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{25-{x}^{2}}=-1$
Возведём обе части в квадрат и приведём подобные:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}^{2}=24$
Наконец, найдём корни уравнения:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x=\pm 2\sqrt{6}$
Итак, мы нашли пару координат на оси абсцисс, которая может удовлетворять искомой точке. Теперь найдём координаты по оси ординат. Для этого нужной найденные иксы подставить сначала в уравнение для первой построенной окружности, затем в уравнение для второй:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{25-{2\sqrt{6}}^{2}}=\sqrt{25-24}=sqrt{1}=1$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{25-{2\sqrt{6}}^{2}}+2=\sqrt{25-24}+2=sqrt{1}+2=3$
Итого четыре разные точки, которые могут являться искомой: P31=( $https://www.cyberforum.ru/cgi-bin/latex.cgi?2\sqrt{6}$ , 1), P32=( $https://www.cyberforum.ru/cgi-bin/latex.cgi?2\sqrt{6}$ , 3), P33=( $https://www.cyberforum.ru/cgi-bin/latex.cgi?-2\sqrt{6}$ , 1), P34=( $https://www.cyberforum.ru/cgi-bin/latex.cgi?-2\sqrt{6}$ , 3). Чтобы узнать, какие из этих точек реально являются искомыми, нужно проверить расстояние от них до других уже найденных точек и отсеять те, которые не подходят (уравнение не имеет действительных корней либо найденное расстояние не совпадает с расстоянием из матрицы расстояний). Проблема (влияющая на скорость алгоритма) заключается в том, что для любой искомой точки мы можем найти до четырёх вариантов координат, и все они будут до определённого момента подходить под исходную матрицу расстояний. Таким образом, если мы ищем 11-ю точку, и все предыдущие имели по 4 набора координат, то нам нужно каждую из 4-х вновь найденных координат сопоставлять с каждыми 4-мя координатами для каждой точки. И даже по завершении работы алгоритма мы можем не получить однозначного набора (могут остаться точки с несколькими наборами координат).
Выше я обещал показать, почему указанная вами матрица расстояний является некорректной. Попробуем найти 4-ю точку так же, как делали это с 3-ей.
Построим две окружности (с центрами в первой и второй точках и соответствующими расстояниями):
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{{7}^{2}-{(x-0)}^{2}}=\sqrt{49-{x}^{2}}$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{{4}^{2}-{(x-0)}^{2}}+2=\sqrt{16-{x}^{2}}+2$
Приравняем правые части и проведум необходимые алгебраические преобразования. В итоге найдём икс:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x=\pm 36.5625$
Сразу можем видеть, что с такими иксами, подставленными в уравнения окружностей, мы не сможем найти действительные корни этих уравнений. Действительно, 36.5625, возведённая в квадрат, больше как 16, так и 49. Разность даст нам отрицательный результат, арифметический квадратный корень из которого не существует (алгебраический же корень является комплексным, что нам не подходит по очевидным причинам). Таким образом, точки, отстоящей от точки P1 на расстояние 7, а от точки P2 на расстояние 4
э при том, что сами эти точки удалены друг от друга на расстояние 2, не существует, а значит, исходная матрица расстояний некорректна.
Честно говоря, у меня до сих пор есть сомнения по поводу полной корректности данного алгоритма. В том, что он безошибочно распознает некорректную матрицу расстояний, я не сомневаюсь, а вот не будет ли ложноотрицательного срабатывания, т.е. не посчитает ли он корректную матрицу расстояний некорректной, я не уверен.
Вообще, если завтра вечером будет время, я попробую написать реализацию алгоритма на C++ (или на Java, зависит от настроения

) и генератор случайных корректных матриц расстояний и посмотрю, отработает ли алгоритм на этих матрицах.

@ColdDeath · 19.01.2014, 23:30

Хорошо, спасибо Вам огромное! Читаю, пытаюсь вникнуть. Буду очень рад исходному коду алгоритма!
Очень приятно и радостно, что в нашем мире есть люди, которые увлечены наукой и двигают прогресс вперед!
А я вот сейчас ещё с нейронными сетями пытаюсь разобраться

Дело в том, что нейронная сеть у меня не может произвести кластеризацию по матрице расстояний, точнее, делает это не всегда корректно. Тогда я подумал, что может быть данные ей будут более понятны, если они будут иметь форму координат.
silent_1991, спасибо за то, что Вы делаете и за то, что так подробно всё для меня расписали!
С нетерпением буду ждать исходного кода на C++.

@Igor3D · 20.01.2014, 15:51

Чего так сложно - на мой взгляд, задачка-то простая. Базовые соображения

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

- Флипнем (отразим) множество точек по x или y или относительно произвольной оси - опять матрица не изменилась.

Отсюда следует что надо выбрать/зафиксировать систему координат.

1) Ставим первую точку в (0, 0)
2) Ставим вторую точку в (0, d(0, 1))
3) Вычисляем 3-ю точку на основании d(0, 2) и d(1, 2). Получаются 2 варианта, принимаем любой
4) Вычисляем все остальные точки на основании d(0, i) и d(1, i). Получаются 2 варианта, используем 3-ю точку как проверочную. Все

Да и вообще, от эксперта С++ ожидалось решение в 3 измерениях, что это за баловство плюшками на плоскости (да еще и на жабе)?

silent_1991 · 20.01.2014, 16:03

Сообщение от Igor3D

4) Вычисляем все остальные точки на основании d(0, i) и d(1, i). Получаются 2 варианта, используем 3-ю точку как проверочную. Все

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

Сообщение от Igor3D

Да и вообще, от эксперта С++ ожидалось решение в 3 измерениях, что это за баловство плюшками на плоскости (да еще и на жабе)?

Не думал, что от меня что-то ожидалось

. Знание С++ ещё не говорит о том, что я так же хорошо знаю математику. Работая по своей специальности, я ни разу не сталкивался с чем-то сложнее арифметики. Поэтому уже начинаю такие вещи забывать... Кроме того, эта задача в 3-хмерном пространстве не сложнее, чем в двумерном. Как и вообще в N-мерном. Так что в качестве примера, думаю, двух измерений будет достаточно.

@Igor3D · 20.01.2014, 17:16

Сообщение от silent_1991

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

Уверен, только не двух а трех - три точки (не лежащие на 1 прямой) задают систему координат. Ну крайний случай - если расстояния (до обоих вариантов) равны, тогда придется провериться по др точке что уже поселена.

silent_1991 · 20.01.2014, 21:58

Сообщение от Igor3D

три точки (не лежащие на 1 прямой) задают систему координат

Это, безусловно, так. Но я всё равно не могу понять, почему трёх точек (с учётом того, что матрица расстояний может быть некорректна) в общем случае достаточно.
Если вам не лень, не могли бы вы восстановить координаты точек для следующей матрицы расстояний:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix} 0& 2& \sqrt{5}& \sqrt{10}& \sqrt{18}\\ 2& 0& \sqrt{5}& \sqrt{2}& \sqrt{10}\\ \sqrt{5}& \sqrt{5}& 0& \sqrt{5}& \sqrt{5}\\ \sqrt{10}& \sqrt{2}& \sqrt{5}& 0& 3\\ \sqrt{18}& \sqrt{10}& \sqrt{5}& 3& 0 \end{pmatrix}$

@Igor3D · 21.01.2014, 11:48

Сообщение от silent_1991

Если вам не лень, не могли бы вы восстановить координаты точек для следующей матрицы расстояний:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix} 0& 2& \sqrt{5}& \sqrt{10}& \sqrt{18}\\ 2& 0& \sqrt{5}& \sqrt{2}& \sqrt{10}\\ \sqrt{5}& \sqrt{5}& 0& \sqrt{5}& \sqrt{5}\\ \sqrt{10}& \sqrt{2}& \sqrt{5}& 0& 3\\ \sqrt{18}& \sqrt{10}& \sqrt{5}& 3& 0 \end{pmatrix}$

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

точка 0 = (0, 0)
точка 1 = (0, 2)
точка 2 = (2, 1) (первый из 2 вариантов)
точка 3 = (1, 3) и (-1, 3) который? Проверяем по точке 2, расстояния sqrt(5) и sqrt(13), значит (1, 3)
точка 4 = ну тут уже сложновато в уме прикинуть где она, но все точно так же

Сообщение от silent_1991

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

А если матрица расстояний некорректна - то все, решения нет. Это называется junk in - junk out

Мы можем выбирать систему координат как угодно, но как только выбрали - все становится определено

silent_1991 · 21.01.2014, 12:22

Сообщение от Igor3D

А если матрица расстояний некорректна - то все, решения нет.

Сообщение от Igor3D

Это называется junk in - junk out

Ну нет, это не выход. Если бы все программы на свете всегда получали на вход априори только корректные данные - профессия программиста была бы одной из ходовых. В реальном же мире программа должна корректно реагировать на некорректные входные данные, при этом получение ответа, который выдаётся за правильный, на заведомо неправильных входных данных, корректным поведением назвать нельзя.
Моя просьба восстановить координаты по указанной матрице не случайна. Данная матрица некорректна, таких расстояний на плоскости быть не может. Но при этом (если я правильно понял ваш алгоритм) при выборе определённых точек в качестве проверочных можно получить координаты всех пяти точек. Если же за проверочную выбрать другую точку, то станет понятно, что такого расстояния от искомой точки до проверочной быть не может. И это снова возвращает нас к моему варианту - проверка по всем уже найденным точкам.
Или я в чём-то не прав?

@Igor3D · 21.01.2014, 14:45

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

В любой задаче что-то "дано" и что-то "нужно получить", это нормально

HighPredator · 21.01.2014, 16:51

Я наверное в танке, но почему-то мне кажется, что такая задача имеет всегда бесконечное число решений... Пример в лоб. Пусть у нас есть набор координат задающий треугольник (x₁,y₁);(x₂;y₂);(x₃;y₃) со сторонами 3,4,5 на плоскости. Мне например очевидно, что применив оператор параллельного переноса мы получим новый набор координат (x^*₁,y^*₁);(x^*₂;y^*₂);(x^*₃;y^*₃) при сохранении длин сторон (расстояний между точками) а следовательно и матрицы расстояний.

Добавлено через 41 секунду
Или я задачу не так понял?

@Igor3D · 21.01.2014, 19:09

Сообщение от HighPredator

Я наверное в танке, но почему-то мне кажется, что такая задача имеет всегда бесконечное число решений...

Так этого никто и не скрывал

Конечно единственного решения здесь не получить, но и без этого задача имеет смысл

silent_1991 · 21.01.2014, 19:16

HighPredator, ты всё правильно понял, на первой странице обсуждалось. Сошлись на том, что достаточно найти частное решение. Как правильно отметил Igor3D, три точки систему координат. Значит можем зафиксировать первую пару точек, найти на их основании третью, а затем, отталкиваясь от этой тройки, искать остальные.

Igor3D, вот, наконец-то вы сказали то, что говорил я ещё три поста назад: без полной проверки не обойтись. Я ничего не хочу получить от некорректной матрицы, я хочу, чтобы алгоритм был универсальным, т.е. корректно реагировал на любые входные матрицы. А для универсальности необходимо проверять расстояния до всех уже найденных точек. Если бы я был уверен в том, что на вход всегда будет продана корректная матрица, мне бы это не понадобилось, но, к сожалению, быть в этом уверенным я не могу.

silent_1991 · 06.02.2014, 21:28

Прошу прощения за столь длительную задержку, оказалось, что выделить полностью свободный вечерок не так-то просто. Приходилось писать урывками, когда было свободное время.
Как и обещал, написал на джаве. Алгоритм получился несколько проще, чем я описывал ранее, всё достаточно подробно написано в комментариях и в документации. Прилагаю архив, в нём исходники и сборочный ant-скрипт, кроме того, уже собранная библиотека и сгенерированная документация.
Вот простенький тестовый класс (сохранять в файле PointsRestorerTest.java, в джаве файл должен называться так же, как и содержащийся в нём публичный класс):

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.Random;
 
import org.spovst.pointsrestorer.primitives.DistMatrix;
import org.spovst.pointsrestorer.primitives.Point;
 
public class PointsRestorerTest {
    private static Random random = new Random();
    
    public static void main(String[] args) {
        Point[] points = generatePoints(random.nextInt(10));
        DistMatrix matrix = new DistMatrix(points);
        Point[] restoredPoints = matrix.restorePoints();
        DistMatrix restoredMatrix = new DistMatrix(restoredPoints);
        
        System.out.println("Source points:");
        printPoints(points);
        System.out.println("Source distances matrix:");
        printDistMatrix(matrix);
        System.out.println("Restored points:");
        printPoints(restoredPoints);
        System.out.println("Restored distances matrix:");
        printDistMatrix(restoredMatrix);
        System.out.println("Matrices are equals: " + matrix.equals(restoredMatrix));
    }
    
    private static Point[] generatePoints(int pointsNumber) {
        Point[] points = new Point[pointsNumber];
        for (int i = 0; i < points.length; i++) {
            points[i] = new Point(random.nextDouble(), random.nextDouble());
        }
        
        return points;
    }
    
    private static void printPoints(Point[] points) {
        for (int i = 0; i < points.length; i++) {
            System.out.println(points[i]);
        }
    }
    
    private static void printDistMatrix(DistMatrix matrix) {
        for (int i = 0; i < matrix.getPointsNumber(); i++) {
            for (int j = 0; j < matrix.getPointsNumber(); j++) {
                System.out.print(matrix.getDistance(i, j));
                System.out.print("  ");
            }
            
            System.out.println();
        }
    }
}

Компилировать и запускать так (предполагается, что мы находимся в директории с исходником тестового класса, и библиотека pr.jar лежит тут же):

Bash
1
2
javac -cp pr.jar PointsRestorerTest.java
java -cp .;pr.jar PointsRestorerTest

@boberjajtsegolo · 04.04.2014, 15:01

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

silent_1991 · 04.04.2014, 17:39

boberjajtsegolo, мне интересно, расскажите, пожалуйста. В частности, мне интересно, насколько мой алгоритм близок к тому (или далёк от того), что используется в ММШ. Ведь часто бывает так, что мы вновь изобретаем в точности то, что уже изобрели задолго до нас.

@kamre · 05.04.2014, 06:25

Сообщение от Igor3D

Чего так сложно - на мой взгляд, задачка-то простая. Базовые соображения...

NP-Hard.

Новые блоги и статьи Все статьи Все блоги /
Администрация Хабра удаляет новые алгоритмы, которые не западно ориентированной философии кода, без уведомлений и объяснений. Hrethgir 20.06.2026 Делается это, как замечено, при правках - при объявлении концептуальных отличий в алгоримах. Делается это, по линейке событий - после дополнения публикации основными отличиями от основных западных. . .	Процесс ориентированная диалектика (не новость - просто системное обновление, философия). Hrethgir 20.06.2026 Однажды один участник в своём блоге, на этом форуме, сделал запись "О языках замолвите слово". Понимая, что язык - важная вещь, я решил хорошо подумать, прежде чем сказать, и сказал то, что вы видите. . .	Контроль уникальности строк в табличной части документа Maks 18.06.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ПланированиеСпецтехники" с табличной частью "НаличиеОборудования", разработанного в КА2. Задача: контроль уникальности строк в. . .	Клиент Uhbif79 18.06.2026 Здесь простой клиент для работы с сервером.
Сервер Uhbif79 18.06.2026 Выкладываю простейший сервер.	Дефенестрация kumehtar 18.06.2026 Узнал интересное слово. Дефенестрация. Это когда ты выбрасываешь кого-либо или что-либо из окна. Возьму на вооружение)))	Дихотомия добра и зла kumehtar 18.06.2026 Как Дзен-буддисты говорят о добре и зле: не нужно воевать против зла, нужно воевать против невежества. Тогда добро станет ествественным, и поэтому вечным. Но дело в том, что невежество всё время. . .	Своя Интернет-Компания iceja 18.06.2026 Я программист с экономическим образованием, пишу свой проект, это SaaS для бизнесов. Мне нужен co-founder с высшим экономическим образованием, и/ или инвестор. Сейчас проект в интенсивной разработке,. . .

@nicolaus2 21 / 21 / 3 Регистрация: 11.07.2010 Сообщений: 63

	Матрица расстояний -> координаты на плоскости 12.02.2011, 18:53. Показов 11220. Ответов 43 Метки нет (Все метки) Здравствуйте. Имея координаты на плоскости мы с легкостью можем построить матрицу расстояний между всеми координатами. Но как сделать обратное(с матрицы расстояний получить координаты на плоскости)? Что-то ничего в голову не приходит. 0

Евгений М. 1080 / 1007 / 107 Регистрация: 28.02.2010 Сообщений: 2,889
	14.02.2011, 06:33
	Я только что врубился о чем речь. Я перечитал тему и понял, что речь идет о точках, с помощью которых можно сделать треугольник. На предыдущее сообщение забейте. 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	14.02.2011, 09:56
	Евгений М., речь идёт не обязательно о трёх точках. Но, возьми мы любые три точки из набора, они будут удовлетворять неравенству треугольника, поэтому предложенный способ справедлив для всего набора, и формально вы правы, из них можно сделать треугольник))). 1

@Ирэнка 0 / 0 / 0 Регистрация: 19.05.2015 Сообщений: 3
	04.06.2011, 21:16
	а как программу записать для нахождения этой матрицы? 0

@ColdDeath 0 / 0 / 0 Регистрация: 09.11.2013 Сообщений: 11
	19.01.2014, 01:47
	Так и не понял, как преобразовать матрицу расстояний в координатыточек. Напишите, пожалуйста, более подробно про преобрахование с помощью уравнения окружности. Лучше всего подкрепить теорию примером. Например, имеем матрицу расстояний: 0 2 5 7 2 0 5 4 5 5 0 6 7 4 6 0 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	19.01.2014, 23:12
	ColdDeath, для начала надо учесть, что матрица расстояний может быть вообще невалидной (т.е. таких расстояний между точками на обычной евклидовой плоскости быть не может). Это легко учесть, если на каком-либо шаге вычислений получилось уравнение, не имеющее действительных корней. Например, ваша матрица смежности невалидна, и дальше я покажу, почему. Давайте попробуем восстановить координаты точек по вашей матрице смежности. Мы сразу можем найти две точки - первую и вторую. Координаты первой точки - P1=(0, 0) (просто поместили её в начало координат). Координаты второй - P2=(0, 2) (отодвинули вторую точку от первой на нужное расстояние - 2 - по оси абсцисс). Теперь найдём координаты третьей точки. Сначала найдём общий вид нужного нам уравнения. Имеем общее уравнение окружности с произвольным центром: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{{(x-{x}_{0})}^{2}+{(y-{y}_{0})}^{2}}=R$ Возведём обе части в квадрат: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{(x-{x}_{0})}^{2}+{(y-{y}_{0})}^{2}={R}^{2}$ Перенесём член с иксом в правую часть: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{(y-{y}_{0})}^{2}={R}^{2}-{(x-{x}_{0})}^{2}$ Извлечём квадратный корень из обеих частей. $https://www.cyberforum.ru/cgi-bin/latex.cgi?y-{y}_{0}=\sqrt{{R}^{2}-{(x-{x}_{0})}^{2}}$ Ну и перенесём $https://www.cyberforum.ru/cgi-bin/latex.cgi?{y}_{0}$ в правую часть: $https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{{R}^{2}-{(x-{x}_{0})}^{2}}+{y}_{0}$ Таким образом, нам удалось выразить y из общего уравнения окружности. Это нам понадобится для того, чтобы найти точки пересечения пары окружностей. Для чего нам эти две окружности - дальше. Если нам требуется найти для известной (с заданными координатами) точки другую точку, расположенную от первой на заданном расстоянии, нам достаточно построить окружность с центром в первой точке радиуса, равного этому заданному расстоянию. Всё множество точек, составляющее полученную окружность, будет удовлетворять заданному условию: любая точка на окружности будет находиться на заданном расстоянии от первой точки. Однако если нам нужно найти точку, расположенную на заданных расстояниях от двух точек, нам нужно построить уже две окружности: одна окружность строится с центром в первой точке радиуса, равного расстоянию от этой первой точки до искомой, вторая - радиуса, равного расстоянию от второй точки до искомой с центром во второй точке. Точки пересечения этих двух окружностей и дадут искомую точку (на самом деле этих точек может быть две - по обе стороны от отрезка, соединяющего две исходные точки; одна (окружности соприкасаются, но не пересекаются) - точка лежит ровно на середине отрезка, соединяющего исходные; ни одной - точка, лежащая одновременно на обоих заданных расстояниях от двух исходных точек, не существует). Именно это мы и будем делать. Поскольку нам известны координаты первых двух точек, мы будем искать расстояния до остальных точек на основе первых двух. При этом надо учитывать следующие случаи: 1) очередная точка не может лежать одновременно на заданных расстояниях от двух первых точек; 2) очередная точка успешно найдена, она действительно лежит на нужных расстояниях от обеих первых точек, т.е. составляет с ними треугольник, но не может лежать на заданном расстоянии от одной или нескольких других точек, найденных в процессе работы алгоритма. В обоих этих случаях можно считать, что исходная матрица расстояний была некорректна. При этом для проверки второго случая необходимо искать расстояния от найденной точки до всех других уже найденных точек и смотреть, возможно ли его найти вообще (уравнение имеет действительные корни) и совпадает ли оно с указанным в матрице расстояний. Попробуем же найти третью точку. Для этого используем ранее найденное уравнение окружности. Построим окружность с центром в точке P1=(0, 0) радиуса 5: $https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{{5}^{2}-{(x-0)}^{2}}+2=\sqrt{25-{x}^{2}}+2$ Теперь построим вторую окружность - с центром в точке P2 радиуса 5 (радиус совпал, потому что у вас такая матрица смежности, в общем случае он, конечно, может быть разным): $https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{{5}^{2}-{(x-0)}^{2}}+2=\sqrt{25-{x}^{2}}+2$ Найдём точки пересечения этих двух окружностей. Для этого приравняем правые части полученных уравнений: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{25-{x}^{2}}=\sqrt{25-{x}^{2}}+2$ Возведём обе части в квадрат: $https://www.cyberforum.ru/cgi-bin/latex.cgi?25-{x}^{2}=25-{x}^{2}+4\sqrt{25-{x}^{2}}+4$ Приведём подобные и попутно выделим квадратный корень в одну часть, всё остальное - в другую: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{25-{x}^{2}}=-1$ Возведём обе части в квадрат и приведём подобные: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}^{2}=24$ Наконец, найдём корни уравнения: $https://www.cyberforum.ru/cgi-bin/latex.cgi?x=\pm 2\sqrt{6}$ Итак, мы нашли пару координат на оси абсцисс, которая может удовлетворять искомой точке. Теперь найдём координаты по оси ординат. Для этого нужной найденные иксы подставить сначала в уравнение для первой построенной окружности, затем в уравнение для второй: $https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{25-{2\sqrt{6}}^{2}}=\sqrt{25-24}=sqrt{1}=1$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{25-{2\sqrt{6}}^{2}}+2=\sqrt{25-24}+2=sqrt{1}+2=3$ Итого четыре разные точки, которые могут являться искомой: P31=( $https://www.cyberforum.ru/cgi-bin/latex.cgi?2\sqrt{6}$ , 1), P32=( $https://www.cyberforum.ru/cgi-bin/latex.cgi?2\sqrt{6}$ , 3), P33=( $https://www.cyberforum.ru/cgi-bin/latex.cgi?-2\sqrt{6}$ , 1), P34=( $https://www.cyberforum.ru/cgi-bin/latex.cgi?-2\sqrt{6}$ , 3). Чтобы узнать, какие из этих точек реально являются искомыми, нужно проверить расстояние от них до других уже найденных точек и отсеять те, которые не подходят (уравнение не имеет действительных корней либо найденное расстояние не совпадает с расстоянием из матрицы расстояний). Проблема (влияющая на скорость алгоритма) заключается в том, что для любой искомой точки мы можем найти до четырёх вариантов координат, и все они будут до определённого момента подходить под исходную матрицу расстояний. Таким образом, если мы ищем 11-ю точку, и все предыдущие имели по 4 набора координат, то нам нужно каждую из 4-х вновь найденных координат сопоставлять с каждыми 4-мя координатами для каждой точки. И даже по завершении работы алгоритма мы можем не получить однозначного набора (могут остаться точки с несколькими наборами координат). Выше я обещал показать, почему указанная вами матрица расстояний является некорректной. Попробуем найти 4-ю точку так же, как делали это с 3-ей. Построим две окружности (с центрами в первой и второй точках и соответствующими расстояниями): $https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{{7}^{2}-{(x-0)}^{2}}=\sqrt{49-{x}^{2}}$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\sqrt{{4}^{2}-{(x-0)}^{2}}+2=\sqrt{16-{x}^{2}}+2$ Приравняем правые части и проведум необходимые алгебраические преобразования. В итоге найдём икс: $https://www.cyberforum.ru/cgi-bin/latex.cgi?x=\pm 36.5625$ Сразу можем видеть, что с такими иксами, подставленными в уравнения окружностей, мы не сможем найти действительные корни этих уравнений. Действительно, 36.5625, возведённая в квадрат, больше как 16, так и 49. Разность даст нам отрицательный результат, арифметический квадратный корень из которого не существует (алгебраический же корень является комплексным, что нам не подходит по очевидным причинам). Таким образом, точки, отстоящей от точки P1 на расстояние 7, а от точки P2 на расстояние 4 э при том, что сами эти точки удалены друг от друга на расстояние 2, не существует, а значит, исходная матрица расстояний некорректна. Честно говоря, у меня до сих пор есть сомнения по поводу полной корректности данного алгоритма. В том, что он безошибочно распознает некорректную матрицу расстояний, я не сомневаюсь, а вот не будет ли ложноотрицательного срабатывания, т.е. не посчитает ли он корректную матрицу расстояний некорректной, я не уверен. Вообще, если завтра вечером будет время, я попробую написать реализацию алгоритма на C++ (или на Java, зависит от настроения ) и генератор случайных корректных матриц расстояний и посмотрю, отработает ли алгоритм на этих матрицах. 2

@ColdDeath 0 / 0 / 0 Регистрация: 09.11.2013 Сообщений: 11
	19.01.2014, 23:30
	Хорошо, спасибо Вам огромное! Читаю, пытаюсь вникнуть. Буду очень рад исходному коду алгоритма! Очень приятно и радостно, что в нашем мире есть люди, которые увлечены наукой и двигают прогресс вперед! А я вот сейчас ещё с нейронными сетями пытаюсь разобраться Дело в том, что нейронная сеть у меня не может произвести кластеризацию по матрице расстояний, точнее, делает это не всегда корректно. Тогда я подумал, что может быть данные ей будут более понятны, если они будут иметь форму координат. silent_1991, спасибо за то, что Вы делаете и за то, что так подробно всё для меня расписали! С нетерпением буду ждать исходного кода на C++. 0

@Igor3D 1977 / 833 / 115 Регистрация: 01.10.2012 Сообщений: 5,074 Записей в блоге: 2
	20.01.2014, 15:51
	Чего так сложно - на мой взгляд, задачка-то простая. Базовые соображения - Возьмем множество точек и поверим вокруг одной из них (как вокруг полярной звезды). Матрица расстояний никак не меняется - Флипнем (отразим) множество точек по x или y или относительно произвольной оси - опять матрица не изменилась. Отсюда следует что надо выбрать/зафиксировать систему координат. 1) Ставим первую точку в (0, 0) 2) Ставим вторую точку в (0, d(0, 1)) 3) Вычисляем 3-ю точку на основании d(0, 2) и d(1, 2). Получаются 2 варианта, принимаем любой 4) Вычисляем все остальные точки на основании d(0, i) и d(1, i). Получаются 2 варианта, используем 3-ю точку как проверочную. Все Да и вообще, от эксперта С++ ожидалось решение в 3 измерениях, что это за баловство плюшками на плоскости (да еще и на жабе)? 0

@Igor3D 1977 / 833 / 115 Регистрация: 01.10.2012 Сообщений: 5,074 Записей в блоге: 2
	21.01.2014, 14:45
	Если задача = проверить корректность матрицы, то можно действовать точно так же, и, если все точки успешно поселены, то просчитать все расстояния и сравнить. Но что Вы хотите от некорректных расстояний - для меня было и остается загадкой В любой задаче что-то "дано" и что-то "нужно получить", это нормально 0

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	21.01.2014, 16:51
	Я наверное в танке, но почему-то мне кажется, что такая задача имеет всегда бесконечное число решений... Пример в лоб. Пусть у нас есть набор координат задающий треугольник (x₁,y₁);(x₂;y₂);(x₃;y₃) со сторонами 3,4,5 на плоскости. Мне например очевидно, что применив оператор параллельного переноса мы получим новый набор координат (x^₁,y^₁);(x^₂;y^₂);(x^₃;y^₃) при сохранении длин сторон (расстояний между точками) а следовательно и матрицы расстояний. Добавлено через 41 секунду Или я задачу не так понял? 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	21.01.2014, 19:16
	HighPredator, ты всё правильно понял, на первой странице обсуждалось. Сошлись на том, что достаточно найти частное решение. Как правильно отметил Igor3D, три точки систему координат. Значит можем зафиксировать первую пару точек, найти на их основании третью, а затем, отталкиваясь от этой тройки, искать остальные. Igor3D, вот, наконец-то вы сказали то, что говорил я ещё три поста назад: без полной проверки не обойтись. Я ничего не хочу получить от некорректной матрицы, я хочу, чтобы алгоритм был универсальным, т.е. корректно реагировал на любые входные матрицы. А для универсальности необходимо проверять расстояния до всех уже найденных точек. Если бы я был уверен в том, что на вход всегда будет продана корректная матрица, мне бы это не понадобилось, но, к сожалению, быть в этом уверенным я не могу. 1

@boberjajtsegolo 35 / 35 / 4 Регистрация: 28.11.2012 Сообщений: 164
	04.04.2014, 15:01
	Вообщето нахождение координат точек по имеющимся расстояниям между ними это задача многомерного шкалирования(просто итеративный алогоритм, со своими плюсами и минусами), если все еще интересно, могу рассказать подробнее. 1

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	04.04.2014, 17:39
	boberjajtsegolo, мне интересно, расскажите, пожалуйста. В частности, мне интересно, насколько мой алгоритм близок к тому (или далёк от того), что используется в ММШ. Ведь часто бывает так, что мы вновь изобретаем в точности то, что уже изобрели задолго до нас. 0