Koch Curves and Canopies

Time for another “math in the moment” post!  There have been a few interesting developments just this past week, so I thought I’d share them with you.

The first revolves around the Koch curve.  I’ve talked a lot about the algorithm used to generate the Koch curve when the angles are changed — but this is the first time I’ve experimented with three different angles.  For example, the recursive procedure

F   +45   F   +180   F   +315   F

generates the following spiral:

spiral8

Looks simple, right?  Just 16 line segments.  But here’s the unexpected part — it takes 21,846 iterations to make!  That’s right — the horizontal segment in the upper left is the 21,846th segment to be drawn.

Why might this be?  Partly because of the fact that one angle is 180, and also the fact that 45 + 415 = 360.  In other words, you are often just turning around and retracing your steps.  These arms are retraced multiple times, not just once or twice like in previous explorations.

I found this family of spirals by having Mathematica generate random angles and using the algorithm to draw the curves.  Without going into too many details, the “obvious” way to generalize the equation I came up with before didn’t work, so I resorted to trial and error — which is easy to do when the computer does all the work!

Notice the pattern in the angles:  45 (1/8 of a circle), 180 (1/2 of a circle), and 315 (7/8 of a circle).  Moving up to tenths, we get angles of 36 (1/10 of a circle), 180 (1/2 of a circle), and 324 (9/10 of a circle), which produce the image below.

spiral5.png

Notice there are only five arms this time (not 10).  And it only takes 342 segments to draw!  There’s an alternating pattern here.  Moving up to twelfths gives 12 arms, and takes a staggering 5,592,406 segments to draw.  Yes, it really does take almost 6,000,000 iterations to draw the 24th and last segment!

With the help of Mathematica, though, I did find explicit formulas to calculate exactly how many iterations it will take to draw each type of image, depending on whether there are an even number of arms, or an odd number.  Now the hard part — prove mathematically why the formulas work!  That’s the next step.

I hope this “simple” example illustrates how much more challenging working with three different angles will be.  I think working out the proof in these cases will give me more insight into how the algorithm with three angles works in general, and might help me derive an equation analogous to the case when the first and third angles are the same.

The second development is part of an ongoing project with Nick to write a paper for the Bridges 2017 conference in Waterloo.  The project revolves around fractal trees generated by L-systems.  (We won’t be discussing L-systems in general, but I mention them because the Wikipedia had a decent article on L-systems.)

trees1

Consider the examples above.  You first need to specify an angle, a, and a ratio, r.  In this example, a is 45 degrees, and r is 0.5.  Start off by drawing a segment of some arbitrary length (in this case the trunk of a tree).  Then turn left by the angle a, and recurse using the length scaled by a factor of r.  When this is done, do the same recursion after turning right by the angle a.

On the left, you should see three different sized lengths, each half the size of the one before.  You should also be able to easily see the branching to the left and right by 45 degrees, and how this is done at each level.

In the middle, there are six levels, with the smallest branches only 1/32 the length of the tree trunk.  Can you guess how many levels on the right?  There are twelve, actually.  At some point, the resolution of the screen is such that recursing to deeper levels doesn’t actually make the fractal look any different.

What Nick is interested in is the following question.  Given an angle a, what is the ratio r such that all the branches of the tree just touch?  In the example below with a being 45 degrees, the leaves are just touching — increasing the ratio r would make them start to overlap.

trees2

What is r?  It turns out that there’s quite a bit of trigonometry involved to find the precise r given an angle a, but it’s not really necessary to go into all those details.  It’s just enough to know that Nick was able to work it out.

But what Nick is really interested in is just the canopies of these trees — in other words, just the outermost leaves, without the trunk or any of the branches.

canopy1

Right now, he’s experimenting with creating movies which show the canopies changing as the angle changes — sometimes the ratio is fixed, other times it’s changing, too.

Two observations are worth making.  First, this was a real team effort!  Nick had done the programming and set up quite a bit of the math, and with the aid of Mathematica, I was able to help verify conjectures and get the expressions into a useable form.  We each had our own expertise, and so were each able to contribute in our own way to solving the problem.

