Coding the Hilbert Curve

hi everyone happy winter it is a beautiful day here in Brooklyn New York the snow is coming down it is quite chilly out it is the perfect time for a coating video so in a moment I'm gonna head into the Cabana and attempt to program the hilbert curve which is known as a space-filling curve and make a visualization of it I hope you enjoy it there's no heat in there so we'll see how long I last but come and join me in the Cabana [Music] can't see anything my glasses fogged up I have a confession to make it's actually the next day I had some technical difficulties after my intro in the snow there but I'm back this morning and it's very cool if you could see by that breath by the steam but I am so excited to be here and to visualize the Hilbert curve with you here in the Cabana today the bells are ringing must be time to get started coding as usual my frame of reference will be the Wikipedia page I should say that though if you're here and you've never heard about the Hilbert curve before what what I would suggest is actually taking a look at the three blue one brown video about space-filling curves the beauty and math of infinity another really important reference for this video that I read this morning that's super helpful is an article blog post by Marcin chadwick apologies if I mispronounce the name from August 2016 which looks at an iterative algorithm for drawing the hilbert curve in fact that's the exact algorithm I'm going to use it's the one that's also described down here in a very opaque and confusing way on the Wikipedia page in pseudocode but hopefully by the time I get finished programming this if it works we'll be able to see how that matches up to these two references so the hilbert curve which is a fractal a space-filling curve described by german mathematician David Hilbert was invented in 1891 and what I'm going to do because I'm living in a discrete world of processing and pixel space is create something called a pseudo-hilbert curve the actual Hilbert curve only exists as iterations go to infinity so let me explain what I mean by this so Hilbert curve can be thought of with it with a given order so if I say order equals 1 then what I have and I have a two-dimensional space and this two-dimensional space can be infinite the Hilbert curve exists as a sequence a series of four points 1 2 3 4 and I really should number them 0 1 2 3 now I'm actually drawing this upside down from how it's usually drawn but that's because I'm going to work in a pixel space where 0 0 is that left corner so that's the pseudo-hilbert curve order 1 if I have order equals 2 then I take that same 2 dimensional space and I subdivide it into 4 quadrants 0 1 2 & 3 and then I take that first order Hilbert curve and put it in every single one of those quadrants and the idea now is to connect them 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 so that's 16 points I should note there's an important property going on here if the order is 2 2 squared is 4 is the number of quadrants I have and then the number of points I have oh actually no no no not it's 2 squared but it's it's 2 to the order power we'll see that and then the number of points I have is actually 4 squared which is 16 this is going to become an important property because these numbers what the order is what's the total number of points in the curve are of how many quadrants are all all those are gonna be important when I program this they have to be but this doesn't look like anything we've seen on the Wikipedia page or the blog post and 3 blue on brown video this doesn't connect up properly what I need to do with this top left quadrant and and top right quadrant is rotate that first order curve like this so now if I draw this again and I take this top left and rotate it counterclockwise these two stay the same and this top right and rotated clockwise now I could connect this here the connect this here I connect this here and this is what we typically see as the second-order hilbert curve let's go ahead and do the third order Hilbert curve I'm gonna have a really hard time drawing this so it'll be much better visualized by this reference image on the Wikipedia page itself first to third order curves but let's give this a try nonetheless so if I have a two-dimensional space it's subdivided it's it's so divided twice so that should be 2 to the third power which is 8 and then eight squared is 6 is 64 so the whole third order Hilbert Cerf chef 64 points but basically the first order curve is in each one of these smaller smallest squares the second order curve is in each one of these and then of course the third order curve makes up the whole thing so let's do this this is right we're just doing copies and then up here this well let me connect them and this connects here and then I need to do the same thing up here but this has to be rotated so I think if I do this right because this goes like this now I can rotate this one to draw it like this connect it come back this gets connected here and this cuts connected here so this is the third order curve oh I don't know if you were able to follow that but basically with each subsequent iteration we take the version of the pseudo-hilbert curve from the previous iteration we tile it rotate the top left and top right and make the connections then this one gets tiled in these four spots with the top left and top right rotate it and those are connected and we could keep going I'm not gonna attempt to draw it I think this is the time where I really need to write some code so a wonderful lucky thing happened it was as if the Cabana gods the gods of the Cabana knew that processing for the alpha version of processing 4 was going to come out overnight and made me have all these technical difficulties yesterday and and forced me to re-record this morning because in fact there is a new version of processing it's alpha processing 4 I'm gonna attempt to use it I've already downloaded it I will include a link to where you can download it if you want to try it but you know I don't know if this is the official there's no official recommendation to move to processing for just yes now fun oh look how pretty it is oh it's lovely save my sketch call it Hilbert fingers are so cold oh there's the butt bug report we gotta file an issue we get some errors in the console that's right setup bitterly that's right draw fortunately I think this won't take too long I have a good sense of how to do it famous last words of the programmer I want to use a square processing window I'm sure you could come up with a clever way of doing it where it isn't square I'm gonna use powers of two that seems to be important and everything that I've been drawing background zero so if I think about this I want a variable that's called order and we'll start with the first order curve the other thing that I want is I want a function called Hilbert that if I pass it in index out comes the XY location of where it is in the pseudo-hilbert curve so if I give it zero I get this point zero zero if I give it one I get this point zero 1 1 1 1 0 let's actually just do that really quickly let's we'll start with that P values P vectors P vector Hilbert into I for index and then I need an array of points I'm just gonna hard code these in the birds are out somehow I don't know who the birds are out there's freezing cold weather a P vector when I say zero zero and then I can just say return points index I this is very easy well it is easy for the first-order filter I need the total number of points so let's take let's make a variable n which is 2 to the order or power and then I know that the total number of points is n time N squared n times n oh and this needs to be converted into an integer ok so now I can iterate over all the points all my fingers are no and I can say P vector V is Hilbert index eyes I have these four points in the first order Hilbert curve pseudo-hilbert curve 0 1 2 3 and I just want the function to them back to me I'm gonna assume that what I ultimately want to do here is animate so I well I could just draw them right there and set up I'm going to create a variable called path which has a new array of P vectors with total number of spots and then I don't even need this V here I just say path index I equals Hilbert I ha so you might notice that the coordinates of these points are the unit of measurement is I don't know what its pixels but I'm only going like one pixel so I need to expand that out according to the width of my wind processing window itself so this should be the width divided this length is probably is ultimately I think width divided by 2 which would be width divided by n so I can say that the length of each line is the width divided by n path index I multiplied by that length and then in draw let's create a counter to go over the points one at a time the game shape let's say begin shape and shape iterate over the path no fill oh there we go ah but I need to offset it so it's in the top left because zero zero is there let's offset by half of the length path index I add length divided by two length divided by two and there we go we're getting there we're gonna go for order number two next let's add a little flair let's draw a little points let's draw than the index there as well copy paste is my friend when it's cold okay so I can also see the index values this is gonna help us as I keep going here let's look at order number two so the first thing I want to see is can I get four copies of order one if I were just to like divide the length again by two I'd see the first order curve in the top left which is good so that means that that's right because this changes to two then now n is four so the length is width divided by four and the total number points is sixteen but I have an array index out of bounds exception because I don't have sixteen points ah now is comes the magic binary numbers counting in binary let's look at the binary representation of the numbers of the first eight points of the Hilbert curve so that's the arrow through seven which would be zero zero zero zero one so this is the binary representation of the first eight numbers and I could keep going with eight because we have 16 but let's just start here you might notice a repeating pattern here 0 1 2 3 0 1 2 3 so interestingly if I look at the first these 2 bits here that's going to give me the index into the first order a Hilbert curve when this comes in say int index equals I ampersand I think three I'll talk about what that is and let's just see if this works aha yes I have all four copies of the pseudo-hilbert curve in the top left because I am just looking at these first two bits now look at this 0 0 0 0 1 1 1 1 what do those two bits mean well those four bits can be mapped to which quadrant they're in 0 0 0 1 1 0 1 1 so the next thing oh I have to talk about ampersand I've typed why do I put ampersand in there this is called bit masking it's not corrected on the screen basically the number 3 in binary is 0 0 1 1 so any binary number that you do the and operator with like let's say I pick 7 which was 0 1 1 1 1 1 true and true is still true 1 1 and 1 is also 1 0 & 1 that's not true they both have to be 1 so this becomes a 0 so it doesn't matter whatever is in here because I'm using the ant operation these will always come zeros and I'm left with just these last two bits so what I want to do though however is look at these two bits next if I have something like 0 1 1 1 I can shift the bits and I believe in Java if I write this I don't remember how many of these I have 2 or 3 this I shift the bits over and I would be left with these come back as zeros like this so these get deleted these shift over and I get leading zeros there so then I can say I equals I shift over by 2 and then index now once again equals I ampersand 3 the point I want to return on the first order Hilbert curve is right here so P vector V equals points index then I'm going to shift over and get the next two bits and there are four possibilities the next two bits could be 0 1 2 or three let's just use an if statement if index equals zero then the the curve still is here so do nothing else if index equals one that's here so V dot y go up by one else if index equals two now increase X and y else if index equals three then just V dot X goes up by one and then return V okay so now I have done both pick the point in the first order Hilbert curve and then based on what the next two bits are I am moving to the correct quadrant for the second order hello curve that does not look right ah okay I think I know why so this is length and I want the next one to go down here so I'm actually going by two times length and so that should be plus equals two I should be more thoughtful about this though and I should actually use a variable so let's say afloat length equals I think it's just n whatever this n is two to the power of the order that's the length then I want to go up by that length this doesn't go here it goes here no not at all oh no by the order the order not the not n the order perfect aha but we have that problem so once again I have the problem where I need to rotate let's say I have 0 1 2 3 and I want this to turn on to its side so it is 0 1 2 3 because then it's going to come down to connect to 4 5 6 7 so 0 and to remain the same one in three are swapped so that's index equals zero all I have to do is say vx is V dot Y and V dot y equals V dot X only that won't work because once I've set V dot X to V dot y I can't set V want Y back to V naught X so I have to use a temporary variable to equal to save the value V dot X and then that's here Wow look at that there it is right over here so then I have to do the top right 0 1 2 3 and we're coming in from the bottom here so this is 0 1 2 3 so 0 and to swap but 3 & 1 stay the same so in index 3 right if I were to do this same exact thing this is rotating the wrong way right so that rotates it the wrong way I need 12 the point 12 to end up down here so that I should be able to say one - and one - there we go ha oh my goodness what second-order hilbert curve oh length equals order so this should be length sorry why do I do I need a separate variable here I'm confused well we're gonna find out I'm sure there's something wrong let's could I possibly have done everything that I need and I can just change this to 3 no oh wait a second here oh my goodness I've lost my mind I forgot that if I go up another oh I'm really crazy if I I need to do a loop now this has happened over and over again because as I go up I need to continue to shift the bits and check the quadrant of course of course that's the whole point of this iterative interative fractal process so let's use J and we're going to go all the way up to the order right and I can start at 1 because ultimately and this happens here and maybe there's a way to like have the loop be from the beginnings I could but I'm just gonna do this this parts gonna be hard-coded then the loop starts at 1 shift the bits over this is gonna be Jay that's how much I'm shifting because based on the quadrant I keep shifting either one spot or two spots or three spots expanding this is the end of the loop shift the bits mask it get the length and move so this should be three no is J times two okay that looks cool oh I already I have order here so this has to be laying okay all right this looks good this is everything's right except for the top right so I need to shift based on that length I believe so just like length minus one oh there we go look at that third order upper curve mmm I feel like I just like fudged my way through that I'm not sure if I explained it properly oh no no no no fourth well that didn't work okay I think I got it now you've all of you probably screaming at your television nobody's watching this on a television let's be real what I'm considering here is the relative length of each iteration of the Hilbert pseudo-hilbert curve and how does this work well I've got one square then I have four then I have 16 so the length here if that's 1 this is 1/2 and this is 1/4 so this is the relative length and by the way it might not have been clear but the smallest one is the one that's coming first because as I am computing all of these locations I'm starting with the smallest first-order Hilbert curve then the next two bits are where is it within it those four quadrants then those four then those four expanding out so this relative length is going up it looks like it's going up times two but I think the next one would be well this times 2 it's 2 to the power so the next one would be 1/8 so this has to be 2 to power of Jay could have sworn this was gonna be right length - oh I'm missing a one here how did I lose that one okay that's back now I believe I can change the number to four oh there we go oh it's so lovely okay I don't need the numbers anymore so let's take out the numbers the other thing is I had this count because the idea was that I don't want to draw the whole thing so let's ask counter in here and then we're gonna say counter plus plus that is delightful oh I'm so happy all right so if counter equals path length should I just stop let's just stop I could start it over by sitting counter equal to zero let's start it over perfect all right throw caution to the wind let's jump up by to go to order six just secured watch this all day eight give myself more pixel space let's go up by ten spots each time and change this to greater than all right so why this is going let's think about what we've actually accomplished here for a moment this is actually a mapping this two-dimensional space any XY point can be mapped to an individual index now of course we do this all the time we all the pixels are ordered right so if I have a 10 by 10 grid this is these are pixels 0 through 9 then 10 11 12 but this particular way of mapping between the two-dimensional space in 1 dimensional space is not as useful in mathematics as the Hilbert curve so I'll leave you to research that on your own to watch the three blue out Brown video that discusses that looks at this topic more closely there's a lot of ways that this mapping can be useful in computer science and mathematics with different algorithms and in fact if we refer back to the Wikipedia page you'll see here description of how a grayscale photograph can be converted to a dither black-and-white image using threshold in with the leftover amount of each pixel additive next pixel along the old bit curve oh you should try that and you'll also often see the Hilbert curves colored let's try something so I'm not sure how to do this with begin shape a 10 shape but let me just start with one and draw these as lines I minus 1 I minus 1 let's take a peek at our curve oh it's almost finished let's just watch it finish this is a single continuous line isn't that amazing re finished uh-huh so let's just make sure this works exactly the same way with lines yep looks like it does if I now say colormode HSB 360 255 255 so I have a hue hue of a color ranges between 0 and 360 along the sort of color wheel and I can say float H equals map I which goes from 0 to path length to between 0 and 360 and then now I'm going to set the stroke to that hue fault call at full brightness full saturation is that color changing I can't tell you oh it's definitely changing let's just draw the whole thing so this would just be total there we go look at that and now I just cannot resist 9 so this by the way is why it's referred to as a space-filling curve if the order of the number of iterations approaches infinity every single spot in this theoretical continuous space would be filled with a line how far can i push this oh look at that we go back to 9 there we go I will leave it at this I will leave this I believe this I'm done I've made this example I will also create a JavaScript version of this with p5.js and I will link that source code in the video description there's so many things you could try here and I would love for you to create your own version of this and share with me so there's a number of ways that you could share with me number one I haven't Kody train is a new discord so you can join the discord of link in this video's description there's a share channel where you can share your work and you can introduce yourself there's a page on the coding training comm for decoding in the Cabana videos where you can submit links to projects and there is the social media so the dot coding train on instagram at Schiffman at the coding korean on twitter please I hope you make something with this hilbert curve think about images and the hilbert curve think about other ways to color other ways to animate other ways to render this one idea that I have if you watch the three blue one brown video you'll see that each iteration each order of the curve interpolates from one to the other that's the animation that three blue one brown demonstrates how would you do that if you compute all the points for the first order and all the points for the second order third order could you interpolate between them more so to speak that I think would be a beautiful thing to try so many more possibilities I hope you enjoyed this video on space-filling curves the hilbert curve my pseudo-hilbert curve right here being rendered in processing for check out for the p5 JavaScript code and I will see you I don't have a catch phrase I've no way of ending these if you have a suggestion for a catch phrase just leave it for me in the comments thank you goodbye [Music] [Music]

Channel: The Coding Train

Views: 109,122

Keywords:

Id: dSK-MW-zuAc

Length: 28min 8sec (1688 seconds)

Published: Sat Feb 08 2020