期刊信息
- 刊名： 河北师范大学学报（自然科学版）Journal of Hebei Normal University (Natural Science)
- 主办： 河北师范大学
- ISSN： 1000-5854
- CN： 13-1061/N
- 中国科技核心期刊
- 中国期刊方阵入选期刊
- 中国高校优秀科技期刊
- 华北优秀期刊
- 河北省优秀科技期刊
Crystal Growth of Higher-order Diagrams
摘要/Abstract
Voronoi图是计算几何的重要分支.高阶Voronoi图是Voronoi图在阶数方面的扩展，在许多领域有着重要应用.本文提出了生成高阶Voronoi图的结晶生长方法.该方法以生成元为初始生长点，使用 4-连通模板、 8-连通模板或二者交替使用进行结晶生长，最后对不同颜色的区域分别进行处理，就会得到基于城区距离、棋盘距离或欧氏距离的各种高阶Voronoi图.
Voronoi diagrams is one of main branches in computational geometry.Higher-older voronoi diagrams is a kind of spread of voronoi in orders and which is used in many fields.In this paper,crystal growth is presented to construct higher-older Voronoi diagrams.In the method,generators of Voronoi diagrams are regarded as initial growing points,then the crystallization process begins from these generators with 4-point template,8-point template or alternating usage about 4-point template and 8-point template.By separating different colour regions,we can obtain higher-order voronoi diagrams based on the city zone distance, the chessboard distance and the euclid distance.
关键词
参考文献 12
- [1] SHAMOS M I,HOEY D.Closest-point Problems [C]//Proceedings of the Sixteenth Annual Institute of Electrical and Electronic Engineers Symposium on the Foundations of Computer Science,Washington:IEEE Computer Society,1975:151-162.
- [2] 周培德.计算几何 [M].北京:清华大学出版社,2000.
- [3] LEE D T.On k-nearest Neighbor Voronoi Diagrams in the Plane [J].IEEE Transactions on Computers,1982,31(6):478-487.
- [4] FRANCO P.PREPARATA,MICHAEL I.庄心谷译.计算几何导论 [M].北京:科学出版社,1990.
- [5] CHAZELLE B,EDELSBRUNNER H.An Improved Algorithm for Constructing Kth-order Voronoi Diagrams [J].IEEE Transactions on Computers,1987,36(11):1349-1354.
- [6] CLARKSON K L.New Applications of Random Sampling in Computational Geometry [J].Discrete and Computational Geometry,1987,2(1):195-222.
- [7] BOISSONNAT J D,DEVILLERS O,TEILLAUD M.A Semidynamic Construction of Higher-order Voronoi Diagrams and Its Randomized Analysis [J].Algorithmic,1993,9(4):329-356.
- [8] BOISSONNAT J D,TEILLAUD M.A Hierarchical Representation of Objects:the Delaunay Tree [C]//Proceeding of the Second ACM Symposium on Computational Geometry,New York:ACM Press,1986:260-268.
- [9] BOISSONNAT J D,TEILLAUD M.On the Randomized Construction of the Delaunay Tree [J].Theoretical Computer Science,1993,112(2):339-354.
- [10] 田孝康 村岛定行.2次元離散画面上の高次のボロノイ 作成について [M].电子情报通信学会论文志.1999:283-288.
- [11] 顾晓青.高阶Voronoi图的生成及应用 [D].石家庄:河北师范大学,2003.
- [12] 曹清洁.障碍Voronoi图的结晶生成 [D].石家庄:河北师范大学,2004.