Coding Challenge #50.1: Animated Circle Packing - Part 1

hello welcome to a coding challenge my name is Dan I know I'm introducing myself at the beginning of this one because anyway but I can because I just did um this is a coding challenge I am going to build off of in some ways a coding challenge that I did previously and I want to look at animated circle packing and I want to look at animated circle packing in the context of forming letter forms look can I do all this in a coding challenge I think that I can I'm going to use processing which is a programming environment built on top of Java I will also hopefully release a JavaScript version of this so you can check this description for the source code after I bake this I'll release the code in both processing Java and also JavaScript using a p5.js library so circle pad King is one of these cut almost computational cliche algorithms in a way there's some images here from an artist named Marius Watts who does lots of beautiful and interesting engaging computational work and has worked with circle packing and the idea of circle packing is fit a lot of circles as many as you can of varying sizes in a small space or a large space and don't have them overlap so in order to do this the first thing that I want to do is I actually want to create a circle class so I'm going to say class circle and what does every circle have in my world every circle has an x and a y storing values for its center and every circle has a radius the distance between its center and the edge and then I'm going to need some other stuff that I just happened but I'm too you know for now I'm just going to put that there so when I make a class which is a template for making objects I need to write a constructor function and my constructor function will take three arguments because whenever and actually actually just two arguments let's just give it an X and a Y because whenever I create a circle I want to say create a circle at this look at a particular location and then X gets that particular value and Y gets that particular value now I'm doing something kind of goofy here which is that the arguments of the constructor I'm using I've been using the same variable name as the properties of the object itself but just with the underscore afterwards and what that does it allows to differentiate these temporary our constructor arguments to fill the actual variables of the object but you know it's kind of a confusing convention but it's one that I'm kind of used to so I'm going to use that here so what this means is now I can say something like Circle C and I can say I'm going to in processing I'm going to say sighs let's just say a 640 360 and in drama say background zero and then I'm going to say in setup C equals a new circle 200 200 and I can run this program and cut off I have a circle where is it I don't see it because what do I want to do I want to write up some functionality in the circle object itself hmm I'm going to call it show and then we use the ellipse function which is a function processing that draws a ellipse and an ellipse with a width and height the diameter across the horizontal and vertical axes of the same amount is a circle and what should that diameter be it's the radius times two so now if I said something like C display Oh any calls display I called it show ah ah where's that circle hmm I don't know why I don't see that circle interesting problem here ah why well R has what's the value of R the value of R is zero so let's give the value of our 50 right now and let's also be a little more thoughtful here and say stroke 255 and no fill so now I see there's my circle now you I don't know how well you can see this I can zoom in you can see it but I'm going to just increase the thickness of the line just because I don't know in terms of broadcasting this on YouTube and all that sort of stuff so you can see there's the nice beautiful lovely circle oh I love that circle that circle is my friend like I got to move on okay so what do I want to do now what I want to do now is not just have one circle I need a system where I'm going to keep track of many circles and a way I can do that in Java is using something called an ArrayList now oops I this syntax is a little bit goofy an ArrayList is an object that creeps that keeps a list of objects and I can say in advance I want a list of objects of type circle and that's what I'm doing right here and that list is called circles so now instead of having a single variable I can say circles dot push new circle and then I can say a for every and this is a nice little enhanced loop that you can write in Java these days with array lists you can say for I'm standing in front of this for every circle see in the ArrayList circles operate call the show function on those circle seats so for every circle call show okay here we go oh snap push it's not push it all this is me I'm the kind of person who programs in too many languages these days it's add push would be a function in JavaScript to push something into an array in Java using ArrayList the function is add so now if I do this we can see ah what happened I got a nullpointerexception see that null pointer exception that's the sound that goes the processing should play whatever you got to know upon your exception I forgot to actually create the ArrayList so I said oh I want to have an ArrayList but it's actually just null at this point so I need to actually take an additional step and say circles equals and new it seems rather redundant but this is the world of Java many people don't like Java but you know what Java is also my friend and I like Java okay so new ArrayList that means are something wrong with me then so be it okay so there you can see now I have this one circles oh boy what about like five minutes into this video and all I have a circle on the screen I hope you're still with me because this this will get more interesting okay so now I want to do I want to do a few different things one thing I want to do is I want to have a function in the circle called grow and what I'm going to do is I'm going to say R equals R plus 1 so I want the radius to increase by one pixel whenever I call the grow function and I'm going to say now every circle see grow you can see that circle is growing now the other thing I want to do is I want to stop the circle I want to have a way of stopping the circle from growing so one thing I should do is I'm going to write a function called edges to see has the circle touched an edge of the window and actually if it has I should maybe I should return a boolean true or false we could do this in a bunch of different ways but let's start with this so how do I know if a circle and let me just come over to the whiteboard here look there's a happy party time so right if this is a the window and this is a circle if the X plus the radius is greater than the width of the window or if X minus the radius is less than zero then it's kind of hit that edge so let's come back and add that if what I say X plus R is greater than width or X minus R is less than 0 or y plus R is greater than height or Y minus R is less than 0 that should do it and actually I could just say return that this is one of these shorthand things that I never use and people always complain in the comments like you're going to just return the result of that so I'm returning the result of this or that or this or that so if any of those are true I'm going to return true so what I'm going to do here is I'm going to say I'm also going to add a variable I'm going to call it growing I'm going to set it equal to false no true and I'm going to say if growing increase the radius by one okay this is good this is good this is good now I'm going to write a function let's uh there's a bunch of different ways I could do this but let's do it actually out here I don't know if I love this but I'm gonna say if C dot edges see growing equals false so this should stop and what did I find missing a semicolon here because I have this like ridiculously long line of code that is very unwieldy to type but it's come back now this should now grow the circle until it reaches the edge and you can see why did it stop it touched the bottom edge down here so this is good I now have a circle that can grow and a circle that can stop growing and what I want to do is I want to add new circles every time through draw and I want to give it a random location so I'm going to create a new circle at a random location and I want the circles to all start not with a radius of 50 but a radius of 1 and watch what happens out so I have all these circles ooh that's kind of actually just nice on its own they're all growing and they're stopping as they reach the edge but let's watch that again let me slow down the framerate what I want to see happen is I want all these circles to grow but it also want them to stop growing if they touch another circle and I don't want to be able to create a circle inside of another circle because I want to have these circles kind of grow to fill as much space as possible okay so how do I do this so the first thing that I need to do is um I don't know what is the first thing that I need to do do you don't want to do I'm going to I'm going to I'm going to create a function called new circle and I'm because I have a feeling this might get a little bit complicated so what I'm going to try to do now here is what I'm going to create a random XY then what I want to do is say for every circle in all the circles what I want to do is determine when I click this XY is it a point that's outside of circles right I don't want to by accident these are my circles if I pick that point it's no good if I pick this point we're good shape so what I need to do is I need to check what are we twin time works okay I need to say what is the distance between this X Y and that circles X Y if the distance is less than that circles radius then it is inside the circle so let's assume that this is a valid circle if I look at all the existing circles and it's inside one of them it's no longer a valid circle and I could also be done with that loop if it's not valid I could just check one of them now what I want to do is if it's valid I want to add it to the ArrayList so I only want to add circles that are valid and you can see now if I run this again you know it's everything still overlapping but technically speaking it's not you can see it's not adding any circles anymore until it finds a spot that's not inside another circle I like this but actually I think what might make more sense here is to return a return a new circle otherwise return null so and then this is going to be a function that returns a circle so what I want to do is I want to say like this is this function is going to attempt to find a new circle and if it does here it is if I can't find one it's no so what I'm going to do now is I'm going to say Circle C equals new circle if C is not equal to no circles add C so now I have oh and you know what I'm going to just call this circle I'll call it new circle oh that's a little bit awkward that I have new circle in the new circle function let's just call it new C it works but you know when we translate this job okay so this is working this is exactly what I just had it's trying to make these circles now I need to add the part where if it touches any other circle it also stops growing so for every circle if it's touching an edge it stops growing so first of all I only want to do this if the circle is growing if the circle is growing check first if it's touching an edge otherwise now I got a look at all the other circles again and I can say boolean overlapping I can assume that it's not overlapping another circle I can assume that it's not overlapping another circle now what I can do is I could say the distance between this particular current circle and the other circle I need that distance if that distance is less than what if that distance is less than this circles radius plus the other my scroll went under control plus the other scrolls the other circles radius then overlapping is true why is that come over here with me please because here's a circle here's a circle here's one radius here's another radius here's the distance between them you can see that if the distance is longer than the sum of the two radii then they're not overlapping if that distance is shorter than adding the two radii together they are they are overlapping so now all I have to do is actually don't need this overlapping variable I just realized because the point of this is I can say if it's overlapping anything tell it to stop growing and break so this is now my algorithm right if a circle is growing there are two reasons why I might stop it from growing one is it might be touching the edge otherwise it might be overlapping with another circle so if either one it should stop so now let's run this and see what we get mmm seems to me that these circles aren't growing ah what did I oh my goodness I like to ring the bell when I discover a really ridiculous bug look at this for every circle see check every other circle called other well guess what see is going to check every other circle and you let's see is it's one of those every other circles so I need to also make sure as long as C does not C does not equal other as long as it's not the same object then I can do this test there we go so now we can see here we go I'm just filling this space and you know it made some big circles at the beginning now it's making some smaller ones because it keeps trying to find more spots where it could possibly fit a circle and we can let this run and eventually it's going to do it now we could say we could we could do some stuff to make this a little fancier so but here's the thing this is a pause point me to do something more of this in a second because I want these circles to form a letter or a shape but what I could do here is I could start to think about well what are some ways you know should I only start the circles where the user clicks the mouse should I start the circles along a sine wave pattern should I start the circles like you know randomly what types of what kind of color what type of rules should I apply to when and where I start the circles and you could probably create more geometric kinds of interesting pattern so I would go with this go forth and make your rainbow circle packing magic and maybe fingers what other you could animate the circles one of things could do besides just drawing circles this idea of filling a space but one thing I do want to do a couple of things here is you can see like that overlapping is a little bit awkward so I think I probably could kind of clean that up by saying like because the the pixel width of those circles is too so you know I could probably oh and the other thing is Oh a - - I mean so you can see this is making it a little bit better so the circle is actually kind of like stop and abut each other a little bit sort of depends on the size but so we could refine that and you know that also like I could probably have the circle grow a little bit slower and then it gives it a little bit more resolution in terms of how close it gets but these are these are smaller points the point that I want to actually do is I think that I think they'll be useful to add is I want to let's say I want to I want to make sure I add 10 new circles every frame so I'm going to say count equals zero and while count is less than total whoops create a new circle if new circle is not no then count goes up and then we're done so this would guarantee that it's going to like keep trying to find more circles every frame up to ten the problem with that you can see it's filling it much more quickly the probably this is it's going to get stuck at some point an infinite loop is it simple it's not going to be able to find ten new spots anymore because the whole screen is going to be full so what I think would make sense to do in that case would be to have some sort of like I'm going to also have a variable called attempts I'm going to say a temp attempts plus plus and if attempts is greater than 1,000 then just let's be done you know I can even say like no loop so I can completely stop the program from running and I can say you know print line finished so this is just sort of like useful say like oh if it took a thousand tries and couldn't find any spots for the circles then it should be done we can kind of zoom in and see what this is doing it's still finding more spots at some point it's going to stop finding spots I'll let this run for a little bit okay so while this is running I'm pretty sure that I did this correctly he's like waiting for it to say finish down here in the console but while this is running let's go and let's let's add one more thing to this Wow I guess it's still just finding spots it's not done there's just so many spots left okay it's really filling it in there the other thing I could do is I could start the circles with like a little bit of a radius like not one but like two anyway but okay all that's neither here and there you can tweak them you can tweak the stuff yourself but I assume it will get to finish at some point what I want to do right now is I have on my desktop here is I have this image and what one trick that I can do so there's a couple different ways I could decide there's a lot of different ways I could decide where to seed the circle points one way that I could do that is like it's a I'm going to have a source image I'm going to read the pixels of that source image and only ever going to be allowed to start circles where there's a white pixel in that source image and that's what I'm going to do right now to make this 2017 message replace it with your own message later okay so let's see is it still going oh I stopped it okay so let's let's do this and I'm going to say this as circle packing animated text and I'm going to ups I'm going to go to the sketch folder I'm going to create a folder called data and I put this 2017 PNG in there what is the size of that image is important the size of that image is 900 by 400 okay so let's make a the window also 900 by 400 let's say a P P image image if I'm going to say image equals load image 2017 dot PNG and then I'm going to just say background just to make sure that image is there we can see the images there now 2017 I'm drawing circles on top of it yay okay so now what do I do here what I want to do is I need to say image load pixels because what am I going to do I'm going to read the pixels of that image then I'm going to say 4 into X equals 0 X is less than image dot with X plus plus 4 int y equals 0 Y is less than image dot height y plus plus what I want to do here in setup is I want to have a nested loop a loop that looks at every single pixel I want to know is the pixel white or black so how do I look at the pixel well the pixels by the way even though I'm thinking of them as XY locations they are just a linear list 0 1 2 3 4 5 6 7 8 9 all the way up to 900 times 400 minus 1 but and I have some videos that cover how this sort of pixel stuff works but I can find the index into that pixel array the one-dimensional pixel array by saying the X location plus the Y location multiplied by the images with you can think about that makes sense if the image was 5 pixels wide it's going to be 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 right 0 5 10 so you can sort of see how that works it's the row plus no it's the column plus what row it is times the width of those columns okay so now I'm going to say the color is image pixels index and then the brightness I'm just gonna look at the brightness of that color if the brightness of that color is greater than I don't know 1 then I've got a white pixel right I could say if it's greater than 254 probably but in this case this was kind of a really simple test if it's greater than what am i standing in front of my code all this time oh okay if it's greater than 1 oh boy this video hope it's not totally ruined if it's greater than 1 then I found a bright pixel so what do I need I want to have an ArrayList of spots and those spots I want to have a list of possible spots that the that the circle packing algorithm can pick from and each one of those spots is essentially a vector processing has a class called P vector that stores an x and a y so what I'm going to do is I'm going to say right before I do this I'm going to say spots equals a new array list full of P vector objects and if the brightness is good spots add a new P vector at that X&Y location todo spots out add a P vector at that X&Y location so now if I run this I'm just going to say print line spots dot size OOP Y may not have been initialized whoops that should be a zero so great so this looks like it worked it found 77,000 759 possible spots so now what can I do here here instead of creating a random x and a y anywhere in the window what I want to do is say I want a random number that is between 0 and the length of that spots ArrayList so the random function gives me a random number between 0 and the length of the list and I want to convert that random number into an integer because I want to use that too as the index to get me a particular spot out of that ArrayList and now I can say X is spot that x and y is spot dot Y and now if I lo what did I miss I guess I just need one more close parenthesis now if I run this oh whoops I ruined it by drawing the image so let's stop drawing the image and we can see there we now have our circle packing algorithm but it is only picking as original spots spots that are that are available in the actual as part of those white pixels from that source image so you can see we have this nice circle packing I'm still finding spots because hold on a sec let's let's let's be a little bit more let's say that it has to be the valid spot has to be um it doesn't have to just be the distance between it and the center has to be less than the radius plus like a little bit of buffer zone like two pixel buffer zone so that I think will cause it to finish you can see there's lots of ways I could futz with like what it's actually going to like what if I just want one circle each frame it's going to pick circles much less frequently and so the circles are going to have a longer time to grow and again you can start to think about color here how you're picking the circles when you're picking the circles you know not being able to pick the same point twice will probably make a lot of sense and here we go animated circle packing making letterforms now this is the end of this video coding challenge thank you very much I hope you make something creative with it you think of a message you think of some other type of pattern you think about color animation in a different way share it with me all that stuff but I do want to say is I am using a source image to find the paths of these letters which is great in the sense that you could use a source image not just to do letters or numbers you could use you know painting and then do circle packing to like fill a space with colors from the painting there's also two possibilities there but one thing I do want to look at and perhaps in a future coding challenge may give you in the next one is how to actually compute these paths of how to actually get these paths of letters dynamically in a program so the user could type in the word hello and then suddenly you could fill a circle packing space or whatever with that with that particular word I'm going to look at that in javascript in the browser because p5 has some nice functionality for that you can do in processing also with the library called jammer tip which I'll try to link in this video's description but that's how you might look for okay so thanks for tuning in to this coding challenge i back it's 2017 i've made a coding challenge i think things are still ok people will hopefully watch this hope we make something with it and talk to you soon goodbye [Music]

Channel: The Coding Train

Views: 242,278

Keywords: live, programming, daniel shiffman, creative coding, p5.js, coding challenge, p5.js tutorial, p5js, javascript (programming language), tutorial, javascript, algorithms, processing load pixels, coding, challenges, circle packing, processing pixel, processing loadPixels(), circle packed letters, circle packing words, circle words, processing pixel analysis, processing java circle packing, java pixel analysis

Id: QHEQuoIKgNE

Length: 28min 32sec (1712 seconds)

Published: Mon Jan 09 2017

Reddit Comments

[u/ademirtas]

Part2 https://www.youtube.com/watch?v=ERQcYaaZ6F0