ABC Logo Lissajous Curve

Over the last couple of days I've seen a few people mention how similar the ABC Australian logo is to the new Disney Movies Anywhere service. I don't know much about the legal side of things, but I thought an explanation of why the ABC logo looks the way it does might be interesting.

The shape of logo is called a Lissajous figure or curve. The shape is generated by a parametric equation where the x and y coordinates are sinusoidal.  The frequency and phase relationship between the two equations for x and y determine the shape.  In the case of the ABC logo, the frequency of the y coordinate is 3 times that of the x coordinate and there is a 90 degree phase shift (I'll clarify this later) applied the y equation.

$$$x=cos(t)$$$ and $$$y=cos(3t+\pi/2)$$$

To make things clearer I've put together an animation. As the vertical bar sweeps across the screen it will intersect the x and y equations. The y coordinate is projected across and the x coordinate is projected across and up. The Lissajous figure is drawn where the project lines intersect.

Tracing a 3:1 Lissajous Curve x=cos(t)  y=cos(3t + $$$\pi$$$/2)

The phase shift is also very important to the shape. In the animation below you can see how the it changes as the phase shift is cycled across all possible values from 0 to $$$2\pi$$$.

Changing the phase relationship of a Lissajous Curve x=cos(t) y =cos(3t + $$$\delta$$$)

These curves aren't just a mathematical curiosity, they have a real world application. They used to be a very important tool for broadcast engineers. If two signals are feed into an oscilloscope (a tool that plots electrical waveforms) while it's in x-y mode, the Lissajous curve on the screen will reveal things about the signals.

The first thing to notice is that the number of horizontal and vertical lobes indicates the ratio of the frequencies. If the ratio of frequencies is rational (can be expressed as the ratio of two integers) the curve will be stationary. If not, it will slowly rotate like the second animation. If the two signal are meant to be locked together so that one is exactly 3 times the other like in the example above but the curve rotates, you know there's a problem. The rotation rate of the curve tells the engineer the deviation from the desired frequency. There are simple lookup tables like the one below that show what the curves should look like for a given phase shift and frequency ratio.

Frequency Ratios and Phase Differences

Earlier I said I'd elaborate on phase shift. The main thing to note is that you are working with two different frequencies.  1 degree of phase shift on one signal will take a different amount of time to 1 degree of phase shift on the other.  So it's important to not just note that there is a phase shift of 30 degrees, you have to specify what waveform you are referring to.  That's why a lot of the table results may be different from what you measure.  In a mathematical sense, it also makes a difference if you are talking about sine or cosine signal as one is a phase shifted version of the other.

Just to clear up another thing as well. The second animation is generated by plotting a waveform frame and then changing the phase an repeating this process. This is what makes it rotate. By chance though, this is exactly what you would see if the frequencies weren't locked together. A time varying phase is no different to making a small deviation to the frequency.

 

The code to generate the animations above is located here.  I did it as a quick project so didn't comment it.

 

Calculating Hilbert Curve Coordinates

You may have noticed from some of my previous blog posts that I've fallen down a rabbit hole learning about Gray codes and Hilbert curves.  They weren't just random topics.  I wrote those articles in order to understand the topic of this one, how to easily convert a Hilbert Index to Hilbert Coordinates via a method described in a paper by John Skilling.

Skilling, J. (2004), "Programming the Hilbert Curve", AIP Conference Proceedings.

Regrettably I don't yet understand why it works to a level that I'm satisfied with.  The paper describes the process and gives a summary of previous work by Butz and Lawder but doesn't really give a clear explanation of why the transform works.  It may be perfectly clear to someone who works in the field, but I don't get it... yet.

What I am capable of doing though is summarising the information here with some graphics to explain the concept to the next person that gets nerd sniped by this.  I'll start by recommending my last few blog posts as they will give you an idea as to my train of thought.

Entry and Exit Points for Space Filling Paths on a Grid

Hilbert Curve Generation With Lookup Tables

Converting Binary to Gray Code with XOR

A basic concept to understand is how binary numbers are treated as coordinates.  In the animation below, the index is 6 bits long and counts up from 000000 to 111111.  This can be used to cover every coordinate on an 8 x 8 two dimensional grid if every second bit belongs to the coordinates of one dimension while the others belong to the other dimension.  In this case the red bits belong to the x axis while the blue bits belong to the y axis.  Everything I'll describe in this post is for two dimensions, but it works for any number of dimensions.  For example an 8x8x8 grid could be covered with a 9 bit index where bits 0, 3, 6 belong to one axis, 1, 4, 7 to another, and 2, 5 ,8 to another.

Binary indexing in 2 dimensions

In the binary indexing animation you can see that there are diagonal lines.  These occur because more than one bit of the index can change at once affecting both dimensions.

The first step in the Skilling Transform is to take the binary reflected Gray code of the index.  This means that only one bit at a time can change.  Therefore the value of only one axis can change at a time leaving only vertical and horizontal movements.

Gray code indexing in 2 dimensions

The addressing scheme detailed above is formally described in this section of the paper.  I put this here just so we're all on the same page about the variable names.

$$$p$$$ is the number of bits in each axis
$$$n$$$ is the number of dimensions

Addressing description

Now onto the actual transform.  It's minimal and easy to compute.  It's not a recursive algorithm and takes a bit string that specifies the Hilbert index as an input and performs a series of swaps and inversions to return a bit string of the same length that describes the Hilbert coordinates.

Skilling transform

To see if I could understand the process better I wanted to visualise the transform.  The animation below show the transformation from Gray code indexing to the Hilbert curve.  You can see how the algorithm starts the transformation on the smaller features first and works up to larger features at each step.

Gray code to Hilbert curve via the Skilling transform in 2 dimensions.

Hopefully the worked example below will help people understand the process a little better.  The index is converted to its Gray code and the algorithm processes bits in a reverse order.  The grey boxes refer to the bit $$$r$$$ shown in the algorithm above.  The bits that are classified as low bits at each stage are underlined.

Worked example

I can't really offer much of a conclusion here.  The understanding I've gleaned so far is minimal and superficial at best.  I 'll leave this one for a while and come back to it in the future when I have more time.

I have a love hate relationship with problems like this.  I find them fascinating, but at the same time they remind me how much I miss formal study, and I get bummed out.  Kinda sucks having no one to bounce ideas off either.  Having said that though, I've finally generated some animations that I'm proud of.  You can find the undocumented scratch code here.

If you come across this page and have a better understanding of why this works I'd be glad to hear from you.

Merge Sort... Sort Of

I have a project in mind that requires a sorting algorithm.  That's easy enough, there are plenty of them out there, the problem I have is that I want to be able to save the state of the sort part way through and resume it later.  The easiest way to explain the solution I devised is to show an example sort in the animation below and then explain it.  First understanding Merge Sort will help as well.

Custom Merge Sort

I haven't really changed much.  I've just implemented Merge Sort in a simple way.  More specifically in a list of lists.  The basic principles of a Merge Sort are still there.  At every stage all sub lists remain sorted and merging two lists is done by comparing the smallest elements of the two lists.

In the animation above, 11 numbers are sorted.  To start, 11 lists that contain only one number each are created to store the numbers to sort.  These are contained within another list that has another empty list placed at the start.  This empty list is called the auxiliary list or List 1.  From this point on the process is simple, merge List 2 and 3 into List 1.  Once this has been done, move the new large list to the end of the outer list. Each time this process is repeated, the number of lists is reduced by one until only one sorted list remains.  It also ensures the the lists are always ordered by the number of elements they contain.  Large ones at the end, smaller ones near the start.

The reason I like this method of sorting is that it's easy to pause the sort, save the state, and resume it later.  All you need to do is save a lists of lists.  You don't need anything else.  When resuming, the next move to make can be determined by looking at the first three lists and seeing if they contain any elements.

Sorting State

It's not ground breaking, and merge sort has probably been implemented like this before, but I found it to be a simple way to go about doing things.  I've mentioned lists throughout this post, but as the program I want to write is likely to be in python, I'll probably use a deque of deques to hold the data.

On another topic, my original plan way to make a nice fancy animation to explain things that had nice transitions, but I just couldn't pull it together in time.  I thought I could find a software package to do it and ended up with Synfig, but that went nowhere.  What kind of program freezes because you have a font installed it can't read.  Some error handling would be nice.

I eventually started hand coding an animated SVG and that showed promise, but it was a bit clumsy and I didn't really have a work flow established as you can see in the image below.  I think I've finally come to a solution that involves d3.js and all that's associated with it.  Fingers crossed.

Makeshift animated SVG IDE

Just for fun, let's speed things up. :-)

Fast Custom Merge Sort

.