针对大数据的种子点生长—

本文主要是介绍针对大数据的种子点生长——分块生长的策略，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

　　在之前的种子点生长系列中，探讨了使用三种提取图像中内容部分种子点生长算法，分别是泛洪法、扫描线法和区段法。我们知道这三种算法在空间上都需要占用三维图像的空间以及相应的位图标记表的空间。有时，我们需要处理一些体积相当大的数据，这些数据都是内存中无法放下的，如数十数百GB的数据，想要获得其中图像内容信息，一般需要对图像进行分块生长。

　　本文使用一种比较直接的思路对数据进行分块，然后探讨分块生长时的算法逻辑以及相关的内存管理策略。

图像分块方式——Block

　　首先直观的分法是将三维图像分成若干等大小的长方体，比如长宽高分别为width、height、depth的大数据三维图像，可以人为指定一个小块的大小如subwidth、subheight、subdepth，就可以把大的三维图像切成这样相等的若干个小长方体。当然如果不是能被整除的边长最后在图像的边缘处会出现较小的长方体。这样的分块，需要保证每一块的大小是内存所能接受的，也就是说假如在内存限制的场合下只具有max的字节可供分配，那么subwidth、subheight、subdepth三者的乘积再乘以图像像素的size之后的大小一定要小于max。下图使用二维图像示意这种划分的方式：

　　在这种分块方式下，种子点生长的过程就是从块内生长到块间生长的反复的过程，下图展示了这样的一个过程：

　　大概的思路就是在块内采用种子点生长算法，在需要在相邻的块内继续寻找的时候就即时加载新的块数据，这些详细的逻辑会在下文探讨。

　　这种长方体的分块方式优点是直观，缺点是对加载新数据的方式没有进行更好的优化。在“图像数据的组织方式”这篇文章里谈到，由于三维图像都是使用一维数组来储存数据，所以在X方向的像素在数组中是相邻存储的，而Y方向连续的像素实际上在数组中相差width的距离，而Z方向连续的像素则相差width*height的距离。所以在一个尺寸为W*H*D的三维数据中，起点为(x,y, z)，尺寸为w*h*d的子长方体的数据其实并不是在原图像的一维数组中是连续的空间。而是只有如下的区段是连续的：

(x,y,z)~(x+w-1,y,z)

(x,y+1,z)~(x+w-1,y+1,z)

...

(x,y+h-1,z)~(x+w-1,y+h-1,z)

...

(x,y+h-1,z+d-1)~(x+w-1,y+h-1,z+d-1)

　　也就是说，假如一个从外部存储器提取文件内容的接口，要求传入需要段的起始偏移量和字节个数，那么为了填充一个子长方体，需要调用这样的接口w*d次。所以这样的分块方法其实对于加载数据的接口而言是很不友好的。所以为了照顾三维图像这种按一维数组存储的这种普遍的方式，引入了按层来分块的机制。

图像分块方式——layer

　　按层来分块其实是按Block来分块的一种特殊的方式，一个层就相当于一个长宽等于原图像长宽，但高度只是原图像高度一段的Block。当然，这样的层也要满足长宽高的乘积小于一定的值才能在内存中能够放下。所以在相同的条件下，使用Block的话小长方体的高度选择会比Layer要灵活一些。下图就是按层来对图像分块的示意图。

　　那么分层之后的种子生长过程就大概如下图的GIF所述的那样，就是一层一层的扩散了。

　　用层来代替块虽然少了灵活性，但是对于加载新块的接口来说就方便了很多，比如在一个W*H*D的三维图像中起始偏移为z，厚度为d的层，他的数据就是从（0，0，z）到（w-1，h-1，z+d-1）这个空间映射到一维数组上是一个连续的，索引从z*W*D到(z+d-1)*W*D。这样每次加载新块都只需要调用一次读取的接口就行了。无形中减少了IO增加了效率。本文主要就针对这种分层生长的方式来探讨如何进行大数据的种子点生长。

LargeImage与Layer的抽象

　　那么现在就把三维图像W*H*D数据分成若干W*H*d的层，这个d就是层的高度，当然允许最后一层厚度不足d，针对这样的层再特殊对待就是。所以先介绍使用c#实现的Layer类和LargeImage类。

　　首先是Layer类，这个类需要保存所有和一个层有关的信息，比如这个层的尺寸和偏移，当然为了方便，还可以记下这个层在所有层中的索引，层的总数。当然由于每个层在进行层内生长时需要访问位图标记表，所以在这个层里保留位图标记表的引用，当然不要初始化这个表，而是应该在首次用到这个表的时候再初始化。

public class Layer
{public int AllWidth;public int AllHeight;public int AllDepth;public int stz;//z起始偏移public int edz;//z结束偏移public int subDepth;public FlagMap3d Flag;//相应位图标记public int indexZ;//自己是第多少个public int AllLayerCount;public int actualDepth { get { return edz - stz + 1; } }//实际高度，考虑到最后一个层高度可能不够public int visitcount;public Layer(int allwidth, int allheight, int alldepth,int subDepth,int stz, int edz){this.AllWidth = allwidth;this.AllHeight = allheight;this.AllDepth = alldepth;this.stz = stz;this.subDepth = subDepth;this.edz = edz;Flag = null;indexZ = -1;visitcount = 0;}public FlagMap3d GetAndInitFlag(){if (Flag != null)return Flag;else{Flag = new FlagMap3d(AllWidth,AllHeight,actualDepth);return Flag;}}//第一次访问时初始化public override string ToString(){return string.Format("[{0}*{1},{2}~{3}]", AllWidth, AllHeight, stz, edz);}public bool HasPoint(Int16Triple seed){return seed.X >= 0 && seed.X <= AllWidth-1 && seed.Y >= 0 && seed.Y <= AllHeight-1 && seed.Z >= stz && seed.Z <= edz;}//检测一个点是否在该层public bool HasLowerLayer(){return this.indexZ > 0;}//检测自己上面是不是还有一层public bool HasUpperLayer(){return this.indexZ < AllLayerCount - 1;}//检测自己下面是不是还有一层
}

