Routing orthogonal connections in chart editors

In this article, I will show how to solve the problem of routing connections in an MS Visio type diagram editor. There will be a minimum of theory and a maximum of practice. If you need to quickly implement connection routing in a two-dimensional scene, and the first time you encounter a similar problem, then this article is for you.

Problematics

I came to this problem in the process of developing my ultra_outliner hobby project. Roughly speaking, it has a two-dimensional scene, in which there are many rectangular cards that can be linked. And there can be quite a few connections - which means they need to be routed so that the segments do not overlap, do not cross the cards, etc.

Many of you worked with Microsoft Visio, and of course appreciated how beautifully the arrows are routed automatically. Of course, Visio does not always cope, and for such cases there is the possibility of manual adjustment. But nevertheless, without considering extreme situations - I wanted to repeat this. Indeed, after all, there all these problems are solved quite well.

At first, I decided that this problem was solved long ago, and there are many libraries to choose from. Unfortunately, I was fundamentally wrong. There are libraries, but I liked less or less only one libavoid , despite the fact that half of the possibilities are in the experimental stage and are not very stable. Nevertheless, its author has several scientific publications on the subject of routing connections, and on the library website you can find links to scientific articles on which you can quite well master the issues.

Own implementation

Having learned enough theory, I could not deprive myself of pleasure and write the implementation myself. Both coordinate axes are divided into discrete segments. The points of division are determined by the orthogonal projections of the boundaries of the objects (cards), and with this, an additional partition is made with the selected step. Thus, we get an irregular grid, the nodes of which can be routed connections.

Further, in the simplest case, we iterate over the connections one by one, and using the Dijkstra algorithm , we construct connections one by one. From the cards we build an obstacle map, and in the heuristic function we add penalties for crossing the connections. Also prohibiting the two compounds to have common matching segments (overlapping along).

The implementation, of course, worked, but because of the uneven splitting of the axes in some places, ladders turned out. Moreover, in a couple of days I certainly cannot achieve the results that the author of libavoid has achieved over the years. Therefore, having played enough, I decided to use libavoid, having entered into contact with the author in order to configure it for stable work.

Software interface development

I didn’t like the prospect of working with libavoid in its pure form in its upper layer code, since The API is specific and you need to keep track of where and when to clear the memory. And besides callback'i go on the global function. Therefore, it was decided to make a wrapper that will follow all this.

Actually, let's start with the inclusion of the header file:

#include <libavoid/libavoid.h> 

The wrapper model is represented as a directed graph, where there are nodes and edges. The node is rectangular. Thus, the router class has the following interface:

 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; }; 

In the node description, apart from the helper methods, we will make a pointer to the libavoid-node:

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

And in the edge we will make a pointer to the libavoid-connection, and why edge_router is needed here, it will be clear later:

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

In edge_satelite, we will store information for a callback, which, as a rule, will be a pointer to a graphic edge (i.e., a connection object on the top layer of our implementation). Therefore, for universality, you can make it generally in the template (and accordingly make such an edit in the edge_router). Then, to handle edge geometry change events, we describe the delegate_t interface:

 template<typename E> class router_delegate { public: using edge_satelite = E; virtual void edge_updated(edge_satelite, const std::vector<pos_t> &) = 0; }; 

Now there is enough wrapper interface to cope with our initial task. All interaction with libavoid (or with its own implementation) will remain inside it. Next, consider the implementation of the described methods.

Routing layer implementation

We start with the libavoid configuration, which allows using only stable parts of it, and for which we had to write to the developer due to the lack of sufficient examples in the documentation. All configuration is done in the constructor:

 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); //   } 

Next, create / delete nodes:

 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); } 

Those. create a rectangular shape with an anchor point in the center. Immediately I warn you - if you make several anchor points - incomprehensible brakes begin, so it is better to do one point, and spread the boundary points of the connections to the border (due to nudge). A change in node geometry (including simple movement) that leads to rerouting is described by:

 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))); } 

With compounds approximately the same:

 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); } 

That's just with the exception that you need to give a link to the callback, which will be called after routing, in case the connection has changed the geometry. It's time to deal with him:

 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); } 

And finally, the routing call itself:

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

Now consider the implementation of the scene itself using this result.

Implement the top layer of the graphic scene

The described implementation was implemented using QT over the base class of a two-dimensional QGraphicsScene scene. At the scene we will create an interface for creating nodes, creating connections, moving and deleting them:

 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; }; 

Putting the scene in the constructor as a recipient of callbacks:

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

Adding the item to be connected to the scene (movable_image inherited from QGraphicsItem) must be followed by adding it to QGraphicsScene with the appropriate wrapper call:

 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())))); //   } 

Removal will be quite symmetrical:

 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); } 

A similar implementation for connections, where routable_link_image is a successor from QGraphicsPathItem, i.e. connection graphic object:

 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); } 

And finally, we will do the rebuilding of the connection when we call the callback.

 void diagram_scene::edge_updated(routable_link_image * img, const std::vector<pos_t> & path) { img->rebuild(path); //  ,   QGraphicsItem } 

Is done. Now we need to deal with the call routing.

Call routing

As a rule, wherever search algorithms on graphs are involved, calculations require quite a lot of resources, and here is no exception. Any rebuild routing in the Debug build will take a few seconds (although it flies in Release). Therefore, it is necessary to minimize the corresponding challenges.

Therefore, it makes sense to call routing:

• When adding new nodes
• When moving nodes
• When removing nodes

Moreover, sometimes it is necessary to do several actions within one logical transaction, and to perform routing only at the end. To do this, we implement some kind of recursive mutex. We enter in diagram_scene an attribute with the initial value true:

 bool enableRouting; 

The routing call will also be made from diagram_scene:

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

But to ensure the so-called transactions, we introduce, by analogy with std :: lock_guard, our structure:

 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; }; 

And you can use as follows:

 { routing_guard grd(pScene); //    ... } //    

You can create multiple routing_guard in a row, and routing will be called after the destruction of the latter.

Conclusion

See how it works in practice in the prototype ultra_outliner . To do this, you do not need to delve into the essence of the program itself, but you can simply open the sample file from the samples folder, open the "plots" or "characters" tab (from the project explorer on the left), and move the connected elements there. Any scene change will cause the routing to be rebuilt.

To make it look prettier, there are additional elements on the connections (arrows, joint-s), but these are all design elements.

And for those who want to understand the theory, I recommend reading the scientific publications on this topic on the libavoid website.