1地形瓦片间遍历
有源洪水淹没分析的过程实际上是从淹没种子点开始搜索全部淹没点的过程，因此找出分析区域内的淹没种子点是分析的关键。在有源洪水淹没中，造成淹没的主要原因是大坝决口或者漫堤导致下游区域被淹没，因此可以选择区域内溃坝或漫堤发生处的地形高程点作为初始淹没种子点。现假定分析区域内存在溃坝点ｏ，通过ｏ点经纬度计算得知ｏ点位于地形瓦片Ａ内，以ｏ点作为初始淹没种子点，根据式（１）式（２），由ｏ点的经纬度坐标可以计算出瓦片Ａ的行列号（ｉＡ，ｊＡ），也可以确定Ａ的邻接关系和邻接瓦片的行列号。同时每个瓦片都定义８个布尔型的邻域标记符，分别对应８个相邻方向，开始分析前将邻域标记符初始化为假（ＦＡＬＳＥ）。算法过程如下：１）由初始种子点ｏ的经纬度坐标（Ｂｏ，Ｌｏ）计算出ｏ点所在地形瓦片Ａ的行列号（ｉＡ，ｊＡ）；２）建立用于存储地形瓦片Ａ的淹没点的临时数据集，由ｏ点沿８个相邻方向进行邻域高程点的搜索，对搜索过程中某个高程点ｄ，若其高程值ｈｄ小于当前水位ｈ水，则将点ｄ加入该临时记录集，并对点ｄ进行邻域高程点搜索，否则直接返回。３）在Ａ中沿一个方向ｄｉｒ（ｄｉｒ表示８个相邻方向中的一个，其反方向为ｏｐ＿ｄｉｒ）进行搜索，当搜索到Ａ中ｄｉｒ方向边界上的淹没点ｐ时，找到Ａ的ｄｉｒ方向上的邻接瓦片Ｂ，判断Ｂ中ｏｐ＿ｄｉｒ方向的邻域标记，如果为真，则返回；否则在该邻接瓦片Ｂ中找到点ｐ的ｄｉｒ方向的邻域高程点ｑ，判断点ｑ是否符合淹没条件，若是，则将点ｑ加入Ｂ的淹没种子点集合，否则返回。４）对Ａ中ｄｉｒ方向边界上的所有淹没点都进行过邻域搜索之后，将Ｂ中ｏｐ＿ｄｉｒ方向的邻域标记为真。同时以Ｂ的淹没种子点为起点向Ａ沿ｏｐ＿ｄｉｒ方向搜索，找出Ａ在ｄｉｒ方向边界上的淹没种子点，并加入Ａ的淹没种子点集合，搜索完后将Ａ中表示ｄｉｒ方向的邻域标记置为真。５）沿顺时针方向改变ｄｉｒ所示方向，重复步骤３），４），当Ａ中８个相邻方向邻域标记全部为真时清空临时记录集，此时即得到Ａ的全部淹没种子点。６）以瓦片Ａ的邻接瓦片Ｂ为待搜索瓦片，淹没种子点为初始种子点，执行步骤２）～５）。７）遍历完区域内所有瓦片之后，结束搜索。瓦片Ａ的淹没种子点集合的搜索过程如图２所示：由初始种子点ｏ开始在Ａ内沿８个方向搜索淹没点，假定Ａ的东边邻接瓦片为Ｂ，当搜索到Ａ、Ｂ边界时，找到瓦片Ａ内的边界淹没点ｐ，判断Ｂ的西边邻域标记Ｗ以确定ｐ点是否可以继续向东进入瓦片Ｂ进行搜索。若为真，则表示之前已经从Ｂ的西边邻接瓦片Ａ进入Ｂ中搜索过，不需要再进入Ｂ中搜索；否则由点ｐ继续向Ｂ内搜索，找到Ｂ内与点ｐ直接相邻的边界点ｑ，若ｑ符合淹没条件，将点ｑ加入到瓦片Ｂ的淹没种子点集合中，否则返回，搜索完所有种子点后将Ｗ标记设置为真。同时由Ｂ向Ａ反向搜索。需要注意的是，在搜索过程中，只需要记录找到的淹没种子点，而除此之外的蔓延淹没点并不需要额外记录，这是因为在之后进行单个瓦片的淹没分析的时候，可以通过淹没种子点进行搜索，找出Ａ的完整淹没区域。在瓦片间的搜索过程中，可以通过设置递归步长以达到控制搜索深度的目的。当从某个瓦片Ａ开始搜索时，设置搜索深度变量ｎＤｅｐｔｈ为１，进入瓦片Ａ的相邻瓦片Ｂ时ｎＤｅｐｔｈ变为２，由瓦片Ｂ进入Ｂ的非Ａ邻接瓦片时，ｎＤｅｐｔｈ变为３，而由瓦片Ｂ返回瓦片Ａ时ｎＤｅｐｔｈ恢复为１。由于搜索瓦片Ａ时，只需搜索到与它直接相邻的８个瓦片即可通过邻接瓦片的反向搜索计算出瓦片Ａ的所有淹没种子点，所以可以将搜索步长控制为１，控制搜索深度ｎＤｅｐｔｈ的最大值为２，将对瓦片的递归遍历转换为迭代遍历，避免搜索扩散到瓦片Ｂ的非Ａ邻接瓦片进而造成内存的大量消耗。
2地形瓦片内遍历
地形瓦片内遍历主要是在获得地形瓦片的淹没种子点基础上，搜索瓦片内蔓延淹没点的过程。算法步骤如下：（１）取待搜索瓦片Ａ中的一个淹没种子点，沿８个方向进行邻域高程点的搜索，当搜索到某个高程点ｄ时，判断ｄ点是否被搜索过，若是则返回；否则判断ｄ是否满足淹没条件，若满足则将ｄ标记为可淹没，同时标记为已搜索，若不满足则返回；（２）继续搜索下一个淹没种子点，执行步骤（１），直到搜索完成，并获取瓦片内的所有蔓延淹没点。如图３所示，得到每个瓦片的淹没种子点集合后，即可独立地在瓦片内部以淹没种子点为起点对格网ＤＥＭ高程点进行递归遍历，找出瓦片内所有连通的淹没点。图３（ａ）显示了瓦片Ａ的淹没种子点集合，经过搜索，Ａ的８个邻域标记全部为真，表示Ａ的淹没种子点集合搜索完成。然后对Ａ进行独立的淹没分析，分别从每个种子点开始，沿８个方向搜索邻域内的高程点，当搜索到某个邻接点ｄ时，先判断ｄ是否被搜索过，若已搜索过，则直接返回，再搜索下一个高程点；否则判断ｄ的高程ｈｄ是否低于水位高度ｈ水，若是则将ｄ标记为可淹没已搜索，继续搜索ｄ的８个邻域内的高程点，否则将ｄ标记为已搜索后返回并搜索下一个高程点。对Ａ中的所有淹没种子点完成搜索之后，可以得到由种子点蔓延产生的一系列蔓延淹没点，在图３（ｂ）中以斜线单元格表示，这些蔓延淹没点和淹没种子点一起构成了Ａ的完整淹没区域。
3实验
为了对上述方法进行验证，基于开放式三维虚拟地球集成共享平台软件ＧｅｏＧｌｏｂｅ进行了实验，实验数据采用了全球９０ｍ分辨率ＳＴＲＭ地形数据，构建了８级连续分辨率全球地形数据集，根据分析精度，选择了第７级，分辨率１８０ｍ的地形瓦片分别进行了无源淹没和有源淹没分析的实验。表１显示了在相同的分析范围下有源淹没分析与无源淹没分析的差异。随着洪水水位的上涨，两种分析方法中的淹没种子点都在增加，但是有源淹没分析中的淹没种子点增长率要低得多。此外，定义具有连通性的淹没范围为淹没区域，有源淹没分析保持了淹没区域数目为１，而无源淹没分析的淹没区域数目从２增加到了９。从图４中可以明显地看出，在２５６ｍ的相同洪水水位下和分析范围内，有源淹没的淹没范围要比无源淹没的淹没范围小得多。无源淹没的淹没范围中包含了许多彼此不连通的独立区域，而有源淹没的淹没范围是一个整体。这说明有源淹没相比于无源淹没体现出了连通性的特征。在此基础上，使用相同实验数据，对本文提出的有源淹没分析方法与文献［２］提出的有源淹没分析方法进行了实验比较，结果如表２所示。从表２可知，在同一个分析范围内，本文提出的有源淹没分析的方法在计算时间要少于传统方法。随着分析范围的扩大，传统方法的计算时间的增长速度要快得多。同时，当分析区域扩大到一定范围后，传统方法就会造成堆栈溢出，而改进的方法却能够很好地运行。
4结语
本文提出了三维虚拟地球下有源洪水淹没分析算法，并且在ＧｅｏＧｌｏｂｅ上通过一系列实验证明了该方法的有效性。该方法弥补了传统方法只能分析小范围或特定区域的不足，为在三维虚拟地球上进行洪水淹没分析和洪水演进仿真模拟奠定了基础，可以为防洪预警和灾后评估提供决策支持。下一步将结合水文模型，研究三维虚拟地球中洪水演进仿真模拟的方法。
作者：陈静 袁思佳 曾方敏 单位：武汉大学测绘遥感信息工程国家重点实验室
