光谱学与光谱分析 |
|
|
|
|
|
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.
|
Received: 2012-10-25
Accepted: 2013-01-30
|
|
Corresponding Authors:
SHEN Zhan-feng
E-mail: shenzf@irsa.ac.cn
|
|
[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. |
[1] |
YANG Hui-hua1, DU Ling-ling2, LI Ling-qiao2, TANG Tian-biao2, GUO Tuo2, LIANG Qiong-lin3, WANG Yi-ming3, LUO Guo-an3. Parallel PLS Aigorithm Using MapReduce and Its Aplication in Spectral Modeling [J]. SPECTROSCOPY AND SPECTRAL ANALYSIS, 2012, 32(09): 2399-2404. |
[2] |
CHEN Yong-ming, LIN Ping, BAO Yi-dan,HE Yong*. Application of the Distributed and Parallel Computation in Spectroscopy Signal Processing[J]. SPECTROSCOPY AND SPECTRAL ANALYSIS, 2009, 29(04): 1074-1077. |
|
|
|
|