　　之后是包含这些层的LargeImage类，这个类存储了层的列表，以及三维图像的描述信息，当然不会包括三维图像的具体数据，因为这个类所表示的图像应该是足够大以至于内存放不下的。这个类同时提供了方法用于创建层。

public class LargeImage
{int width;int height;int depth;int subDepth;Layer[] layers;int layerCount;public int GetLayerCount(){return layerCount;}public int GetLayerDepth(){return subDepth;}public int GetWidth(){return width;}public int GetHeight(){return height;}public int GetDepth(){return depth;}public LargeImage(int width, int height, int depth){this.width = width;this.height = height;this.depth = depth;}public void CreateLayers(int subDepth){if (!(subDepth <= depth))throw new Exception();this.subDepth = subDepth;layerCount = (depth % subDepth == 0) ? (depth / subDepth) : (depth / subDepth + 1);layers = new Layer[layerCount];for (int k = 0; k < layerCount; k++){Layer b = new Layer(width, height, depth, subDepth, k * subDepth,(k + 1) * subDepth - 1);layers[k] = b;layers[k].indexZ = k;layers[k].AllLayerCount = layerCount;if (layers[k].edz > depth - 1)layers[k].edz = depth - 1;}}public Layer GetLayer(int k){if (k < 0 || k >= GetLayerCount())return null;return layers[k];}public int GetLayerIndex(Int16Triple innerPoint){for (int k = 0; k < layerCount; k++){Layer b = this.GetLayer(k);if (b.HasPoint(innerPoint)){return k;}}throw new Exception();}
}

层内生长与边界记录

　　容易想到，整个体数据的生长结果是层内生长的结果的合集。对于用户来说，他们手上只能提供一个大的三维图像以及一个种子点Seed。假如图像不大，完全可以对三维图像采用三种种子点生长算法中的一种来获取生长后的区域。但是在图像大了之后，只有每一层的数据能依次加载入内存，而且内存里最多同时存有一层的数据，这样的话只能先对包含种子点的层进行生长，然后根据生长到的边界来判断下一步可能包含区域的层，再加载这个层的数据。这也是大数据种子点生长的主要逻辑。

　　那么下面就说明如何在层内生长中进行边界记录。层内生长可以采用泛洪法、扫描线法、区段法三种中的任何一种，但是采用任何一种，边界标记方式都是不一样的，这里笔者采用了泛洪法和区段法来实现层内生长和边界记录。

　　首先是泛洪法，为泛洪法的输入输出设置一个结构来传入其所需要的参数和存储其需要的结果，即FloodFillInput结构和FloodFillResult结构。

