4 ms·

You can always try Bresenham’s circle drawing algorithm.

scrubs 5y ago
Beat me to it. And there are several optimizations on top that by, more or less, by reflecting the points as you compute one quadrant of the circle.
gotaquestion 5y ago
This is the era where prior art doesn't exist. Why read a book when you can blog about discovering "something new". I could probably make a killing blogging about my "discovery" of the algorithms in the book "Hacker's Delight".
- Mr_P 5y ago
  The author titled one of the sections "Midpoint circle algorithm". There happens to be a Wikipedia page on "Midpoint circle algorithm": https://en.wikipedia.org/wiki/Midpoint_circle_algorithm https://en.wikipedia.org/wiki/Midpoint_circle_algorithm The page claims, "Bresenham's circle algorithm is derived from the midpoint circle algorithm." The author of this blog post even made it clear, at the end of their article, that... "many explanations of midpoint algorithm use the final, optimized version. But I added several unoptimized steps." I think there's a lot of value in a blogpost that demonstrates how someone could re-derive a widely-used algorithm from scratch.
- taneq 5y ago
  This always blows my mind - for the first time in human history we live in a world where almost all prior art is relatively easily discoverable, and people don't even bother. I guess I shouldn't be surprised, after all, I've met a lot of people.
  - pjc50 5y ago
    The sheer weight of information can make it harder to find. Also, nobody gets paid for being the prior art.
    - taneq 5y ago
      Finding the prior art pays you back the time you’d have spent repeating the same mistakes, though.
nikolay 5y ago
Back in the '80s in Bulgaria, I was only able to find the Bresenham's algorithm for circles, but needed to draw an ellipse (in 6052 assembly, well, machine code), and was so proud that I manage to do it.
- mjcohen 5y ago
  Did it work for any axes?
  - nikolay 5y ago
    As far as I can recall, yeah. By the way, I found this [0] implementation in pseudo code. [0]: https://dai.fmph.uniba.sk/upload/0/01/Ellipse.pdf https://dai.fmph.uniba.sk/upload/0/01/Ellipse.pdf
- Radim 5y ago
  The lessons you learn on your own stick the best, don't they? I remember a similar "heureka" moment when I derived a line-drawing algorithm that respected "subpixel" starting and ending points. That is, don't assume a line starts/ends in the middle of a pixel (like most algos do), but rather at an arbitrary point. I forgot why I needed this (something to do with near-axis-aligned polygon slopes not looking right on a highly rasterized problem). But I do remember the elation when I finally got it to work :-) Also early 1990s, no internet and no English for extra fun.
thealig 5y ago
that was my first reaction on reading the title..that's how retro computers back in the day displayed circles on sparse pixel displays
- jacquesm 5y ago
  And pen based vector plotters.
  - christkv 5y ago
    I loved pen based plotters it was mesmerising to watch them draw.
    - jacquesm 5y ago
      Indeed, but oh those pens were so expensive and woe to you if a pen ever punctured the paper. That could get messy in a hurry. And then of course the printerbuffer would have another 250K worth of plotter commands and good luck getting that to stop.

Beat me to it. And there are several optimizations on top that by, more or less, by reflecting the points as you compute one quadrant of the circle.

gotaquestion 5y ago

This is the era where prior art doesn't exist. Why read a book when you can blog about discovering "something new". I could probably make a killing blogging about my "discovery" of the algorithms in the book "Hacker's Delight".

Mr_P 5y ago
The author titled one of the sections "Midpoint circle algorithm". There happens to be a Wikipedia page on "Midpoint circle algorithm": https://en.wikipedia.org/wiki/Midpoint_circle_algorithm https://en.wikipedia.org/wiki/Midpoint_circle_algorithm The page claims, "Bresenham's circle algorithm is derived from the midpoint circle algorithm." The author of this blog post even made it clear, at the end of their article, that... "many explanations of midpoint algorithm use the final, optimized version. But I added several unoptimized steps." I think there's a lot of value in a blogpost that demonstrates how someone could re-derive a widely-used algorithm from scratch.
taneq 5y ago
This always blows my mind - for the first time in human history we live in a world where almost all prior art is relatively easily discoverable, and people don't even bother. I guess I shouldn't be surprised, after all, I've met a lot of people.
- pjc50 5y ago
  The sheer weight of information can make it harder to find. Also, nobody gets paid for being the prior art.
  - taneq 5y ago
    Finding the prior art pays you back the time you’d have spent repeating the same mistakes, though.

nikolay 5y ago

Back in the '80s in Bulgaria, I was only able to find the Bresenham's algorithm for circles, but needed to draw an ellipse (in 6052 assembly, well, machine code), and was so proud that I manage to do it.

mjcohen 5y ago
Did it work for any axes?
- nikolay 5y ago
  As far as I can recall, yeah. By the way, I found this [0] implementation in pseudo code. [0]: https://dai.fmph.uniba.sk/upload/0/01/Ellipse.pdf https://dai.fmph.uniba.sk/upload/0/01/Ellipse.pdf
Radim 5y ago
The lessons you learn on your own stick the best, don't they? I remember a similar "heureka" moment when I derived a line-drawing algorithm that respected "subpixel" starting and ending points. That is, don't assume a line starts/ends in the middle of a pixel (like most algos do), but rather at an arbitrary point. I forgot why I needed this (something to do with near-axis-aligned polygon slopes not looking right on a highly rasterized problem). But I do remember the elation when I finally got it to work :-) Also early 1990s, no internet and no English for extra fun.

thealig 5y ago

that was my first reaction on reading the title..that's how retro computers back in the day displayed circles on sparse pixel displays

jacquesm 5y ago
And pen based vector plotters.
- christkv 5y ago
  I loved pen based plotters it was mesmerising to watch them draw.
  - jacquesm 5y ago
    Indeed, but oh those pens were so expensive and woe to you if a pen ever punctured the paper. That could get messy in a hurry. And then of course the printerbuffer would have another 250K worth of plotter commands and good luck getting that to stop.