Fractal Dimension Computation in Python Code
Andrew Kuchling
akuchlin at mems-exchange.org
Fri Sep 29 16:36:39 CEST 2000
A Google search on "calculating the fractal dimension of a set of
points" turns up lots of pointers. What about a procedure like the
one described at http://hypertextbook.com/chaos/33.shtml?
1) Choose a number of sizes h1, h2, ...
2) for h in h1, h2, ...:
Divide the 2D or 3D region into little boxes of size h.
Count how many boxes contain a data point, and call it N(h)
3) Plot N(h) on a logarithmic scale and measure the slope of the line, which
will be the fractal dimension.
I'm not sure how to make step 2 fast, though. Perhaps you could loop
over each data point, figure out what box it falls in, and scan
through the other points eliminating any that would fall into the same
box. That would be O(n**2) for n data points.
<think think>
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().
--amk
More information about the Python-list
mailing list