Есть граф-дерево. Ну вообще в задаче оно в 3D, но я думаю алгоритм такой же будет и в 2D, так что пусть дерево плоское.
Надо как-то оптимально и понятным для визуального восприятия отрисовать линии в графе, чтоб они не сливались, не превращались в месиво и при этом обходили сами узлы графа. И еще одно условие- линии параллельны осям координат, ну то есть не гладкие сплайны надо, а состоящие из перпендикулярных кусочков.
Н>Есть где описание такой оптимальной отрисовки?
Так как неизвестно, что ты имеешь в виду под оптимальным, то спроси у гугла. Алгоритмов отрисовки графов море и под разные понимания оптимальности.
Здравствуйте, Нomunculus, Вы писали:
Н>Есть где описание такой оптимальной отрисовки?
В проекте GraphViz упоминает какой-то древний трактат, на основе которого создавался проект. Если лень читать манулы, то можно реализовать "детский" алгоритм:
1. Вершины представляем положительно заряженными частицами.
2. Рёбра представляем отрицательно заряженными частицами.
3. Частицы с разными знаками притягиваются, с одинаковыми — отталкиваются.
4. Моделируем движение всех частиц до наступления относительного покоя.
Здравствуйте, cppguard, Вы писали:
C>3. Частицы с разными знаками притягиваются, с одинаковыми — отталкиваются. C>4. Моделируем движение всех частиц до наступления относительного покоя.
Здравствуйте, Нomunculus, Вы писали:
Н>Есть граф-дерево. Ну вообще в задаче оно в 3D, но я думаю алгоритм такой же будет и в 2D, так что пусть дерево плоское.
Н>Надо как-то оптимально и понятным для визуального восприятия отрисовать линии в графе, чтоб они не сливались, не превращались в месиво и при этом обходили сами узлы графа. И еще одно условие- линии параллельны осям координат, ну то есть не гладкие сплайны надо, а состоящие из перпендикулярных кусочков.
Н>Есть где описание такой оптимальной отрисовки?
В общем случае похоже на задачу трассировки печатных плат.
Но для дерева она выглядит более-менее элементарно. Только надо уточнить, что такое "оптимально для визуального восприятия".
Дерево каталогов — одна история, ментальная карта — другая, дисковое пространство — третья...
Здравствуйте, Нomunculus, Вы писали: Н>Есть где описание такой оптимальной отрисовки?
1. Задача называется "планаризация графа". В общем случае — неразрешима. Для деревьев — разрешима.
2. Очевидных решений в заданных ограничениях — море. В качестве простейшего примера можно посмотреть на то, как Windows Explorer строит дерево каталогов:
— одна из координат X или Y выбирается для "глубины" элемента в дереве
— вторая координата определяется количеством потомков у всех предшествующих узлов текущего узла.
— множители при этих параметрах определяют шаг расстояния между узлами. Выбираем его таким, чтобы влезли изображения узлов, а также линий между ними
3. "Оптимальность" — штука субъективная. Для её достижения придётся задать какую-то метрику оптимальности.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Перекуём баги на фичи!
