Generating a space filling curve in Python
As mentioned in a previous post, I had taken an interest in space filling curves as a method for approaching the traveling salesman problem. Bartholdi (link) presented an algorithm (p. 20) for generating such curves written in Modula-2. In this post, I will show a translation into Python, which was straightforward to implement.
Note there is an excellent Python library for generating different kinds of space filling curves (including Sierpinski and Hilbert), but for now, I will be using the translated Bartholdi code as shown below.
# Calculate Sierpinski Index for a (x,y) pair
# Taken from Appendix A from
#http://www2.isye.gatech.edu/~jjb/research/mow/mow.pdf
# This is a rewrite in Python
def sierp_index(x,y,maxin):
maxInput = maxin
assert x < maxInput +1
assert y < maxInput +1
result = 0
loopIndex = maxInput
if x > y:
result += 1
x = maxInput - x
y = maxInput - y
while loopIndex > 0:
result = result + result
if x + y > maxInput:
result +=1
oldx = x
x = maxInput - y
y = oldx
x = x + x
y = y + y
result = result + result
if y > maxInput:
result += 1
oldx = x
x = y - maxInput
y = maxInput - oldx
loopIndex = int(loopIndex/2)
return result