問題タブ [boost-graph]

Boost Graph Libraryのアルゴリズムのドキュメントには、名前付きパラメーターとが引数として2進関数をとると記載されています。ただし、ソースによると、これらのパラメーターのデフォルト値は、単項関数オブジェクトであるです。isomorphismvertex_invariant1vertex_invariant2degree_vertex_invariant

何かが足りないのですか、それともドキュメントが間違っていますか？

だから私はこれによく似たいくつかの単純なジェネレータークラスを持っています. 生成されたデータをレンダラーに渡すのに役立つグラフを作成するにはどうすればよいですか?

現在、Char Ptr をデータ ジェネレーターに渡し、結果をレンダラーに渡すために、次のようなことを行います。

しかし、Boost Graph を使用して、データを表すクラスをいくつかの関数への入力としていくつかのクラスにマップし、その関数から他のクラスを返すことができるかどうかを知りたいです。Graph(MyInstanceOfMyDatatype)一般に、「グラフ」を呼び出して、あるグラフ要素から別のグラフ要素に（最小限の対処で）ブーストパスを渡すことができるようにしたいですか？

これは非常に単純なサンプルなので、グラフはやり過ぎのように見えるかもしれませんが、たとえば 1 つのジェネレーターと N 個のレンダラーがある場合に備えて、クラス間で自動値が渡されるようにグラフを作成したいと考えています。最初を除くすべてのレンダラーに私のクラスの -1 コピー。

Boostグラフライブラリに慣れていないので、例のどの部分が特定の例に関連付けられているか、どの部分が使用法に普遍的であるかを理解するのは難しいことがよくあります。

演習として、単純なグラフを作成し、頂点にcolorプロパティを割り当て、その結果をgraphvizに出力して、色がレンダリングされる色属性として表示されるようにします。どんな助けでもいただければ幸いです！これが私がこれまでに持っているものです（より具体的な使用法の質問はここのコメントにあります）：

次の簡単なアプリをコンパイルできないのはなぜですか。listSをvecSに変更すると、すべてが正常に機能します。（私はブースト1.46.1とgcc 4.4.5を使用しています）

BGLのサンプルコード：

とは何ですかcolor_map、どこで定義されていますか？そして、それはどこに文書化されていますか？

現在の状況: 画像からセグメントを抽出しようとしています。openCV のメソッドのおかげfindContours()で、すべての等高線の 8 連結点のリストができました。ただし、これらのリストには多くの重複が含まれているため、直接使用することはできません。

問題:重複を含む可能性のある 8 連結点のリストを指定して、そこからセグメントを抽出します。

可能な解決策：

• 最初はopenCVのapproxPolyDP()方法を使いました。ただし、結果はかなり悪いです...ズームされた等高線は次のとおりです。

の結果は次のとおりですapproxPolyDP(): (9 セグメント! 一部重複)

しかし、私が欲しいのはもっと似ています:

approxPolyDP()「いくつかのセグメントに見える」ものを「いくつかのセグメント」に変換できるので悪いです。ただし、私が持っているのは、それ自体を数回反復する傾向があるポイントのリストです。

たとえば、私のポイントが次の場合：

次に、ポイントのリストは次のようになります0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 9...そして、ポイントの数が大きくなった場合（> 100）、によって抽出されたセグメントapproxPolyDP()は残念ながら重複していません（つまり、互いに重なり合っていますが、厳密には等しくないので、できます'たとえば、ピクセルとは対照的に、「重複を削除する」と言うだけです）

• おそらく、私は解決策を持っていますが、それはかなり長いです (興味深いですが)。まず、すべての 8 連結リストに対して、疎行列を作成し(効率化のため)、ピクセルがリストに属している場合は行列の値を 1 に設定します。次に、ピクセルに対応するノードと隣接するピクセル間のエッジを持つグラフを作成します。これは、ピクセル間に欠けているすべてのエッジを追加することも意味します(複雑さが小さいため、スパース マトリックスが原因である可能性があります)。次に、可能なすべての「正方形」 (隣接する 4 つのノード) を削除します。これは、すでにかなり細い輪郭で作業しているため可能です。次に、最小スパニング ツリーアルゴリズムを起動します。そして最後に、ツリーのすべてのブランチを openCV で近似することができますapproxPolyDP()

要約すると、エラーが発生しやすいように思われるため、まだ実装していない面倒な方法があります。ただし、スタック オーバーフローの皆さんにお尋ねします。他に既存のメソッドがあり、適切に実装されている可能性がありますか?

編集：明確にするために、ツリーを作成したら、「ブランチ」を抽出できます（ブランチは、3つ以上の他のノードにリンクされた葉またはノードから始まります）次に、openCVのアルゴリズムapproxPolyDP()はRamer–Douglas–Peuckerアルゴリズムです。それが何をするかのウィキペディアの写真：

この図では、ポイントが互いに重複している可能性がある場合に失敗する理由を簡単に理解できます

別の編集: 私の方法では、注目すべき興味深いことがあります。グリッド内に配置されたポイント (ピクセルなど) を考慮する場合、一般に、最小スパニング ツリー アルゴリズムは有用ではありません。

とは根本的に大きく異なります。

しかし、どちらも最小全域木です

ただし、私の場合、ノードは輪郭であると想定されているため、ノードがクラスターを形成することはめったにありませんfindContours()。

トマラクのコメントへの回答：

DP アルゴリズムが 4 つのセグメントを返す場合 (点2から中心までのセグメントが 2 回ある)、私は満足です! もちろん、適切なパラメータを使用すると、「たまたま」同一のセグメントが存在する状態になり、重複を削除できます。ただし、明らかに、アルゴリズムはそのように設計されていません。

以下は、セグメントが多すぎる実際の例です。

こんにちは私は次のようなブーストグラフを持っています：

問題は、Edgeクラスの再帰テンプレートにあります。頂点のベクトルを保存する必要があります。

mygraph から頂点のベクトルがあり、頂点をトポロジカルに並べ替えます。

頂点を「順番に」位相的にソートします。v1 と v2 を比較して、元の頂点のベクトル (v1) が「順序どおり」または「順序どおり」であるかどうかをテストする最良の方法は何ですか。

編集: 例: ベクトル v1 に頂点 {A, B, C} があり、エッジ (A,B) (C,A) がある場合

したがって、トポロジカルソートの後、v2 になります

{タクシー}

一意のトポロジー順序が得られない場合があります。たとえば、(A,C) が唯一のエッジである場合、v2 は {A , B , C} または {B , A , C} になる可能性があります。

ここで、v1 と v2 を調べて、v1 と v2 の両方が同じ順序を表しているかどうかを確認する必要があります。

2番目の編集：私はアプローチを試みましたが、今のところうまくいきます。これが良いアプローチかどうか教えてください。

を生成しておりboost::graph、エッジ数は 300k です。エッジのセットをループで作成し、エッジのいくつかのプロパティも計算します。グラフを作成するにはすべてのエッジが必要なので、edge_descriptorまだ s にアクセスできません。セット全体をもう一度パスすることなくこれを行う方法はありますか? エッジを作成するときは を使用しますstd::pair<int, int>が、これは記述子と互換性がありますか?