北京航空航天大学学报 ›› 2017, Vol. 43 ›› Issue (6): 1182-1190.doi: 10.13700/j.bh.1001-5965.2016.0425

• 论文 • 上一篇    下一篇

重叠网格装配中的一种改进ADT搜索方法

李鹏, 高振勋, 蒋崇文, 李椿萱   

  1. 北京航空航天大学 航空科学与工程学院, 北京 100083
  • 收稿日期:2016-05-20 出版日期:2017-06-20 发布日期:2016-10-28
  • 通讯作者: 高振勋,E-mail:gaozhenxun@buaa.edu.cn E-mail:gaozhenxun@buaa.edu.cn
  • 作者简介:李鹏 男,博士研究生。主要研究方向:计算流体力学;高振勋 男,博士,讲师。主要研究方向:计算流体力学。
  • 基金资助:
    航空科学基金(20141251015)

Improved ADT searching method in overlapping grid assembly

LI Peng, GAO Zhenxun, JIANG Chongwen, LEE Chunhian   

  1. School of Aeronautic Science and Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China
  • Received:2016-05-20 Online:2017-06-20 Published:2016-10-28
  • Supported by:
    Aeronautical Science Foundation of China (20141251015)

摘要: 针对现有交替数字二叉树(ADT)方法的不足,引入辅助笛卡儿网格提出了一种基于散列数据结构的改进搜索方法以缓解可能出现堆栈溢出的问题和提高重叠网格装配的效率。该方法以散列数据结构的方式对网格单元进行存储和搜索,首先以辅助笛卡儿网格对网格单元的存储空间进行初步映像,然后基于ADT搜索树作进一步检索。在ADT搜索方法的基础上,笛卡儿网格的引入进一步缩小了网格单元的搜索范围使得改进方法具有更好的效率。基于单个网格节点,查询深度和搜索耗时的测试显示改进方法相比现有ADT搜索方法能使挖洞的平均效率提高25%以上。此外,挖洞结果和基于网格装配的数值计算验证了改进搜索方法在重叠网格装配中的可靠性。

关键词: 重叠网格, 网格装配, 交替数字二叉树(ADT), 贡献单元, 搜索方法

Abstract: An improved searching method of alternating digital tree (ADT) is proposed for making up the deficiency of the existing ADT method and improving the efficiency of the overlapping grid assembly. The new method stores and retrieves donor cells based on a hash data structure, in which an auxiliary Cartesian mesh is first applied to map the storage address similar to the table of contents in hash table, and then a node-oriented ADT is used for further retrieval in accordance with the aforementioned storage space. Based on ADT search, the introduction of the Cartesian mesh can further narrow the search scope of donor cell, which makes the present one have better efficiency. Tests of searching depth and time consumption based on several discrete grid nodes indicate that the present method can enhance the average hole-cutting efficiency by more than 25% compared with the existing ADT method. Moreover, the hole-cutting results and numerical computations of typical configurations confirm the reliability of the improved ADT searching method in overlapping grid assembly.

Key words: overlapping grid, grid assembly, alternating digital tree (ADT), donor cell, searching method

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发