uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A chronological and mathematical overview of digital circle generation algorithms: Introducing efficient 4- and 8-connected circles
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Visual Information and Interaction. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computerized Image Analysis and Human-Computer Interaction.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Visual Information and Interaction. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computerized Image Analysis and Human-Computer Interaction.ORCID iD: 0000-0003-1054-2754
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Visual Information and Interaction. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computerized Image Analysis and Human-Computer Interaction.
2016 (English)In: International Journal of Computer Mathematics, ISSN 0020-7160, E-ISSN 1029-0265, Vol. 93, no 8, 1241-1253 p.Article in journal (Refereed) Published
Abstract [en]

Circles are one of the basic drawing primitives for computers and while the naive way of setting up an equation for drawing circles is simple, implementing it in an efficient way using integer arithmetic has resulted in quite a few different algorithms. We present a short chronological overview of the most important publications of such digital circle generation algorithms. Bresenham is often assumed to have invented the first all integer circle algorithm. However, there were other algorithms published before his first official publication, which did not use floating point operations. Furthermore, we present both a 4- and an 8-connected all integer algorithm. Both of them proceed without any multiplication, using just one addition per iteration to compute the decision variable, which makes them more efficient than previously published algorithms.

Place, publisher, year, edition, pages
2016. Vol. 93, no 8, 1241-1253 p.
Keyword [en]
digital circle drawing; all integer arithmetic; connectivity; Bresenham; midpoint and Michener circle
National Category
Other Computer and Information Science
Research subject
Computerized Image Processing
Identifiers
URN: urn:nbn:se:uu:diva-266119DOI: 10.1080/00207160.2015.1056170ISI: 000377224200001OAI: oai:DiVA.org:uu-266119DiVA: diva2:867495
Available from: 2015-06-24 Created: 2015-11-05 Last updated: 2017-12-01Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Hast, AndersBengtsson, Ewert

Search in DiVA

By author/editor
Hast, AndersBengtsson, Ewert
By organisation
Division of Visual Information and InteractionComputerized Image Analysis and Human-Computer Interaction
In the same journal
International Journal of Computer Mathematics
Other Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 489 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf