Lessons taught; Lessons learnt

I've had a fun weekend playing with Processing and improving the clumping visualisation I posted earlier this week. The new version has been uploaded to OpenProcessing.org, a site which contains over 1000 visualisations, many of them containing beautiful and interesting mathematics:

A brief reminder of the situation: We have a grid of squares, of several different types. These squares are happy when they are surrounded by enough squares of the same type as them, and unhappy otherwise. We take two unhappy squares, swap them over, and repeat until bored!

There are two key parameters here: the number of different types of cell/person/house/whatever these squares are representing, and the happiness threshold: how many neighbours need to be the same as a cell for it to be happy.

Let's look at the types of behaviour that emerge for different values of the parameters:

A behaviour catalogue

		Neighbours needed for happiness
		2	3	4	5	6
Types	2
	3
	4
	5
	6

You find that it takes longer and longer for the state to settle down as you increase the number of types of cell. With 6 cells, and a happiness threshold of 4, for example, you can see from the table that it does eventually settle into a fairly stable clustered pattern, but it takes a very long time. After 50,000 swaps the grid looked like this:

Apart from the special case of two types, with happiness threshold five or six, the cells always seem to settle into a relatively small small clustered pattern (with small threshold), or to not stabilise at all (large threshold).

2 types; threshold 5: this is the case explored in the earlier post on this clustering behaviour. The cells cluster together fairly quickly, and then over the next 20,000 swaps or so the clusters join together into larger features, with the borders being long stretches of horizontal/vertical/diagonal lines.

2 types; threshold 6: this is perhaps even more interesting then the previous case. We do get some clustering, but the clusters don't hold together, but fray, and move around.

As with the previous post on this topic, I have wrapped left-right and top-bottom. This doesn't change the behaviour significantly. If you'd like to explore what happens without this wrapping, then go get the source code and dive in!

Emergent Behaviour.

This 'clumping' behaviour is just one of many examples of emergent behaviour, where small-scale local actions add up to a sometimes surprising global behaviour. Sometimes, as the old aphorism says, the whole is more than the sum of its parts.

One of the best known examples of this emergent behaviour is flocking, where groups of birds fly together in flocks that seem to require some collective intelligence, but are actually generated from purely local actions. This behaviour was modelled in Boids, a classic Artificial Life simulation from 1986. Here's an excellent 3D Boids simulation.

For the last few days, I've been diving into Processing -- basically an integrated Java wrapper which makes it easy to create simple graphical visualisations (see here for some beautiful examples). Coming from Python, I particularly like not being forced not to write the 500 pages of OO wrapping that turned me off Java in the first place a few years ago.

My first Processing visualisation demonstrates how seating plans degrade over time!

From mixed to clumped

Imagine you have a square array of seats, and a group of boys and girls sit in them, alternately boy then girl. If we highlight one of the sexes we will get a checkerboard pattern.

Now imagine that boys like to have more boys than girls around them (and vice versa for girls). To try and make everyone happy, we implement the following scheme:

• Identify at random two people who aren't happy with their seat.
• Swap them.
• Repeat until everyone's happy.

If we repeat this procedure thousands of times, what will happen to the layout? Click below to find out:

Sorry, the visualisation could not be started.

Clicking again will restart the procedure.

You've probably noticed that I've wrapped left-right and top-bottom... which does move it away a little from the classroom context! This was basically to make the calculations easier.

Here are some examples of what happens if you let this run for a while:

• 

• 

• 

Each frame of these animations represents 2000 swaps, and each animation covers 50000. You can see that there are similar phases in each one: a quick 'clumping', and then a much slower phase where the boundaries settle down into long straight/diagonal lines.

Notes and Extensions

There are many ways to push this visualisation further -- we could change the number of types (English, Welsh, Scottish?); change the 'happiness threshold' (which is currently 5 out of the 8 neighbours); perhaps even have different thresholds for each group. You find really interesting behaviour as you change the threshold -- too high, for example, and the pattern doesn't settle down because there are too many unhappy people.

If you'd like to use my visualisation as a starting point to explore these extensions, then the source is here: clump2.pde. Have fun!

Imagine you are given some points, and asked to join them together. Probably the easiest way to do this is to use straight lines:

What if we wanted the line joining these points together to be a curve, rather than a sequence of straight lines? Even better, to be a smooth curve (in other words, to not have any sharp changes in direction)? One of the simplest ways to do this is to move into the world of Bézier curves.

The geometry of Bézier curves