Second, Nick is using mathematics to aid in the design process.  My first attempts to create symmetric curves using the algorithm for the Koch snowflake were fairly random.  But now that I’ve worked out the mathematics of what’s going on, I can design images with various interesting properties.

Likewise, Nick has in mind a very particular animation for his movies — using the just-touching canopies — and is using mathematics in a significant way to facilitate the design process.  Sure, you can let the computer crunch numbers until you get a good enough approximation — but the formula we derived gives the exact ratio needed for a given angle.  This is truly mathematical art.

I’ll keep you updated as more progress is made on these projects.  I’ll end with my favorite image of the week.  The idea came from Nick, but I added my own spin.  It’s actually canopies from many different trees, all superimposed on each other.  Enjoy!

canopy2

Color II: Opacity and Josef Albers

Remember from last week we were discussing the following image:

AlbersSquares1

What colors are the squares?  Recall that when we allowed one or both squares to be transparent to some degree, there were many possible answers to this question.  Last week, we found out all possible color/opacity combinations for the purple square alone.

First, we’ll examine the case that the pink square is transparent and on top of the purple square.  Whether the purple square is transparent actually doesn’t matter, so we’ll be perfectly fine if we assume the purple square has RGB values (0.6,0.5,1) with opacity 1.

To begin, we need to establish the apparent color of the pink square.  If I load this image into Photoshop and use the eyedropper tool, I get integer RGB values of  (229, 51, 255).  Dividing these by 255 to convert to values between 0 and 1, I get (0.898039, 0.2, 1).  I actually used RGB values of (0.9,0.2,1) to create the image, so the eyedropper tool did its job….

Now let’s call the color of the pink square (R,G,B), and the opacity a.  Recall the formula from last week for the result of looking through a transparent color:

a\, C_1+(1-a)\,C_2.

In our case, C_1 is the color of the pink square, and C_2 is the color of the purple square.  So we get the equation

(0.9,0.2,1)=a\,(R,G,B)+(1-a)\,(0.6,0.5,1).

As before, we need to break this down into three separate equations, one for each component.  For exactly the same reasons as last week, we must have B=1 (go back and reread this argument if you forgot).  The equations for the Red and Green components are

0.9=a\,R+(1-a)\,0.6,\qquad 0.2=a\,G+(1-a)\,0.5,

which may be rearranged to yield

R=0.6+\dfrac{0.3}a,\qquad G=0.5-\dfrac{0.3}a.

Since color values lie between 0 and 1, we see from the Red equation that we must have

0\le\dfrac{0.3}a\le0.4.

Note that when this is true, the Green value also lies between 0 and 1, so this is all we need to check.  A little simplification shows that this implies 0.75\le a, so the pink square can be transparent as long as

0.75\le a\le1.

We can then use the formulas above to fing the Red and Green values (remembering that Blue is always 1).  Below are the possibilities in RG space:

RGSpace2

The point X corresponds to the value a=1, while the point Y corresponds to a=0.75.  Note that while the possible points in RG space lie on a line segment (it is easy to see from the above formulas that R+G=1.1), the points on the line segment do not vary linearly with a since the a occurs in the denominator in the above formulas.

So now we’ve looked at all the possibilities when the pink square is transparent and on top of the purple square.  What if the purple square is transparent and on top of the pink square?

We first note that half the work is already done, since we worked out the possibilities for a transparent purple square last week.  Here is what we obtained, where again the opacity of the purple square is denoted by a:

R=\dfrac{a-0.4}a,\quad G=\dfrac{a-0.5}a,\quad B=1.

This corresponds to the color C_1 in the formula for opacity.  Now let (R,G,B) denote the color of the pink square underneath, which will be C_2.  Using the opacity formula, we obtain the equation

(0.9,0.2,1)=a\,\left(\dfrac{a-0.4}a,\dfrac{a-0.5}a,1\right)+(1-a)\,(R,G,B).

This may look a little complicated, but it turns out we only need to look at the Red component.  Looking at the Red color value, we get

0.9=a\left(\dfrac{a-0.4}a\right)+(1-a)\,R,

