チャートエディターでの直交接続ルーティング

この記事では、MS Visioなどのダイアグラムエディターで接続ルーティングの問題を解決する方法を示します。 最小限の理論と最大限の実践があります。 2次元シーンで接続ルーティングをすばやく実装する必要があり、これが同様の問題に遭遇するのが初めての場合は、この記事が役立ちます。

発行

趣味のプロジェクトultra_outlinerの開発中にこの問題に遭遇しました 。 大まかに言えば、相互接続可能な長方形のカードが多数ある2次元のシーンがあります。 また、かなりの数の接続が存在する可能性があります。つまり、セグメントを重複させたり、カードを交差させたりしないようにルーティングする必要があります。

多くの方がMicrosoft Visioを使用してきましたが、もちろん、矢印がどれほど美しくルーティングされるかを高く評価しています。 もちろん、Visioは常に対応しているわけではなく、そのような場合は手動で調整する可能性があります。 それにもかかわらず、極端な状況を考慮せずに-私はこれを繰り返したかった。 実際、結局のところ、これらの問題はすべて非常によく解決されています。

最初、この問題はかなり前に解決されたと判断しました。多くのライブラリーがあります。 残念ながら、私は根本的に間違っていました。 ライブラリはありますが、可能性の半分は実験段階にあり、非常に安定して動作しないという事実にもかかわらず、多かれ少なかれ私はlibavoidが1つだけ好きでした。 それにもかかわらず、その著者は接続ルーティングのテーマに関するいくつかの科学出版物を持っています。図書館のウェブサイトでは、問題を非常によくマスターできる科学記事へのリンクを見つけることができます。

独自の実装

十分な理論を学んだので、私は喜びを奪い、実装を自分で書くことができませんでした。 両方の座標軸は個別のセグメントに分割されます。 分割点は、オブジェクト（カード）の境界の正射影によって決定され、同時に、選択されたステップで追加のパーティションが作成されます。 したがって、不均等なグリッドが得られ、そのノードは接続をルーティングできます。

さらに、最も単純なケースでは、接続を1つずつソートし、 ダイクストラアルゴリズムを使用して接続を順番に構築します。 カードから障害マップを構築し、ヒューリスティック関数への交差接続の罰金を追加します。 また、2つのジョイントが共通の一致するセグメントを持つことを禁止します（重複する）。

もちろん、実装は機能しましたが、いくつかの場所で軸の不均等な分割のために、はしごが得られました。 さらに、2、3日後には、もちろん、 libavoidの著者が長年達成してきた結果を達成することはできません。 したがって、十分にプレイしてから、私はlibavoidを使用し、作者と連絡を取り、安定して動作するように設定することにしました。

ソフトウェアインターフェース開発

トップレイヤーのコードでlibavoidを最も純粋な形で使用することを期待していませんでした。 APIは特定のものであり、メモリをクリアする場所とタイミングを追跡する必要があります。 また、コールバックはグローバル関数によって行われます。 したがって、このすべてに従うラッパーを作成することが決定されました。

実際には、ヘッダーファイルを含めることから始めましょう。

#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には、コールバックの情報を格納します。これは、原則として、グラフィックエッジ（つまり、実装の最上層の接続オブジェクト）へのポインターになります。 したがって、汎用性を高めるために、テンプレートに完全に入れることができます（したがって、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); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

つまり 中央にアンカーポイントを持つ長方形を作成します。 すぐに警告する必要があります-複数のアンカーポイントを作成する場合-理解できないブレーキが開始するため、1ポイントを作成し、境界への接続の境界点を広げる（ナッジのため）方が良いです。 再ルーティングにつながるノードのジオメトリの変更（単純な移動を含む）について説明します。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ただし、接続によってジオメトリが変更された場合、ルーティング後に呼び出されるコールバックへのリンクを与える必要があるという例外があります。 彼に対処する時が来ました：

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、この結果を使用してシーン自体の実装を検討します。

グラフィックシーンの最上層の実装

説明した実装は、2次元シーンQGraphicsSceneの基本クラスの上でQTを使用して実行されました。 ノードを作成し、接続を作成し、それらを移動および削除するためのシーンのインターフェイスを作成します。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コールバックの受信者としてシーン自体をコンストラクターに配置します。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして最後に、コールバックを呼び出すときに接続を再構築しましょう。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

できた 次に、ルーティングコールを処理する必要があります。

呼ルーティング

原則として、グラフ検索アルゴリズムが関係するすべての場所で、計算には多くのリソースが必要になりますが、ここも例外ではありません。 デバッグアセンブリでのルーティングの再構築には数秒かかります（リリースでは飛ぶことになりますが）。 したがって、関連する課題を最小限に抑える必要があります。

したがって、ルーティングを呼び出すことは理にかなっています。

• 新しいノードを追加するとき
• ノードを移動するとき
• ノードを削除する場合

さらに、同じ論理トランザクション内でいくつかのアクションを実行し、最後にのみルーティングを実行する必要がある場合があります。 これを行うために、何らかの再帰的ミューテックスを実装します。 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プロトタイプで確認できます。 これを行うには、プログラム自体の本質を詳しく調べる必要はありませんが、サンプルフォルダーからサンプルを使用してファイルを開き、「プロット」または「キャラクター」タブ（左側のプロジェクトエクスプローラーから）を開き、接続された要素をそこに移動できます。 シーンを変更すると、ルーティングが再構築されます。

すべてをきれいに見せるために、ジョイントに追加の要素（矢印、ジョイント）がありますが、これらはすべて設計要素です。

そして、理論を理解したい人には、 libavoidウェブサイトのこのトピックに関する科学出版物を読むことをお勧めします。