Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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. This can affect the quality of the approximating surface. In fact, it has long been recognized that sometimes it may be beneficial to use other, non-Delaunay, criteria that take elevation into account to build TINs. Data-dependent triangulations were introduced decades ago to address this exact issue. However, data-dependent trianguations are rarely used in practice, mostly because the optimization of data-dependent criteria often results in triangulations with many slivers (i.e., thin and elongated triangles), which can cause several types of problems. More 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—by combining data-dependent criteria with a relaxation of the Delaunay criterion. In this paper, 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 30m digital elevation models that show that the use of HODTs can give significant improvements over the Delaunay triangulation for the criteria previously identified as most important for data-dependent triangulations, often with only a minor increase in running times. The triangulations produced have measure values comparable to those obtained with pure data-dependent approaches, without compromising the shape of the triangles, and can be computed much faster. © 2017 by the authors.

Registro:

Documento: Artículo
Título:Implementing data-dependent triangulations with higher order delaunay triangulations
Autor:Guez, N.R.; Silveira, R.I.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, C1428EGA, Argentina
Departament de Matem tiques, Universitat Polit cnica de Catalunya, Barcelona, 08034, Spain
Palabras clave:Data-dependent triangulation; Delaunay triangulation; Digital terrain model; Higher order Delaunay triangulation; Triangulated irregular network
Año:2017
Volumen:6
Número:12
DOI: http://dx.doi.org/10.3390/ijgi6120390
Título revista:ISPRS International Journal of Geo-Information
Título revista abreviado:ISPRS Int. J. Geo-Inf.
ISSN:22209964
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_22209964_v6_n12_p_Guez

Referencias:

  • Dyn, N., Levin, D., Rippa, S., Data dependent triangulations for piecewise linear interpolation (1990) IMA J. Numer. Anal., 10, pp. 137-154
  • Alboul, L., Kloosterman, G., Traas, C., Van Damme, R., Best data-dependent triangulations (2000) J. Comput. Appl. Math., 119, pp. 1-12
  • Brown, J., Vertex based data dependent triangulations (1991) Comput. Aided Geom. Des., 8, pp. 239-251
  • 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, pp. 743-762
  • Weisz, J., Bodnar, R., A refined angle between normals criterion for scattered data interpolation (2001) Comput. Math. Appl., 41, pp. 531-534
  • Garland, M., Heckbert, P.S., (1995) Fast Polygonal Approximation of Terrains and Height Fields, , Technical Report CMU-CS-95-181; Carnegie Mellon University: Pittsburgh, PA, USA
  • Gudmundsson, J., Hammar, M., Van Kreveld, M., Higher order delaunay triangulations (2002) Comput. Geom. Theory Appl., 4, pp. 85-98
  • Mitsche, D., Saumell, M., Silveira, R.I., On the number of higher order delaunay triangulations (2011) Theor. Comput. Sci., 412, pp. 3589-3597
  • Abe, Y., Okamoto, Y., On algorithmic enumeration of higher-order delaunay triangulations (2008) Proceedings of The 11th Japan-Korea Joint Workshop on Algorithms and Computation, , Seoul, Korea, 19–20 July
  • Biniaz, A., Dastghaibyfard, G., Drainage reality in terrains with higher-order delaunay triangulations (2008) Advances in 3D Geoinformation Systems, pp. 199-211. , van Oosterom, Zlatanova, S., Penninga, F., Fendel, E.M., Eds.; Springer: Berlin/Heidelberg, Germany
  • Biniaz, A., Dastghaibyfard, G., Slope fidelity in terrains with higher-order delaunay triangulations (2008) Proceedings of The 16th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision, pp. 17-23. , Plzen, Czech Republic, 4–7 February
  • De Kok, T., Van Kreveld, M., Löffler, M., Generating realistic terrains with higher-order delaunay triangulations (2005) Algorithms, 3669, pp. 85-98
  • Lawson, C.L., (1977) Mathematical Software III; Software for C1 Surface Interpolation, pp. 161-194. , Academic Press: New York, NY, USA
  • Van Kreveld, M., Löffler, M., Silveira, R.I., Optimization for first order delaunay triangulations (2010) Comput. Geom., 43, pp. 377-394
  • Rippa, S., Long and thin triangles can be good for linear interpolation (1992) SIAM J. Numer. Anal., 29, pp. 257-270
  • Hjelle, O., Daehlen, M., (2006) Triangulations and Applications, , Springer-Verlag Inc.: Secaucus, NJ, USA
  • Reparaz, M., Rodriguez, N., (2014) Higher Order Delaunay Triangulations in Practice, , Master’s Thesis, Universidad de Buenos Aires, Buenos Aires, Argentina
  • Schumaker, L.L., Computing optimal triangulations using simulated annealing (1993) Comput. Aided Geom. Des., 10, pp. 329-345
  • Kreylos, O., Hamann, B., On simulated annealing and the construction of linear spline approximations for scattered data (2001) IEEE Trans. Vis. Comput. Graph., 7, pp. 17-31
  • Kolingerov, I., Ferko, A., Multicriteria-optimized triangulations (2001) Vis. Comput., 17, pp. 380-395

Citas:

---------- APA ----------
Guez, N.R. & Silveira, R.I. (2017) . Implementing data-dependent triangulations with higher order delaunay triangulations. ISPRS International Journal of Geo-Information, 6(12).
http://dx.doi.org/10.3390/ijgi6120390
---------- CHICAGO ----------
Guez, N.R., Silveira, R.I. "Implementing data-dependent triangulations with higher order delaunay triangulations" . ISPRS International Journal of Geo-Information 6, no. 12 (2017).
http://dx.doi.org/10.3390/ijgi6120390
---------- MLA ----------
Guez, N.R., Silveira, R.I. "Implementing data-dependent triangulations with higher order delaunay triangulations" . ISPRS International Journal of Geo-Information, vol. 6, no. 12, 2017.
http://dx.doi.org/10.3390/ijgi6120390
---------- VANCOUVER ----------
Guez, N.R., Silveira, R.I. Implementing data-dependent triangulations with higher order delaunay triangulations. ISPRS Int. J. Geo-Inf. 2017;6(12).
http://dx.doi.org/10.3390/ijgi6120390