Рисование двумерных точечных графиков

Question

У меня есть список объектов (вероятно, не более 100), где у каждого объекта есть расстояние до всех других объектов. Это расстояние - просто добавленная абсолютная разница между всеми полями, которые разделяют эти объекты. Может быть несколько (одно) или много (десятки) полей, поэтому размерность расстояния не важна.

Я бы хотел отобразить эти точки на двухмерном графике так, чтобы объекты с небольшим расстоянием появлялись близко друг к другу. Я надеюсь, что это ясно покажет, сколько подгрупп есть во всем списке. Очевидно, что оси этого графа не имеют смысла (я даже не уверен, что «график» - правильное слово для использования).

Какой будет хороший алгоритм для преобразования сети расстояний в двухточечное распределение точек? В идеале я хотел бы, чтобы небольшое изменение в дистанционной сети привело к небольшому изменению графики, чтобы постепенный прогресс можно было рассматривать как плавное изменение во времени.

Я сделал небольшой пример того результата, который ищу: Пример графика http://en.wiki.mcneel.com/content/upload/images/GraphExample.png

Любые идеи с благодарностью, David

---

Edit:

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

альтернативный текст http://en.wiki.mcneel.com/content/upload/images/ParticleCloudSolution.png

Я могу опубликовать код C #, если кому-то интересно (его, к сожалению, довольно много)

Answer 1

Graphviz содержит реализации нескольких различных подходов к решению этой проблемы; рассмотрите возможность использования инструментов макета графа пружинной модели в качестве основы для вашего решения. Кроме того, его сайт содержит хорошую коллекцию исходного материала по соответствующей теории.

Answer 2

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

Я думаю, что вам нужно немного разбираться в кластерном анализе, потому что есть алгоритмы для сортировки ваших точек в кластеры на основе метрики родства, а затем вы можете использовать graphviz или что-то подобное для получения результатов. http://en.wikipedia.org/wiki/Cluster_analysis

Мне очень нравится «алгоритм разбиения с минимальным вырезом», см. Здесь: http://en.wikipedia.org/wiki/Cut_(graph_theory)

Answer 3

Вы можете использовать Google для таких терминов, как:

• автоматическая разметка графика; и
• алгоритмы, основанные на силе.

GraphViz реализует некоторые из этих алгоритмов, но не уверен, что он включает в себя те, которые вам полезны.

Одно предостережение: для некоторых алгоритмов небольшие изменения в содержании вашего графика могут привести к очень большим изменениям в графике.