Contour Tracing by Piecewise Linear Approximations

David P. Dobkin, Allan R. Wilks, Silvio V.F. Levy, William P. Thurston

Research output: Contribution to journalArticlepeer-review

49 Scopus citations


We present a method for tracing a curve that is represented as the contour of a function in Euclidean space of any dimension. The method proceeds locally by following the intersections of the contour with the facets of a triangulation of space. The algorithm does not fail in the presence of high curvature of the contour; it accumulates essentially no round-off error and has a well-defined integer test for detecting a loop. In developing the algorithm, we explore the nature of a particular class of triangulations of Euclidean space, namely, those generated by reflections.

Original languageEnglish (US)
Pages (from-to)389-423
Number of pages35
JournalACM Transactions on Graphics (TOG)
Issue number4
StatePublished - Jan 10 1990

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Contour Tracing by Piecewise Linear Approximations'. Together they form a unique fingerprint.

Cite this