1

对标题道歉，不能使用“图论问题名称”。

我正在尝试处理一些数据，我需要在其中提取有关数据中包含的结构的信息。

  • 是封闭的空间体积
  • 所述封闭空间的体积

编辑： 初始的“原始”数据是一系列字节，我可以访问类似于多维数组。

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

如果在该位置的数据中存在大于零的值，则此数据结构中的每个邻居都是可能的边缘节点对。所以数据结构中的每个元素/节点可能有六个可能的边。

因为我知道起始位置（种子），所以将这些原始数据转换为类似结构的图形对我来说是微不足道的。

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 空间中的结构，每个结构都有一个特定的种子（下方为深灰色），其位置是已知的。从这个位置我需要扫描数据/结构以验证它的完整结构，即没有间隙，如果是，计算它的内部体积。

虽然我确信我能够拼凑出某种解决方案，但它不会是最佳的，并且每个数据集都有数百万个这样的结构要扫描。

我猜我可以使用一个标准的图论解决方案，它比我破解的任何东西都要好。不幸的是，我对这种数学不太熟悉，所以我什至不知道从哪里开始寻找。

下面是三个有效的二维数据切片示例。#3 上的红线说明了我对该示例感兴趣的修剪结构。

一个有效的结构总是有种子，结构是完全封闭的。无效结构将是在完整 3D 结构中的任何位置具有间隙的任何结构，或者种子在其所在的切片上具有两个以上的邻居/边缘。即不得在外表面或内表面上阻塞。

下面立方体的新图片在一定程度上说明了这一点。假设它有一个中空的内部。红色球体是种子，蓝线表示单个切片，在 2D 示例中为 #1。不幸的是，它永远不会成为像这样规则的结构，因此需要 imo 图形算法。

如果有人能提供一些关于从哪里开始的指示，我将不胜感激。我不指望有人给我代码，只是为了教育我；）

片 立方体

4

2 回答 2

0

以下是可以解决您的问题的步骤：-

1.> 从数据点构造有向图（使用 DFS 构造有向图，以种子为源）。

2.> 计算图的强连通分量

3.> 检查种子属于哪个 SCC，这将是您的有效间隙

时间复杂度将是图中 T(E) 没有边。

上述算法的伪代码：-

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 回答
0

要查找连接到特定初始种子块的所有块，请使用深度优先搜索算法。

http://en.wikipedia.org/wiki/Depth-first_search

于 2013-11-13T03:20:32.703 回答