Маршрутизация ортогональных соединений в редакторах диаграмм

  • Tutorial

Маршрутизация ортогональных соединений в редакторах диаграмм


В данной статье я покажу, как решить проблему маршрутизации соединений в редакторе диаграмм типа MS Visio. Здесь будет минимум теории и максимум практики. Если вам нужно быстро реализовать маршрутизацию соединений в двумерной сцене, и вы первый раз сталкиваетесь с подобной проблемой — то эта статья для вас.



Проблематика


К данной проблеме я пришел в процессе разработки своего хобби-проекта ultra_outliner. Грубо говоря, в нем есть двумерная сцена, в которой находится много прямоугольных карточек, которые могут быть связаны между собой. И соединений может быть довольно много — а значит их нужно маршрутизировать, чтобы сегменты не накладывались, не пересекали карточки и др.


Многие из вас работали с Microsoft Visio, и конечно же оценили, как красиво автоматически маршрутизируются стрелочки. Конечно, и Visio не всегда справляется, и для таких случаев есть возможность ручной подгонки. Но тем не менее, не рассматривая крайние ситуации — мне захотелось это повторить. Действительно, ведь там все этим проблемы достаточно неплохо решены.



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


Собственная реализация


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


Далее, в простейшем случае, перебираем соединения по одному, и алгоритмом Алгоритм Дейкстры по очереди строим соединения. Из карточек строим карту препятствий, а в эвристическую функцию добавляем штрафы за пересечение соединений. Также запрещаем двум соединениям иметь общие совпадающие сегменты (наложение вдоль).


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


Разработка программного интерфейса


Перспектива работать с libavoid в чистом виде в своем коде верхнего слоя мне не понравилась, т.к. API специфическое и надо следить, где и когда очищать память. Да и к тому же callback'и идут по глобальной функции. Поэтому было решено сделать обертку, которая за всем этим будет следить.


Собственно, начнем с включением заголовочного файла:


#include <libavoid/libavoid.h>

Модель обертки представляется в виде ориентированного графа, где есть узлы и ребра. Узел прямоугольный. Таким образом, у класса маршрутизатора получается следующий интерфейс:


class edge_router
{
public:
    //Создать узел с заданной геометрией и вернуть указатель на него
    node_t * create_node(const rect_t & rect);

    //Изменить геометрию заданного узла
    void set_node_rect(node_t * pnode, const rect_t & rect);

    //Создать соединение между двумя узлами
    edge_t * create_edge(node_t * src, node_t * dest)

    //Удалить соединение
    void remove_edge(edge_t * p_edge);

    //Удалить узел
    void remove_node(node_t * p_node);

    //Маршрутизировать
    void reroute();

private:
    Avoid::Router aRouter;
    std::vector<node_t*> nodes;
    std::vector<edge_t*> edges; 
    delegate_t * pDelegate;
};

В описании узла, не считая вспомогательных методов сделаем указатель на libavoid-узел:


struct node_t
{
    ...
    Avoid::ShapeRef * aNode;
};

А в ребре сделаем указатель на libavoid-соединение, а зачем здесь нужен edge_router, станет ясно позже:


struct edge_t
{
    ...
    edge_satelite data;
    edge_router * pRouter;
    Avoid::ConnRef * aEdge;
};

В edge_satelite будем хранить информацию для callback-a, который, как правило, будет являться указателем на графическое ребро (т.е. объект соединения на верхнем слое нашей реализации). Поэтому для универсальности можно вынести его вообще в шаблон (и соответственно, внести такую правку в edge_router). Тогда для обработки событий изменения геометрии ребер опишем интерфейс delegate_t:


template<typename E>
class router_delegate
{
public:
    using edge_satelite = E;

    virtual void edge_updated(edge_satelite, const std::vector<pos_t> &) = 0;
};

Теперь интерфейса обертки хватит, чтобы справиться с нашей первоначальной задачей. Все взаимодействие с libavoid (либо с собственной реализацией) останется внутри него. Далее, рассмотрим реализацию описанных методов.


Реализация слоя маршрутизации


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


edge_router::edge_router()
    :aRouter(Avoid::OrthogonalRouting) //Ортогональная маршрутизация
{
    aRouter.setRoutingPenalty(Avoid::segmentPenalty, 50);   //Штраф за "лесенки""
    aRouter.setRoutingPenalty(Avoid::shapeBufferDistance, 20);  //Толщина "мертвой" зоны вокруг узлов
    aRouter.setRoutingPenalty(Avoid::idealNudgingDistance, 20); //Оптимальная дистанция между содеинениями с узлами
    aRouter.setRoutingOption(Avoid::RoutingOption::nudgeOrthogonalSegmentsConnectedToShapes, true); //Разносить точки соединения
}