public struct FloodFillResult
{//public List<Int16Triple> resultPointSet;public int resultCount;public List<Int16Triple>[] boundaryRequestPoints;//存储越界点的列表 上越界点存在第0个，下越界点存第1个public bool GetNeedsSeekLower(){return boundaryRequestPoints[0].Count > 0;}//返回是否需要往上层找public bool GetNeedsSeekUpper(){return boundaryRequestPoints[1].Count > 0;}//返回是否需要往下层找public void Init(){boundaryRequestPoints = new List<Int16Triple>[2];for (int i = 0; i < 2; i++){boundaryRequestPoints[i] = new List<Int16Triple>();}//resultPointSet = new List<Int16Triple>();resultCount = 0;}public void Clear(){//r//esultPointSet = 0;boundaryRequestPoints[0] = null;boundaryRequestPoints[1] = null;}
}
public struct FloodFillInput
{public byte[] data;public int width;public int height;public int depth;public FlagMap3d flag;public List<Int16Triple> overstepList;public bool recordUpper;public bool recordLower;public bool IsFirst;public FloodFillInput(byte[] data, int width, int height, int depth, FlagMap3d flag, List<Int16Triple> overstepList, bool recordUpper, bool recordLower, bool isfirst){this.data = data;this.width = width;this.height = height;this.depth = depth;this.flag = flag;this.overstepList = overstepList;for (int i = 0; i < overstepList.Count; i++){if (!(overstepList[i].X >= 0 && overstepList[i].X < width && overstepList[i].Y >= 0 && overstepList[i].Y < height && overstepList[i].Z >= 0 && overstepList[i].Z < depth)){throw new Exception();}}//确保越界点都确实在这层里this.recordLower = recordLower;this.recordUpper = recordUpper;this.IsFirst = isfirst;}public void Clear(){data = null;flag = null;overstepList = null;}
}//存储输入参数

　　可以看出在FloodFillResult结构中存储了边界点，即在执行泛洪过程中，检查到的超出了本层但处在更上一层或者更下一层的点。

　　下面的示意图展示了泛洪法的超出边界的点，这些点用橙色标记，他们的坐标通过转换之后就会成为新的层中的点坐标，而其中可能存在符合要求的点，就会成为新层中进行泛洪法的种子点。

　　下面的代码是层内执行泛洪法的类FloodFillBase，可以看出在需到了边界的时候在else情况里有不同于原来针对小数据泛洪法的逻辑，即将越界点进行了存储：

public class FloodFillBase
{protected int width;protected int height;protected int depth;protected byte[] data;protected FlagMap3d flagsMap;protected Container_Queue<Int16Triple> queue;//protected List<Int16Triple> result = new List<Int16Triple>();protected int resultCount = 0;public FloodFillBase(){queue = new Container_Queue<Int16Triple>();}public FloodFillResult ExecuteSeededGrow(FloodFillInput input){queue.Clear();//result.Clear();resultCount = 0;this.width = input.width;this.height = input.height;this.depth = input.depth;this.flagsMap = input.flag;this.data = input.data;List<Int16Triple> oversteps = input.overstepList;FloodFillResult ret = new FloodFillResult();ret.Init();Int16Triple[] adjPoints6 = new Int16Triple[6];if (!input.IsFirst){for (int i = 0; i < oversteps.Count; i++){if (!flagsMap.GetFlagOn(oversteps[i].X, oversteps[i].Y, oversteps[i].Z) && IncludeConditionMeets(oversteps[i])){flagsMap.SetFlagOn(oversteps[i].X, oversteps[i].Y, oversteps[i].Z, true);Process(oversteps[i]);InitAdj6(adjPoints6, oversteps[i]);for (int adjIndex = 0; adjIndex < 6; adjIndex++){Int16Triple t = adjPoints6[adjIndex];if (t.X < width && t.X >= 0 && t.Y < height && t.Y >= 0 && t.Z < depth && t.Z >= 0){int indext = t.X + width * t.Y + width * height * t.Z;if (!flagsMap.GetFlagOn(t.X ,t.Y ,t.Z) && IncludeConditionMeets(t)){flagsMap.SetFlagOn(t.X, t.Y, t.Z, true);queue.Push(t);Process(t);}}}}//首次生长需要避免让越界种子点又重新回溯到原先的层
            }}else{//以下是第一次生长的时候种子点不需要担心回溯if (oversteps.Count != 1) { throw new Exception(); }for (int i = 0; i < oversteps.Count; i++){if (!flagsMap.GetFlagOn(oversteps[i].X,oversteps[i].Y,oversteps[i].Z) && IncludeConditionMeets(oversteps[i])){flagsMap.SetFlagOn(oversteps[i].X, oversteps[i].Y, oversteps[i].Z, true);queue.Push(oversteps[i]);Process(oversteps[i]);}}}while (!queue.Empty()){Int16Triple p = queue.Pop();InitAdj6(adjPoints6, p);for (int adjIndex = 0; adjIndex < 6; adjIndex++){Int16Triple t = adjPoints6[adjIndex];if (t.X < width && t.X >= 0 && t.Y < height && t.Y >= 0 && t.Z < depth && t.Z >= 0){int indext = t.X + width * t.Y + width * height * t.Z;if (!flagsMap.GetFlagOn(t.X, t.Y, t.Z) && IncludeConditionMeets(t)){flagsMap.SetFlagOn(t.X, t.Y, t.Z, true);queue.Push(t);Process(t);}}else{if (input.recordLower && t.Z < 0){if (t.Z != -1) { throw new Exception(); }ret.boundaryRequestPoints[0].Add(t);continue;}if (input.recordUpper && t.Z >= depth){if (t.Z > depth) { throw new Exception(); }ret.boundaryRequestPoints[1].Add(t);continue;}}}}//ret.resultPointSet = this.result;ret.resultCount = this.resultCount;return ret;}protected virtual void Process(Int16Triple t){//result.Add(t);resultCount++;}protected virtual bool IncludeConditionMeets(Int16Triple t){throw new Exception();}protected void InitAdj6(Int16Triple[] adjPoints6, Int16Triple p){adjPoints6[0].X = p.X - 1;adjPoints6[0].Y = p.Y;adjPoints6[0].Z = p.Z;adjPoints6[1].X = p.X + 1;adjPoints6[1].Y = p.Y;adjPoints6[1].Z = p.Z;adjPoints6[2].X = p.X;adjPoints6[2].Y = p.Y - 1;adjPoints6[2].Z = p.Z;adjPoints6[3].X = p.X;adjPoints6[3].Y = p.Y + 1;adjPoints6[3].Z = p.Z;adjPoints6[4].X = p.X;adjPoints6[4].Y = p.Y;adjPoints6[4].Z = p.Z - 1;adjPoints6[5].X = p.X;adjPoints6[5].Y = p.Y;adjPoints6[5].Z = p.Z + 1;}
}

　　存储越界点之后，层间生长的逻辑会根据当前层生长情况来决定是否提请相邻层的数据进行生长。这里需要注意一个问题，在检测出越界点中符合纳入条件的种子点后，我们会发现这些种子点的邻域中也会含有在原来层中存在的越界点，而这些“原越界点”是在原层中已经被考察过的点，所以有必要避免重新回溯这些点，所以在第一次入队时有额外的逻辑确保这一点。下图指示这一现象：

　　其中绿色框住的点是由黑色层产生的越界点，将这些越界点在浅蓝色层进行生长，会再次访问到红色框原层的点，而这其实是不必要的，需要避免他。避免的方法就是在越界点中找到种子点后先不入队而是使用其在层内的邻域入队，这样就避免了这种回溯。

　　下面介绍层间生长的逻辑。

层间生长

　　层间生长的逻辑也十分类似与一个小的泛洪法。首先建一个用来存储参数的结构，之后就是层间生长的主逻辑。

