Fitting 1 dimensional data into 2 dimensional space


A few notes to myself.

Let's consider a set of 1 dimensional data. For example, the alphabet:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

What do we mean by "1 dimensional"?

Consider the element "B". From there you can go left to "A" or right to "C". Left and right are the only directions you can move. You cannot go up or down from "B". There's no way to go in or out. You're trapped in a single dimension.

What if we want to write the data onto a 2 dimensional space - like a bit of paper or a website.

Well, if the space is big enough, we can write it as we have above. A single line. Job done, go home.

But what if the space is too small in the horizontal direction to contain it all? Well, we could write it in the vertical direction:

A
B
C
D
…

OK, but what if the 2D space is too small in both the horizontal and the vertical directions to contain the 1D data? Now we get into the "exciting" world of space-filling algorithms.

Here's the approach that you're probably most used to. It's certainly the one which springs to most people's minds:

ABCDEFG
HIJKLMN
OPQRSTU
VWXYX

The algorithm is simple. Write horizontally from left to right until you run out of space, then move down one line, return to the left-most side, and continue writing. Repeat.

Except! That's not necessarily the simplest or most obvious way of writing!

There is a different algorithm - Boustrophedon:

ABCDEFG
NMLKJIH
OPQRSTU
  ZYXWV

Start at the left, when you run out of space, move down a line and continue writing in the opposite direction!

→ABCDEFG
        ↓
 NMLKJIH←
↓
→OPQRSTU
        ↓
   ZYXWV←

If you haven't spent years learning to read "properly" this form of bi-direction writing may well be easier. You don't need to move your finger or eyes back in a perfectly straight line.

We can go a little further. What if we started at the centre of the page, and wrote out in a spiral?

Z
YJKLM
XIBCN
WHADO
VGFEP
UTSRQ

As pretty as this looks, there are some obvious drawbacks. Unless you know exactly how long the 1D data is, you won't know where to start on the page. It also might not fill the space in the most efficient manner.

Here's a different algorithm. It starts in the top left corner of the space and gradually spreads out. Growing to fit the data in the space:

 ABIJYZ 
 DCHKX  
 EFGLW  
 PONMV  
 QRSTU  

If you're having trouble following that, here it is in diagram form:

 →↓→↓→ 
 ↓←↑↓↑ 
 →→↑↓↑ 
 ↓←←←↑ 
 →→→→↑ 

That's quite a nice algorithm. It starts in a predictable place and it fills up both horizontal and vertical space in equal amounts.

Introducing Hilbert Curves!!

Let's start with a simple curve:

D__C
   |
A__B

Where do we go from here? The Hilbert Curve is a fractal algorithm which starts like this:

F__G  J__K
|  |  |  |
E  H__I  L
|        |
D__C  N__M
   |  |
A__B  O__P

And ends up doing this:

Lovely!

Non-rectangular curves

Not every 2D space is a rectangle. Some have the audacity to be hexagons!

3D!

And then...

I wonder what interesting things I can do with this new knowledge?


Share this post on…

What are your reckons?

All comments are moderated and may not be published immediately. Your email address will not be published.Allowed HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <p> <pre> <br> <img src="" alt="" title="" srcset="">

Discover more from Terence Eden’s Blog

Subscribe now to keep reading and get access to the full archive.

Continue reading