Sök:

Summary | Source files | Compilation | Precompiled | Gallery | References

BoxCount

A program for calculating box-counting estimates to the fractal dimension of curves in the plane. For an extensive description of the algorithms used in the program, supported command-line options and syntax, as well as the full documentation of the source, see boxcount.pdf. [932 kB, 46 pages].

fig0

Summary of the program

This CWEB [1] computer program calculates box-counting estimates of the fractal dimension of curves in the two-dimensional plane.

the two-dimensional plane. In the box-counting estimate to the fractal dimension of a curve in the domain {xy : xmin ≤ x ≤ xmaxymin ≤ y ≤ ymax}, a grid of squares, each of horizontal dimension (xmax - xmin) / 2m and vertical dimension (ymax - ymin) / 2m, is superimposed onto the graph for integer numbers m. By counting the total number of such squares Nm needed to cover the entire graph at a given m (hence the term »box counting»), an estimate Dm to the fractal dimension D (or Hausdorff dimension) is obtained as Dm = ln(Nm)/ln(2m). This procedure may be repeated many times, with Dm → D as m→∞ for real fractal sets. However, for finite-depth fractals (as generated by a computer), some limit on m is necessary in order to prevent trivial convergence towards Dm → 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 post-processed 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 2006-2011, 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 ANSI-C (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] ANSI-C (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 TeX-code, which in turn is generated from the CWEB master source code.

Source for the Koch snowflake data set generator

koch.c [2 kB] ANSI-C (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 ANSI-C (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 ANSI-C source file 'boxcount.c', which may be compiled in the usual way using any ANSI-C 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 cross-index 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 ready-to-use 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 UNIX-like environment CYGWIN.

Precompiled executables

boxcount [31 kB] Executable program compiled for Mac OS X 10.7 (Intel) using the GNU C Compiler (GCC).

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 (1870-1924). 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).

The triangle resulting after step A1 is denoted as the initiator of the fractal. After the first iteration of steps A1-A4, 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 one-third 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 space-filling 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.

fig1a fig1b fig1c fig1d fig1e fig1f
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×31/2 while its area is A = L²/(6×31/2) = 3×31/2/2. For each fractal recursion depth n, the trajectory consists of a total of 3×4(n-1) 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]:



Deprecated: Function split() is deprecated in /storage/content/45/2011745/jonsson.eu/public_html/php/htmlicise.php on line 46
/*-----------------------------------------------------------------------------
| File: koch.c [ANSI-C 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 box-counting 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+(xb-xa)/3.0;
      yca=ya+(yb-ya)/3.0;
      xcb=xb-(xb-xa)/3.0;
      ycb=yb-(yb-ya)/3.0;
      xcc=(xa+xb)/2.0-(yb-ya)/(2.0*sqrt(3.0));
      ycc=(ya+yb)/2.0+(xb-xa)/(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) 2002-2006, 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 box-counting 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.

fig2a fig2b fig2c fig2d fig2e fig2f

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 2m × 2m boxes is superimposed on the trajectory (fractal) and the number Nm 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(7-1) = 12288 connected linear segments.

The estimated boxcounting dimension Dm = ln(Nm)/ln(2m), with Nm as previously denoting the number of boxes in a 2m×2m-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 Minkowski-Bouligand dimension, at http://en.wikipedia.org/wiki/Minkowski-Bouligand_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, Nm is the number of covering boxes counted at refinement level m, and Dm = ln(Nm)/ln(2m) is the estimate of the boxcounting dimension.

mNmDm = ln(Nm)/ln(2m)
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://www-cs-faculty.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.bell-labs.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" (Adison-Wesley, Reading, Massachusetts, 1985), ISBN 0-201-10179-3.

Tillbaka till föregående sida

Lämna ett meddelande

Ditt namn:

Din epost-adress: (obligatorisk)

Meddelande:

Generated by ::emailform::

Senast modifierad Saturday 10 Dec 2011
Denna sajt är XHTML 1.0 Strict