public class LargeSeededGrowManager_FloodFill
{#region Staticstruct LayerDataAndInput{public Layer layer;public FloodFillInput input;public LayerDataAndInput(Layer layer,FloodFillInput input){this.layer = layer;this.input = input;}}#endregionLargeImage image;Container_Stack<LayerDataAndInput> queue;byte[] buffer;FloodFillBase seedGrowExecutor;DataFiller dataProvider;public List<Int16Triple> resultSet=new List<Int16Triple>();public int resultCount = 0;public LargeSeededGrowManager_FloodFill(){}public void SetScale(int width, int height, int depth,int subDepth){this.image = new LargeImage(width, height, depth);SetLayerSize(subDepth);}private void SetLayerSize(int subdepth){image.CreateLayers(subdepth);buffer = new byte[image.GetWidth() * image.GetHeight() * subdepth];}public void SetExecutor(FloodFillBase grower){this.seedGrowExecutor = grower;}public void SetDataProvider(DataFiller df){dataProvider = df;}public void ExecuteSeededGrow(Int16Triple firstseed){if (buffer == null||seedGrowExecutor==null||dataProvider==null)throw new Exception();queue = new Container_Stack<LayerDataAndInput>();Layer firstLayer = GetFirstLayer(firstseed);FloodFillInput firstInput = new FloodFillInput(buffer, firstLayer.AllWidth, firstLayer.AllHeight, firstLayer.actualDepth, firstLayer.GetAndInitFlag(), new List<Int16Triple>() {ConvertGlobalCoodToLayerCoold(firstLayer,firstseed)},firstLayer.HasUpperLayer(),firstLayer.HasLowerLayer(),true);queue.Push(new LayerDataAndInput(firstLayer,firstInput));while (!queue.Empty()){LayerDataAndInput sgi = queue.Pop();Layer layer = sgi.layer;layer.visitcount++;FloodFillInput input = sgi.input;FillLayerData(layer);FloodFillResult ret1 = seedGrowExecutor.ExecuteSeededGrow(input);input.overstepList.Clear();//ConvertLayerCoordsToGlobalCoords(layer,ret1.resultPointSet);//resultSet.AddRange(ret1.resultPointSet);resultCount += ret1.resultCount;if (ret1.GetNeedsSeekLower()){Layer lowerlayer = image.GetLayer(layer.indexZ - 1);if (lowerlayer == null){ret1.boundaryRequestPoints[0].Clear();continue;}ConvertOtherLayerCoordsToThisLayerCoords(layer,lowerlayer, ret1.boundaryRequestPoints[0]);FloodFillInput newinput = new FloodFillInput(buffer, lowerlayer.AllWidth, lowerlayer.AllHeight, lowerlayer.actualDepth, lowerlayer.GetAndInitFlag(),ret1.boundaryRequestPoints[0], lowerlayer.HasUpperLayer(), lowerlayer.HasLowerLayer(),false);queue.Push(new LayerDataAndInput(lowerlayer, newinput));}if (ret1.GetNeedsSeekUpper()){Layer upperlayer = image.GetLayer(layer.indexZ + 1);if (upperlayer == null){ret1.boundaryRequestPoints[1].Clear();continue;}ConvertOtherLayerCoordsToThisLayerCoords(layer,upperlayer, ret1.boundaryRequestPoints[1]);FloodFillInput newinput = new FloodFillInput(buffer, upperlayer.AllWidth, upperlayer.AllHeight, upperlayer.actualDepth, upperlayer.GetAndInitFlag(),ret1.boundaryRequestPoints[1], upperlayer.HasUpperLayer(), upperlayer.HasLowerLayer(),false);queue.Push(new LayerDataAndInput(upperlayer, newinput));}}}private Layer GetFirstLayer(Int16Triple seed){if(seed.X<0||seed.X>image.GetWidth()||seed.Y<0||seed.Y>image.GetHeight()||seed.Z<0||seed.Z>image.GetDepth())throw new Exception();int index=image.GetLayerIndex(seed);return image.GetLayer(index);}private void FillLayerData(Layer b){dataProvider.LoadLayerData(buffer, b.stz, b.edz);}private Int16Triple ConvertGlobalCoodToLayerCoold(Layer thislayer, Int16Triple globalCoord){return new Int16Triple(globalCoord.X, globalCoord.Y, globalCoord.Z - thislayer.stz);}private void ConvertLayerCoordsToGlobalCoords(Layer thislayer, List<Int16Triple> adjSeedList){for (int i = 0; i < adjSeedList.Count; i++){Int16Triple old = adjSeedList[i];old.Z += thislayer.stz;adjSeedList[i] = old;}}private void ConvertOtherLayerCoordsToThisLayerCoords(Layer thislayer, Layer other, List<Int16Triple> adjSeedList){for (int i = 0; i < adjSeedList.Count; i++){Int16Triple old = adjSeedList[i];old.Z += (thislayer.stz - other.stz);adjSeedList[i] = old;}}
}

　　简单的用文字来描述这样的逻辑：

首先针对已经分层完毕的图像，找到种子点所在的那一层，使用该种子点初始化泛洪法输入参数，将输入参数和相应的层放入队列
如果队列不空，进入循环
1. 取出输入参数和层
2. 根据层信息提请改层图像数据和标记表数据
3. 使用输入参数和数据执行层内生长，获得生长结果
4. 考察生长结果，若其中包含上一层越界点，则将这些越界点坐标进行转换后创建新输入参数，将其和相应层加入队列
5. 考察生长结果，若其中包含下一层越界点，则将这些越界点坐标进行转换后创建新输入参数，将其和相应层加入队列
结束循环

　　下图使用二维图像的例子来说明层间生长，其中红色的线是层间的分割线，每一层的实点用不同的蓝色标志，而越界点使用绿色框标注，咖啡色为最初的种子点：

　　对于层间生长需要注意问题如下：

一、不能将越界点直接当种子点在新层中生长，而应该从中筛选出符合纳入条件的点。
二、可能有层的数据会被不止一次加载。
三、每个层的位图标记表会在第一次访问该层时创建。所以没有扩散到的层永远不会有位图标记表被初始化。
四、如果认为层的位图标记表所在的空间也很可观，可以采取额外的措施将位图标记表也进行外部存储，相应的机制本文暂不讨论。
五、代码中提请数据的时机也可以进一步优化，本文中是在每个层被队列弹出后即加载其数据，实际上可以在验证其存在有效种子点后再加载。

相应的区段法的代码

　　基于区段法的大数据生长逻辑和基于泛洪法的是一致的，不同点就是由于区段法的单位是区段而不再是点，所以泛洪法使用的越界点的概念到了区段法中就成了越界区段。相应的代码如下：

