The integer circle allgorithm can be used to ... generate points on a circle. Here is a simple example:
from math import floor
import matplotlib.pyplot as plt
x = 32
y = 0
factor_a = 1/8
pointlist = []
for i in range(100):
x = x - floor( factor_a * y)
y = y + floor( factor_a * x)
pointlist.append((x, y))
pointlist = set(pointlist)
plt.scatter([point[0] for point in pointlist], [point[1] for point in pointlist])
print(pointlist)
#lets check if our list contains duplicates ....
print(f"set not containing any duplicates: {len(pointlist) = }")
print(f"contains starting position I: {(32, 0) in pointlist = }")
print(f"contains other quadrants II: {(-32, 0) in pointlist = }")
print(f"contains other quadrants III: {(0, 32) in pointlist = }")
print(f"contains other quadrants IV: {(0, -32) in pointlist = }")
{(31, 11), (25, 23), (29, 17), (-7, 30), (-16, 24), (-13, 26), (-4, -26), (24, -16), (-17, -20), (-10, 28), (26, -13), (32, 0), (23, 25), (12, -24), (-23, 15), (-24, -11), (-14, -22), (-26, 4), (0, -26), (8, -25), (0, 32), (28, -10), (-22, -14), (-20, -17), (30, -7), (-4, 31), (15, -23), (-21, 18), (-19, 21), (18, -21), (-25, 8), (30, 14), (14, 30), (-11, -24), (21, -19), (4, -26), (32, 8), (4, 32), (17, 29), (-26, 0), (11, 31), (8, 32), (-24, 12), (-8, -25), (-25, -8), (20, 27), (32, 4), (27, 20), (-26, -4), (31, -4)}
set not containing any duplicates: len(pointlist) = 50
contains starting position I: (32, 0) in pointlist = True
contains other quadrants II: (-32, 0) in pointlist = False
contains other quadrants III: (0, 32) in pointlist = True
contains other quadrants IV: (0, -32) in pointlist = False
Changing the variable factor_a from $\frac{1}{8}$ to $\frac{1}{16}$ in the code above results in points ... on an Octagon.
x = 32
y = 0
pointlist = []
factor_a = 1/16
for i in range(100):
x = x - floor( factor_a * y)
y = y + floor( factor_a * x)
pointlist.append((x, y))
pointlist = set(pointlist)
print(f"pointlist contains {len(pointlist) = } elements")
plt.scatter([point[0] for point in pointlist], [point[1] for point in pointlist])
pointlist contains len(pointlist) = 96 elements
<matplotlib.collections.PathCollection at 0x7f990c46a8b0>
The integer circle algorithm can be parametricied by 4 parameters:
the factors $a$ and 4. $b$ inside the floor call
In the case in the code sample below a = b = $\frac {1}{16}$. By choosing a larger $x_0$ we will get a rounder circle. In this code sample we iterate until we end up at the starting position (x_0, y_0):
x_0 = 128
y_0 = 0
a = b = 1/16
x = x_0
y = y_0
pointlist = set()
while True:
x = x - floor( a * y)
y = y + floor( b * x)
pointlist.add((x, y))
if x == x_0 and y == y_0:
break
pointlist = set(pointlist)
print(f"pointlist contains {len(pointlist) = } elements")
plt.scatter([point[0] for point in pointlist], [point[1] for point in pointlist])
pointlist contains len(pointlist) = 304 elements
<matplotlib.collections.PathCollection at 0x7f990e03ac40>
Now we can get a little bit crazyier with these starting parameters discovererd by Steve Witham:
it takes 17070 steps for x, y to return to its inital position
x_0 = 233
y_0 = 0
a = 1
from math import sin, pi
b = 4 * sin(pi/5)**2
print(f"{b=}")
x = x_0
y = y_0
pointlist = set()
while True:
x = x - floor( a * y)
y = y + floor( b * x)
pointlist.add((x, y))
if x == x_0 and y == y_0:
break
print(f"it took {len(pointlist)} steps for the iteration to complete")
pointlist = set(pointlist)
print(f"pointlist contains {len(pointlist) = } elements")
plt.scatter([point[0] for point in pointlist], [point[1] for point in pointlist], s=1)
b=1.381966011250105 it took 17070 steps for the iteration to complete pointlist contains len(pointlist) = 17070 elements
<matplotlib.collections.PathCollection at 0x7f990c437340>
Having an algorithm with 4 parameters means we have a 4 Dimensional object to explore its convergence behavior. The following function returns how many steps it takes to return to the starting condition.
def integer_circle_algorithm_step_count(param_x0: int, param_y0: int, param_a: float, param_b: float, maxloop=50000)->int:
steps = 0
x = param_x0
y = param_y0
while True:
x = x - floor( param_a * y)
y = y + floor( param_b * x)
steps += 1
if steps > maxloop:
return -100
if x == param_x0 and y == param_y0:
return steps
print(f"{integer_circle_algorithm_step_count(233, 0, 1, 4 * sin(pi/5)**2) = }")
integer_circle_algorithm_step_count(233, 0, 1, 4 * sin(pi/5)**2) = 17070
Now we render some 2D fractals holding 2 parameters constant and varying over the other 2: For know we hold the params $a$ and $b$ constant:
from matplotlib.pyplot import matshow
param_a = 1
param_b = 4 * sin(pi/5)**2
size = 100
fractal_image = [[integer_circle_algorithm_step_count(x, y, param_a, param_b) for x in range(-size, size)] for y in range(-size, size)]
matshow(fractal_image)
<matplotlib.image.AxesImage at 0x7f990c192220>
param_a = 1
param_b = 0.91939
size = 100
fractal_image = [[integer_circle_algorithm_step_count(x, y, param_a, param_b) for x in range(-size, size)] for y in range(-size, size)]
matshow(fractal_image)
<matplotlib.image.AxesImage at 0x7f990c244250>
# ab plot:
x_0 = 1
y_0 = 0
size = 5
fractal_image = [[integer_circle_algorithm_step_count(x_0, y_0, param_a = x, param_b = y, maxloop=20000) for x in range(size)] for y in range(size)]
matshow(fractal_image)
<matplotlib.image.AxesImage at 0x7f9907f634c0>