Implementing data-dependent triangulations with higher order delaunay triangulations
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...
Guardado en:
| Autores principales: | , , , , , , , |
|---|---|
| Formato: | CONF |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_97814503_v_n_p_Rodriguez |
| Aporte de: |
| id |
todo:paper_97814503_v_n_p_Rodriguez |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_97814503_v_n_p_Rodriguez2023-10-03T16:43:22Z Implementing data-dependent triangulations with higher order delaunay triangulations Rodríguez, N. Silveira, R.I. Renz M. Ali M. Newsam S. Renz M. Ravada S. Trajcevski G. Amazon; ESRI; Facebook; Google; Microsoft; Oracle 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 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. CONF info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_97814503_v_n_p_Rodriguez |
| 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 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 |
| spellingShingle |
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 Rodríguez, N. Silveira, R.I. Renz M. Ali M. Newsam S. Renz M. Ravada S. Trajcevski G. Amazon; ESRI; Facebook; Google; Microsoft; Oracle Implementing data-dependent triangulations with higher order delaunay triangulations |
| topic_facet |
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 |
| 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. 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. |
| format |
CONF |
| author |
Rodríguez, N. Silveira, R.I. Renz M. Ali M. Newsam S. Renz M. Ravada S. Trajcevski G. Amazon; ESRI; Facebook; Google; Microsoft; Oracle |
| author_facet |
Rodríguez, N. Silveira, R.I. Renz M. Ali M. Newsam S. Renz M. Ravada S. Trajcevski G. Amazon; ESRI; Facebook; Google; Microsoft; Oracle |
| author_sort |
Rodríguez, N. |
| 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_97814503_v_n_p_Rodriguez |
| work_keys_str_mv |
AT rodriguezn implementingdatadependenttriangulationswithhigherorderdelaunaytriangulations AT silveirari implementingdatadependenttriangulationswithhigherorderdelaunaytriangulations AT renzm implementingdatadependenttriangulationswithhigherorderdelaunaytriangulations AT alim implementingdatadependenttriangulationswithhigherorderdelaunaytriangulations AT newsams implementingdatadependenttriangulationswithhigherorderdelaunaytriangulations AT renzm implementingdatadependenttriangulationswithhigherorderdelaunaytriangulations AT ravadas implementingdatadependenttriangulationswithhigherorderdelaunaytriangulations AT trajcevskig implementingdatadependenttriangulationswithhigherorderdelaunaytriangulations AT amazonesrifacebookgooglemicrosoftoracle implementingdatadependenttriangulationswithhigherorderdelaunaytriangulations |
| _version_ |
1807321437111844864 |