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

В данной статье я покажу, как решить проблему маршрутизации соединений в редакторе диаграмм типа 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 почитать научные публикации по данной тематике.