Beziér curves are a class of surprisingly easy to generate curves which can be specified completely by a small number of points. Here is how to geometrically construct the two most common types of Bézier curve:

First, a quadratic Bézier curve:

To see this Geogebra worksheet, please enable Java.

Second, a cubic Bézier curve:

To see this Geogebra worksheet, please enable Java.

(Both of these are interactive -- move the blue points around and see how the curve changes.)

It should be obvious that we could continue this process with more and more control points to get Bézier curves of even higher orders.

From curves to splines

These curves are very nice, but they only go through the first and last points, with the others acting like 'control points', influencing the direction of the curve. If we create a Bézier curve using all the points given earlier, for example, we get this:

To connect up the points we are going to need to join together several of these Bézier curves, to form a spline. The full theory of splines is very complicated, but we can make a good start by connecting together a bunch of cubic Bézier curves:

If you have ever used a vector graphics package (like Inkscape, Illustrator or Coreldraw), this is exactly how they create paths through specified points. They tend not to draw the line segment connecting the two control points together, which makes the path look like this:

Sorry, the GeoGebra Applet could not be started. Please make sure that Java 1.4.2 (or later) is installed and active in your browser (Click here to install Java now)

Playing with the path above, you soon notice that it is very easy to get kinks (cusps) at the points where the Bézier curves meet. We can avoid this by making sure that the control points before and after a curve point are on the same straight line. Drawing packages also usually make the control points the same distance away from the curve point, giving you something like this:

Sorry, the GeoGebra Applet could not be started. Please make sure that Java 1.4.2 (or later) is installed and active in your browser (Click here to install Java now)

There is still too much choice here, though -- remember that we have just been given the points for the curve to go through. We can get a fairly nice curve, which just depends on one parameter (the 'curviness', lambda), by setting the control points as follows:

Given points up to , for , set the control point to the left of to be , and the control point to the right of to be .

In other words, the line between the two control points is parallel to the line between the two neighbouring curve points, and the distance is proportional to the distance between the curve points.

We also need to decide what to do with the control points of the ends of the curve, and . Probably the simplest thing to do is to set the control points equal to the curve points themselves.

This gives us something like this:

Sorry, the GeoGebra Applet could not be started. Please make sure that Java 1.4.2 (or later) is installed and active in your browser (Click here to install Java now)

I call the parameter the 'curviness', because the spline becomes more and more like a collection of straight line segments the closer lambda is to 0. The higher the value of lambda, the more pronounced the curve is -- and interesting things happen if lambda becomes negative!

Solving our original problem

We can now solve our original problem, by connecting our collection of points together with an appropriately generated set of Bézier curves. We might decide to have an 'open' curve (with endpoints):

Sorry, the GeoGebra Applet could not be started. Please make sure that Java 1.4.2 (or later) is installed and active in your browser (Click here to install Java now)

or indeed to create a 'closed' curve, treating all the points equally:

Sorry, the GeoGebra Applet could not be started. Please make sure that Java 1.4.2 (or later) is installed and active in your browser (Click here to install Java now)

Why not see what different types of shapes you can generate from these seven points? How close to a perfect circle can you get, for example?

Further notes

Without realising it, you have been looking at Bézier curves for years: every scalable Truetype font is defined using quadratic Bézier curves, and many other font systems use quadratic or cubic ones. The mass use of scalable fonts (first popularised in the Postscript printing system) was a major innovation, rendering the old bitmap system, where fonts came in one particular pixel-based size, almost entirely redundant.

Interestingly, Bézier was not the first person to discover, or to work with Bézier curves. One of the most common algorithms for drawing Bézier curves is due to de Casteljau, who was working with Bézier curves several years before Bézier! 

Although probably the most common, Bézier curves are certainly not the only choice to use for splines. If you are interested, see this Wikipedia article for more information than you probably wanted on the deeper mathematics behind them.

A Geogebra postscript

All the interactive sections above were generated using Geogebra. Double-clicking on any of them will open the interactivity in its own window, where you can save it to your computer, or explore how it was generated. If the interactivities are not there, then the Geogebra website is probably down!

One of the features introduced in version 3 of Geogebra is custom tools. I have created one of these custom tools which will let you easily create cubic Bézier curves. Simply open the following file: cubic-bezier-tool.ggt, and you will see a cubic Bézier tool appear in the toolbar.

Appendix: The algebra of Bézier curves

The reason for the names 'quadratic' and 'cubic' becomes clearer when we try to figure out an algebraic way to generate Bézier curves. It is apparent from the geometric construction that the key to constructing these curves is to move a certain proportion of the way between pairs of points, and then repeat this process until we have only one point, which will trace out the Bézier curve.

