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

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

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

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

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

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

Евгений М. · 13.02.2011, 12:24

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

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

Можно примерчик?

@nicolaus2 · 13.02.2011, 21:15 **[ТС]**

Запросто.

Допустим, есть точки с координатами
(0,0)
(1,1)
(2,2)

Тогда матрица расстояний между ними будет выглядеть как:
0 1.4 2.8
1.4 0 1.4
2.8 1.4 0

Первая проблема заключается в том, что расстояние может быть следующим ...
1 до 3 - 50
1 до 2 - 10
2 до 3 - 10

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

Евгений М. · 13.02.2011, 21:26

Не понял.
А для точек
(1,1)
(2,2)
(3,3)
Матрица будет такая-же?

silent_1991 · 13.02.2011, 21:37

Евгений М., да, такая же))) Поэтому задача однозначно не разрешима.

Добавлено через 1 минуту
nicolaus2, это почему нам двухмерной системой координат не обойтись? В чём базис от расстояний между точками зависит?

Добавлено через 1 минуту
Погодите, и как такие расстояния могут быть? Неравенству треугольника не удовлетворяет.

Добавлено через 6 минут
Пускай даже нам действительно не хватает плоскости (точки в пространстве расположены), всё равно, эта задача аналогична исходной (когда точки лежат в плоскости).

@nicolaus2 · 13.02.2011, 21:47 **[ТС]**

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

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

silent_1991 · 13.02.2011, 21:48

Не-не, погодите. Данные не валидны, такого треугольника вам не найти.

@nicolaus2 · 13.02.2011, 22:27 **[ТС]**

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

Не-не, погодите. Данные не валидны, такого треугольника вам не найти.

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

Говорю же, что допустить. Те что выше - да, невалидны. Но допустить, что есть набор валидных данных и руководствоваться этим.

silent_1991 · 13.02.2011, 22:32

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

Добавлено через 3 минуты
Для примера:
Возьмём треугольник. Мы можем поворачивать его вокруг любой точки, не меняя его линейных размеров, и можем двигать этот треугольник как захотим по плоскости. Значит, можно всегда найти три такие координаты, для которых матрица расстояний будет равна заданной (достаточно таскать треугольник по плоскости и вертеть его, как нам захочется, не трансформируя его при этом).

Евгений М. · 13.02.2011, 22:37

nicolaus2, в каком пространстве Вы хотите найти такие точки?

Добавлено через 41 секунду
В векторном Вы их не найдете. Там действует неравенство треугольника.

silent_1991 · 13.02.2011, 22:40

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

@nicolaus2 · 13.02.2011, 22:41 **[ТС]**

Евгений М., в евклидовой плоскости.

silent_1991, верно. Целью является найти хотя бы один набор точек, который удовлетворяет матрице расстояний.

Евгений М. · 13.02.2011, 22:47

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

в евклидовой плоскости.

Там тоже действует неравенство треугольника.

silent_1991 · 13.02.2011, 22:48

Ну тогда берём за основу (первую точку) точку (0, 0). Откладываем вторую точку по оси абсцисс на столько, чтобы получилось расстояние между (0, 0) и второй точкой как в матрице. Затем третью по оси же абсцисс откладываем от первой на нужное расстояние, а потом начинаем двигать её по окружности вокруг первой, пока не достигнем нужного расстояния со второй. и так далее... По-моему, что-то должно выйти.

@nicolaus2 · 13.02.2011, 22:53 **[ТС]**

Ну тогда берём за основу (первую точку) точку (0, 0). Откладываем вторую точку по оси абсцисс на столько, чтобы получилось расстояние между (0, 0) и второй точкой как в матрице. Затем третью по оси же абсцисс откладываем от первой на нужное расстояние, а потом начинаем двигать её по окружности вокруг первой, пока не достигнем нужного расстояния со второй. и так далее... По-моему, что-то должно выйти.

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

Ну да, так я и думал ... просто если таких точек 100 или больше, то долго двигать придется.

Спасибо.

silent_1991 · 13.02.2011, 22:57

nicolaus2, ну бинарный поиск помочь должен в этом случае. Делим первую приблизительную дугу на две и смотрим, в центрах какой из полученных двух дуг расстояние ближе к нужному.
Или я что-то гоню?.. По логике вроде должно работать.

Евгений М. · 13.02.2011, 23:05

См. вложение.
Поставил точки (0;0) и (1;0). Точка (0;0) "пытается найти" точку у которой расстояние равна 1 (по зеленой окружности), точка (1;0) пытается найти точку у которой расстояние равна 5.
Пересечение окружностей - нужная третья точка. В данном случае ничего не пересекается.

silent_1991 · 13.02.2011, 23:10

Евгений М., не понял... Какая матрица смежности подразумевается для данного примера?

@nicolaus2 · 13.02.2011, 23:13 **[ТС]**

Евгений М.Ю., немного не понял о чем Вы.

silent_1991, ну тут проблема не в том как двигать, а как расставить точки сразу, чтобы совсем не двигать)

silent_1991 · 13.02.2011, 23:30

Тут для каждой точки достаточно составить два уравнения окружности - одно с центром в нуле и радиусом, равным расстоянию от нуля (первой точки) до данной, а второе - с центром в предыдущей точке и радиусом, равным расстоянию от предыдущей точки до данной. Приравниваем их, выражаем y, решаем, находим пару иксов. Вот и мгновенная расстановка.

Добавлено через 1 минуту
С учётом того, что координаты первой пары точек известны изначально ((0; 0) и (d; 0), где d - расстояние от первой точки до второй), то на каждом шаге всё необходимое нам известно.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

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

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

