Feeds:
Posts
Comments

Posts Tagged ‘Fractals’

While searching for some methods for face representation in connection with my recent project, I lost the way clicking on some stray links and landed up on some beautiful art work involving Voronoi diagrams. I was aware of art work based on Voronoi diagrams (it kind of follows naturally that Voronoi diagrams can lead to very elegant designs, isn’t it?) but a couple of images on them were enough to re-ignite interest. It was also interesting to see an alternate solution to my problem based on Voronoi diagrams as well. However I intend to share some of the art work I came across.

———-

Before I get to the actual art-work I suppose it would be handy to give a very basic introduction to Voronoi Diagrams with a couple of handy applications.

Introduction: Voronoi diagrams are named after Georgy Voronoy (1868-1908), an eminent Russian/Ukrainian mathematician. A number of mathematicians before Voronoy such as Descartes and Dirichlet have been known to have used them, Voronoy extended the idea to \mathcal{N} dimensions. The Voronoi diagram is a tessellation, or a tiling. A tiling of a plane is simply a collection of plane figures that fills the plane with no overlaps and no gaps in between. This idea can ofcourse be extended to \mathcal{N} dimensions, but for simplicity let us stick with 2 dimensions.

tessellation

[A pavement Tessellation/Tiling]

Definition: A Voronoi diagram is a special kind of a decomposition of a metric space which is determined by a discrete set of points.

Generally speaking for a 2-D case:

>> Let us designate a set of n distinct points that we call sites as \mathcal{P}. i.e \mathcal{P}=\{P_1, P_2\ldots, P_n\}

>> We may then define the Voronoi Diagram of P as a collection \mathcal{V}=\{V_1,V_2,\ldots, V_n\} of subsets of the plane. These subsets are called as Voronoi Regions. Each point in V_i is such that it is closer to \mathcal{P}_i than any other point in \mathcal{P}.

To be more precise:

A point Q lies in the Voronoi Region corresponding to a site P_i \in \mathcal{P} if and only if –

Euclidean\_Distance(Q,P_i) < Euclidean\_Distance(Q,P_j) for each P_i \neq P_j

However it might be the case that there are some points in the plane that might have more than one site that is the closest to it. These points do not lie in either Voronoi Region, but simply lie on the boundary of two adjacent regions. All such points form a skeleton of lines that is called the Voronoi Skeleton of \mathcal{P}.

We can say that \mathcal{V(P)} is the Voronoi Transform, that transforms a set of discrete points (sites) into a Voronoi Diagram.

———-

For more clarity on the above, consider a sample Voronoi Diagram below:

sample_voronoi_diagram

The dots are called the Sites. The Voronoi Regions are simply areas around a site but enclosed by the lines around them. The network of lines is simply the Voronoi Skeleton.

———-

Some Extensions to the above Definition: The above definition which is ofcourse extremely simple can be extended very easily[1] for getting some fun art forms.

Some of these extensions could be as follows [1]:

1. Since each region corresponds to a site, each site can be associated with a color. Hence the Voronoi diagram can be colored accordingly.

2. In the definition the sites were considered to be simply points, we can obtain a variety of figures by allowing the “sites” to be subsets of the plane than just points. We see, that if the sites are defined as simply points, the Voronoi skeleton would always be composed of straight lines. With this change there could be interesting skeletal figures emerging.

3. We could also modify the distance metric from the Euclidean distance to some other to get some very interesting figures.

This just shows the kind of variety of figures that can be generated by just a small change in one aspect of the basic definition.

———-

Constructing a Voronoi Diagram:

Let us forget the extensions that we spoke of for a moment and come back to the basic definition. Looking at the definition it  seems constructing Voronoi diagrams is a simple process. And it is not difficult at all. The steps are as follows:

1. Consider a random set of points.

2. Connect ALL of these points by straight lines.

3. Draw a perpendicular bisector to EACH of these connecting lines.

4. Now select pieces that are formed, such that each site (point) is encapsulated.

Voronoi Diagrams can be very easily made by direct commands in both MATLAB and MATHEMATICA.

———-

Voronoi Diagrams in Nature: It is interesting to see how often Voronoi diagrams occur in nature. Just consider two examples:

reticulum1

gir

[Left: Reticulum Plasmatique (Image Source) Right: Polygons on Giraffes]

———-

Uses of Voronoi Diagrams: There are a wide variety of applications of Voronoi diagrams. They are more important then what one might come to believe. Some of the applications are as follows:

1. Nearest Neighbour Search: This is the most obvious application of Voronoi Diagrams.

2. Facility Location: The example that is often quoted in this case is the example of choosing where to place a new Antenna in case of cellular mobile systems and similarly deciding the location of a new McDonalds given a number of them already exist in the city.

3. Path Planning: Suppose one models the sites as obstacles, then they can be used to determine the best path (a path that stays at a maximum distance from all obstacles or sites).

