Маршрутизация ортогональных соединений в редакторах диаграмм
В данной статье я покажу, как решить проблему маршрутизации соединений в редакторе диаграмм типа 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 почитать научные публикации по данной тематике.
ссылка на оригинал статьи https://habrahabr.ru/post/318722/
Добавить комментарий