1. 中国科学院遥感与数字地球研究所, 北京 100101 2. Department of Geography, University of California, Los Angeles (UCLA), Los Angeles, CA 90095, USA
A Fast Algorithm to Find the Largest Inner Circle of a Complex Polygon
SHEN Zhan-feng1, Yongwei Sheng2, LUO Jian-cheng1
1. Institute of Remote Sensing and Digital Earth, Chinese Academy of Sciences, Beijing 100101, China 2. Department of Geography, University of California, Los Angeles, CA 90095, USA
Abstract：It is necessary to find the largest inner circle of a complex polygon in many applications. The present paper develops a method for finding the largest inner circle of a polygon based on Voronoi diagram, and then improves the algorithm by medial axis simplification (MAS) and parallel computing. Data partition is a key issue in parallel computing of vector data. The algorithm complexity equalization strategy (ACES) is then presented. By several experimental tests of large quantity of lakes in Alaska we conclude that the approach developed in this paper performs effectively and efficiently by using MAS and ACES methods.
Key words：The largest inner circle of a polygon;Voronoi;Medial axis;Parallel computing;Data partitioning strategy
沈占锋1，Yongwei Sheng2，骆剑承1 . 一种复杂多边形最大内圆的快速查找算法 [J]. 光谱学与光谱分析, 2013, 33(06): 1581-1586.
SHEN Zhan-feng1, Yongwei Sheng2, LUO Jian-cheng1 . A Fast Algorithm to Find the Largest Inner Circle of a Complex Polygon . SPECTROSCOPY AND SPECTRAL ANALYSIS, 2013, 33(06): 1581-1586.
[1] Blum H. A Transformation for Extracting New Descriptors of Shape. Ed. Cambridge, MA: M. I. T. Press. 1967. 362. [2] Lee D T. Medial Axis Transformation of a Planar Shape. 1982，4(4): 363. [3] Preparata P. Proc. 6th Symp. Math. Foundations of Comput. Sci., Sept. 1977. 443. [4] Lee D T, Drysdale R L. SIAM J. Comput. 1981，10: 73. [5] Ramamurthy R, Farouki R T. Journal of Computational and Applied Mathematics，1999，102: 119. [6] Shen D Y，Sheng Y W. IEEE Geoscience and Remote Sensing Letters, 2012, 9(2): 194. [7] Drysdale R L，Lee D T. Proc. 16th Allerton Conf. Commun. Control Comput，1978. 833. [8] Oishi Y, Sugihara K. Graphical Models and Image Processing, 1995, 57(4): 303. [9] Preparata P. Proc. 6th Symposium Mathematical Foundations of Computer Science, Sept., 1977. 443. [10] Drysdale R L，Lee D T. Control and Computing, 1978. 833. [11] Cheonga O, Everettb H, Glisse M. Computational Geometry, 2011, 44: 234. [12] Kirkpatrick D G. Proc. 20th Annu. Symp. Found. Computer Sci., 1979. 18. [13] Dey T K, Zhao W. Computer-Aided Design，2004，36: 195. [14] Beristain A M，Gonzalez A I. Journal of Mathematical Imaging and Vision，2012，42: 225. [15] Dorado R. Computer-Aided Design，2009，41: 1050. [16] SHEN Zhan-feng, LUO Jian-cheng, CHEN Qiu-xiao，et al(沈占锋，骆剑承，陈秋晓，等). Journal of Harbin Institute of Technology(哈尔滨工业大学学报)，2006，38(11): 1968. [17] Shen Z F, Luo J C, Wu W. Journal of the Indian Society of Remote Sensing, 2012, 40(3): 357. [18] Shah C A, Sheng Y W, Smith L C. IEEE Transactions on Geoscience and Remote Sensing, 2008, 46: 3908. [19] Joseph O’ Rourke. Cambridge University Press，2005.
