Implementing data-dependent triangulations with higher order delaunay triangulations

Mostrar todas las versiones(2)

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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Guez, N.R., Silveira, R.I.
Formato:	JOUR
Materias:	Data-dependent triangulation Delaunay triangulation Digital terrain model Higher order Delaunay triangulation Triangulated irregular network
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_22209964_v6_n12_p_Guez
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_22209964_v6_n12_p_Guez
record_format	dspace
spelling	todo:paper_22209964_v6_n12_p_Guez2023-10-03T16:40:42Z Implementing data-dependent triangulations with higher order delaunay triangulations Guez, N.R. Silveira, R.I. Data-dependent triangulation Delaunay triangulation Digital terrain model Higher order Delaunay triangulation Triangulated irregular network 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_22209964_v6_n12_p_Guez
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Data-dependent triangulation Delaunay triangulation Digital terrain model Higher order Delaunay triangulation Triangulated irregular network
spellingShingle	Data-dependent triangulation Delaunay triangulation Digital terrain model Higher order Delaunay triangulation Triangulated irregular network Guez, N.R. Silveira, R.I. Implementing data-dependent triangulations with higher order delaunay triangulations
topic_facet	Data-dependent triangulation Delaunay triangulation Digital terrain model Higher order Delaunay triangulation Triangulated irregular network
description	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.
format	JOUR
author	Guez, N.R. Silveira, R.I.
author_facet	Guez, N.R. Silveira, R.I.
author_sort	Guez, N.R.
title	Implementing data-dependent triangulations with higher order delaunay triangulations
title_short	Implementing data-dependent triangulations with higher order delaunay triangulations
title_full	Implementing data-dependent triangulations with higher order delaunay triangulations
title_fullStr	Implementing data-dependent triangulations with higher order delaunay triangulations
title_full_unstemmed	Implementing data-dependent triangulations with higher order delaunay triangulations
title_sort	implementing data-dependent triangulations with higher order delaunay triangulations
url	http://hdl.handle.net/20.500.12110/paper_22209964_v6_n12_p_Guez
work_keys_str_mv	AT gueznr implementingdatadependenttriangulationswithhigherorderdelaunaytriangulations AT silveirari implementingdatadependenttriangulationswithhigherorderdelaunaytriangulations
_version_	1807318981604802560

Implementing data-dependent triangulations with higher order delaunay triangulations

Ejemplares similares