Summary  Source files  Compilation  Precompiled  Gallery  References
BoxCount
A program for calculating boxcounting estimates to the fractal dimension of curves in the plane. For an extensive description of the algorithms used in the program, supported commandline options and syntax, as well as the full documentation of the source, see boxcount.pdf. [932 kB, 46 pages].
Summary of the program
This CWEB [1] computer program calculates boxcounting estimates of the fractal dimension of curves in the twodimensional plane.
the twodimensional plane. In the boxcounting estimate to the fractal dimension of a curve in the domain {x, y : x_{min} ≤ x ≤ x_{max}, y_{min} ≤ y ≤ y_{max}}, a grid of squares, each of horizontal dimension (x_{max}  x_{min}) / 2^{m} and vertical dimension (y_{max}  y_{min}) / 2^{m}, is superimposed onto the graph for integer numbers m. By counting the total number of such squares N_{m} needed to cover the entire graph at a given m (hence the term »box counting»), an estimate D_{m} to the fractal dimension D (or Hausdorff dimension) is obtained as D_{m} = ln(N_{m})/ln(2^{m}). This procedure may be repeated many times, with D_{m} → D as m→∞ for real fractal sets. However, for finitedepth fractals (as generated by a computer), some limit on m is necessary in order to prevent trivial convergence towards D_{m} → 1.
In addition to mere numerical calculation, the program also generates graphs of the box distributions, in form of MetaPost [2] code which can be postprocessed by other programs.
For simply generating an image of the Koch snowflake fractal, see also an old program of mine for the recursive formulation of the fractal directly in PostScript.
Current revision
Revision 1.6, as of 26/11/2011. Copyright © Fredrik Jonsson 20062011, under GPL
Source files
boxcount.pdf [932 kB] Documentation of the BoxCount program in Portable Document Format (PDF) [3], generated from the PostScript [5] documentation.
boxcount.w [91 kB]
The CWEB [1] master source code for the BoxCount program.
From this master, the ANSIC (ISO C90) source code for the program and TeX
code for the documentation is extracted using the CTANGLE and CWEAVE
compilers, respectively.
[ download 
view source ]
boxcount.tar.gz
[2.66 MB]
Gzip:ed
tape archive of
the entire BoxCount program directory, including the CWEB
[1] master source code source, Makefile:s and all
examples needed to rebuild the program and documentation from scratch.
Requires CTANGLE and
CWEAVE.
[ download ]
Makefile
[3 kB]
The Makefile for compilation of the executable file, as well as generation
of the documentation of the program. Extracts the C and TeX code from the
CWEB source, and compiles the C and TeX code into binary executable and
PostScript, respectively.
To compile the executable and documentation, simply run 'make' in the
directory containing the source files and this Makefile.
[ download 
view source ]
boxcount.c
[24 kB]
ANSIC (ISO C90) conforming source code, extracted from the CWEB master
source code using the CTANGLE program by Donald E. Knuth.
[ download 
view source ]
boxcount.tex
[112 kB]
Plain TeX [4] source code, extracted from the CWEB master
source code using the CWEAVE program by Donald E. Knuth.
[ download 
view source ]
boxcount.ps [16.53 MB] PostScript [5] documentation of the BoxCount program, generated from the TeXcode, which in turn is generated from the CWEB master source code.
Source for the Koch snowflake data set generator
koch.c [2 kB]
ANSIC (ISO C90) conforming source code for the generator of the data sets
used as test objects for the BoxCount program.
[ download 
view source ]
Makefile
[2 kB]
The corresponding Makefile for compilation of koch.c.
[ download 
view source ]
Compilation
Compile the CWEB [1] code 'boxcount.w' using the enclosed Makefile, or use the blocks of the Makefile as listed in the documentation.
The BoxCount program is written in CWEB [1], generating ANSIC (ISO 9899/C90) conforming source code and documentation as plain TeX [4] source, and is to be compiled using the sequences as outlined in the enclosed Makefile. The Makefile essentially executes two major calls. First, the CTANGLE program parses the CWEB source document 'boxcount.w' to extract a ANSIC source file 'boxcount.c', which may be compiled in the usual way using any ANSIC conformant compiler. The output source file includes #line specifications so that any debugging can be done conveniently in terms of the original CWEB source file. Second, the CWEAVE program parses the same CWEB source file to extract a plain TeX source file 'boxcount.tex' which may be compiled in the usual way. It takes appropriate care of typographic details like page layout and the use of indentation, italics, boldface, and so on, and it supplies extensive automatically gathered crossindex information.
After having executed make in the same catalogue where the files boxcount.w and Makefile are located, one is left with an executable file boxcount, being the readytouse compiled program, and a PostScript file boxcount.ps [5] which contains the full documentation of the program. Notice that on platforms running Windows NT, Windows 2000, Windows ME, or any other operating system by Microsoft, the executable file will instead automatically be called boxcount.exe. This convention also applies to programs compiled under the UNIXlike environment CYGWIN.
Precompiled executables
boxcount [31 kB] Executable program compiled for Mac OS X 10.7 (Intel) using the GNU C Compiler (GCC).
Example gallery
The Koch snowflake is one of the earliest described fractal curves, appearing in the 1904 article Sur une courbe continue sans tangente, obtenue par une construction géeométrique élémentaire, written by the Swedish mathematician Helge von Koch (18701924). In this application example, we employ the »snowflake» variant of the Koch fractal (merely for the sake of its beauty). The Koch snowflake fractal is constructed recursively using the following algorithm.
Algorithm A (Construction of the Koch snowflake fractal).
 A1. [Create initiator.] Draw three line segments of equal length so that they form an equilateral triangle.
 A2. [Line division.] Divide each of the line segments into three segments of equal length.
 A3. [Replace mid segment by triangle.] Draw an equilateral triangle that has the middle segment from step one as its base.
 A4. [Remove base of triangle.] Remove the line segment that is the base of the triangle from step A3.
 A5. [Recursion step.] For each of the line segments remaining, repeat steps A2 through A4.
