Как визуализировать взаимное расположение точек, зная расстояние между ними?

Question

[coolakov]

Приветствую. Способов определения расстояния между точками по их координатам полно. Но у меня обратная задача: известны попарные расстояние между множеством точек, нужно отобразить их на плоскости: без координат, но с корректным отображением расстояния между точками. В математике и геометрии я слабоват, самостоятельно решения найти не смог.
Конкретизирую задачу.
Есть 4 точки на плоскости, A, B, C, D. Попарные расстояния:
AB=3, AC=4, AD=5;
BA=3, BC=5, BD=4;
CA=4, CB=5, CD=3;
DA=5, DB=4, DC=3.
Нужно отобразить взаимное расположение этих точек на плоскости. Подскажите возможные способы решения.

Answer 1

[SeptiM]

Берем две точки A и B на расстоянии r, желательно, максимально удаленные. Одну ставим в (0, 0), другую в (r, 0). Берем третью точку C. Нам известно AC и BC. Находим пересечение двух окружностей с радиусом AC и BC и центрами в A и B соответственно. Пересечение состоит не более чем из двух точек, берем любую.

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

Answer 2

[Николай]

Предположите, что одна из точек находится в (0,0), составьте систему уравнений используя формулу о расстоянии между двумя точками, решите её любым методом.

Answer 3

[coolakov]

Николай, спасибо за ответ.
Да, для данного конкретного случая я пришел к аналогичному решению: выбираем опорную точку, составляем систему уравнений, решаем.
Но нет ли какого-либо общего алгоритма решения, упрощающего расчеты при наличии 100, 1000 точек? Или в любом случае, для 1000 точек придется решать систему из 1000 (даже больше) уравнений?

Comments

[Николай]

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

[coolakov]

Николай: coolakov @coolakov
Нагуглил матричные способы решения для систем линейных уравнений. Для систем квадратных уравнений решения через матрицы найти не удалось.
Вот получилась у меня система уравнений (при x1=0, y1=0):
(0-x2)^2 + (0-y2)^2 = 3^2
(0-x3)^2 + (0-y3)^2 = 4^2
(0-x4)^2 + (0-y4)^2 = 5^2
(x2-x3)^2 + (y2-y3)^2 = 5^2
(x2-x4)^2 + (y2-y4)^2 = 5^2
(x3-x4)^2 + (y3-y4)^2 = 3^2
Что мне с этим дальше делать?

[Николай]

Можно попробовать сделать замену переменной: x1-x2 = t1, x1-x3 = t2, x2-x3=tn.... и добавив в систему новые уравнения: t1-t2 + tn = 0. Честно говоря линейная алгебра была давно, но мне кажется - это должно решить.