A Hybrid Algorithm for Terrain Simplification
Subject Areas : electrical and computer engineeringF. Dabaghi Zarandi 1 * , Mohammad Ghodsi 2
1 -
2 -
Keywords: Terraun simplification triangulated irregular networks clustering hybrid greedy algorithms,
Abstract :
Terrain simplification problem is one of fundamental problems in computational geometry and it has many applications in other fields such as geometric information systems, computer graphics, image processing. Terrain is commonly defined by a set of n points in three dimension space. Major goal of terrain simplification problem is removing some points of one terrain so that maximum error of simplified surface is a certain threshold. There are two optimization goals for this problem: (1) min-k, where for a given error threshold , the goal is to find a simplification with the minimum number of points for which the error is that most , and (2) min-, where for a given number n, the goal is to find a simplification of at most m points that has the minimum simplification error. Simplification problem is NP-hard in optimal case. In this paper we present a hybrid algorithm for terrain simplification that performs in three phases. First, terrain is divided to some clusters, then any cluster is simplified independently and finally, the simplified clusters are merged. Our algorithm solves the problem in . The proposed algorithm is implemented and verified by experiments.
[1] P. K. Agarwal and S. Surii, "Surface approximation and geometrics partitions," in Proc. 5th ACM-SIAM Symp. Discrete Algorithms, pp. 24-33, 1994.
[2] M. Garland and P. S. Heckbert, "Fast polygonal approximation of terrains and height fields," in Technical Report, CMU-CS-95-181, 1995.
[3] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry, Springer-Verlag New York Inc, 3rd Edition, May 2008.
[4] J. Gudmundsson, M. Hammar, and M. van Kreveld, "Higher order delaunay triangulations," Computational Geometry: Theory and Applications, vol. 23, no. 1, pp. 85-98, Jul. 2002.
[5] M. Van Kreveld and R. I. Silveira, "Optimal higher order delaunay triangulations of polygons," Computational Geometry: Theory and Applications, vol. 42, no. 8, pp. 803-813, Oct. 2009.
[6] I. Dong Yun, K. Choo, and S. Uk Lee, "Mesh simplification using the edge attributes," EURASIP J. Appl. Signal Process., vol. 2002, no. 1, pp. 1102-1115, Jan. 2002.
[7] C. Chuon and S. Guha, "Volume cost based mesh simplification," in Proc. Int. Conf. on Computer Graphics, Imaging and Visualization, pp. 164-169, 11-14 Aug. 2009.
[8] Y. Guoqing, C. Zhun, and W. Mao, "The new triangulation-simplify algorithm of tin," in Proc. Int. Conf. on Computer Graphics and Virtual Reality, CGVR'06, pp. 79-85, 2006.
[9] M. Garland and P. S. Heckbert, "Surface simplification using quadric error metrics," in Proc. of the 24th Annual Conf. on Computer Graphics and Interactive Techniques, SIGGRAPH'97, pp. 209-216, New York, NY, US, 1997.
[10] W. Zhao, T. Tang, H. Gong, F. Duan, and Y. Mo, "Dynamic data retrieval and distance decay of triangulated irregular network (TIN)," Annals of GIS, vol. 12, no. 1, pp. 21-26, 2006.
[11] W. Xie and J. Lu, "An improved simplification algorithm of 3d terrain visualization model," in Proc. IAPRS Integrated System for Spatial Data Production, Custodian and Decision Support, pp. 545-548, 20-23 Aug. 2002.
[12] J. Wang, L. Wang, J. Li, and I. Hagiwara, "A feature preserved mesh simplification algorithm," J. of Engineering and Computer Innovations, vol. 2, no. 6, pp. 98-105, Jun. 2011.
[13] M. Garland and P. S. Heckbert, "Surface simplification using quadric error metrics," in Proc. 24th Annual Conf. on Computer Graphics and Interactive Techniques, SIGGRAPH '97, 1997.
[14] P. S. Heckbert and M. Garland, "Optimal triangulation and quadric-based surface simplification," J. of Computational Geometry: Theory and Applications, vol. 14, no. 1-3, pp. 49-65, Nov. 1999.
[15] J. Wei and Y. Lou, "Feature preserving mesh simplication using feature sensitive metric," J. of Computer Science and Technology, vol. 25, no. 3, pp. 595-605, May 2010.
[16] ف. دباغی و م. قدسی، "یک الگوریتم تقریبی برای سادهسازی سرزمین،" شانزدهمین کنفرانس ملی سالانه انجمن کامپیوتر ایران، دانشگاه صنعتی شریف، تهران، صص. 595-591، 1389.
[17] P. K. Agarwal and P. K. Desikan, "An efficient algorithm for terrain simplification," in Proc. 8th ACM-SIAM Symp. on Discrete Algorithms, pp. 139-147, 1997.
[18] Software, Lakes Environmental, Web gis. http://www.webgis.com/