Рассчитать возможные координаты узлов

Это может быть странное приложение. Краткое описание проблемы: «Как получить абсолютную координацию узлов на основе относительных положений (расстояний)?»

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

Требуемый результат будет одним из возможных способов размещения этих узлов на 2D-поверхности.

Полученный алгоритм будет использоваться в C#... Так что внешние библиотеки .net тоже могут помочь.

Было бы здорово, если бы вы могли посоветовать мне способ сделать это. Заранее спасибо.


c# nodes algorithm
person uncommon_name    schedule 19.12.2015    source источник
comment
Под двумерной поверхностью вы подразумеваете плоскость или что-то более экзотическое, например, сферу или тор? Кроме того, что вы подразумеваете под соседними узлами? Удовлетворяет ли ваше назначение расстояний парам узлов неравенству треугольника? Без некоторых предположений о расстояниях не ясно, есть ли решение.   -  person John Coleman    schedule 20.12.2015
comment
Чтобы добавить к моему последнему комментарию: если у вас есть 4 узла, каждый из которых находится на расстоянии 1 от других 3 (назначение расстояний, удовлетворяющее неравенству треугольника), невозможно делать то, что вы хотите, на плоской поверхности в Евклидовом Космос. Последние три точки должны быть вершинами равностороннего треугольника, вписанного в окружность радиуса 1 с центром в первой точке, но равносторонний треугольник, вписанный в единичную окружность, не имеет ребер длины 1.   -  person John Coleman    schedule 20.12.2015
comment
Спасибо за комментарий. 2D-поверхность — это простая плоскость... ось XY с двойными шнурами. (На самом деле экран) Ввод осуществляется таким образом, чтобы обеспечить по крайней мере решение, и они удовлетворяют неравенству треугольника.   -  person uncommon_name    schedule 20.12.2015
comment
Я думаю, это правильный вопрос. Он имеет множество решений в зависимости от глубины понимания проблемы, что делает его еще более интересным. +1   -  person Gangnus    schedule 20.12.2015
comment
Я считаю, что вы ищете встраивание плоского графа.   -  person beaker    schedule 20.12.2015

Ответы (1)


arrow_upward
1
arrow_downward

Вы должны иметь координаты не менее трех известных точек на старте.

Способ I. Если известные точки соседние, то процесс прост - вы зацикливаете все свои точки, ищете такие, в списках которых есть три известные точки. Используйте два из них, чтобы подсчитать две возможные позиции, затем используйте третий, чтобы выбрать правый или левый вариант. Повторяйте циклы, пока у вас не будет новых точек во время цикла.

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

Путь 2. Если известные точки не соседствуют друг с другом, процесс усложняется.

  • Допустим, у вас есть начальные известные точки A,B,C.
  • Возьмите A и примыкающую к ней точку D. Поместите ее где-нибудь на правильном расстоянии от A.
  • Найдите некоторую точку E, смежную с A и D. Выберите любое из двух возможных положений.
  • Начиная с A, D, E, используйте способ I.
  • Когда вы дойдете по расстояниям до второй известной точки старта, пусть это будет B, конечно, она будет в плохом месте. Поверните всю сеть, которую вы построили вокруг A, так, чтобы B получил правильные координаты. Продолжайте зацикливание.
  • Когда вы достигнете последней из известных стартовых точек, C, она будет установлена ​​правильно или нет. Если нет, зеркально отобразите всю сеть относительно оси AB - C будет установлена ​​правильно. (Если нет, у вас неверные данные). Продолжайте так, как я зацикливаюсь до конца.

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

person Gangnus    schedule 19.12.2015