#!/usr/bin/env python3
from math import floor, isqrt, sqrt
from lib import draw_circle, mirror_points_4, mirror_points_8
def get_circle_points_naive_4(r):
""" Draw a circle by pairing up each Y value with an X value that lie on a
circle with radius 'r'. This has a bug because some Y values get skipped.
Can you see why?
"""
points = []
for x in range(r + 1):
# isqrt() gets the integer square root.
y = isqrt((r * r) - (x * x))
points.extend(mirror_points_4(x, y))
return points
def get_circle_points_naive_8(r):
""" Better than get_circle_points_naive_4, but wastes CPU cycles because
the 8-way symmetry overcorrects and we draw some pixels more than once.
"""
points = []
for x in range(r + 1):
y = isqrt((r * r) - (x * x))
points.extend(mirror_points_8(x, y))
return points
def get_circle_points_naive_8_faster(r):
""" Slightly faster than get_circle_points_naive_8, because of the break
condition at the middle of the arc. However this is still inefficient due
to the square root calculation with `isqrt()`.
"""
points = []
for x in range(r + 1):
y = isqrt((r * r) - (x * x))
# When we cross the middle of the arc, stop, because we're already
# invoking 8-way symmetry.
if x > y:
break
points.extend(mirror_points_8(x, y))
return points
def get_circle_points_naive_8_faster_tweaked_radius(r):
""" This is much closer to Bresenham's algorithm aesthetically, by simply
using 'r + 0.5' for the square root calculation instead of 'r' directly.
"""
points = []
# In the square root calculation, we just use (r + 0.5) instead of just r.
# This is more pleasing to the eye and makes the lines a bit smoother.
r_tweaked = r + 0.5
for x in range(r + 1):
y = sqrt((r_tweaked * r_tweaked) - (x * x))
if x > y:
break
points.extend(mirror_points_8(x, floor(y)))
return points
if __name__ == "__main__":
draw_circle(get_circle_points_naive_4, 17)
# 11111111 11111111
# 76543210987654321012345678901234567
# ╭───────────────────────────────────╮
# 17│·················█·················│17
# 16│············█████·█████············│16
# 15│·········███···········███·········│15
# 14│········█·················█········│14
# 13│·······█···················█·······│13
# 12│·····██·····················██·····│12
# 11│···································│11
# 10│····█·························█····│10
# 9│···█···························█···│9
# 8│··█·····························█··│8
# 7│···································│7
# 6│···································│6
# 5│·█·······························█·│5
# 4│···································│4
# 3│···································│3
# 2│···································│2
# 1│···································│1
# 0│█················+················█│0
# 1│···································│1
# 2│···································│2
# 3│···································│3
# 4│···································│4
# 5│·█·······························█·│5
# 6│···································│6
# 7│···································│7
# 8│··█·····························█··│8
# 9│···█···························█···│9
# 10│····█·························█····│10
# 11│···································│11
# 12│·····██·····················██·····│12
# 13│·······█···················█·······│13
# 14│········█·················█········│14
# 15│·········███···········███·········│15
# 16│············█████·█████············│16
# 17│·················█·················│17
# ╰───────────────────────────────────╯
# 11111111987654321012345678911111111
# 76543210 01234567
# Signature: b6f7a9ebafd39870c7cf16be29208ad3
# These two draw the same circle.
draw_circle(get_circle_points_naive_8, 17)
draw_circle(get_circle_points_naive_8_faster, 17)
# 11111111 11111111
# 76543210987654321012345678901234567
# ╭───────────────────────────────────╮
# 17│·················█·················│17
# 16│············█████·█████············│16
# 15│·········███···········███·········│15
# 14│········█·················█········│14
# 13│·······█···················█·······│13
# 12│·····██·····················██·····│12
# 11│·····█·······················█·····│11
# 10│····█·························█····│10
# 9│···█···························█···│9
# 8│··█·····························█··│8
# 7│··█·····························█··│7
# 6│··█·····························█··│6
# 5│·█·······························█·│5
# 4│·█·······························█·│4
# 3│·█·······························█·│3
# 2│·█·······························█·│2
# 1│·█·······························█·│1
# 0│█················+················█│0
# 1│·█·······························█·│1
# 2│·█·······························█·│2
# 3│·█·······························█·│3
# 4│·█·······························█·│4
# 5│·█·······························█·│5
# 6│··█·····························█··│6
# 7│··█·····························█··│7
# 8│··█·····························█··│8
# 9│···█···························█···│9
# 10│····█·························█····│10
# 11│·····█·······················█·····│11
# 12│·····██·····················██·····│12
# 13│·······█···················█·······│13
# 14│········█·················█········│14
# 15│·········███···········███·········│15
# 16│············█████·█████············│16
# 17│·················█·················│17
# ╰───────────────────────────────────╯
# 11111111987654321012345678911111111
# 76543210 01234567
# Signature: f6c20c82b8bcef31fc4b43dd42316140
# Some edge-cases.
draw_circle(get_circle_points_naive_8_faster, 0)
# 0
# ╭─╮
# 0│█│0
# ╰─╯
# 0
# Signature: 4ba6b15b13cd6adb310eeab8ee1adfd0
draw_circle(get_circle_points_naive_8_faster, 1)
# 101
# ╭───╮
# 1│·█·│1
# 0│█+█│0
# 1│·█·│1
# ╰───╯
# 101
# Signature: 625c57cb30c48aeb33b48bebea893e83
draw_circle(get_circle_points_naive_8_faster, 2)
# 21012
# ╭─────╮
# 2│··█··│2
# 1│·█·█·│1
# 0│█·+·█│0
# 1│·█·█·│1
# 2│··█··│2
# ╰─────╯
# 21012
# Signature: ed32e3d382baa7d5014bd00caa17c708
draw_circle(get_circle_points_naive_8_faster, 3)
# 3210123
# ╭───────╮
# 3│···█···│3
# 2│·██·██·│2
# 1│·█···█·│1
# 0│█··+··█│0
# 1│·█···█·│1
# 2│·██·██·│2
# 3│···█···│3
# ╰───────╯
# 3210123
# Signature: 53f14d3462c32d694aa688d8685b50d7
draw_circle(get_circle_points_naive_8_faster_tweaked_radius, 0)
# 0
# ╭─╮
# 0│█│0
# ╰─╯
# 0
#
# Signature: 4ba6b15b13cd6adb310eeab8ee1adfd0
draw_circle(get_circle_points_naive_8_faster_tweaked_radius, 1)
#
# 101
# ╭───╮
# 1│███│1
# 0│█+█│0
# 1│███│1
# ╰───╯
# 101
#
# Signature: 879ffc6eb52acdea4996c531bb3e2663
draw_circle(get_circle_points_naive_8_faster_tweaked_radius, 2)
# 21012
# ╭─────╮
# 2│·███·│2
# 1│█···█│1
# 0│█·+·█│0
# 1│█···█│1
# 2│·███·│2
# ╰─────╯
# 21012
#
# Signature: e6539d664b9120b376d1d4cda8574b6d
draw_circle(get_circle_points_naive_8_faster_tweaked_radius, 3)
# 3210123
# ╭───────╮
# 3│··███··│3
# 2│·█···█·│2
# 1│█·····█│1
# 0│█··+··█│0
# 1│█·····█│1
# 2│·█···█·│2
# 3│··███··│3
# ╰───────╯
# 3210123
#
# Signature: 463d7ac7210badfbb18c47a313cd16aa
draw_circle(get_circle_points_naive_8_faster_tweaked_radius, 17)
# 11111111 11111111
# 76543210987654321012345678901234567
# ╭───────────────────────────────────╮
# 17│·············█████████·············│17
# 16│··········███·········███··········│16
# 15│········██···············██········│15
# 14│·······█···················█·······│14
# 13│······█·····················█······│13
# 12│·····█·······················█·····│12
# 11│····█·························█····│11
# 10│···█···························█···│10
# 9│··█·····························█··│9
# 8│··█·····························█··│8
# 7│·█·······························█·│7
# 6│·█·······························█·│6
# 5│·█·······························█·│5
# 4│█·································█│4
# 3│█·································█│3
# 2│█·································█│2
# 1│█·································█│1
# 0│█················+················█│0
# 1│█·································█│1
# 2│█·································█│2
# 3│█·································█│3
# 4│█·································█│4
# 5│·█·······························█·│5
# 6│·█·······························█·│6
# 7│·█·······························█·│7
# 8│··█·····························█··│8
# 9│··█·····························█··│9
# 10│···█···························█···│10
# 11│····█·························█····│11
# 12│·····█·······················█·····│12
# 13│······█·····················█······│13
# 14│·······█···················█·······│14
# 15│········██···············██········│15
# 16│··········███·········███··········│16
# 17│·············█████████·············│17
# ╰───────────────────────────────────╯
# 11111111987654321012345678911111111
# 76543210 01234567
#
# Signature: c9f411704292f582ed3085695ac47d31