Fractal Dimension Computation in Python Code
Jake Speed
speed at ?.com
Fri Sep 29 14:02:07 EDT 2000
akuchlin at mems-exchange.org (Andrew Kuchling) wrote in
<3d4s2zxo20.fsf at kronos.cnri.reston.va.us>:
>
>Or, loop over the data point and compute the box coordinates (x,y) for
>each point, storing it (O(n)). Sort the list of (x,y) coordinates
>(O(n lg n)) and then eliminate any duplicates (O(n)); N(h) is the
>number of unique coordinates. O(n lg n) running time. Or just store
>each (x,y) coordinate in a dictionary; N(h) == len(dictionary) when
>it's done. That should be just O(n), one pass to compute (x,y) and
>then a len().
This was so cool, I had to do it!
(apologies if the Koch curve isn't quite correct)
import math
def fractaldim(pointlist, boxlevel):
"""Returns the approximate fractal dimension of pointlist,
via the box-counting algorithm. The elements of pointset
should be three-element sequences of numbers between 0.0
and 1.0. The boxlevel is the number of divisions made on
each dimension, and should be greater than 1."""
if boxlevel <= 1.0: return -1
pointdict = {}
def mapfunction(val, level=boxlevel):
return int(val * level)
for point in pointlist:
box = (int(point[0] * boxlevel),
int(point[1] * boxlevel),
int(point[2] * boxlevel))
#box = tuple(map(mapfunction, point))
if not pointdict.has_key(box):
pointdict[box] = 1
num = len(pointdict.keys())
if num == 0: return -1
return math.log(num) / math.log(boxlevel)
print "line dimension"
list1d = []
for x in xrange(100):
list1d.append((x/100.0, 0, 0))
for level in xrange(1,10):
boxsize = int(2 ** level)
print level, fractaldim(list1d, boxsize)
print "plane dimension"
list2d = []
for x in xrange(100):
for y in xrange(100):
list2d.append((x/100.0, y/100.0, 0))
for level in xrange(1,10):
boxsize = int(2 ** level)
print level, fractaldim(list2d, boxsize)
print "space dimension"
list3d = []
for x in xrange(30):
for y in xrange(30):
for z in xrange(30):
list3d.append((x/30.0, y/30.0, z/30.0))
for level in xrange(1,10):
boxsize = int(2 ** level)
print level, fractaldim(list3d, boxsize)
def makekoch(x1, y1, x2, y2, level, flist=[]):
xd = (x2 - x1)
yd = (y2 - y1)
xa = x1 + xd / 3.0
ya = y1 + yd / 3.0
xb = x1 + xd * 2.0 / 3.0
yb = y1 + yd * 2.0 / 3.0
xm = (x1 + x2) / 2.0 - 0.866 * yd / 3.0
ym = (y1 + y2) / 2.0 + 0.866 * xd / 3.0
flist.append((xa,ya,0))
flist.append((xm,ym,0))
flist.append((xb,yb,0))
if (level > 0):
makekoch(x1, y1, xa, ya, level-1, flist)
makekoch(xa, ya, xm, ym, level-1, flist)
makekoch(xm, ym, xb, yb, level-1, flist)
makekoch(xb, yb, x2, y2, level-1, flist)
return flist
print "koch dimension"
listfract = makekoch(0,0,1,0,6)
for level in xrange(1,10):
boxsize = int(2 ** level)
print level, fractaldim(listfract, boxsize)
More information about the Python-list
mailing list