Piecewise optimal triangulation for the approximation of scattered data in the plane

Martin Bertram, James C. Barnes, Bernd Hamann, Kenneth I. Joy, Helmut Pottmann, Dilinur Wushour

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


We present an efficient algorithm to obtain a triangulated graph surface for scattered points (xi yi)T, i = 1, ..., n, with associated function values fi. The maximal distance between the triangulated graph surface and the function values is measured in z-direction (z = f(x, y)) and lies within a user-defined tolerance. The number of triangles is minimized locally by adapting their shapes to different second-degree least squares approximations of the underlying data. The method consists of three major steps: (i) subdividing the given discrete data set into clusters such that each cluster can be approximated by a quadratic polynomial within a prescribed tolerance; (ii) optimally triangulating the graph surface of each quadratic polynomial; and (iii) `stitching' the triangulations of all graph surfaces together. We also discuss modifications of the algorithm that are necessary to deal with discrete data points, without connectivity information, originating from a general two-manifold surface, i.e., a surface in three-dimensional space that is not necessarily a graph surface.

Original languageEnglish (US)
Pages (from-to)767-787
Number of pages21
JournalComputer Aided Geometric Design
Issue number8
StatePublished - Sep 2000

ASJC Scopus subject areas

  • Modeling and Simulation
  • Automotive Engineering
  • Aerospace Engineering
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Piecewise optimal triangulation for the approximation of scattered data in the plane'. Together they form a unique fingerprint.

Cite this