Contour Tracing by Piecewise Linear Approximations

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

doi:10.1145/88560.88575

Contour Tracing by Piecewise Linear Approximations

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

Research output: Contribution to journal › Article › peer-review

49 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	389-423
Number of pages	35
Journal	ACM Transactions on Graphics (TOG)
Volume	9
Issue number	4
DOIs	https://doi.org/10.1145/88560.88575
State	Published - Jan 10 1990

All Science Journal Classification (ASJC) codes

Computer Graphics and Computer-Aided Design

Access to Document

10.1145/88560.88575

Cite this

@article{640712d1ceca401d8aac5eb9aca077ae,

title = "Contour Tracing by Piecewise Linear Approximations",

abstract = "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.",

author = "Dobkin, {David P.} and Wilks, {Allan R.} and Levy, {Silvio V.F.} and Thurston, {William P.}",

year = "1990",

month = jan,

day = "10",

doi = "10.1145/88560.88575",

language = "English (US)",

volume = "9",

pages = "389--423",

journal = "ACM Transactions on Graphics (TOG)",

issn = "0730-0301",

publisher = "Association for Computing Machinery (ACM)",

number = "4",

}

TY - JOUR

T1 - Contour Tracing by Piecewise Linear Approximations

AU - Dobkin, David P.

AU - Wilks, Allan R.

AU - Levy, Silvio V.F.

AU - Thurston, William P.

PY - 1990/1/10

Y1 - 1990/1/10

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

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

UR - http://www.scopus.com/inward/record.url?scp=0025503218&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025503218&partnerID=8YFLogxK

U2 - 10.1145/88560.88575

DO - 10.1145/88560.88575

M3 - Article

AN - SCOPUS:0025503218

SN - 0730-0301

VL - 9

SP - 389

EP - 423

JO - ACM Transactions on Graphics (TOG)

JF - ACM Transactions on Graphics (TOG)

IS - 4

ER -

Contour Tracing by Piecewise Linear Approximations

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this