Fast exact digital differential analyzer for circle generation

DOI10.1016/J.AMC.2015.08.104MaRDI QIDQ1732162zbMATH OpenOpenAlexFDO

Authors Jan L. Cieśliński, Leonid V. Moroz, Cezary J. Walczyk

Publication date 22 March 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.4974

zbMATH Keywords

circle generationdigital differential analyzersexact discretizationexplicit midpoint rule

Mathematics Subject Classification ID

Computer-aided design (modeling of curves and surfaces) (65D17) Finite difference and finite volume methods for ordinary differential equations (65L12)

Abstract: In the first part of the paper we present a short review of applications of digital differential analyzers (DDA) to generation of circles showing that they can be treated as one-step numerical schemes. In the second part we present and discuss a novel fast algorithm based on a two-step numerical scheme (explicit midpoint rule). Although our algorithm is as cheap as the simplest one-step DDA algoritm (and can be represented in terms of shifts and additions), it generates circles with maximal accuracy, i.e., it is exact up to round-off errors.

Recommendations

• A chronological and mathematical overview of digital circle generation algorithms -- introducing efficient 4- and 8-connected circles
• Fast scan conversion algorithm for circles
• Best approximate circles on integer grids
• Fast and numerically stable circle fit
• Incremental linear interpolation

Cites work

• A First Course in the Numerical Analysis of Differential Equations
• A linear algorithm for incremental digital display of circular arcs
• Algorithm for circle approximation and generation
• Approximation of logarithmic spirals
• Difference method for generation of circular arcs and ellipses
• scientific article; zbMATH DE number 4041188 (Why is no real title available?)
• scientific article; zbMATH DE number 3453104 (Why is no real title available?)
• Incremental Curve Generation
• Interpolator for a Computer Numerical Control System
• On simulations of the classical harmonic oscillator equation by difference equations
• On the exact discretization of the classical harmonic oscillator equation

Cited in

(2)

• Fast scan conversion algorithm for circles
• A chronological and mathematical overview of digital circle generation algorithms -- introducing efficient 4- and 8-connected circles

This page was built for publication: Fast exact digital differential analyzer for circle generation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1732162)