Abstract: This paper mainly discusses the overset mesh pre-processing technology, and supplies a new efficient and robust hole-cutting algorithm applied in the overset mesh preprocessing, which is based on maze algorithm and can be easily implemented with low complexity. Then the paper brings forward the overset relationship graph to deal with the problems brought by multi-level overset grids. Finally, to increase the intersection efficiency, the grid-based kd tree is introduced. Experiment results show that even in the case of complicated overset areas of large grids number, the overset preprocessing technology can get good performance.

Key words: Maze Algorithm, Overset Relationship Graph, Grid-based KD Tree

摘要： 本文主要讨论重叠网格预处理方法，并提出迷路算法应用于“挖洞”过程，为重叠网格预处理提供了高效、可靠的“挖洞”方法，算法复杂度低，实现简单，健壮性好；在多层次嵌套重叠方面，引入了重叠网格主从关系图有效解决多层次嵌套重叠带来的问题；在提高找重效率方面，建立基于网格的kd树加快了找重过程。实验结果表明在大网格量、复杂重叠区域时该重叠网格预处理技术仍能得到较理想的效率。

关键词: 迷路算法, 重叠网格主从关系, 基于网格的kd树