Packing Algorithms & Collision Detection

[00:00:00]
>> So with the illustration of these concepts out of the way, I wanna make sure your brains are fully firing on all cylinders. So we're gonna go through some warm-up exercises. These are not actually ones that you're gonna be coding. But I am going to pause for a moment in between each and actually want you to spend a little bit of time thinking about writing, coding, drawing something, how you might tackle these kinds of problems.

[00:00:27]
So here are a few warm-ups that I want us to go through. The first one you don't actually need to code, but I just want you to think about in your mind. This is actually code, fun little story that my son wrote. I taught my son how to write this code.

[00:00:45]
I had to dictate a fair amount of it to him, let's be honest. But he's twelve, and he asked me one day, I don't even know how we got on the topic, but he asked me one day about binary versus base 10 number representation. And I said, this is a very straightforward algorithm for how you convert from binary to base 10 and vice versa.

[00:01:05]
And I learned it about his age, maybe age 13 or so. So I was like, let me explain the algorithm to you. So I explained to him the steps that you take, and we did it manually first, where he converted a number from, he just made up some ones and zeros, and then we figured out what the number representation of that was.

[00:01:22]
And then I was like, now that we've written out those steps, we could write that in code. And let me show you how to do that. So it was mostly me teaching him how to do the steps and then I helped him kind of figure out what code to write here.

[00:01:34]
But if we wanted to convert from binary to decimal, you can go back and take a look at the slides. The point of the workshop is not that code, but think in your mind, if somebody asked you convert binary to decimal and you didn't already have it, is the only answer, let me look for an NPM package?

[00:01:54]
Sometimes that's the right answer. I'm not saying that's a bad answer. Sometimes that's the right answer if it's something that we definitely know there's a lot of gotchas and we don't wanna trip over those gotchas and we just need to expediently get a good solid solution. Nothing wrong with looking for a good solid solution.

[00:02:12]
But sometimes being able to solve that problem yourself is useful, being able to translate a series of steps that you could do on pen and paper down into code, that's one of the key first steps to becoming a better algorithmist. So maybe on some free time, you might try your hand at this and then check your code against mine.

[00:02:31]
There's other ways of doing it, maybe you have a better way. Here's another problem. I actually stumbled across this one most recently. This one might look kinda strange. I don't know why, but in my social media feeds, these were popping up for a while. If somebody gave you a set of squares, you were told they were squares, and they said, how can you pack those squares into a larger square that is of the smallest possible size?

[00:02:56]
If we were thinking about this as a shipping container and this is 2D, we're looking at it from above, how would we pack these boxes into the smallest shipping container? Well, for four, that's pretty straightforward. You just do a two by two grid, that's the smallest. For nine, that's pretty easy, a three by three grid.

[00:03:16]
But what about for other numbers? And this is the question for 17 boxes, and you think to yourself, well, how would I make a square? It can't be a rectangle. How would I make a square? What's the smallest square container? You might think a five by five would be the smallest container, and then you just wouldn't use some of the free space.

[00:03:38]
But it turns out that you can rearrange things, and this, I think, is a 4.356 by 4.356 outer square. And at present, this is not proven to be the best solution, but it is the best known solution to the number 17 square packing problem. There are all kinds of other packing problems, by the way, packing of spheres and packing of other kinds of shapes.

[00:04:04]
This is a whole area of mathematics. But take a moment and think, if you were asked to write some code to figure this out, where would you start? And this is rhetorical, I'm not actually asking you where would you start, but I'm asking you to think about it.

[00:04:23]
Where would you start if the problem was, given n number of squares, how do I compute the best packing? Because that is a piece of software that I guarantee somebody has written somewhere, somebody's written for shipping, manufacturing, whatever. Somebody's written algorithms for figuring out how to pack stuff into the boxes.

[00:04:43]
Although, the junk that I get from Amazon doesn't look particularly optimized, so maybe that software does exist. But I just imagine somebody's got to have written the software to figure out how to pack things more efficiently. How would you do that if you were tasked with it? An algorithmist doesn't shun away from a problem like that.

[00:05:02]
I'll be honest with you, I don't know that there is code. It's not like I'm withholding the right answer from you. This is purposely trying to get your brain firing on those cylinders, to think about what could be a potentially pretty challenging problem, what are the first steps that you'd take?

[00:05:21]
Hopefully, in your mind, you're going back to the list of four techniques that I gave you at the beginning of our workshop. Hopefully, you're going back and saying I need to ask some questions. Is it any number? Is there a maximum number? [LAUGH] Even am I allowed to go outside of the bounds?

[00:05:40]
There's all kinds of questions that you probably wanna ask to clarify and go about this solution differently. You might ask, is it only two dimensional or do I also have to have an algorithm that works three dimensionally stacking on top? Cuz it might be very different if I had three dimensions to work with.

[00:05:57]
Asking good clarifying questions should be your first step. Probably step 1.b, if I went back and added a little step in between those, is pull out a pen and a sheet of paper, in this case, literally having a pen and a sheet of paper drawing out solutions. But you'd be surprised how often writing out your problem and drawing out your problem helps your brain to organize and get to those first few steps that you might start picking a data structure or picking an algorithm, just being able to organize things visually.

