1

タイトルに「グラフ理論の問題名」は使用できません。

データに含まれる構造に関する情報を抽出する必要があるデータを処理しようとしています。

  • 囲まれた空間の体積です
  • 前記密閉空間の容積

編集： 最初の「生」データは一連のバイトにあり、多次元配列と同様にアクセスできます。

//   X   Y   Z 
data(10, 10, 8);   // 0
data(10, 10, 9);   // 1
data(10, 10, 10);  // 1 
data(10, 10, 11);  // 1

このデータ構造の各近傍は、その位置のデータに 0 より大きい値がある場合、可能なエッジ ノード ペアになります。したがって、データ構造内の各要素/ノードには、6 つのエッジが存在する可能性があります。

開始位置 (シード) を知っているので、この生データをグラフのような構造に変換するのは簡単です。

node = dataToGraph(10,10,10); // seed position 
node->Edges[0]; // this would correspond to node represented by the value at 9,10,10
                // returns null if the value is less than zero. i.e. no edge/node.

データは 3D 空間の構造を表し、各構造には特定のシード (下の濃い灰色) があり、その位置がわかっています。この位置から、データ/構造をスキャンして、その完全な構造、つまりギャップがないことを確認し、そうである場合は、その内部ボリュームを計算する必要があります。

ある種の解決策を見つけることができると確信していますが、それは最適ではなく、データセットごとにスキャンするこれらの構造が何百万もあります。

私がハッキングするものよりも優れた、使用できる標準的なグラフ理論ソリューションがあると思います。残念ながら、私はこの種の数学にあまり詳しくないので、どこから調べればよいかさえわかりません。

以下は、有効なデータの 2D スライスの 3 つの例です。#3 の赤い線は、その例で私が興味を持っている剪定された構造を示しています。

有効な構造には常にシードがあり、構造は完全に閉じています。無効な構造とは、完全な 3D 構造のどこかにギャップがある構造、またはシードが存在するスライスに 2 つ以上の隣接/エッジがあるシードです。すなわち、外面または内面でブロックされてはなりません。

下の立方体の新しい写真は、これをある程度示しています。内部が空洞になっているとします。赤い球はシードで、青い線は 1 つのスライス (2D の例では #1) を表します。残念ながら、これほど規則的な構造にはならないため、グラフ アルゴリズムが必要になります。

誰かがこれをどこから始めるべきかについての指針を提供できれば幸いです。誰かが私にコードを教えてくれるとは思っていません。ただ私を教育するためです ;)

スライス 立方体

4

2 に答える 2

0

以下は、問題を解決する手順です: -

1.> データ ポイントから有向グラフを作成します (DFS を使用して、シードからソースとして有向グラフを作成します)。

2.> グラフの強連結成分を計算する

3.>シードが属するSCCを確認し、それが有効なギャップになります

時間計算量は、グラフのエッジの T(E) no になります。

上記のアルゴリズムの擬似コード: -

for(int i = 0;i<seeds.length;i++) {

DiGraph = []
DFS(seeds[i],Digraph);
comps = SCC(Digraph)
getVolume(comps[seeds[i]])

}

//DFS for above algorithm

DFS(Node i,Digraph) {

if(!visited(i)) {
   visited(i) = true 

  for every adjacent node v {

       Digraph.AddEdge((i,v))
       DFS(v,Digraph)

  }

}
}


getVolume(component k) {

   // get all 8 points bounding the gap
   Bounds = getBounds(k);
   Count = floodFill(Bounds);
   return(Count)
}
于 2013-11-13T04:42:54.927 に答える