Далее, создание/удаление узлов:


node_t * edge_router::create_node(const rect_t & rect = rect_t(0, 0, 10, 10))
{
    node_t * new_node = new node_t;
    Avoid::Rectangle shapeRect(Avoid::Point(rect.x, rect.y), Avoid::Point(rect.x + rect.w, rect.y + rect.h));
    new_node->aNode = new Avoid::ShapeRef(&aRouter, shapeRect);
    new Avoid::ShapeConnectionPin(new_node->aNode, 1, Avoid::ATTACH_POS_CENTRE, Avoid::ATTACH_POS_CENTRE, true, 0.0, Avoid::ConnDirNone);
    nodes.push_back(new_node);
    return new_node;
}

void edge_router::remove_node(node_t * p_node)
{
    auto it = std::find(nodes.begin(), nodes.end(), p_node);
    nodes.erase(it);
    aRouter.deleteShape(p_node->aNode);
}

Т.е. создаем прямоугольную фигуру с точкой привязки в центре. Сразу предостерегу — если делать несколько точек привязки — начинаются непонятные тормоза, поэтому лучше делать одну точку, и разносить граничные точки соединений на границу (за счет nudge). Изменение геометрии узла (включая простое перемещение), которое приводит к перемаршрутизации, описывается:


void edge_router::set_node_rect(node_t * pnode, const rect_t & rect)
{
    aRouter.moveShape(pnode->aNode, Avoid::Rectangle(Avoid::Point(rect.x, rect.y), Avoid::Point(rect.x + rect.w, rect.y + rect.h)));
}

С соединениями примерно аналогично:


edge_t * edge_router::create_edge(node_t * src, node_t * dest)
{
    edge_t * new_edge = new edge_t;
    new_edge->pRouter = this;   //Понадобится дальше для callback'a
    edges.push_back(new_edge);

    Avoid::ConnEnd dstEnd(src->aNode, 1);
    Avoid::ConnEnd srcEnd(dest->aNode, 1);
    new_edge->aEdge = new Avoid::ConnRef(&aRouter, srcEnd, dstEnd);
    new_edge->aEdge->setCallback(libavoid_conn_callback<E>, new_edge);

    return new_edge;
}

void edge_router::remove_edge(edge_t * p_edge)
{
    auto it = std::find(edges.begin(), edges.end(), p_edge);
    edges.erase(it);
    aRouter.deleteConnector(p_edge->aEdge);
}

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


template<typename E>
static void libavoid_conn_callback(void *ptr)
{
    using edge_t = typename edge_router<E>::edge_t;
    auto edge = static_cast<edge_t*>(ptr);

    //Получим рассчитанный маршрут
    auto & route = edge->aEdge->displayRoute(); 

    //И выполним небольшую постобработку
    std::vector<pos_t> path;
    for (size_t i = 0; i < route.ps.size(); ++i)
        path.push_back(pos_t(route.ps[i].x, route.ps[i].y));

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

    //И поскольку функция глобальная - получим нужный объект через ребро, и вызове callback 
    edge->pRouter->pDelegate->edge_updated(edge->data, path);
}

И, наконец, вызов самой маршрутизации:


void edge_router::reroute()
{
    aRouter.processTransaction();
}

Теперь рассмотрим реализацию самой сцены с использованием данного результата.


Реализация верхнего слоя графической сцены


Описываемая реализация осуществлялась с использованием QT поверх базового класса двумерной сцены QGraphicsScene. У сцены сделаем интерфейс для создания узлов, создания соединений, их перемещения и удаления:


class diagram_scene : public QGraphicsScene, public router_delegate<routable_link_image*>
{
    Q_OBJECT

public:
    using router_t = edge_router<routable_link_image*>;

    diagram_scene();
    void add_image(movable_image * img);
    void remove_image(movable_image * img);
    routable_link_image * create_connection(movable_image * src, movable_image * dst);
    void remove_connection(connector_image * conn);
private:
    router_t edgeRouter;

    std::map<movable_image*, router_t::node_t*> routableNodes;
    std::vector<movable_image*> nodes;
    std::vector<routable_link_image*> edges;

    bool enableRouting;
};

Проставим в конструкторе саму сцену в качестве получателя callback-ов:


diagram_scene::diagram_scene()
{
    edgeRouter.pDelegate = this;
}