enum ParentDirections
{Y0 = 1, Y2 = 2, Z0 = 3, Z2 = 4, Non = 5
}
enum ExtendTypes
{LeftRequired = 1, RightRequired = 2, AllRez = 3, UnRez = 4
}
struct Span
{public int XLeft;public int XRight;public int Y;public int Z;public ExtendTypes Extended;public ParentDirections ParentDirection;
}
struct Range
{public int XLeft;public int XRight;public int Y;public int Z;public Range(int xleft, int xright, int y, int z){this.XLeft = xleft;this.XRight = xright;this.Y = y;this.Z = z;}
}
struct SpanFillResult
{//public List<Int16Triple> resultPointSet;public int resultCount;public List<Range>[] boundaryRequestPoints;public bool GetNeedsSeekLower(){return boundaryRequestPoints[0].Count > 0;}public bool GetNeedsSeekUpper(){return boundaryRequestPoints[1].Count > 0;}public void Init(){boundaryRequestPoints = new List<Range>[2];for (int i = 0; i < 2; i++){boundaryRequestPoints[i] = new List<Range>();}//resultPointSet = new List<Int16Triple>();
    }public void Clear(){//resultPointSet = null;boundaryRequestPoints[0] = null;boundaryRequestPoints[1] = null;}
}
struct SpanFillInput
{public byte[] data;public int width;public int height;public int depth;public FlagMap3d flag;public List<Range> spanlist;public Int16Triple seed;public bool recordUpper;public bool recordLower;public bool IsFirst;public SpanFillInput(byte[] data, int width, int height, int depth, FlagMap3d flag, List<Range> spanList, Int16Triple seed, bool recordUpper, bool recordLower, bool isfirst){this.data = data;this.width = width;this.height = height;this.depth = depth;this.flag = flag;this.spanlist = spanList;this.seed = seed;if(spanlist!=null)for (int i = 0; i < spanlist.Count; i++){if (!(spanlist[i].Y >= 0 && spanlist[i].Y < height && spanlist[i].Z >= 0 && spanlist[i].Z < depth)){throw new Exception();}}this.recordLower = recordLower;this.recordUpper = recordUpper;this.IsFirst = isfirst;}public void Clear(){data = null;flag = null;spanlist = null;}
}
class SpanFillBase
{public SpanFillBase(){container = new Container_Stack<Span>();}protected BitMap3d data;protected FlagMap3d flagsMap;protected Container<Span> container;//以Span为单位的Queue或Stack容器//protected List<Int16Triple> result = new List<Int16Triple>();protected int resultCount = 0;public virtual SpanFillResult ExecuteSeededGrow(SpanFillInput input){this.data = new BitMap3d(input.data, input.width, input.height, input.depth);flagsMap = input.flag;//result.Clear()resultCount = 0;container.Clear();SpanFillResult ret = new SpanFillResult();ret.Init();if (input.IsFirst){Int16Triple seed = input.seed;Process(seed);flagsMap.SetFlagOn(seed.X, seed.Y, seed.Z, true);Span seedspan = new Span();seedspan.XLeft = seed.X;seedspan.XRight = seed.X;seedspan.Y = seed.Y;seedspan.Z = seed.Z;seedspan.ParentDirection = ParentDirections.Non;seedspan.Extended = ExtendTypes.UnRez;container.Push(seedspan);}else{ParentDirections p=(input.spanlist[0].Z==0)?ParentDirections.Z0:ParentDirections.Z2;for (int i = 0; i < input.spanlist.Count; i++){Range r = input.spanlist[i];CheckRange(r.XLeft, r.XRight, r.Y,r.Z,p);}}while (!container.Empty()){Span span = container.Pop();#region AllRezif (span.Extended == ExtendTypes.AllRez){if (span.ParentDirection == ParentDirections.Y2){if (span.Y - 1 >= 0)//[spx-spy,y-1,z]CheckRange(span.XLeft, span.XRight, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Z - 1 >= 0)//[spx-spy,y,z-1]CheckRange(span.XLeft, span.XRight, span.Y, span.Z - 1, ParentDirections.Z2);else OnOverstepSpanFound(span.XLeft, span.XRight, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth)//[spx-spy,y,z+1]CheckRange(span.XLeft, span.XRight, span.Y, span.Z + 1, ParentDirections.Z0);else OnOverstepSpanFound(span.XLeft, span.XRight, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);continue;}if (span.ParentDirection == ParentDirections.Y0){if (span.Y + 1 < data.height)//[spx-spy,y+1,z]CheckRange(span.XLeft, span.XRight, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Z - 1 >= 0)//[spx-spy,y,z-1]CheckRange(span.XLeft, span.XRight, span.Y, span.Z - 1, ParentDirections.Z2);else OnOverstepSpanFound(span.XLeft, span.XRight, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth)//[spx-spy,y,z+1]CheckRange(span.XLeft, span.XRight, span.Y, span.Z + 1, ParentDirections.Z0);else OnOverstepSpanFound(span.XLeft, span.XRight, span.Y, span.Z + 1, ParentDirections.Z0, ref ret);continue;}if (span.ParentDirection == ParentDirections.Z2){if (span.Y - 1 >= 0)//[spx-spy,y-1,z]CheckRange(span.XLeft, span.XRight, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Y + 1 < data.height)//[spx-spy,y+1,z]CheckRange(span.XLeft, span.XRight, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Z - 1 >= 0)//[spx-spy,y,z-1]CheckRange(span.XLeft, span.XRight, span.Y, span.Z - 1, ParentDirections.Z2);else OnOverstepSpanFound(span.XLeft, span.XRight, span.Y, span.Z - 1, ParentDirections.Z2 ,ref ret);continue;}if (span.ParentDirection == ParentDirections.Z0){if (span.Y - 1 >= 0)CheckRange(span.XLeft, span.XRight, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Y + 1 < data.height)CheckRange(span.XLeft, span.XRight, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Z + 1 < data.depth)CheckRange(span.XLeft, span.XRight, span.Y, span.Z + 1, ParentDirections.Z0);else OnOverstepSpanFound(span.XLeft, span.XRight, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);continue;}throw new Exception();}#endregion#region UnRezif (span.Extended == ExtendTypes.UnRez){int xl = FindXLeft(span.XLeft, span.Y, span.Z);int xr = FindXRight(span.XRight, span.Y, span.Z);if (span.ParentDirection == ParentDirections.Y2){if (span.Y - 1 >= 0)CheckRange(xl, xr, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Y + 1 < data.height){if (xl != span.XLeft)CheckRange(xl, span.XLeft, span.Y + 1, span.Z, ParentDirections.Y0);if (span.XRight != xr)CheckRange(span.XRight, xr, span.Y + 1, span.Z, ParentDirections.Y0);}if (span.Z - 1 >= 0)CheckRange(xl, xr, span.Y, span.Z - 1, ParentDirections.Z2);else OnOverstepSpanFound(xl, xr, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth)CheckRange(xl, xr, span.Y, span.Z + 1, ParentDirections.Z0);else OnOverstepSpanFound(xl, xr, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);continue;}if (span.ParentDirection == ParentDirections.Y0){if (span.Y + 1 < data.height)CheckRange(xl, xr, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Y - 1 >= 0){if (xl != span.XLeft)CheckRange(xl, span.XLeft, span.Y - 1, span.Z, ParentDirections.Y2);if (span.XRight != xr)CheckRange(span.XRight, xr, span.Y - 1, span.Z, ParentDirections.Y2);}if (span.Z - 1 >= 0)CheckRange(xl, xr, span.Y, span.Z - 1, ParentDirections.Z2);else OnOverstepSpanFound(xl, xr, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth)CheckRange(xl, xr, span.Y, span.Z + 1, ParentDirections.Z0);else OnOverstepSpanFound(xl, xr, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);continue;}if (span.ParentDirection == ParentDirections.Z2){if (span.Y - 1 >= 0)CheckRange(xl, xr, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Y + 1 < data.height)CheckRange(xl, xr, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Z - 1 >= 0)CheckRange(xl, xr, span.Y, span.Z - 1, ParentDirections.Z2);else OnOverstepSpanFound(xl, xr, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth){if (xl != span.XLeft)CheckRange(xl, span.XLeft, span.Y, span.Z + 1, ParentDirections.Z0);if (span.XRight != xr)CheckRange(span.XRight, xr, span.Y, span.Z + 1, ParentDirections.Z0);}else{if (xl != span.XLeft)OnOverstepSpanFound(xl, span.XLeft, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);if (span.XRight != xr)OnOverstepSpanFound(span.XRight, xr, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);}continue;}if (span.ParentDirection == ParentDirections.Z0){if (span.Y - 1 >= 0)CheckRange(xl, xr, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Y + 1 < data.height)CheckRange(xl, xr, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Z - 1 >= 0){if (xl != span.XLeft)CheckRange(xl, span.XLeft, span.Y, span.Z - 1, ParentDirections.Z2);if (span.XRight != xr)CheckRange(span.XRight, xr, span.Y, span.Z - 1, ParentDirections.Z2);}else{if (xl != span.XLeft)OnOverstepSpanFound(xl, span.XLeft, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.XRight != xr)OnOverstepSpanFound(span.XRight, xr, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);}if (span.Z + 1 < data.depth)CheckRange(xl, xr, span.Y, span.Z + 1, ParentDirections.Z0);else OnOverstepSpanFound(xl, xr, span.Y, span.Z + 1, ParentDirections.Z0, ref ret);continue;}if (span.ParentDirection == ParentDirections.Non){if (span.Y + 1 < data.height)CheckRange(xl, xr, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Y - 1 >= 0)CheckRange(xl, xr, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Z - 1 >= 0)CheckRange(xl, xr, span.Y, span.Z - 1, ParentDirections.Z2);else OnOverstepSpanFound(xl, xr, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth)CheckRange(xl, xr, span.Y, span.Z + 1, ParentDirections.Z0);else OnOverstepSpanFound(xl, xr, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);continue;}throw new Exception();}#endregion#region LeftRequiredif (span.Extended == ExtendTypes.LeftRequired){int xl = FindXLeft(span.XLeft, span.Y, span.Z);if (span.ParentDirection == ParentDirections.Y2){if (span.Y - 1 >= 0)CheckRange(xl, span.XRight, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Y + 1 < data.height && xl != span.XLeft)CheckRange(xl, span.XLeft, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Z - 1 >= 0)CheckRange(xl, span.XRight, span.Y, span.Z - 1, ParentDirections.Z2);else OnOverstepSpanFound(xl, span.XRight, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth)CheckRange(xl, span.XRight, span.Y, span.Z + 1, ParentDirections.Z0);else OnOverstepSpanFound(xl, span.XRight, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);continue;}if (span.ParentDirection == ParentDirections.Y0){if (span.Y - 1 >= 0 && xl != span.XLeft)CheckRange(xl, span.XLeft, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Y + 1 < data.height)CheckRange(xl, span.XRight, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Z - 1 >= 0)CheckRange(xl, span.XRight, span.Y, span.Z - 1, ParentDirections.Z2);else OnOverstepSpanFound(xl, span.XRight, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth)CheckRange(xl, span.XRight, span.Y, span.Z + 1, ParentDirections.Z0);else OnOverstepSpanFound(xl, span.XRight, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);continue;}if (span.ParentDirection == ParentDirections.Z2){if (span.Y - 1 >= 0)CheckRange(xl, span.XRight, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Y + 1 < data.height)CheckRange(xl, span.XRight, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Z - 1 >= 0)CheckRange(xl, span.XRight, span.Y, span.Z - 1, ParentDirections.Z2);else OnOverstepSpanFound(xl, span.XRight, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth && xl != span.XLeft)CheckRange(xl, span.XLeft, span.Y, span.Z + 1, ParentDirections.Z0);else if(xl != span.XLeft) OnOverstepSpanFound(xl, span.XLeft, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);continue;}if (span.ParentDirection == ParentDirections.Z0){if (span.Y - 1 >= 0)CheckRange(xl, span.XRight, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Y + 1 < data.height)CheckRange(xl, span.XRight, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Z - 1 >= 0 && xl != span.XLeft)CheckRange(xl, span.XLeft, span.Y, span.Z - 1, ParentDirections.Z2);else if( xl != span.XLeft) OnOverstepSpanFound(xl, span.XLeft, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth)CheckRange(xl, span.XRight, span.Y, span.Z + 1, ParentDirections.Z0);else OnOverstepSpanFound(xl, span.XRight, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);continue;}throw new Exception();}#endregion#region RightRequiredif (span.Extended == ExtendTypes.RightRequired){int xr = FindXRight(span.XRight, span.Y, span.Z);if (span.ParentDirection == ParentDirections.Y2){if (span.Y - 1 >= 0)CheckRange(span.XLeft, xr, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Y + 1 < data.height && span.XRight != xr)CheckRange(span.XRight, xr, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Z - 1 >= 0)CheckRange(span.XLeft, xr, span.Y, span.Z - 1, ParentDirections.Z2);else OnOverstepSpanFound(span.XLeft, xr, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth)CheckRange(span.XLeft, xr, span.Y, span.Z + 1, ParentDirections.Z0);else OnOverstepSpanFound(span.XLeft, xr, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);continue;}if (span.ParentDirection == ParentDirections.Y0){if (span.Y + 1 < data.height)CheckRange(span.XLeft, xr, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Y - 1 >= 0 && span.XRight != xr)CheckRange(span.XRight, xr, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Z - 1 >= 0)CheckRange(span.XLeft, xr, span.Y, span.Z - 1, ParentDirections.Z2);else OnOverstepSpanFound(span.XLeft, xr, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth)CheckRange(span.XLeft, xr, span.Y, span.Z + 1, ParentDirections.Z0);else OnOverstepSpanFound(span.XLeft, xr, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);continue;}if (span.ParentDirection == ParentDirections.Z2){if (span.Y - 1 >= 0)CheckRange(span.XLeft, xr, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Y + 1 < data.height)CheckRange(span.XLeft, xr, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Z - 1 >= 0)CheckRange(span.XLeft, xr, span.Y, span.Z - 1, ParentDirections.Z2);else OnOverstepSpanFound(span.XLeft, xr, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth && span.XRight != xr)CheckRange(span.XRight, xr, span.Y, span.Z + 1, ParentDirections.Z0);else if(span.XRight != xr) OnOverstepSpanFound(span.XRight, xr, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);continue;}if (span.ParentDirection == ParentDirections.Z0){if (span.Y - 1 >= 0)CheckRange(span.XLeft, xr, span.Y - 1, span.Z, ParentDirections.Y2);if (span.Y + 1 < data.height)CheckRange(span.XLeft, xr, span.Y + 1, span.Z, ParentDirections.Y0);if (span.Z - 1 >= 0 && span.XRight != xr)CheckRange(span.XRight, xr, span.Y, span.Z - 1, ParentDirections.Z2);else if( span.XRight != xr) OnOverstepSpanFound(span.XRight, xr, span.Y, span.Z - 1, ParentDirections.Z2,ref ret);if (span.Z + 1 < data.depth)CheckRange(span.XLeft, xr, span.Y, span.Z + 1, ParentDirections.Z0);else OnOverstepSpanFound(span.XLeft, xr, span.Y, span.Z + 1, ParentDirections.Z0,ref ret);continue;}throw new Exception();}#endregion}//ret.resultPointSet = this.result;ret.resultCount = this.resultCount;return ret;}protected void CheckRange(int xleft, int xright, int y, int z, ParentDirections ptype){for (int i = xleft; i <= xright; ){if ((!flagsMap.GetFlagOn(i, y, z)) && IncludeConditionMeets(i, y, z)){int lb = i;int rb = i + 1;while (rb <= xright && (!flagsMap.GetFlagOn(rb, y, z)) && IncludeConditionMeets(rb, y, z)){rb++;}rb--;Span span = new Span();span.XLeft = lb;span.XRight = rb;span.Y = y;span.Z = z;if (lb == xleft && rb == xright){span.Extended = ExtendTypes.UnRez;}else if (rb == xright){span.Extended = ExtendTypes.RightRequired;}else if (lb == xleft){span.Extended = ExtendTypes.LeftRequired;}else{span.Extended = ExtendTypes.AllRez;}span.ParentDirection = ptype;for (int j = lb; j <= rb; j++){flagsMap.SetFlagOn(j, y, z, true);Process(new Int16Triple(j, y, z));}container.Push(span);i = rb + 1;}else{i++;}}}//区段法的CheckRange 注意与扫描线的CheckRange的不同protected int FindXRight(int x, int y, int z){int xright = x + 1;while (true){if (xright == data.width || flagsMap.GetFlagOn(xright, y, z)){break;}else{if (IncludeConditionMeets(xright, y, z)){Int16Triple t = new Int16Triple(xright, y, z);flagsMap.SetFlagOn(xright, y, z, true);Process(t);xright++;}else{break;}}}return xright - 1;}protected int FindXLeft(int x, int y, int z){int xleft = x - 1;while (true){if (xleft == -1 || flagsMap.GetFlagOn(xleft, y, z)){break;}else{if (IncludeConditionMeets(xleft, y, z)){Int16Triple t = new Int16Triple(xleft, y, z);flagsMap.SetFlagOn(xleft, y, z, true);Process(t);xleft--;}else{break;}}}return xleft + 1;}protected virtual bool IncludeConditionMeets(int x, int y, int z){throw new Exception();//byte v = bmp.GetPixel(x, y, z);//return v > min && v < max;
    }protected virtual void Process(Int16Triple p){resultCount++;// result.Add(p);
    }protected void OnOverstepSpanFound(int xleft, int xright, int y, int z, ParentDirections ptype,ref SpanFillResult ret){if (z == -1){Range r = new Range(xleft, xright, y, z);ret.boundaryRequestPoints[0].Add(r);}else if (z == data.depth){Range r = new Range(xleft, xright, y, z);ret.boundaryRequestPoints[1].Add(r);}elsethrow new Exception();}
}

