Abstract:
The Delaunay triangulation is the standard choice for building triangulated irregular networks (TINs) to represent terrain surfaces. However, the Delaunay triangulation is based only on the 2D coordinates of the data points, ignoring their elevation. It has long been recognized that sometimes it may be beneficial to use other, non-Delaunay, criteria to build TINs. Data-dependent triangulations were introduced decades ago to address this. However, they are rarely used in practice, mostly because the optimization of datadependent criteria often results in triangulations with many thin and elongated triangles. Recently, in the field of computational geometry, higher order Delaunay triangulations (HODTs) were introduced, trying to tackle both issues at the same time-data-dependent criteria and good triangle shape. Nevertheless, most previous studies about them have been limited to theoretical aspects. In this work we present the first extensive experimental study on the practical use of HODTs, as a tool to build data-dependent TINs. We present experiments with two USGS terrains that show that HODTs can give significant improvements over the Delaunay triangulation for the criteria identified as most important for data-dependent triangulations. The resulting triangulations have data-dependent values comparable to those obtained with pure data-dependent approaches, without compromising the shape of the triangles, and are faster to compute. © 2016 ACM.
Registro:
| Documento: |
Conferencia
|
| Título: | Implementing data-dependent triangulations with higher order delaunay triangulations |
| Autor: | Rodríguez, N.; Silveira, R.I.; Renz M.; Ali M.; Newsam S.; Renz M.; Ravada S.; Trajcevski G.; Amazon; ESRI; Facebook; Google; Microsoft; Oracle |
| Filiación: | Dept. de Computación - FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina
|
| Palabras clave: | Data-dependent triangulations; Delaunay triangulation; Triangulated irregular networks; Computational geometry; Geographic information systems; Information systems; Surveying; Tinning; 2D coordinates; Data dependent; Data dependent triangulations; Delau-nay triangulations; Higher-order delaunay triangulations; Terrain surfaces; Theoretical aspects; Triangulated irregular networks; Triangulation |
| Año: | 2016
|
| DOI: |
http://dx.doi.org/10.1145/2996913.2996958 |
| Título revista: | 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2016
|
| Título revista abreviado: | GIS Proc. ACM Int. Symp. Adv. Geogr. Inf. Syst.
|
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_97814503_v_n_p_Rodriguez |
Referencias:
- Alboul, L., Kloosterman, G., Traas, C., Van Damme, R., Best data-dependent triangulations (2000) J. Comput. Appl. Math., 119 (1-2), pp. 1-12
- Brown, J., Vertex based data dependent triangulations (1991) Comput. Aided Geom. D., 8, pp. 239-251
- De Kok, T., Van Kreveld, M., Löffler, M., Generating realistic terrains with higher-order delaunay triangulations (2005) Algorithms, 3669 (23), pp. 85-98
- Dyn, N., Levin, D., Rippa, S., Data dependent triangulations for piecewise linear interpolation (1990) IMA J. Numer. Anal., 10 (1), pp. 137-154
- Garland, M., Heckbert, P.S., Fast polygonal approximation of terrains and height fields (1995) Technical Report CMU-CS-95-181, , Sept
- Gudmundsson, J., Hammar, M., Van Kreveld, M., Higher order Delaunay triangulations (2002) Comput. Geom. Theory Appl., 4 (23), pp. 85-98
- Hjelle, O., Daehlen, M., (2006) Triangulations and Applications, , Springer-Verlag New York, Inc., Secaucus, NJ, USA
- Lawson, C.L., (1977) Mathematical Software III; Software for C1 Surface Interpolation, pp. 161-194. , Academic Press, New York
- Lehner, B., Umlauf, G., Hamann, B., Survey of techniques for data-dependent triangulations: Approximating color images (2007) GI Lecture Notes in Informatics, Visualization of Large and Unstructured Data Sets, pp. 178-187
- Li, P., Adams, M.D., A tuned mesh-generation strategy for image representation based on data-dependent triangulation (2013) IEEE T. Image Process., 22 (5), pp. 2004-2018
- Mitsche, D., Saumell, M., Silveira, R.I., On the number of higher order delaunay triangulations (2011) Theor. Comput. Sci., 412 (29), pp. 3589-3597
- Quak, E., Schumaker, L.L., (1991) Curves and Surfaces Chapter Least Squares Fitting by Linear Splines on Data Dependent Triangulations, pp. 387-390
- Reparaz, M., Rodriguez, N., (2014) Higher Order Delaunay Triangulations in Practice, , Master's thesis, Universidad de Buenos Aires
- Rippa, S., Long and thin triangles can be good for linear interpolation (1992) SIAM J. Numer. Anal., 29 (1), pp. 257-270
- Van Kreveld, M., Löffler, M., Silveira, R.I., Optimization for first order delaunay triangulations (2010) Comput. Geom. Theory Appl., 43 (4), pp. 377-394
- Wang, K., Lo, C.-P., Brook, G.A., Arabnia, H.R., Comparison of existing triangulation methods for regularly and irregularly spaced height fields (2001) Int. J. Geogr. Inf. Sci., 15 (8), pp. 743-762
- Weisz, J., Bodnar, R., A refined angle between normals criterion for scattered data interpolation (2001) Comput. Math. Appl., 41 (3-4), pp. 531-534A4 - Amazon; ESRI; Facebook; Google; Microsoft; Oracle
Citas:
---------- APA ----------
Rodríguez, N., Silveira, R.I., Renz M., Ali M., Newsam S., Renz M., Ravada S.,..., Amazon; ESRI; Facebook; Google; Microsoft; Oracle
(2016)
. Implementing data-dependent triangulations with higher order delaunay triangulations. 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2016.
http://dx.doi.org/10.1145/2996913.2996958---------- CHICAGO ----------
Rodríguez, N., Silveira, R.I., Renz M., Ali M., Newsam S., Renz M., et al.
"Implementing data-dependent triangulations with higher order delaunay triangulations"
. 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2016
(2016).
http://dx.doi.org/10.1145/2996913.2996958---------- MLA ----------
Rodríguez, N., Silveira, R.I., Renz M., Ali M., Newsam S., Renz M., et al.
"Implementing data-dependent triangulations with higher order delaunay triangulations"
. 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2016, 2016.
http://dx.doi.org/10.1145/2996913.2996958---------- VANCOUVER ----------
Rodríguez, N., Silveira, R.I., Renz M., Ali M., Newsam S., Renz M., et al. Implementing data-dependent triangulations with higher order delaunay triangulations. GIS Proc. ACM Int. Symp. Adv. Geogr. Inf. Syst. 2016.
http://dx.doi.org/10.1145/2996913.2996958