Determination of Circumcenter of Triangle on Ellipsoidal Surface Based on Map Algebra

doi:10.11947/j.AGCS.2016.20140503

Abstract

Abstract: The geodesic distances from the circumcenter to 3 vertexes of the triangle on ellipsoidal surface are equal. The ellipsoid-oriented determination of circumcenter of triangle on ellipsoidal surface is applicable when it comes to generation of the Voronoi diagram and construction of the Delaunay triangulation net on the ellipsoidal earth, which can be considered as a solution of significance in computation of geometries and spatial analysis on the ellipsoid. Based on the idea of combining the raster and vector methods and the theory of map algebra, the working process can be described as below: firstly, initiate the geographical distance transformation and create the distance field with a high degree of accuracy; secondly, conduct boundary tracking and matching and then determinate the range of grids where the circumcenter of triangle locates; thirdly, interpolate the initial equidistant point; finally, approximate the circumcenter of triangle on earth ellipsoidal surface by means of numeric calculation. The positioning error of this algorithm is controlled less than 0.001 m within several thousand kilometers range of span. As regards the method proposed in the present paper, its computational efficiency is O(m) where m is the number of pixels in the image, i.e., grid resolution. In conclusion, this algorithm can be considered as both ellipsoid-oriented and not content-related, which is especially appropriate for complex geocomputation globally.

Key words: map algebra, geographical distance transformation, ellipsoidal surface, circumcenter of triangle, raster&vector-based

CLC Number:

P208