Добавление соединяемого элемента в сцену (movable_image, наследованного от QGraphicsItem) должно сопровождаться добавлением его в QGraphicsScene с соответствующим вызовом обертки:


void diagram_scene::add_image(movable_image * img)
{
    addItem(img);
    nodes.push_back(img);
    routableNodes.insert(make_pair(img, edgeRouter.create_node(to_rect(img->sceneBoundingRect()))));        //Создаем в маршрутизаторе
}

Удаление будет достаточно симметричным:


void diagram_scene::remove_image(movable_image * img)
{
    removeItem(img);
    auto it = std::find(nodes.begin(), nodes.end(), img);
    nodes.erase(it);

    auto rit = routableNodes.find(img);
    edgeRouter.remove_node(rit->second);    //Удаляем из маршрутизатора
    routableNodes.erase(rit);
}

Аналогичная реализация для соединений, где routable_link_image — это наследник от QGraphicsPathItem, т.е. графический объект соединения:


routable_link_image * diagram_scene::create_connection(movable_image * src, movable_image * dst)
{
    auto new_img = new routable_link_image(pConfig, src, dst);
    auto src_it = routableNodes.find(src),
        dst_it = routableNodes.find(dst);

    new_img->routerEdge = edgeRouter.create_edge(src_it->second, dst_it->second);   //Создаем в маршрутизаторе
    new_img->routerEdge->data = new_img;
    addItem(new_img);   //Добавляем на сцену
    edges.push_back(new_img);

    return new_img;
}

void diagram_scene::remove_connection(connector_image * conn)
{
    auto it = std::find(edges.begin(), edges.end(), conn);
    edgeRouter.remove_edge((*it)->routerEdge);  //Удаляем из маршрутизатора
    edges.erase(it);
}

И, наконец, сделаем перестроение соединения при вызове callback-а.


void diagram_scene::edge_updated(routable_link_image * img, const std::vector<pos_t> & path)
{
    img->rebuild(path); //Пробежаться по точкам, обновить сам QGraphicsItem
}

Готово. Теперь надо разобраться с вызовом маршрутизации.


Вызов маршрутизации


Как правило, везде, где задействованы алгоритмы поиска на графах, вычисления требуют достаточно много ресурсов, и здесь — не исключение. Любое перестроение маршрутизации в Debug сборке будет происходить несколько секунд (хотя в Release летает). Поэтому, необходимо свести к минимуму соответствующие вызовы.


Поэтому, маршрутизацию есть смысл вызывать:


  • При добавлении новых узлов
  • При пермещении узлов
  • При удалении узлов

Более того, иногда надо сделать несколько действий в рамках одной логической транзакции, и выполнить маршрутизацию только в конце. Для этого реализуем некое подобие рекурсивного mutex-а. Введем в diagram_scene атрибут с инициализирующим значением true:


bool enableRouting;

Вызов маршрутизации тоже будем осуществляться из diagram_scene:


void diagram_scene::reroute()
{
    if (enableRouting)
        edgeRouter.reroute();
}

А вот для обеспечения так называемых транзакций, введем по аналогии с std::lock_guard свою структуру:


struct routing_guard
{
    routing_guard(diagram_scene * obj)
        :pObject(obj), baseVal(pObject->enableRouting)
    {
        pObject->enableRouting = false;
    }

    ~routing_guard()
    {
        pObject->enableRouting = baseVal;
        pObject->reroute();
    }

    diagram_scene * pObject;
    bool baseVal;
};

И пользоваться можно следующим образом:


{
    routing_guard grd(pScene);
    //Осуществление манипуляций со сценой
    ...
}   //Вызов деструктора и маршрутизация

Можно создавать несколько routing_guard подряд, и маршрутизация будет вызвана после уничтожения последнего.


Заключение