There are a number of other applications, such as in Geophysics, Metrology, Computer Graphics, Epidemiology and even pattern recognition. A very good example that illustrates how they can be used was the analysis of the Cholera epidemic in London in 1854, in which physician John Snow determined a very strong correlation of deaths with proximity to a particular infected pump (specific example from Wolfram Mathworld).

Let’s consider the specific example of path planning [2]. Consider a robot placed in one corner of a room with stuff dispersed around.

image0042

[Illustration Source]

Now the best path from the point where the robot is located to the goal would be the one in which the robot is farthest from the nearest obstacle at any point in time. To find such a path, the Voronoi diagram of the room would be required to be found out. Once it is done, the vertices or the skeleton of the Voronoi Diagram provides the best path. Which path ultimately is to be taken can be found out by comparing the various options (alternative paths) by using search algorithms.

image0061

[Illustration Source]

Now finally after the background on Voronoi Diagrams let’s look at some cool artwork that i came across. ;-)

———-

Fractals from Voronoi Diagrams:

This I came across on the page of Kim Sherriff[3]. The idea is straightforward to say the least.

It is: To create a fractal, first create a Voronoi diagram from some points, next add more points and then create the Voronoi diagrams inside individual Voronoi Regions. Some sample progression could be like this:

vor1

[Image Source]

Repeating the above process recursively on the above would give the following Voronoi fractal.

vor2

[Image Source]

Interestingly, this fractal looks like the structure of a leaf.

The above was repeated in color by Frederik Vanhoutte[4] to get some spectacular results. Also I would highly recommend his blog!

voronoi-fractal

[Voronoi Fractal – Image Source]

I am really going to try this myself, it seems a few hours of work at first sight. Ofcourse I won’t use the code that the author has provided. ;-)

———-

Mosaic Images Using Voronoi Diagrams[5] :

I have not had the time to read this paper. However, I am always attracted by mosaics, and these ones (the ones in the paper) as created using Voronoi Diagrams have an increased coolness quotient for me. Sample this image:

butterfly_mosaic

[Image Source]

Golan Levin’s[6] experiments in using Voronoi diagrams to obtain aesthetic forms yielded probably even more pleasant results. The ones below give a very delicate look to their subjects.

child

[Image Source]

The tilings that are produced by just mild tweaks to the basic definition of a Voronoi Diagram for a 2-D case that I had talked about earlier can give rise to a variety of tilings. Say like the one below:

kaplan_voronoi[Image Source]

Also, today I came across a nice Voronoi Diagram on The Reference Frame:

The diagram is a representation of 17,168 weather stations around the world. Dr Motl illustrates how handy MATHEMATICA is for such things.

voronoi-weatherdata-screenshot1

Click to Enlarge

———-

References:

[1] Craig Kaplan, Voronoi Diagrams and Ornamental Design.

[2] Introduction to Voronoi Diagrams – Example.

[3] Kim Sherriff, “Fractals from Voronoi Diagrams“.

[4] Frederik Vanhoutte, “Voronoi Fractal“.

[5] A Method for creating Mosiac Images using Voronoi Diagrams.

[6] Golan Levin, “Segmentation and Symptom

———-

Applets:

1. Voronoi Diagram Applet.

2. Bubble Harp.

———-

Additional Links:

1. Image Stained Glass using Voronoi Diagrams.

2. Interactive Design of Authentic Looking Mosaics using Voronoi Diagrams.

3. Voronoi Diagrams of Music.

———-

Onionesque Reality Home >>

Read Full Post »

Following a discussion on Reasonable Deviations. I was prompted to write on this.

512px-sierpinski_triangle_evolutionsvg.png

The above is an illustration on the generation of the Sierpinski Gasket. For simplicity we assume that the area of the initial triangle is 1. We split this triangle into four triangles by joining the mid-points of the sides of the triangle. These smaller triangles as shown in figure 2 have equal areas. We then remove the middle triangle. We adopt the convention that we will only remove the middle triangle and not a triangle at the edge.

In each of the three remaining triangles we repeat the process and remove the middle triangles. This is where self-symmetry comes in. If we pretend to see only one of the three small triangles then we are actually doing the same thing as we did to the original triangle. Albeit on a smaller scale. The above figure shows the third and fourth iterates of the original triangle. This process repeated ad infinitum gives rise to the Sierpinski gasket.

The L-System representation of the process is:

variables : A B

constants : + −

start : A

rules : (A → B−A−B),(B → A+B+A)

angle : 60°

Anyway, now what is interesting about this figure is its area and the perimeter.

Continuing with our earlier assumption, suppose the initial triangle had an area

A0= 1;

Now in the first iteration we remove one of the four equal areas in that triangle and keeping the other three that remain.

Therefore the total area of the first iterate will be equal to

A1 = (3/4) x 1;

Similarly in the second iteration, we repeat the process as I have already noted above. Thus,

