11.03.2024, 20:25 | #1 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,015
|
Координаты точек по матрице расстояний
Прямая задача.
Дан набор точек, заданных своими координатами (xi,yi). По ним можно рассчитать матрицу попарных расстояний между точками dij=sqrt( (xi-xj)^2+(yi-yj)^2 ) Обратная задача. Дана матрица расстояний между точками D=(dij). Т.е. dij - расстояние между двумя точками (xi,yi) и (xj,yj) Можно ли найти координаты точек?
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
11.03.2024, 20:28 | #2 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,716
|
Иногда, многогранник жёсткий. тогда, с точностью до поворотов и переносов, наверное.
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
11.03.2024, 20:29 | #3 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,716
|
Если мы на плоскости то жёсткий это треугольник. Если в объеме то тетраэдр.
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
11.03.2024, 20:30 | #4 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,015
|
Цитата:
если точек больше, то уже не вариант)))
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
11.03.2024, 20:33 | #5 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,716
|
То есть по матрице надо понять, все ли жёсткие фигуры жёстко связаны между собой прямо или косвенно.
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
11.03.2024, 20:51 | #6 | |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,015
|
Цитата:
матрица расстояний - частный случай, более общее понятие - матрица различий, чем показатель меньше, тем менее различаются объекты, и наоборот может иметь в принципе любой смысл 1. например, расстояние по графу дорог тогда, если две точки на карте расположены напротив друг друга через железную дорогу (или речку), а переезд через 10 км - в евклидовом пространстве должны быть разнесены друг от друга далеко 2. время проезда от точки А в точку Б. Если есть временные окна - тогда время проезда + время ожидания, если приехали раньше назначенного времени 3. стоимость проезда - если например, развозим не груз. а мастер по заявкам выполняет настройку оборудования - тогда стоимость проезда + стоимость работ 4. сложность выполнения заявки - может быть вообще в баллах (или усл. ед.)
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
|
11.03.2024, 20:59 | #7 |
Администратор
Регистрация: 18.02.2010
Сообщений: 17,015
|
в такой постановке могут возникать разные сложности
1. не выполняется неравенство треугольника, т.е. доехать через третью точку реально может оказаться быстрее, чем напрямую 2. матрица различий не обязана быть симметричной (dij=dji), например, в случае односторонней дороги, из А в Б едем 5 мин, а обратно - 15 мин 3. граф может быть неполным, первый клиент ждет товар с утра, второй вечером, тогда от А до Б есть путь, обратно нет 4. граф может быть непланарным, т.е. не лежать в плоскости без самопересечений - многоуровневые развязки на дорогах, трубопроводы (одна труба под другой) и еще куча всяких нюансов и заморочек.... )))
__________________
Да здравствует то благодаря чему мы несмотря ни на что!!! |
11.03.2024, 22:31 | #8 | |
Шволочь. И провокатор.
Регистрация: 12.02.2006
Сообщений: 31,362
|
Цитата:
__________________
... Survivors will be shot again. |
|
11.03.2024, 23:20 | #9 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,716
|
Ну, если граф предполагается на эвклидовых точках, то можно поставить вопрос о его жёсткости.
Если 4 точки на плоскости соединить 4 мя ребрами то это или подвижный 4 угольник либо треугольник к которому прикреплен отрезок, обе конструкции допускают вариативность за пределами поворотов и смещений. Третий признак равенства треугольников по 3 сторонам. А вот четырехугольник по четырем сторонам равнять нельзя у них углы варьировать можно. Но задав доп ограничения опять можно жёстким сделать. Поэтому вопрос о жёсткости графа не лишён какого то топологического смысла.
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |
11.03.2024, 23:26 | #10 |
Сетевой эльф
Регистрация: 27.09.2007
Сообщений: 37,716
|
Допустим граф построен по ограничениям расстояний. Если существует такое расстояние эль малое, что переместив любую вершину кроме нулевой на это или меньшее расстояние, можно путем смещения остальных вершин сохранить весь набор ограничений, то граф нежесткий.
Так себе определение, конечно....
__________________
Магическое зеркало: видеть себя в других, видеть других в себе... Предпочитаю вежливость. |