Посмотреть как это работает на практике можно в прототипе ultra_outliner. Для этого совсем не надо вникать в суть самой программы, а можно просто открыть файл с примером из папки samples, открыть вкладку "сюжеты" или "персонажи" (из project explorer'a слева), и там подвигать соединенные элементы. Любое изменение сцены будет вызывать перестроение маршрутизации.


Чтобы все выглядело симпатичней, на соединениях есть дополнительные элементы (стрелочки, joint-ы), но это уже все элементы дизайна.


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

Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 21

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

    На что тут тратить много лет непонятно? Но Вам виднее. Точнее не виднее.

      +1
      почитайте научные публикации автора по тематике, думаю станет понятней
      http://marvl.infotech.monash.edu/~mwybrow/#publications
      +1
      Потребности в приложении не испытываю, но симпатичный интерфейс, векторная графика схем и наличие английского языка вызывают желание поискать ему применение.

      Иконка ужасна, английский хотелось бы по-умолчанию, а «кастомизацию» лучше всё-таки заменить на «настройку». С переводом на немецкий могу помочь (пока что он у вас очень… своеобразный ;).
        0
        немецкий пока добавлен скорее для эксперимента, это небольшой хобби-проект, далекий от боевого релиза. но спасибо за предложение, может обращусь в будущем :)
        0
        Глупый вопрос. А вы помогли автору задокументировать то, что вам не хватало?
          0
          ну это тяжело выделить в страницу формальной документации. фактически это и есть назначение данной публикации
            0
            Знаю, что трудно. Но это было бы намного ценнее.
            Кстати, нигде не нашёл исходников. Выглядит красиво, но под мои нужды не очень подходит. На базе вашей программы можно попробовать сделать красивую mind-map программу.
            Может быть хотя бы куски реализации графики опубликуете? Классы для qt там…
              0
              если у кого-то будет интерес, и у меня силы — то я смогу выдрать реализацию diagram_scene со всей обвязкой, и сделать соответствующий разъясняющий пост. Фактичкски, это сцена, в которой можно выделять объекты, перемещать, и соединять. Но пока это все в таком экспериментальном состоянии, что местами даже стыдно показывать. Поэтому этот материал пока не созрел.
          +1
          У вас есть серьезные трудности с оптимальностью кода.

          1) Векторы и push_back, или «автор не знает о resize»
          std::vector<pos_t> path;
          for (size_t i = 0; i < route.ps.size(); ++i)
          path.push_back(pos_t(route.ps[i].x, route.ps[i].y));

          Многократный вызов push_back здесь неуместен (будут переаллокации). Лучше сделать resize заранее:
          std::vector<pos_t> path;
          path.resize(route.ps.size());
          for (size_t i = 0; i < route.ps.size(); ++i)
             path[i]=pos_t(route.ps[i].x, route.ps[i].y);
          


          2) А вот тут уже серьезный источник проблем с производительностью:
          auto it = std::find(nodes.begin(), nodes.end(), p_node);

          Честно говоря, это абсурд. Потому что вы для контейнера с логарифмическим поиском (map) вызываете линейный поиск.

          Ну и (хотя бы во время отладки) имеет смысл проверять, не вернул ли find конец контейнера. И использовать константные декларации.
            +2
            трудностей нету, здесь было целью наглядно и просто показать. поэтому упрощал как мог.
            1) код выполняется редко, и потери ничтожны по сравнению с работой маршрутизации
            2) nodes вообще-то вектор. можно сделать map-индексы, но код сложней воспринимать.
              0
              Мне кажется, что тут оптимально будет вызывать не resize() + push_back(), а reserve() + emplace_back() — нет лишних копирований и вызовов дефолтных конструкторов, еще и перемещение в push_back() экономится.
                0
                если уж совсем грамотно — то тут можно лишнего вектора избежать, и копирования вообще :) но как я уже сказал — здесь главное наглядность
              0

              Поискал на сайте и в gihub-репозитории, но не нашёл, какая у библиотеки лицензия. Вы не в курсе?..

                0
                вот здесь информация http://www.adaptagrams.org
                0
                Это ж то же самое, что трассировка проводников на печатных платах?
                  0
                  насколько я помню — достаточно близко (по крайней мере по используемым алгоритмам). к печатным платам ближе вот эта библиотека http://www.ogdf.net/ogdf.php
                    0

                    Конечно! С небольшой модификацией. Для вложенных слоев. Но они даже по-моему у автора не используются.

                    0

                    Программа интересная, хочется попробовать. Но где найти сборку под Ubuntu?

                      0
                      в этой версии пришлось пропустить линуху, т.к. сдался собрать под ней qt 5.7.1. В след. версии попробую разобраться с автоматизацией сборки под базовый набор линуховых веток, надеюсь за праздники разберусь.
                        0

                        Как можно будет узнать о выходе новой версии? Следить за блогом программы?

                          +1
                          Там на странице Скачать (http://ultraoutliner.com/download?locale=ru) есть на твиттер кнопка, или на почту можно подписаться. В блог редко и только что-то важное переношу, а на почту/твиттер робот автоматом уведомления рассылает, когда новые версии публикую.

                    Only users with full accounts can post comments. Log in, please.