which after multiplying out and rearranging results in

R=\dfrac{1.3-a}{1-a}.

Can you see any problem with this formula for R?  Since the opacity must be between 0 and 1 — in other words, 0\le a\le1 — the numerator of this expression will always be greater than the denominator.  This means that the Red color value would have to be greater than 1, which we know is not possible!

Our conclusion?  It is not possible that the two squares can be obtained by a pinkish square beneath a transparent purple square.  Essentially, the pink is “too red.”  In order to make the pink show through the purple, the opacity of the purple would have to be too close to 0, which would then mean that we’re not seeing enough blue.

In general, this is not easy to just see by quickly glancing at an image.  But if we use the formula for opacity and are careful with our calculations, we can prove that certain color/transparency combinations are impossible.

And what about a more complex figure?

Josef_Albers's_painting_'Homage_to_the_Square',_1965

Well, there are four different squares to consider, and several different possible layerings.  But it’s even more complicated than that.

What you’re seeing is an image on your color monitor or phone, which is on my website.  I got the image from the Wikipedia commons.  Someone uploaded a digital file of the image, which was either taken of the original piece, or digitized from a photograph of the piece.  Which might have been from a book, published long enough after Albers finished the piece that the photo was actually of a faded original.

So what we’re actually seeing is only an approximation to Albers’ original painting.  To make the analysis more realistic, we’d have to assume that the apparent color we’re seeing is within a certain tolerance of the original.  Meaning each color doesn’t have just one value, but a range of possible values.

We won’t go into this more complicated issue today.  But I hope you now appreciate that an image of just a few squares may be much more intriguing than you might originally think!

Color I: Opacity and Josef Albers

What do you see?AlbersSquares1

Looks like a pink square on top of a purple square.  But after hearing a talk about Josef Albers’ work at Bridges 2016 a few weeks ago, I realized there is more than one way to look at this image.

Maybe the square is actually more red, but transparent — so that the purple showing through makes it pink.  Or maybe the pink square is behind the purple square, and it’s the purple square which is transparent.  Or maybe the purple square isn’t a square at all, but a frame — that is, a square with a hole in it!

This first post in a series on color will explore this apparently simple figure.  The ultimately goal will be to analyze images in Josef Albers’ series Homage to the Square. But as mentioned last week, James Mai found that there are 171 possible combinations of opaqueness, transparency, frames, and squares in this series!  So we’ll start with a basic example.

But first, we have to understand how opacity works in computer graphics.  We’ve used RGB colors in several posts so far, but rarely mentioned opacity.  When this is included, the color system is referred to as RGBA, where the “A” represents the opacity (or alternatively, the transparency), which is also sometimes called the alpha.  A value of a=0 means that the color is completely transparent, so it doesn’t affect the image at all, while a value of a=1 means the color is completely opaque, meaning you can’t see through it at all.

As an example, in the series below, the squares have RGB values of (0.2, 0, 1.0), and A values of 0.25, 0.5, 0.75, and 1.0 (going from left to right).

OpacityExample

But these squares could also have been created without any transparency at all!  What this means is that if you include transparency/opacity, there are many different ways to specify a color that appears on your screen, not just one.  So in an Albers’ piece with four squares, where all of them may have some degree of transparency, the analysis can be quite difficult.

Josef_Albers's_painting_'Homage_to_the_Square',_1965

Next, we have to understand how the opacity is used to create the colors you see.  If color C_1 has opacity a and is on top of a color C_2, the apparent or observed color is then

a\,C_1+(1-a)\,C_2.

If you thought to yourself, “Oh, it’s linear interpolation again!”, you’d be right!  In other words, the observed color is a linear combination of the transparent color and the background color.

Keep in mind that is an idealized situation.  It is very difficult to make a correspondence with how we “actually” see.  If you were looking at an object throught a square of colored glass — maybe sunglasses — there would be concerns about the distance between the glass and the object, multiple lighting sources, etc.  For now, we just want to understand the mathematics of using opacity in computer graphics.

Another complication arises in considering the following two squares — a pure red square on top of a pure blue square.

AlbersSquares2