We will build up the formulae from the simplest case:

Straight lines (linear Bézier curves): If is a parameter between and , then the point th of the way between and is . As changes, will trace out the line segment . This is sometimes called linear interpolation.

Quadratic Bézier curves: We are given points , , and . From these we generate the two points and . Moving th of the way between these two points we generate :

Rearranging and simplifying, we get

.

This will trace out our quadratic Bézier curve.

Cubic Bézier curves: We are now given four points, to . We can generate two quadratic points, and , with equations as above. Combining them, we get , which will trace out our cubic Bézier curve. The simplified form of its equation is:

.

We could continue this as far as we wanted, to get equations for higher order Bézier curves.

The next version of Geogebra is nearing release, with quite an impressive list of changes and additions. One of the key additions, for me, is the integration of animation into Geogebra itself. It takes the approach of animating sliders: you can specify the increment, the speed, and what to do when you hit a boundary (bounce, or repeat).

At first I didn’t think there was any way of getting the animation to start automatically, but it looks like all you need to do is to save the worksheet with the animation running. It will then still be running when you reload it. This means we no longer need Javascript to kludge together animated Geogebra files on webpages.

Here, for example, are some animated rotating squares, which originally appeared in non-animated form last year:

You need to enable Java to see this Geogebra applet.

(Source: rotating_tesselation_2.ggb)

The only change I had to made was to alter the animation properties, right click on the slider, and select ‘Animation On’. To put it on the webpage I basically copy-and-pasted the ‘applet’ tag from the ‘Dynamic Webpage’ export option. No extra Javascript is needed.

The pre-release isn’t quite ready for prime time yet (when I tested it, it had a habit of losing its containing window, for example), but I look forward to spending some time exploring the other features, like the spreadsheet view. There also seem to be a whole host of statistics-related features (such as the drawing of histograms and box-and-whisker plots).

Introduction

Bitwise operations like AND and NOT are fundamental to the low-level operation of the computer you’re sitting at now. When operating on single-bit values (‘0′ or ‘1′), we can describe the outcomes using the following tables:

• NOT
  

  x	NOT x
  0	1
  1	0

• AND
  

  x	y	x AND y
  0	0	0
  0	1	0
  1	0	0
  1	1	1

• OR
  

  x	y	x OR y
  0	0	0
  0	1	1
  1	0	1
  1	1	1

   

• XOR
  

  x	y	x XOR y
  0	0	0
  0	1	1
  1	0	1
  1	1	0

If we interpret ‘0′ as FALSE and ‘1′ as TRUE, then we can see where the names come from: ‘x AND y’ is true exactly when both x and y are true; ‘x OR y’ is true when either x or y or both are true; and ‘x XOR y’ is true when either x or y but not both are true (hence eXclusive OR, to contrast with ‘normal’ inclusive OR).

We can also apply these operations to any two numbers, by writing both numbers in binary (or ‘base 2′, just as we normally work in ‘base 10′), and working along bit by bit. For example,

5 AND 3 = 101 (base 2) AND 011 (base 2) = 001 (base 2) = 1,

while

5 OR 3 = 101 (base 2) OR 011 (base 2) = 111 (base 2) = 7

The Graphs

 Allow x and y to take any value from 0 to 31, and let z be the result of AND, OR, or XOR. We get a collection of points in 3D space which we can graph. Here’s what they look like:

In this view, AND and OR look very similar to each other, and both look intriguingly like a distorted Serpinski gasket, while XOR looks quite different. In one respect this is a trick of the perspective used. If we rotate the XY axis by 45 degrees, we get the following:

(Images generated using Autograph. Click for a more detailed view.)

Interpretation

I think these images are intriguing enough to spark quite a few questions — for a start, why on earth are all those triangles there? I’m going to leave most of these for interested readers to ponder by themselves.

There is one point I’d like to follow up, though. The first view does highlight a key way in which XOR is different to both AND and OR: Given a and b, the equation a XOR x = b always has a solution — something which certainly isn’t true of AND or OR (there is no solution, for example, to 0 AND x = 1).

Indeed, the solution is simply a XOR b, due to two magical properties of XOR:

x XOR x = 0 for any x;
x XOR 0 = x for any x.

This is the basis of a very old low-level trick used to swap two numbers without having to use a temporary variable:

TO SWAP a AND b:

1. a = a XOR b
2. b = a XOR b  [b now holds the original contents of a]
3. a = a XOR b  [a now holds the original contents of b]