A2 = (3/4)(3/4) x 1;

For n iterations the area will be given by:

An = (3/4)n x 1;

Now if n is arbitrarily large then the area, it would follow will be ZERO.

Now finding out the perimeter is a similar exercise. The length of the boundary of the nth iterate of the original triangle is the total length of the boundaries of all the shaded small triangles in the nth iterate. It can be shown that this gets arbitrarily large as n gets arbitrarily large. Therefore we conclude that a Sierpinski gasket has infinite perimeter!

And that it has zero area inside and infinite perimeter.

This is against the Koch Snowflake, which is a figure having a finite area inside an infinite perimeter. This goes against the way we think and according to geometric intuition that we have. But it actually is characteristic of many shpaes in nature. For example (i really like this example :D ) if we take all the arteries, veins and capillaries in the human body, then they occupy a relative small fraction of the body. Yet if we were able to lay them out end to end, we would find that the total length would come to over 60000 kilometres. This example i am quoting from an article i had copied years ago.

von_koch_curve.gif

Related Article:

Lindenmayer systems and Fractals

Onionesque Reality Home >>

Read Full Post »

This post is as a follow up to the previous post.

I have greatly been interested in fractals and have played around with models and mathematics of the same. With a friend of mine i have developed many NetLogo models as well.

The NetLogo website offers very decent models of fractals. These can be run for the curves.

The models allows the user to change parameters and see the change. NetLogo models such systems amazingly!

1. Koch Curves

2. L-Systems

3. Mandelbrot

4. Sierpinski

5. Recursive Tree

You could play around with these models to get a good understanding of L-system generation. These models can also be extended if they really fire you up!

Related Post: NetLogo Version 4.0.2 released

Read Full Post »

L-systems are very simple and elegant grammars (a set of rules and symbols) originally developed by biologist Aristid Lindenmayer to describe the growth of plants and trees.

tsr-fractals.jpg

These as we can see can lead to very beautiful figures as above!

Photo Credit.

The Lindenmayer system is recursive in nature which leads to self-similarity and hence fractal like structures. Plant models and natural-looking organic forms are similarly easy to define, as by increasing the recursion level the form slowly ‘grows’ and becomes more complex.

The components of a L-system are:

A) The alphabet, which is a finite set V of formal symbols or characters, generally they are taken to be letters A,B,C etc. These are the variables as they can be replaced. A set of symbols which will remain fixed are constants. These may be represented as another finite set.

B) The start, axiom or initiator ω, it basically is a string of symbols from V. If suppose V = {a,b,c} then ω can be aabc, abcc, abcab etc. There are many possibilities. This defines the initial state of the system.

C) Production rules, P that define how a variable can be replaced by a combination of variables and constants.

The rules of the L-system grammar are applied iteratively starting from the initial state. As many rules as possible are applied simultaneously, per iteration. This is the distinguishing feature of a L-system from a language.

There are many examples of the same that lead to very beautiful structures!

Some are:

A) Cantor Dust:

variables : A B

constants : none

start : A {starting character string}

rules : (A → ABA), (B → BBB)

Let A mean “draw forward” and B mean “move forward”.

Put in a different manner. We could say that a cantor dust fractal may be reconstructed using string rewriting using an initial cell {1} and then iterating the below rules.

{0->[0 0 0; 0 0 0; 0 0 0],1->[1 0 1; 0 0 0; 1 0 1]}.

Thus we would get the fractal as :

cantordustfractal_700.gif

B) Fractal Tree:

variables : X F

constants : + −

start : X

rules : (X → F-[[X]+X]+F[+FX]-X),(F → FF)

angle : 25°

Here, F means “draw forward”, – means “turn left 25º”, and + means “turn right 25º”. X does not correspond to any drawing action and is used to control the evolution of the curve. For n=6 the following figure may be generated.

453px-fractal-plantsvg.png

C) The Sierpinski Triangle:
variables : A B

constants : + −

start : A

rules : (A → B−A−B),(B → A+B+A)

angle : 60°

Here, A and B mean both “draw forward”, + means “turn left by angle”, and − means “turn right by angle”. The angle changes sign at each iteration so that the base of the triangular shapes are always in the bottom (they would be in the top and bottom, alternatively, otherwise).

Evolution for n = 2, n = 4, n = 6, n = 9

Other curves include the famous Koch Curve, Dragon Curve, Penrose Tilings etc.

Good places to do initial research on L-Systems:

1. Wikipedia

2. Fractinct L-system True Fractals, A tutorial by William Mcworter.

3. Fractals and Cellular Automata. by Daniel Shiffman.

4. Fractals and Recursion in the Nature of Code.

I would try to follow these initial posts on fractals with applications in RFID and in other smart antenna applications.

Also check out this voronoi fractal on this post. Credits to the image given in the original post.

voronoi-fractal

Read Full Post »