In this case, it is impossible that the red square has any degree of transparency.  If it did, some of the blue would show through.  If the red square had a transparency of a, our linear interpolation formula would give an apparent color of

a,(1,0,0)+(1-a)\,(0,0,1)=(a,0,1-a).

This means if there were any transparency at all, there would be a Blue component of the observed color, which is not possible since Red has RGB values of (1,0,0).  So before you go about calculating opacity, you’ve got to decide if it’s even possible!

Let’s start with the purple square.

PurpleSquare

What color could this square be, with what transparency?  Let’s call the color C_1 and the opacity a.  Since the background (screen color) is white, we use C_2=(1,1,1).

To assess what the color “looks like,” you’d go to PhotoShop and use the eyedropper tool, for example — or another other application which allows you to point to a color and get the RGB values.  In this case, you’d get (0.6, 0.5, 1.0).  Basically, what you get with such tools are RGB values, assuming an opacity of a=1.

But of course we’re wondering what is possible if the opacity is not 1.  If we denote C_1 by (R,G,B),, we get

(0.6, 0.5, 1.0) = a\,(R,G,B)+(1-a)\,(1,1,1),

which simplifes to

(0.6, 0.5, 1.0)=(a\,R+1-a, a\,G+1-a, a\,B+1-a).

This gives us three equations in four unknowns, which makes sense — we know the answer is likely not unique since it may be possible to create the square using different opacities.

Note that the third equation is

1.0 = a\,B+1-a,

which when rearranged gives us

a\,(B-1)=0.

Of course a cannot be 0, or we wouldn’t see anything!  This means B=1, which makes sense since if we’re interpolating between B and 1, the only way to get a result of 1.0 would be if B=1.

What about the other equations,

0.6=a\,R+1-a,\qquad 0.5=a\,G+1-a?

Solving them, we get

R=\dfrac{a-0.4}a,\qquad G=\dfrac{a-0.5}a.

Keep in mind that the R, G, and a values must all be between 0 and 1.  So we must at least have

a\ge0.5

to guarantee that all values are positive.  Further, observe that for any a value between 0.5 and 1 (inclusive), we have that the numerators of both color values are less than the demoninators, and are therefore less that 1.

So this means that the purple square may be created using the color values

R=\dfrac{a-0.4}a,\quad G=\dfrac{a-0.5}a,\quad B=1,

as long as the opacity satisfies 0.5\le a\le1.  This is illustrated graphically below, where the solid line segment represents all possible colors for the square.RGSpace

Here, the horizontal axis is the Red component and the vertical axis is the Green component.  Since we observed earlier that the Blue component must alwas be 1, the lower-left corner would be (0,0) in RG space (Blue), and the upper-right corner would be (1,1) (White).  When a=1, we obtain the point X with RGB values (0.6, 0.5).  This makes sense, since we observed the color to have RGB values (0.6, 0.5, 1.0).

When a=2/3\approx0.67, we obtain the point Y with coordinates (0.4, 0.25) in RG space.  This means the purple square could be obtained using RGB values of (0.4, 0.25, 1.0) and opacity 2/3.

And when a=0.5, we obtain the point Z with coordinates (0.2, 0) in RG space.  This means the purple square could be obtained using RGB values of (0.2, 0, 1.0) and opacity 0.5.

Note that even though Y is  halfway between X and Z in RG space, the a value is not halfway between 0.5 and 1.0.  This is because of the a in the denominators in the fractions above giving solutions for R and G.

There’s a nice geometrical interpretation of this picture, too.  If one color is an interpolation of two others, it must lie on the segment joining those two others.  So we need all colors C such that X is on the segment between C and (1,1).  This is just that part of RG space which is a continuation of the line starting at (1,1) and going past X.

Now we could have just used this geometrical idea from the beginning — but I wanted to work out the mathematics so you could see how to use the definition of opacity to solve color problems.  And of course sometimes the geometry is not so obvious, so you need to start with the algebraic definition.

So working with opacity isn’t too difficult as long as you understand what your computer is doing.  In the next post on Color, we’ll tackle the issue of the pink square….