36

Fractals have always been a bit of a mystery for me.

What practical uses (beyond rendering to beautiful images) are there for fractals in the various programming problem domains? And please, don't just list areas that use them. I'm interested in specific algorithms and how fractals are used with those algorithms to solve something in practice. Please at least give a short description of the algorithm.

0

8 Answers 8

24

Absolutely computer graphics. It's not about generating beautiful abstract images, but realistic and not repeating landscapes. Read about Fractal Landscapes.

Perlin Noise, which might be considered a simple fractal is used in computer graphics everywhere. The author joked around that if he would patent it, he'd be a millionare now. Fractals are also used in animation and lossy image compression.

1
11

A Peano curve is a space-filling fractal, which allows you to cover a 2-D area (or higher-dimensional region) uniformly with a 1-D path. If you are doing local operations on a multidimensional array, storing and/or accessing the array data in space-filling curve order can increase your cache coherence, for all levels of cache.

2
  • 1
    A Hilbert curve is another example of this. See my post for a practical implementation: blog.notdot.net/2009/11/… Jan 16, 2010 at 20:12
  • 2
    If I remember rightly, the Sega Dreamcast's 'swizzled' texture format used this to get a higher cache hit rate on their tile-rendering graphics architecture.
    – matja
    Mar 12, 2010 at 9:30
4

Fractal image compression. There are some more applications thought not all in programming here.

3
  • Do you have any specific examples of fractal image compression algorithms that people would be well served to know about?
    – Sami
    Jan 16, 2010 at 19:30
  • I'm afraid not. I was exposed to the algorithms around a decade ago but haven't rally kept up. Jan 17, 2010 at 5:39
  • 1
    That's because fractal image coders simply have not gained traction over transform coders.
    – Steve Tjoa
    Jan 18, 2010 at 6:19
4

Error diffusion along a Hilbert curve.

It's a simple idea - suppose that you convert an image to a 0-1 black & white bitmap. Converting a 55% brightness pixel to white yields a +45% error. Instead of just forgetting it, you keep the 45% to take into account when processing the next pixel. Suppose its value is 80%. Normally it would be converted to white, but a neighboring pixel is too bright, so taking the +45% error into account, you convert it to black (80%-45%=35%), keeping a -35% error to be spread into next pixels.

This way a 75% gray area will have white/black pixel ratio close to 75/25, which is good. But if you process the pixels left-to-right, the error only spreads in one direction, which yields worse looking images. Enter space-filling curves. Processing the pixels along a Hilbert curve gets good locality of the error spread. More here, with pictures.

4

Fractals are used in finance for analyzing the prices of stock. The are also used in the study of complex systems (complexity theory) and in art.

1
  • 2
    You have any specific algorithms in mind where fractals have been shown to be practically useful in analyzing prices of stocks? In the link you gave, the author finishes up by saying that the hurst exponent estimation (what he was doing) seemed to be of little use for analyzing financial time series. How about some examples on what algorithms are used with study of complexity theory for achieving something practical with fractals?
    – Sami
    Jan 16, 2010 at 19:11
1

One can use computer science algorithms to compute the fractal dimension, or Haussdorff dimension of black-and-white images. It is not that difficult to implement.

It turns out that this is used in biology and medicine to analyze cell samples, for example, analyze how aggressive a cancer cell is, or how far a disease have gone. A cell is in general more healthy the higher the dimension is, meaning you wish for low fractal dimension for cancer samples.

2
  • 1
    There is a direct correlation between fractal dimension and complexity (or chaos), which is why it detects cancer -- the branching of the veins and arteries is haphazard in a cancer, chaotic because the cancer grows too fast to grow in an orderly fashion. This was explained in the decent video "NOVA: Fractals - Hunting the Hidden Dimension" May 29, 2022 at 13:55
  • 1
    @MicroservicesOnDDD one probably wants a high fractal dimension for the lung surface as well... in healthy humans, this dimension is close to 3 May 29, 2022 at 16:01
0

Another uses of fractal theory is fractal image interpolation. For example, Perfect Resize 7 is using fractals to resize images with very good quality. They are, most likely, using partition iterated function systems (PIFS), that assume that different parts of an image are self-similar to each other. The algorithm is based on searching of self-similar parts of an image and describing transformation between them.

0

used in image compression, any mobile phone, the antenna chip design is a fractal for maximum surface area, texture generation, mountain generation, understanding trees, cliffs, jellyfish, emulating any natural phenomena where there is a degree of recursion and self similarity at different scales. a lot of scientific applications.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.