@nicolaus2 21 / 21 / 3 Регистрация: 11.07.2010 Сообщений: 63
	13.02.2011, 21:15 [ТС]
	Запросто. Допустим, есть точки с координатами (0,0) (1,1) (2,2) Тогда матрица расстояний между ними будет выглядеть как: 0 1.4 2.8 1.4 0 1.4 2.8 1.4 0 Первая проблема заключается в том, что расстояние может быть следующим ... 1 до 3 - 50 1 до 2 - 10 2 до 3 - 10 И тогда двумерной системой координат нам не обойтись. Но все равно, даже без этой проблемы ничего в голову не приходит. 0

Евгений М. 1080 / 1007 / 107 Регистрация: 28.02.2010 Сообщений: 2,889
	13.02.2011, 21:26
	Не понял. А для точек (1,1) (2,2) (3,3) Матрица будет такая-же? 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	13.02.2011, 21:37
	Евгений М., да, такая же))) Поэтому задача однозначно не разрешима. Добавлено через 1 минуту nicolaus2, это почему нам двухмерной системой координат не обойтись? В чём базис от расстояний между точками зависит? Добавлено через 1 минуту Погодите, и как такие расстояния могут быть? Неравенству треугольника не удовлетворяет. Добавлено через 6 минут Пускай даже нам действительно не хватает плоскости (точки в пространстве расположены), всё равно, эта задача аналогична исходной (когда точки лежат в плоскости). 0

@nicolaus2 21 / 21 / 3 Регистрация: 11.07.2010 Сообщений: 63
	13.02.2011, 21:47 [ТС]
	Ну так я ж и говорю, допустить, что все данные валидны и отбросить все остальные проблемы. Но даже в таком случае, все равно, в голову ничего вразумительного не приходит, кроме как в цикле как то двигать точки, пока расстояния между ними не буду удовлетворительными. 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	13.02.2011, 21:48
	Не-не, погодите. Данные не валидны, такого треугольника вам не найти. 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	13.02.2011, 22:32
	nicolaus2, ну если так - только что вам Евгений М. на примере доказал что возможны как минимум два набора точек для одной матрицы расстояний (на самом деле их бесконечное множество). Добавлено через 3 минуты Для примера: Возьмём треугольник. Мы можем поворачивать его вокруг любой точки, не меняя его линейных размеров, и можем двигать этот треугольник как захотим по плоскости. Значит, можно всегда найти три такие координаты, для которых матрица расстояний будет равна заданной (достаточно таскать треугольник по плоскости и вертеть его, как нам захочется, не трансформируя его при этом). 0

Евгений М. 1080 / 1007 / 107 Регистрация: 28.02.2010 Сообщений: 2,889
	13.02.2011, 22:37
	nicolaus2, в каком пространстве Вы хотите найти такие точки? Добавлено через 41 секунду В векторном Вы их не найдете. Там действует неравенство треугольника. 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	13.02.2011, 22:40
	Евгений М., полагаю, речь про обычную евклидову плоскость, просто там был не совсем корректный пример ("ляпнул, не подумав"), а так точки должны быть валидные (как раз подчиняющиеся неравенству треугольников). 0

@nicolaus2 21 / 21 / 3 Регистрация: 11.07.2010 Сообщений: 63
	13.02.2011, 22:41 [ТС]
	Евгений М., в евклидовой плоскости. silent_1991, верно. Целью является найти хотя бы один набор точек, который удовлетворяет матрице расстояний. 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	13.02.2011, 22:48
	Ну тогда берём за основу (первую точку) точку (0, 0). Откладываем вторую точку по оси абсцисс на столько, чтобы получилось расстояние между (0, 0) и второй точкой как в матрице. Затем третью по оси же абсцисс откладываем от первой на нужное расстояние, а потом начинаем двигать её по окружности вокруг первой, пока не достигнем нужного расстояния со второй. и так далее... По-моему, что-то должно выйти. 1

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	13.02.2011, 22:57
	nicolaus2, ну бинарный поиск помочь должен в этом случае. Делим первую приблизительную дугу на две и смотрим, в центрах какой из полученных двух дуг расстояние ближе к нужному. Или я что-то гоню?.. По логике вроде должно работать. 0

Евгений М. 1080 / 1007 / 107 Регистрация: 28.02.2010 Сообщений: 2,889
	13.02.2011, 23:05
	См. вложение. Поставил точки (0;0) и (1;0). Точка (0;0) "пытается найти" точку у которой расстояние равна 1 (по зеленой окружности), точка (1;0) пытается найти точку у которой расстояние равна 5. Пересечение окружностей - нужная третья точка. В данном случае ничего не пересекается. Миниатюры 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	13.02.2011, 23:10
	Евгений М., не понял... Какая матрица смежности подразумевается для данного примера? 0

@nicolaus2 21 / 21 / 3 Регистрация: 11.07.2010 Сообщений: 63
	13.02.2011, 23:13 [ТС]
	Евгений М.Ю., немного не понял о чем Вы. silent_1991, ну тут проблема не в том как двигать, а как расставить точки сразу, чтобы совсем не двигать) 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	13.02.2011, 23:30
	Тут для каждой точки достаточно составить два уравнения окружности - одно с центром в нуле и радиусом, равным расстоянию от нуля (первой точки) до данной, а второе - с центром в предыдущей точке и радиусом, равным расстоянию от предыдущей точки до данной. Приравниваем их, выражаем y, решаем, находим пару иксов. Вот и мгновенная расстановка. Добавлено через 1 минуту С учётом того, что координаты первой пары точек известны изначально ((0; 0) и (d; 0), где d - расстояние от первой точки до второй), то на каждом шаге всё необходимое нам известно. 0