Какие хорошие алгоритмы для рисования линий между узлами графа?

То, что я специально занимаюсь, - это не только макет графика, но когда пользователь выбирает граф node и начинает перетаскивать его вокруг области экрана, строка должна постоянно перерисовываться, чтобы отразить то, что она будет выглядеть, если пользователь выпустит node. Я полагаю, что это часть алгоритма компоновки?

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

alt text http://img260.imageshack.us/img260/5458/nodesr.png

Ответ 1

Если ваши диаграммы не сумасшедшие, вам не нужен дополнительный алгоритм для этого, но просто используйте здравый смысл.

Покройте поверхность прямоугольной сеткой, а затем найдите способ подключения к ящикам с прямыми линиями вдоль линий сетки с минимальным количеством углов: если ящики не находятся на одинаковых линиях сетки, и вы не если вы подключаетесь, вам нужен один угол, если между ними нет другого node. Если есть, например, узлы в том, как вам нужен хотя бы еще один угол.
В качестве второго шага для более полных диаграмм добавьте код, который не только оптимизирует минимальное количество ребер, но и минимальную длину строк. Если ваши диаграммы не сумасшедшие, это должно быть едва заметным с точки зрения ответа приложения.
Для дополнительных глазных конфет вокруг углов с учетом длины обеих ног и проверки пересечений с другими предметами на поверхности. Я бы использовал 90 ° -круги кругов и отрегулировал радиус кругов (видимо, не то, что было сделано выше) - для более длинных ног радиус должен быть больше. Возможно, этот инструментарий, который вы используете, может помочь вам здесь.

Ответ 2

Вы знакомы с Graphviz? Я не уверен, как "динамические" и восстанавливаемые алгоритмы компоновки, но это может быть хорошей отправной точкой.

Ответ 3

Почему вы не смотрите в исходном коде Dia, чтобы узнать, как они это делают? http://live.gnome.org/Dia/Download

Ответ 4

чтобы продлить ответ @honk: для более плавных кривых вы можете просто взять 3 или 4 точки поворота и подключить их, используя квадратичные/кубические линии безье.

это пример в javascript из библиотеки графических изображений raphael

Ответ 5

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

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

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

Для алгоритмов "избегания" это не так сложно реализовать, когда вы просто хотите избежать "ящиков", представляющих ваши узлы... для удаления всех ваших строк немного больше задачи, а что-то, что не даже Visio работает. Чтобы избежать ящиков/узлов, использование промежуточной точки между краями окна (например, вертикальные края между geo1 и geo3) приятно делать для симметрии, а затем выбирать простое предопределенное расстояние, чтобы сохранить несвязанные линии (то есть линии которые не подключаются к этому конкретному ящику), вдали от ящиков тоже хорошо работает. Обобщенный алгоритм для этого прост в использовании, но слишком подробный для описания здесь, но по существу представляет собой набор обобщенных проверок и переключателей, работающих на горизонтальных и вертикально выровненных линиях и четвертных поворотах. Если вы хотите больше узнать о том, как это сделать, просто опубликуйте комментарий к этому ответу.

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