JIANG Huiping, TAN Shudong, HU Hai. Determination of Circumcenter of Triangle on Ellipsoidal Surface Based on Map Algebra[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(2): 241-249.

References

[1] 周培德. 计算几何[M]. 北京: 清华大学出版社, 2000. ZHOU Peide. Computational Geometry[M]. Beijing: Tsinghua University Press, 2000.
[2] GOLD C M. The Global GIS[C]//Proceeding of the International Workshop on Dynamic and Multi-Dimension GIS. Hong-Kong, China: [s.n.], 1997: 80-91.
[3] 刘广军, 郭晶, 刘旭东. 基于椭球面大地线三角网的CORS布站研究与仿真[C]//第13届中国系统仿真技术及其应用学术年会论文集. 黄山: 中国自动化学会系统仿真专业委员会, 2011. LIU Guangjun, GUO Jing, LIU Xudong. Research and Simulation on CORS Station Distribution Based on Ellipsoid Geodetic-line Triangulation Network[C]//Proceedings of 13th Chinese Conference on System Simulation Technology & Application. Huangshan: Professional Committee of China Automation Society System Simulation, 2011.
[4] 施一民, 朱紫阳. 椭球面上Delaunay三角形的外接大地圆圆心的求解[J]. 同济大学学报, 2004, 32(1): 78-81. SHI Yimin, ZHU Ziyang. Determination of Center for Geodetic Circle Which Passes through Three Top Points of Triangle on Ellipsoidal Surface[J]. Journal of Tongji University, 2004, 32(1): 78-81.
[5] 冯琰, 施一民. 基于区域性椭球面数字地面模型的研究[J]. 同济大学学报, 2003, 31(8): 964-967. FENG Yan, SHI Yimin. New DTM Based on Surface of Regional Ellipsoid[J]. Journal of Tongji University, 2003, 31(8): 964-967.
[6] 赵学胜, 陈军, 王金庄. 基于O-QTM的球面Voronoi图的生成算法[J]. 测绘学报, 2002, 31(2): 157-163. ZHAO Xuesheng, CHEN Jun, WANG Jinzhuang. QTM-based Algorithm for the Generating of Voronoi Diagram for Spherical Objects[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2): 157-163.
[7] HOREMUZ M. Error Calculation in Maritime Delimitation between States with Opposite or Adjacent Coasts[J]. Marine Geodesy, 1999, 22(1): 1-17.
[8] 施一民, 冯琰. 地球椭球面上另一种形式的测地坐标系的建立[J]. 同济大学学报, 2001, 29(11): 1282-1285. SHI Yimin, FENG Yan. Establishment of Another Form of Geodesic Coordinate System on Earth Ellipsoid[J]. Journal of Tongji University, 2001, 29(11): 1282-1285.
[9] 赵文婷, 彭俊毅. 基于Voronoi图的无人机航迹规划[J]. 系统仿真学报, 2008(z2): 159-162, 165. ZHAO Wenting, PENG Junyi. Voronoi Diagram-based Path Planning for UAVs[J]. Journal of System Simulation, 2008(z2): 159-162, 165.
[10] 阎代维, 谷良贤, 王兴治. 基于Voronoi图的巡航导弹突防路径规划研究[J]. 弹箭与制导学报, 2005, 25(2): 11-13. YAN Daiwei, GU Liangxian, WANG Xingzhi. The Study of Cruise Missile Path Planning with Voronoi Diagram[J]. Journal of Projectiles, Rockets, Missiles and Guidance, 2005, 25(2): 11-13.
[11] FERRERO S, PIEROZZI M, REPETTI L, et al. An Algorithm for the Unambiguous Determination of the Equidistant Boundary Line between Two (or More) Coastlines[J]. Applied Geomatics, 2009, 1(3): 49-58.
[12] SJÖBERG L E. The Three-point Problem of The Median Line Turning Point: on the Solutions for the Sphere and Ellipsoid[J]. International Hydrographic Review, 2002, 3(1): 81-87.
[13] 李庆扬, 王能超, 易大义. 数值分析[M]. 第5版. 北京: 清华大学出版社, 2008. LI Qingyang, WANG Nengchao, YI Dayi. Numerical Analysis[M]. 5th ed. Beijing: Tsinghua University Press, 2008.
[14] 胡鹏, 游涟, 胡海. 地图代数概论[M]. 北京: 测绘出版社, 2008. HU Peng, YOU Lian, HU Hai. Introduction to Map Algebra[M]. Beijing: Publishing House of Surveying and Mapping, 2008.
[15] 胡鹏, 范青松, 胡海. 椭球上的测地变换和Voronoi图的生成--地理空间度量[J]. 武汉大学学报(信息科学版), 2007, 32(9): 825-828. HU Peng, FAN Qingsong, HU Hai. Distance Transformation and Voronoi Generation on Earth Ellipsoid--Metrics of Geographic Space[J]. Geomatics and Information Science of Wuhan University, 2007, 32(9): 825-828.
[16] GOLD C, MOSTAFAVI M A. Towards the Global GIS[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2000, 55(3): 150-163.
[17] 胡鹏, 刘沛兰, 胡海, 等. 地球信息的度量空间和Global GIS[J]. 武汉大学学报(信息科学版), 2005, 30(4): 317-321. HU Peng, LIU Peilan, HU Hai, et al. Metric Space of Earth Information and Global GIS[J]. Geomatics and Information Science of Wuhan University, 2005, 30(4): 317-321.
[18] KJENSTAD K. Construction and Computation of Geometries on the Ellipsoid[J]. International Journal of Geographical Information Science, 2011, 25(9): 1413-1437.
[19] HU Hai, LIU Xiaohang, HU Peng. Voronoi Diagram Generation on the Ellipsoidal Earth[J]. Computers & Geosciences, 2014, 73: 81-87.
[20] 胡鹏, 杨传勇, 胡海, 等. GIS的基本理论问题--地图代数的空间观[J]. 武汉大学学报(信息科学版), 2002, 27(6): 616-621. HU Peng, YANG Chuanyong, HU Hai,et al. Space View of Map Algebra[J]. Geomatics and Information Science of Wuhan University, 2002, 27(6): 616-621.
[21] 熊介. 椭球大地测量学[M]. 北京: 解放军出版社, 1988. XIONG Jie. Ellipsoidal Geodesy[M]. Beijing: Publishing House of Liberation Army, 1988.
[22] 张楚宾. 球面三角学[M]. 北京: 高等教育出版社, 1959. ZHANG Chubin. Spherical Trigonometry[M]. Beijing: Higher Education Press, 1959.
[23] 陈健, 晁定波. 椭球大地测量学[M]. 北京: 测绘出版社, 1992. CHEN Jian, CHAO Dingbo. Ellipsoidal Geodesy[M]. Beijing: Publishing House of Surveying and Mapping, 1992.
[24] 刘相滨, 向坚持, 阳波. 基于八邻域边界跟踪的标号算法[J]. 计算机工程与应用, 2001, 37(23): 125-126, 132. LIU Xiangbin, XIANG Jianchi, YANG Bo. A Labeling Algorithm Based on 8-Connected Boundary Tracking[J]. Computer Engineering and Applications, 2001, 37(23): 125-126, 132.
[25] 孔祥元, 郭际明, 刘宗泉. 大地测量学基础[M]. 武汉: 武汉大学出版社, 2005. KONG Xiangyuan, GUO Jiming, LIU Zongquan. Foundation of Geodesy[M]. Wuhan: Wuhan University Press, 2005.
[26] 宋树华, 程承旗, 关丽, 等. 全球空间数据剖分模型分析[J]. 地理与地理信息科学, 2008, 24(4): 11-15. SONG Shuhua, CHENG Chengqi, GUAN Li, et al. Analysis on Global Geodata Partitioning Models[J]. Geography and Geo-Information Science, 2008, 24(4): 11-15.
[27] 胡海, 吴艳兰. 椭球面上混合基线图形的缓冲区和等比例线问题[J]. 测绘工程, 2011, 20(3): 1-4, 8. HU Hai, WU Yanlan. Problems of Graphics Buffers and the Proportion Line of Ellipsoid Mixed Baseline (or Normal Curve)[J]. Engineering of Surveying and Mapping, 2011, 20(3): 1-4, 8.