The triangle resulting after step A1 is denoted as the initiator of the fractal. After the first iteration of steps A1A4, the result should be a shape similar to the Star of David; this is called the generator of the fractal. The Koch fractal resulting of the infinite iteration of the algorithm of construction has an infinite length, since each time the steps above are performed on each line segment of the figure there are four times as many line segments, the length of each being onethird the length of the segments in the previous stage. Hence, the total length of the perimeter of the fractal increases by 4/3 at each step, and for an initiator of total length L the total length of the perimeter at the nth step of iteration will be (4/3)^{nL}. The fractal dimension is hence D = ln(4)/ln(3)≈1.26, being greater than the dimension of a line (D = 1) but less than, for example, Peano's spacefilling curve (D = 2). The Koch fractal is an example of a curve which is continuous, but not differentiable anywhere. The area of the Koch snowflake is 8/5 that of the initial triangle, so an infinite perimeter encloses a finite area. The stepwise construction of the snowflake fractal is illustrated in Fig. 1.
Figure 1.
Construction of the Koch fractal of the »snowflake» type,
in this case as inscribed in the unitary circle. For this case, the length
of the initiator is L = 3×3^{1/2} while its
area is
A = L²/(6×3^{1/2}) = 3×3^{1/2}/2. For each fractal recursion depth n, the
trajectory consists of a total of 3×4^{(n1)}
connected linear segments.
The data set for the Koch fractal is straightforward to generate by means of recursion, as for example by using the following compact C program [ download  2 kB]:
/*
 File: koch.c [ANSIC conforming source code]
 Created: May 8, 2006, Fredrik Jonsson <fj@phys.soton.ac.uk>
 Last modified: May 8, 2006, Fredrik Jonsson <fj@phys.soton.ac.uk>
 Description:
 The KOCH program creates data sets corresponding to the Koch fractal,
 for the purpose of acting as test objects for the program BOXCOUNT,
 which calculates boxcounting estimates to the fractal dimension.
 The program is simply executed by 'koch <N>', where <N> is an integer
 describing the maximum depth of recursion that is to be used in the
 generation of the data set for the fractal. If invoked without any
 arguments present at the command line, a default value of <N>=6 is
 assumed. The generated data stream is sent to standard terminal output,
 easy to pipe into files (as suitable for the BOXCOUNT program) or as
 feeds to other programs of data analysis.

 Compile with: gcc O2 g Wall pedantic ansi koch.c o koch lm

 Copyright (C) 2006 Fredrik Jonsson <fj@phys.soton.ac.uk>
=============================================================================*/
#include <math.h>
#include <stdio.h>
extern char *optarg;
void kochsegment(double xa,double ya,double xb,double yb,
int depth,int maxdepth) {
double xca,yca,xcb,ycb,xcc,ycc;
if (depth==maxdepth) {
fprintf(stdout,"%2.8f %2.8f\n",xb,yb);
} else {
xca=xa+(xbxa)/3.0;
yca=ya+(ybya)/3.0;
xcb=xb(xbxa)/3.0;
ycb=yb(ybya)/3.0;
xcc=(xa+xb)/2.0(ybya)/(2.0*sqrt(3.0));
ycc=(ya+yb)/2.0+(xbxa)/(2.0*sqrt(3.0));
kochsegment(xa,ya,xca,yca,depth+1,maxdepth);
kochsegment(xca,yca,xcc,ycc,depth+1,maxdepth);
kochsegment(xcc,ycc,xcb,ycb,depth+1,maxdepth);
kochsegment(xcb,ycb,xb,yb,depth+1,maxdepth);
}
}
int main(int argc, char *argv[]) {
int maxdepth=6;
if (argc>1) sscanf(argv[1],"%d",&maxdepth);
if (maxdepth>0) {
fprintf(stdout,"%2.8f %2.8f\n",0.0,1.0);
kochsegment(0.0,1.0,sqrt(3.0)/2.0,0.5,1,maxdepth);
kochsegment(sqrt(3.0)/2.0,0.5,sqrt(3.0)/2.0,0.5,1,maxdepth);
kochsegment(sqrt(3.0)/2.0,0.5,0.0,1.0,1,maxdepth);
}
return(0);
}
The boxcounting dimension of the Koch snowflake fractal can now be investigated
with assistance of the BoxCount program. In the analysis as here presented,
this is done using the following Makefile
[ download  2 kB ]:
#
# Makefile designed for use with gcc, MetaPost and plain TeX.
#
# Copyright (C) 20022006, Fredrik Jonsson <fj@phys.soton.ac.uk>
#
CC = gcc
CCOPTS = O2 Wall ansi std=iso9899:1990 pedantic
LNOPTS = lm
TEX = tex
DVIPS = dvips
METAPOST = mpost
#
# Define path and executable file for the BOXCOUNT program, used
# for calculating estimates of the boxcounting fractal dimension
# of a trajectory in the plane.
#
BOXCOUNTPATH = ../
BOXCOUNT = $(BOXCOUNTPATH)/boxcount
#
# Define path and executable file for the KOCH program, used for
# generating the trajectory of the Koch snowflake fractal.
#
KOCHPATH = ../koch/
KOCH = $(KOCHPATH)/koch
all: koch kochgen kochtab
koch:
make C ../koch/
kochgen:
$(KOCH) 7 > koch.trj
$(BOXCOUNT) verbose boxmaps graphsize 42.0 42.0 \
computationwindow llx 1.1 lly 1.1 urx 1.1 ury 1.1 \
minlevel 3 maxlevel 8 \
trajectoryfile koch.trj outputfile overwrite koch
for k in 03 04 05 06 07 08; do \
$(METAPOST) koch.$$k.mp ;\
$(TEX) jobname=koch.$$k '\input epsf\nopagenumbers\
\centerline{\epsfxsize=120mm\epsfbox{koch.'$$k'.1}}\bye';\
$(DVIPS) D1200 E koch.$$k o koch.$$k.eps;\
done
kochtab:
$(KOCH) 7 > koch.trj
$(BOXCOUNT) verbose minlevel 3 maxlevel 14 \
computationwindow llx 1.1 lly 1.1 urx 1.1 ury 1.1 \
trajectoryfile koch.trj outputfile overwrite koch
clean:
rm Rf koch *~ *.o *.exe *.dat *.mp *.mpx *.trj
rm Rf *.tex *.aux *.log *.toc *.idx *.scn *.dvi *.1 *.eps
Having executed the Makefile as displayed above, where a recursion depth of n = 7 is used for the generation of the Koch fractal, we are left with a set of images of the consecutively refined grids in the boxcounting algorithm, and a table containing the estimates of the boxcounting dimension of the Koch snowflake fractal. In Fig. 2, the resulting maps of the boxes used in the boxcounting algorithm for refinement levels m = 3, 4, …, 8 are shown, and as the grid refinement is finer and finer, the boxes finally will be barely visible in the limited resolution of computer graphics, on screen as well as in the generated Encapsulated PostScript code.
Figure 2. Consecutive steps of refinement m = 3, 4, . . . ,8 of the grid of boxes covering the input trajectory, in this case a Koch snowflake fractal of recursion depth n = 7 (see Fig. 1). At each step m of refinement, a virtual grid of 2^{m} × 2^{m} boxes is superimposed on the trajectory (fractal) and the number N_{m} of boxes covering the trajectory are counted. For the Koch snowflake fractal of recursion depth n = 7, the trajectory consists of a total of 3 × 4^{(71)} = 12288 connected linear segments.
The estimated boxcounting dimension D_{m} = ln(N_{m})/ln(2^{m}), with N_{m} as previously denoting the number of boxes in a 2^{m}×2^{m}grid required to cover the entire curve, is displayed in Table A.1. The values for the estimates could be compared with the analytically obtained value of D = ln(4)/ln(3) ≈ 1.26 for the fractal dimension. However, it should be emphasized that the box counting dimension here just is an estimate of one definition of the fractal dimension, which in many cases do not equal to other measures, and that we in the computation of the estimate always will arrive at a truncated result due to a limited precision and a limited amount of memory resources and computational time. As can be seen in the table, the initial estimates at lower resolutions are pretty crude, but in the final estimate we nevertheless end up with the box counting estimate of the fractal dimension as 1.29, which is reasonably close to the analytically obtained value of D ≈ 1.26. Of course, further refinements such as Richardson extrapolation could be applied to increase the accuracy, but this is outside of the scope of the BoxCount program, which only serves to provide the raw, basic algorithm of boxcounting. For discussions on different definitions of the fractal dimension, see the English Wikipedia section on the MinkowskiBouligand dimension, at http://en.wikipedia.org/wiki/MinkowskiBouligand_dimension.
Table A.1 Boxcounting estimates of the fractal dimension of the Koch snowflake fractal of recursion order n = 7. In the table, m is the refinement order as indicated in the graphs in Fig. 2, N_{m} is the number of covering boxes counted at refinement level m, and D_{m} = ln(N_{m})/ln(2^{m}) is the estimate of the boxcounting dimension.
m  N_{m}  D_{m} = ln(N_{m})/ln(2^{m}) 
3  44  1.8198 
4  96  1.6462 
5  196  1.5229 
6  504  1.4962 
7  1180  1.4578 
8  2856  1.4350 
9  6844  1.4156 
10  15620  1.3931 
11  32320  1.3618 
12  66200  1.3345 
13  133600  1.3098 
14  268804  1.2883 
References
[1] For information on the CWEB programming language as written by Donald E. Knuth, as well as samples of CWEB programs, see Knuth's homepage at http://wwwcsfaculty.stanford.edu/~knuth/cweb.html For information on literate programming, as well as additional CWEB examples, see http://www.literateprogramming.com
[2] MetaPost is both a programming language and the only known interpreter of the MetaPost programming language. Both are derived from Donald E. Knuth's Metafont language and interpreter. The language shares Metafont's elegant declarative syntax for manipulating lines, curves, points and geometric transformations [Wikipedia]. The originator of MetaPost, John Hobby, has a page on the MetaPost language at http://cm.belllabs.com/who/hobby/MetaPost.html. The TeX Users Group (TUG) has tutorials and links to MetaPost resources listed at http://www.tug.org/metapost.html.
[3] For information on the Portable Document Format (PDF) of Adobe, see for example the homepage of Adobe Systems Inc., at http://www.adobe.com/products/acrobat/
[4] For information on the TeX typesetting system, as well as on the dvips program, see for example the website of the TeX Users Group, at http://www.tug.org
[5] For information on the PostScript programming language, see for example the PostScript area on the website of Adobe Systems Inc., at http://www.adobe.com/products/postscript/ or the reference book "PostScript Language  Tutorial and Cookbook" (AdisonWesley, Reading, Massachusetts, 1985), ISBN 0201101793.