Linear-time geometric algorithm for evaluating Bézier curves. (January 2020)

• Record Type: Journal Article
• Authors: Woźny, Paweł; Chudy, Filip
• Is Part Of: Computer aided design. Volume 118(2020)
• Publication Date: 2020-01
• Subjects: Bernstein polynomials -- Bézier curves -- Bézier surfaces -- Convex hull property -- Geometric algorithms -- Linear complexity; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2019.102760
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: A new algorithm for computing a point on a polynomial or rational curve in Bézier form is proposed. The method has a geometric interpretation and uses only convex combinations of control points. The new algorithm's computational complexity is linear with respect to the number of control points and its memory complexity is O ( 1 ) . Some remarks on similar methods for surfaces in rectangular and triangular Bézier form are also given. Highlights: A new algorithm for computing a point on a polynomial or rational curve in Bézier form is proposed. The method has a geometric interpretation and uses only convex combinations of control points. The new algorithm's computational complexity is linear with respect to the number of control points and its memory complexity is O ( 1 ) . Some remarks on similar methods for surfaces in rectangular and triangular Bézier are also given.