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

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

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


lead


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


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


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



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


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


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


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


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


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


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


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


#include

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


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 nodes;
    std::vector 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
class router_delegate
{
public:
    using edge_satelite = E;

    virtual void edge_updated(edge_satelite, const std::vector &) = 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, 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
static void libavoid_conn_callback(void *ptr)
{
    using edge_t = typename edge_router::edge_t;
    auto edge = static_cast(ptr);

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

    //И выполним небольшую постобработку
    std::vector 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
{
    Q_OBJECT

public:
    using router_t = edge_router;

    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 routableNodes;
    std::vector nodes;
    std::vector 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 & 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 почитать научные публикации по данной тематике.

Комментарии (5)

  • 29 декабря 2016 в 13:54

    –1

    ↑

    ↓

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

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

    • 29 декабря 2016 в 14:22

      0

      ↑

      ↓

      почитайте научные публикации автора по тематике, думаю станет понятней
      http://marvl.infotech.monash.edu/~mwybrow/#publications

  • 29 декабря 2016 в 14:11 (комментарий был изменён)

    0

    ↑

    ↓

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

    Иконка ужасна, английский хотелось бы по-умолчанию, а «кастомизацию» лучше всё-таки заменить на «настройку». С переводом на немецкий могу помочь (пока что он у вас очень… своеобразный ;).

  • 29 декабря 2016 в 14:46

    0

    ↑

    ↓

    Глупый вопрос. А вы помогли автору задокументировать то, что вам не хватало?

  • 29 декабря 2016 в 15:07 (комментарий был изменён)

    0

    ↑

    ↓

    У вас есть серьезные трудности с оптимальностью кода.

    1) Векторы и push_back, или «автор не знает о resize»

    std: vector 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 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 конец контейнера. И использовать константные декларации.

© Habrahabr.ru