[00:06:32]
It is said, and I don't know whether it's true, but it is said that we're all born inherently with visual communication and visual spatial skills, and many of us unlearn those skills through nature and nurture. I don't know that to be scientifically factual, but I do know many, many people, including myself, who have been able to foster that skill.

[00:06:55]
It is a discipline that you can foster and build. And so if even if you're one of those who would never think to pull out a sheet of paper and draw something, I encourage you to try that. As an algorithmist, I think you will find that it will help you unlock and organize better.

[00:07:11]
Okay, let's move on to the next one. I'm gonna play this video in just a moment, but I wanna give you the problem. This happened to be, I had this problem on my mind, I had written it down, and then I just happen to experience this live having been done.

[00:07:27]
Here's the problem. Let's say that you're working with a geographic map and you see on here these icons, the multicolor with the numbers in between them. These various different icons that have been plotted onto this I'll explain in just a moment what the icons represent. But imagine if the problem was, at different zoom levels of this map, you need to decide whether or not to individually represent each one of those points of interest as an icon.

[00:07:54]
Or at what level of the zoom are points close enough that they should be combined into a single icon, just to reduce the visual clutter of the map? This is an extremely important kind of an algorithm, and there actually are real algorithms for this and you can go and Google them.

[00:08:12]
But if somebody asked you, hey, our map is too cluttered, when people zoom out to level 11, it's too cluttered, how do we figure out how to make it less cluttered? Dropping the icons is one answer, but merging the icons is another answer. It's a more sophisticated and more pleasing answer.

[00:08:29]
So as I play this, you'll see this was actually a map that I encountered a few weeks ago. And literally, I just accidentally found, you'll notice as I zoom out, there's pretty cluttered. Notice how they replotted those points and they start grouping them together. And the numbers go up as they've grouped them together, so they kind of indicate to you visually more of these things have been grouped together.

[00:08:53]
S, they're applying something like this algorithm in this map. Where would you start? How would you decide how to implement something like that? And while you think about that, I'll give you the backstory of the map. This is a map from a couple of weeks ago. I'm from Austin and we had a historic electrical outage after a historic ice storm, we don't get very many of those in Austin, Texas.

[00:09:17]
We had a huge ice storm and there was a ridiculous amount of power outages. I think something like 70% of the city was without power for prolonged periods of time, and some people, it took almost two weeks to get their electricity restored. And this is in a major metropolitan city.

[00:09:36]
Imagine the rural areas must have much worse. But this was the power outage map, and this was day 12, and there were still that many power outages on day 12 in the middle of Austin, Texas. So I just happened to see it, seem like a really good illustration of what I was describing.

[00:09:54]
But again, think to yourself for a moment, what would be the questions you would ask? What would you do if you were gonna draw it out to figure out, A solution? Where would you start? An algorithmist is not intimidated by hard problems like this. They break it down into smaller and smaller pieces, and they solve each small piece, and then they assemble it into larger and larger pieces.

[00:10:25]
I'll tell you one question I would ask, are all my icons the same aspect ratio? Right, cuz I'm gonna need to figure out where my icons overlap and if they're all circular or they're all square, or some of them are rectangular or triangular, I'm gonna need to use some different geometry.

[00:10:43]
So that's one of the first clarifying questions. At every level of zoom, are my icons the same or are they different? Here's another little algorithmic trick for you. This is more in, it's often used in game programming and things like that. We have this notion of what's called collision detection, which is, I need to know if two items are moving across, do they ever overlap?

[00:11:07]
Are they about to basically hit, like a bullet hitting a character in a game or something like that, right, something moving around? Collision detection, it's interesting and I'll just simplify this. If you think about a box that is the bounding box for some element and you wanna ask, does the bounding box of this element overlap the bounding box of some other element?

[00:11:32]
That's effectively how we do collision detection. And it would be similar here, there's some bounding box around these icons. And when I zoom out and I render my icons and their bounding boxes overlap, do I want to allow any overlap, or do I want to immediately merge as soon as there's any overlap?

[00:11:51]
Is it once they're 70% overlapped, then I need to merge them? Those are questions that we wanna ask. But for a collision detection, if you have two bounding boxes and they have x, y coordinates, this is in 2D, it's a lot easier, same algorithm works in 3D, but in 2D, it's a lot easier.

[00:12:08]
But you effectively have to ask eight questions to see if the x and/or y coordinate of any of the four corners is overlapped with the x or y coordinate of any of the other four corners of a bounding box. And by the way, more complex shapes are typically made up as a composite of several smaller bounding boxes.

[00:12:28]
Bounding boxes, the math is a lot easier. So instead of trying to literally calculate the intersection with a sphere, which is much more complicated math, you might just actually approximate it with a bunch of smaller boxes. But anyway, if I needed to know, is these two boxes overlapping in any way, you might ask directly, do they overlap?

[00:12:48]
And the answer to that requires you to basically do eight if statements. But here's an interesting observation that the algorithmist eventually comes to, which is, we can answer that question in the negation. And it turns out you only need four if statements to be sure that they don't overlap, and then you negate the result.

[00:13:09]
So it's more efficient and it's less code to maintain. To write the negation, I wanna know that they don't overlap and then I negate that to know if they do overlap. So again, thinking like that, that's part of what an algorithmist has to learn to do.