class LargeSeededGrowManager_SpanFill
{#region Staticstruct LayerDataAndInput{public Layer layer;public SpanFillInput input;public LayerDataAndInput(Layer layer, SpanFillInput input){this.layer = layer;this.input = input;}}#endregionLargeImage image;Container_Stack<LayerDataAndInput> queue;byte[] buffer;SpanFillBase seedGrowExecutor;DataFiller dataProvider;//public List<Int16Triple> resultSet=new List<Int16Triple>();public int resultCount = 0;public LargeSeededGrowManager_SpanFill(){}public void SetScale(int width, int height, int depth,int subDepth){this.image = new LargeImage(width, height, depth);SetLayerSize(subDepth);}private void SetLayerSize(int subdepth){image.CreateLayers(subdepth);buffer = new byte[image.GetWidth() * image.GetHeight() * subdepth];}public void SetExecutor(SpanFillBase grower){this.seedGrowExecutor = grower;}public void SetDataProvider(DataFiller df){dataProvider = df;}public void ExecuteSeededGrow(Int16Triple firstseed){if (buffer == null||seedGrowExecutor==null||dataProvider==null)throw new Exception();queue = new Container_Stack<LayerDataAndInput>();Layer firstLayer = GetFirstLayer(firstseed);SpanFillInput firstInput = new SpanFillInput(buffer, firstLayer.AllWidth, firstLayer.AllHeight, firstLayer.actualDepth, firstLayer.GetAndInitFlag(),new List<Range>(), ConvertGlobalCoodToLayerCoold(firstLayer,firstseed), firstLayer.HasUpperLayer(), firstLayer.HasLowerLayer(), true);queue.Push(new LayerDataAndInput(firstLayer,firstInput));while (!queue.Empty()){LayerDataAndInput sgi = queue.Pop();Layer layer = sgi.layer;layer.visitcount++;SpanFillInput input = sgi.input;FillLayerData(layer);SpanFillResult ret1 = seedGrowExecutor.ExecuteSeededGrow(input);input.spanlist.Clear();//ConvertLayerCoordsToGlobalCoords(layer,ret1.resultPointSet);// resultSet.AddRange(ret1.resultPointSet);resultCount += ret1.resultCount;if (ret1.GetNeedsSeekLower()){Layer lowerlayer = image.GetLayer(layer.indexZ - 1);if (lowerlayer == null){ret1.boundaryRequestPoints[0].Clear();continue;}ConvertOtherLayerCoordsToThisLayerCoords(layer,lowerlayer, ret1.boundaryRequestPoints[0]);SpanFillInput newinput = new SpanFillInput(buffer, lowerlayer.AllWidth, lowerlayer.AllHeight, lowerlayer.actualDepth, lowerlayer.GetAndInitFlag(),ret1.boundaryRequestPoints[0],input.seed,lowerlayer.HasUpperLayer(), lowerlayer.HasLowerLayer(),false);queue.Push(new LayerDataAndInput(lowerlayer, newinput));}if (ret1.GetNeedsSeekUpper()){Layer upperlayer = image.GetLayer(layer.indexZ + 1);if (upperlayer == null){ret1.boundaryRequestPoints[1].Clear();continue;}ConvertOtherLayerCoordsToThisLayerCoords(layer, upperlayer, ret1.boundaryRequestPoints[1]);SpanFillInput newinput = new SpanFillInput(buffer, upperlayer.AllWidth, upperlayer.AllHeight, upperlayer.actualDepth, upperlayer.GetAndInitFlag(),ret1.boundaryRequestPoints[1],input.seed, upperlayer.HasUpperLayer(), upperlayer.HasLowerLayer(),false);queue.Push(new LayerDataAndInput(upperlayer, newinput));}}}private Layer GetFirstLayer(Int16Triple seed){if(seed.X<0||seed.X>image.GetWidth()||seed.Y<0||seed.Y>image.GetHeight()||seed.Z<0||seed.Z>image.GetDepth())throw new Exception();int index=image.GetLayerIndex(seed);return image.GetLayer(index);}private void FillLayerData(Layer b){dataProvider.LoadLayerData(buffer, b.stz, b.edz);}private Int16Triple ConvertGlobalCoodToLayerCoold(Layer thislayer, Int16Triple globalCoord){return new Int16Triple(globalCoord.X, globalCoord.Y, globalCoord.Z - thislayer.stz);}private void ConvertLayerCoordsToGlobalCoords(Layer thislayer, List<Int16Triple> adjSeedList){for (int i = 0; i < adjSeedList.Count; i++){Int16Triple old = adjSeedList[i];old.Z += thislayer.stz;adjSeedList[i] = old;}}private void ConvertOtherLayerCoordsToThisLayerCoords(Layer thislayer, Layer other, List<Range> adjSeedList){for (int i = 0; i < adjSeedList.Count; i++){Range old = adjSeedList[i];old.Z += (thislayer.stz - other.stz);adjSeedList[i] = old;}}}