AI - Circle Packing
This comment was split from the discussion: NodeBox and AI
EDIT: i split this comment in 2 parts
Hi John,
Thanks for starting this topic. I went ahead and tried to make a packing script. The results can be found in the attachments. It still has its quirks, so it probably could be improved upon, like a wrapper to make it more user-friendly, but this way it's a little more visible what is happening. I also found that the result is not static (rendering different nodes within the same branch, like before and after the groupings).
Here's the prompt I used as a starting point.
Can you generate a Python 2.7 script for circle packing for use in Nodebox 3 based on the documentation provided? It should have different sized circles packed within a certain rectangular bound. Don't use any external libraries. Please specify the type of input per argument (float, integer, etc.)
- Make arguments for X and Y, which are scattered point coordinates. The amount of points is the maximum amount of circles.
- Make an argument for padding: the space between the circles
- Make an argument for the size of the radii. This is a list of values within a range with steps of 10 between each value
- Make arguments for both the width and the height of the bounds.
Begin with the largest circles and end with the smallest circles. For each circle size, attempt to insert new circles in the spaces between until you hit the maximum amount of circles. Once the count limit is hit, move on to a smaller size.
Output a list of the necessary sizes in the same order as the points are which were used as input. This should create a properly packed arrangement of circles.
This a selection of what Claude came up with (I also did tests with Gemini and ChatGPT, but the results were less good). The first 2 fragments is the description of circle_packing.py script.
This enhanced algorithm uses a three-pass approach to maximize circle placement: First Pass
The algorithm attempts to place circles starting with the largest sizes, working down to smaller ones. This is similar to the previous version but serves as a foundation for the next passes.
Second Pass (Key Improvement)
For each point that doesn't yet have a circle:It calculates the maximum possible radius that would fit at that point without:
Extending beyond the rectangular bounds Colliding with any existing circle
It then places the largest possible circle at that point (rounded to the nearest step size), even if it's smaller than what we initially tried in the first pass.
Third Pass As a final sweep, it tries to place the minimum-sized circles at any remaining points. This ensures we make use of even the smallest gaps.
Additional ImprovementsDynamic Sizing: The second pass is the major improvement, allowing circles to be sized exactly to fit available space rather than using predetermined sizes. No Wasted Points: By adapting circle sizes to the available space, many more points should get non-zero radii.
Boundary Awareness: The algorithm carefully checks edge conditions to prevent circles from extending beyond the width/height bounds.Tips for Best Results
Input Point Distribution: The algorithm works best with a relatively even distribution of points. If you're using scattered points, try using a larger number with a good spread. Parameters:
Use a smaller step value (e.g., 2-5) for smoother size transitions Start with a smaller padding value (0-2) and adjust as needed
Make sure max_radius isn't too large relative to your boundsThe key differences in this aggressive approach:
Center-First Placement: The algorithm sorts points by distance from the center of the canvas and places circles starting from the center outward. This creates a more visually balanced result and often leads to better packing in practice. Direct Radius Calculation: For points without circles after the first pass, the algorithm directly calculates the maximum possible radius that can fit without any collisions, rather than trying to fit into predetermined size buckets.
Exact Sizing: This version places circles with exact calculated radii rather than rounding to the nearest step size. This ensures we're making the most efficient use of space.
The enhanced algorithm from Claude has resulted in the circle_packing_dense.py script
This enhanced algorithm includes several significant improvements to maximize packing density: Key Improvements:
Grid-Based Initial Placement: The algorithm starts by placing larger circles in a grid pattern. This creates a more even distribution of larger circles and avoids the common problem of random placement leaving awkward gaps. Space Score Ranking: Points are ranked by how much empty space surrounds them - prioritizing points in larger open areas for each radius size.
Adaptive Radius Selection: The algorithm dynamically adjusts circle sizes based on available space, maximizing the use of every potential point.
Multiple Strategic Passes: The implementation uses multiple passes with different strategies to ensure comprehensive packing.
Debug Information: Added output to show how many circles were successfully placed.Tips for Best Results:
Parameter Tuning: Smaller padding: Try setting padding to 0 or a very small value (0.5-1.0) for maximum density
Smaller step size: Use a smaller step (2-3) between radius values for smoother size transitions
Appropriate min and max radius: Make sure the radius range makes sense for your canvas sizePoint Distribution: Provide plenty of input points (2-4× more than the number of circles you expect)
A uniform distribution with slight randomness works best
Use a scatter node with a high amount settingCanvas Size: Ensure width and height values make sense relative to your radius settings
A good rule of thumb: width and height should be at least 10× your max_radius
Floris
Schermafbeelding_2025-04-16_om_21.33.24.png
Keyboard shortcuts
Generic
| ? | Show this help |
|---|---|
| ESC | Blurs the current field |
Comment Form
| r | Focus the comment reply box |
|---|---|
| ^ + ↩ | Submit the comment |
You can use Command ⌘ instead of Control ^ on Mac
Support Staff 1 Posted by john on 16 Apr, 2025 11:14 PM
Floris,
Circle packing is a GREAT idea - another one I've been meaning to tackle for ages.
I haven't yet taken a close look at either circle_packing or circle_packing_dense. But before we go any further I made a few simple modifications that should save us both a little time (attached).
I wish the Python code would handle the culling of dust itself, but if that proves difficult we could move that culling into a wrapper subnetwork. We could also either change the module or the wrapper to output diameters instead of radii (multiply by 2).
But before we go there it seems like we need to do more fundamental thinking about the algorithm itself: what you should feed into it and what you should get back.
As I said, I haven't even looked at this yet or done any research but I have two problems off the bat:
Thanks again for launching another AI adventure. I think this will make an excellent test case and probably another great node.
John
Support Staff 2 Posted by john on 17 Apr, 2025 05:54 AM
Floris,
I took a nap and then did a little research. Some thoughts.
A few more problems with the current approach:
In addition to the usual Wikipedia articles, I found two particularly good links that describe the kind of thing I'd like to do:
https://mathematica.stackexchange.com/questions/40334/generating-vi...
This starts with a gallery of all the things I'd love to be able to do, and then breaks the desired outcomes into multiple problems with algorithms and code snippets. Perfect!
https://www.tylerxhobbs.com/words/a-randomized-approach-to-circle-p...
An essay on this very topic from none other than Tyler Hobbs. He gives a rough sketch of the approach he uses.
I have not yet studied this in depth, but my initial take-away is that we might want two nodes:
Node 1 (pack_full?) would seek to fill an arbitrary shape with as many circles as possible given a min circle size (target), max circle size (target), and minimum padding.
Node 2 (pack_values?) would seek to fill an arbitrary shape with a defined number of circles of proportional sizes.
I gather this is not the kind of thing that can ever yield a precise final solution. Instead, you must iterate to some defined limit and then quit at that point. So we may also need to supply a time limit or limit on the number of iterations.
So here is my first cut at parameters.
Pack_full:
Pack_value:
In both cases, I think the node should return actual circles (ellipses). This will save us the bother of converting centroids and radii into circles ourselves.
I really think having any closed boundary shape is possible and highly desirable (see the cool shapes in that first link). As a torture test I'd like to be able to fill any textpath (e.g. a lower case a) with circles. But if that proves too hard, we might fall back to, say, any polygon (closed shape with no curves), or even any convex polygon. That would still allow us to resample many arbitrary shapes and use, say, a 100-sided regular polygon to serve as a proxy circle for circle-within-circle packing.
We might also consider adding a color list input to color the circles at some point as a convenience, but that could be handled in the wrapper subnetwork or done after the fact, so let's not worry about that for now.
It might be possible to combine these two nodes into one, by only using min and max circle inputs if no value list is supplied. But I think these two functions may require different algorithms and asking Claude to do both at once might trigger some kind of AI uprising. Anyway, that's another thing that could be handled with a single subnetwork wrapper calling one of the two Python-based nodes.
I'm not sure how unreasonable all this is. I do think it's possible but it may be a challenge getting Claude to meet these specs. My approach, however, is always user-centered: understand what the user needs and then build a solution to that, not do what's easiest for the computer and make the user adapt to that.
Please look at these links and see if you agree with my proposed specs. Feel free to provide other use cases, links, or constraints. This might take even more than 15 iterations to get right. Are you up for the challenge?
John
3 Posted by florisdejonge on 17 Apr, 2025 07:13 AM
Hi John,
I'll get back to your second comment. But in regard to the first one and some of the questions you raised.
Floris
4 Posted by florisdejonge on 17 Apr, 2025 03:50 PM
Hi John,
I had some time to read and ponder you second response.
I did come across Tyler Hobbs’ article beforehand and I did use some elements in my prompts, especially the steps of the algorithm. Based on this I also added an argument for maximum amount of attempts and I do have some prototypes of this scripts (the total amounts easily to 15 different ones btw), but Nodebox seemed to interpret this as frames. Therefore it was not a process within the algorithm that would give better results, so I scratched that.
The suggestion to let the algorithm decide where to place the points, as illustrated in the other article, is interesting though. Especially dealing with packing in irregular shapes. Your suggestions for parameters help in that direction.
In regard to the custom nodes and its output. I am still learning how they work. There seems to be a lot of possibilities hidden. It is possible to combine two algorithms in one script, I have seen the generated examples. But I think you have to call them in separate custom nodes, or is that what you can fix with a wrapper, with like a switch? In addition, I wasn’t aware one could output a list. But now your also suggesting the script could return the actual geometry, is that correct? Do you have an example of that - within your library perhaps? That would help in next attempts.
Floris
5 Posted by florisdejonge on 17 Apr, 2025 06:49 PM
Hi John,
Here is the result of another step which I took based on your suggestions. I think were making progress.
This was the prompt I gave to Claude:
And its response:
It also gave the suggestion to add Force-directed packing:
Now I am out of messages again. So this is the result for now. I still could not figure out how to elegantly make the output work better without clunky extra nodes. Looking forward to your response.
Floris
6 Posted by florisdejonge on 17 Apr, 2025 06:52 PM
Something seemed to go wrong with the attached files. This is another try to upload them.
Support Staff 7 Posted by john on 17 Apr, 2025 07:02 PM
Hi Floris,
I have to run in 3 minutes, so will read and respond later today.
But you can look at contours.py for an example of how to return a path (like a circle). The trick is to import the path function from Nodebox:
from nodebox.graphics import Path
def contours(path):
return [Path(c) for c in path.contours]
In that case we pass a path and get a list of contours back.
in convex_hull.py we import Point from Nodebox and return Nodebox points.
Or look at the bounds function in image.py. Returns a rectangle path.
make_curve.py returns a curve in a similar way. An ellipse is just four curves. I can't seem to find a case where I returned an ellipse, but I'm sure it's possible using a similar approach.
Thanks for all your work. More later!
John
Support Staff 8 Posted by john on 18 Apr, 2025 04:22 AM
Floris,
We are indeed making progress!
Attached is a revised version of pack_values that now seems to be working pretty well, with some improvements added to the Python code by hand:
I forgot to mention the seed parameter in my earlier spec. Just as with noise_loop the seed is essential; without it the node would return a different solution each time you hit reload. Fortunately it was easy to add by hand this time.
It took some trial and error, but I finally figured out how to make the Python code return circles instead of centers and diameters. You can look in the code to see how I did it. The Path.ellipse function adds all the circles as separate contours in a single path so I had to separate out the contours before returning it. There is probably a cleaner way to do this, but the code works so I'm declaring victory.
I also changed the node type in Nodebox to geometry (black) and added a comment.
The attached demo shows a circle and a letter a as boundaries. I also added a heart filled with hearts to demonstrate that you can easily retrieve the centers and diameters from the circles if you need to.
FURTHER THOUGHTS
I also added circle counts below each boundary. In the current configuration I am sending a list of 200 values, so ideally there should be 200 circles (or hearts) each time. But as you can see, this is not always the case.
At 2000 Max Attempts the circle boundary only held 199 circles. I was able to get the last missing circle by raising that value to 2500.
The letter a, at 2000 Max Attempts, only contains 195 circles. You could get this up to 200 if you decrease padding to 0.
The hearts only holds 175 circles, and that was even after I increased Max Attempts to 5000. I tried increasing Max Attempts to 10000 but that only added one extra heart.
The moral of this story is that you are not guaranteed to have every value in your list represented. Depending on the boundary shape, seed, padding, and Max Attempts you may fall short, and in some cases there may be no way to cover all the supplied values.
This is probably not too much of a problem for generative art (as long as you are aware of it). But for information visualization, it could be a serious shortcoming. One area of future research might be to ask Claude for an algorithm that could guarantee every value is represented (i.e. that the number of circles produces always equals the number of values supplied).
You may also notice I removed the force-directed packing alternate node. I played with it for awhile and, despite Claude's insistence that it produces more aesthetically pleasing results, I couldn't really see that much difference. And it's more complicated with more parameters to confuse end users. If you don't like one arrangement from pack_values you can just keep changing the seed until you get something better. So that seems good enough to me - would you agree?
The node is a little slower than I'd like; it starts to drag if you feed it more than a few hundred values. But that seems to be the nature of the beast, and a few hundred circles per boundary is enough to produce many interesting projects.
NEXT STEPS
I would still like to see a pack_full node (with the addition of a seed and the ability to return circles) that just needs min and max circle size and provides as many circles as needed to fill the available boundary. Pack_values gives you more control, but you have to adjust the number of values to fill a given shape in a pleasing way. It would be nice just to fill whatever shape you give it with no adjustments or value list needed.
But if this is hard I think we could live with what we have now.
As I said above, it would also be nice if the node could guarantee that every value was represented. I think it's worth asking Claude if he can do that. But again, we can do a lot with what we already have.
Other than that, I think we should just play with the attached node and see if it really does meet our needs.
I must say, I am again impressed by how quickly we arrived at a workable solution. I was afraid this might be too hard for Claude. He still needed help returning circles, but I can't really blame him for that.
I look forward to your reaction!
John
9 Posted by florisdejonge on 18 Apr, 2025 06:10 AM
Hi John,
Thanks for the reply and the improvements. The seed was necessary as a requirement in my regard, you don't want to change the design when you close and open the file again, so its great you were able to add it. But the design/script still seems to reload every time, is that correct? That would make it impossible to replicate a design based on a seed number.
If that would work as intended, I think the challenge has been completed. This result is for me good enough to use and has unlocked a lot of possibilities. I like the use case of the hearts by the way, it demonstrates nicely what also could be done. It's fast enough as far as I'm concerned, I have way slower networks.
The force directed solution doesn't seem to add much visually indeed, but I got the impression from the description this could lead to animation applications (moving circles, which in my mind look like the network graphs from Gephi). That would be cool, but not plottable, and there are other possibilities for moving circles, so I am not that interested in that. The same accounts for data visualization applications, since I mostly use Nodebox for generative art/design.
I do like the suggestion to see if a full_pack node is possible, since it could be a little easier in use. I have to take a good look at how geometry is generated in the script and how to call it from a custom node.
As far as I am concerned, were going up to the next challenge (Voronoi?) or would you want to pursue fine-tuning this one?
Floris
10 Posted by florisdejonge on 18 Apr, 2025 06:33 AM
I was worried about the seed function. So I asked Claude to fix it to maintain consistent across node selections. Looks like it did a good job. Attached is an updated script.
Support Staff 11 Posted by john on 18 Apr, 2025 08:21 AM
Floris,
I'm a tad confused by the seed issue. I tested my version repeatedly and each seed number I tried reproduced the same pattern of circles. Changing to a different seed changed the pattern; changing it back again restored the previous pattern. I even tried quitting and relaunching Nodebox and comparing the patterns to the screenshot I took earlier.
So I could not find a case where the pattern ever changed with the same seed. Did you find such a case? There's probably something I don't understand. Random numbers are notoriously tricky.
But in any case, the new version seems to work just fine, If you and Claude are happy, then I am too.
One thing. You attached the same zip file twice. The folder contained only packed_values_seed.py, but the ndbx file wanted both packed_values.py AND packed_values_seed.py and so wouldn't open until I edited the file. Also the name change of the .py file conflicts with the reference in the node comment. Madness reigns!
I was also thinking we should change the name anyway, especially if we are going to declare victory and move on. So I'd like to change the name of the node (and the comment and the .py file) from pack_values to pack_circles. I only suggested pack_values to distinguish it from a second node (pack_full). But if we are only going to have one node, pack_circles will be more descriptive of what it actually does. The node packs circles, not values.
SO, I went ahead and renamed everything. I will formally publish the node separately after a little more testing, But until then I suggest that everyone who wants to play with this use the version attached to THIS post:
I even redid the screenshot. All attached.
And yes, if you don't want to explore any more variants of circle packing then, by all means, feel free to tackle Voronoi next. Please start a new thread for that.
And thanks again for ushering in the dawn of a new era!
John
Support Staff 12 Posted by john on 19 Apr, 2025 06:56 AM
Hi Floris,
I think we have a good working baseline circle packing node now. And I know I said feel free to move on in my last note. But I'm starting to play with it and now I think we might all benefit from a few more experiments.
Two issues...
1 - Reliable Output
I still think it's an issue that the current node can't guarantee that you will get circles for all the values you give it. This is obviously a major problem for people doing data visualization; your response was that as a generative artist you weren't particularly interested in data visualization.
Fair enough. But I'm already finding situations - purely as an artist - that not having a reliable count of circles is a hinderance. I want to play with different configurations of the same number of circles in the same container. But this breaks if those configuration lists don't have the same number of items. I want to be able to freely step through different seeds without having things break downstream. So I'm already seeing that not having a reliable output is a problem for artists as well.
I am also just curious. How easy would it be for Claude to solve this problem? Would Claude have to switch to an entirely different approach? Would the resulting output still look the same aesthetically? Might it be even better? No way of knowing unless we try,
2 - Absolute Boundaries
One of the first things I thought of making was a bubble gum machine. Are you old enough to remember those? A bunch of colorful gumballls held inside a glass globe?
But here's the problem. The current node defines containment as any circle whose center is inside the boundary. It doesn't matter if part of the circle pokes out beyond the boundary,
This is fine for some applications. But sometimes I want my circles to respect the boundary absolutely. I don't want any gumboils sticking outside the globe. So again I wonder: how hard would it be for Claude to fix that problem? "Make a version of the current node where no part of any circle can protrude beyond the boundary".
One way of doing this would be to add an extra test. If the shortest distance from a circle's center to any point on the boundary is less than the circle's radius, that circle is no longer considered inside.
If Claude could do this, it would be interesting to see what effect it would have on the overall output. Would it make it even hard to achieve full coverage (see issue 1)? Would it cause a significant slowdown? Would the resulting packing patterns look noticeably sharper? No way of knowing unless we try.
For both of these issues, if we get interesting results we could possibly package them as separate nodes inside a single wrapper subnetwork, with a check box that said "Absolute boundaries" or "Guarantee full coverage" or something.
As I start to play more with circle packing I'm coming to realize that this is not an all-or-nothing thing. There are all sorts of different ways to pack circles, each with its own pros and cons. I don't think we've fully explored these possibilities yet.
What do you think?
John
13 Posted by florisdejonge on 20 Apr, 2025 10:11 AM
Hi John,
I agree that we should explore possibilities further. After some testing making a penplot design, I found it takes quite some work-arounds to get the circles to actually not overlap with the boundaries. In addition, I think that giving it an exact number of circles or specific mininum and maximum sizes would be more intuitively.
Floris
14 Posted by florisdejonge on 09 May, 2025 08:27 AM
Hi John,
It took a while (I got sidetracked into other AI-penplot applications), but I continued the development of the circle packing node. You can find the example attached. It's based on your earlier demo. This file contains, aside from the earlier version, 3 new examples.
The first one needs improved_pack_circles.py. This forces the circles within the boundaries. The argument 'ensure all fit' is a boolean, but I think it's on by default, so I don't think we actually need the control. This is what Claude gave as a description
The 2nd and 3rd example needs improved_pack_circles2.py. It uses a fixed amount, which can be based on the input range or seperately set. I found the max_attemps ought to be set higher to get a similar packed result, making this a little slower. And again, some notes from Claude.
Looking forward to your respons,
Floris
Support Staff 15 Posted by john on 11 May, 2025 02:07 AM
Floris,
First of all, thanks for sticking with this. I think we are making steady progress and may in fact have reached our goal.
I was a little confused by the demo. It wouldn't open because the original pack_circles.py, needed by the first of your four new examples, was not included. So I just disabled that example.
Also the demo contained not just the four examples shown in your screenshot, but my previous three examples - except that those three had been modified to use improved_pack_circles. Took me a little while to figure all that out.
So let's just focus on the last three of the four new examples shown in your screenshot, which I'll call example 2, example 3, and example 4.
Let's see if I've got this right:
I played with these for awhile and came up with the following observations.
ENSURE ALL FIT CHECKBOX
For example 2 at first it looked like this had no effect, but if you get the right seed and padding you can find examples where it does make a difference. I thought that checking this box might reduce circles that were two closely packed, but the reverse is true: if you check this box it may add a few more circles that just barely fit the padding requirements (without affecting the previous circles picked).
So I gather from Claude's comments that what this does is try even harder (up to 5x the original max_attempts). If you're lucky this might yield a few more circles in the current configuration. You can get a similar effect by just increasing the Max Attempts - though that would change the configuration.
At first I thought this setting was not even used in improved_pack_circles2 since it always returned the exact number of circles requested. But I looked at the code and discovered that this setting DOES matter IF Max Attempts is less than about 10.
Improved_pack_circles2 guesses at a circle size proportional to the values that it thinks will fit, and then reduces that by 15% each iteration. This means that if you only have a few iterations the circles may not shrink enough to fit. But after 10 iterations the size is already down to about 20% of the initial guess - which usually seems be enough. After 20 iterations the circles are less than 4%, at 30 iterations less than 1% of the initial guess size.
This means that, for improved+pack_circles2, Ensure All Fit will probably never be needed if Max Attempts is set to anything over 20. Even at 1000 circles 20 iterations only takes a few seconds, and the results are rather poor, so I don't see much reason users would ever want to set Max Attempts to less than 20.
Leaving this option checked does not seem to noticeably degrade performance, so it's safe to leave it checked.
Conclusion: exposing this option is dubious for example 2, unnecessary for examples 3 and 4.
EXACT COUNT
Based on my experiments, here's what this seems to do:
Conclusion: all this does is slice the value list, which is not terribly useful. I think it would be better if it served as an alternative to the value list. We could let users EITHER supply a value list (in which case Exact Count would be ignored) or skip the value list and just return a number equal sized circles defined by Exact Count. I could do this easily with the existing node by wrapping it in a subnetwork.
MAX ATTEMPTS
The number of attempts needed for a good result will depend on the container shape, the number of values, the padding and the seed. For example 2, more attempts may slightly increase the number of circles. For examples 3 and 4, more attempts may increase the size of the circles (wasting less space within the container).
Of course, the higher you set this number, the longer the node will take.
I found that a value between 1000 and 2000 max attempts produced a fairly decent packing in most cases. Cranking that to a higher value (like 10,000) took noticeably more time but rarely resulted in a significant improvement. Even in the rare cases where it produced a noticeably tighter fit for examples 3 and 4, you could get an equal improvement by just trying other seeds.
For an example with 300 circles, 1000 took about 2.3 seconds; 2000 took about 3.8 seconds - on my fast MacBook Pro. (10,000 took 13 seconds.). Sometimes 2000 was slightly better, sometimes there was not much noticeable difference. My preference is to return results as quickly as possible so the user gets immediate feedback; if they are not happy they can always try upping the max attempts or changing the seed. And 1000 is a round number.
The processing time becomes more problematic as the number of values increases. Even at only 1000 max attempts, packing a thousand circles took 35 seconds, long enough that some users would give up and assume the node had frozen. I am therefor inclined to limit the size of the value list to no more than 1000, or even lower if default max attempts was higher than 1000.
Setting Max Attempts to 0 causes an error so that should not be allowed.
Conclusion: the default value should be 1000. I wish we didn't even have to expose a fudge factor like this to end users, but there do appear to be cases where a tighter packing may be worth the extra time, so I do think we need to expose this choice to end users.
THE BOTTOM LINE
MY RECOMMENDATION
To be clear, I can implement all of these recommendations using a wrapper subnetwork with no need to change the Python code any further.
What do you think?
If you have no objections, I will create the wrapper subnetwork and post a candidate for our final version. We can then play with that for a few days and see how we like it.
I haven't even looked at Voronoi yet; I want to get this locked down first. But I am very excited to look at it soon!
John
16 Posted by florisdejonge on 12 May, 2025 04:55 PM
John,
Thanks for your reply and thorough analysis. Apologies for the trouble the file gave you, I just started building onto the previous demo.
So, if you want to go ahead and finalise this one, I’d be happy. Please give it version number, just like you do with other nodes in your library. I only found the limitations of our first version after trying to actually make something with it. This might be the case for this one as well, so we might want to improve it in future.
Looking forward to your response regarding the Voronoi node.
Floris
Support Staff 17 Posted by john on 12 May, 2025 07:26 PM
Thanks Floris.
Attached is a demo with a v2 version of our node. It takes the following parameters:
The node returns the circles sorted from largest to smallest. So if you want to maintain an association between specific values and specific circles (as you would need to do in an information visualization), you will want to sort your values before submitting them.
The demo is as before but adds a fourth container: a square. The square example is currently set to place 15 uniform circles. I also added a density score to all examples. The density is an approximation for shapes with curves and contours, but is close enough for our purposes.
I wanted to get this out there ASAP so that you and others can play with it. I think this version is a clear improvement over our previous version, but I still have some concerns.
Especially when you place uniform circles in a square or rectangle you can see that the densities are pretty low. In fact for rectangles the MAXIMUM density possible with the current algorithm is only 50%. For uniform circles, depending on the container and the number of circles, it is generally possible to get around 70% to 90% density, so there is still a lot of empty space here; the circles don't look fully packed. I am almost tempted to call this place_circles instead of pack_circles.
I tried tweaking the algorithm to improve this (alternate code included in zip file). I was able to get the densities up a bit, but doing so caused the node to run noticeably slower. A modest improvement caused the render time for the whole demo to increase from about 3 seconds to 13 seconds - which I find unacceptable. And even with this change, the results vary wildly with the seed and are often still poor.
The algorithm is actually a bit lame. It begins by making a very rough estimate of the container area by simply multiplying the boundary box by 50%. This is low even for a circle (which occupies 78% of a square) and very low for a rectangle. It then tries a guess based on this low density. If that doesn't work it reduces the size by a whopping 15%. So for a rectangle, if 50% density doesn't work, it then tries 42.5%, then 36.12%. That's usually enough.
But when I increased the initial density and caused it to reduce density more slowly, this dramatically slowed performance, often with little apparent improvement. This is because most random scatterings used for the positioning are doomed to fail. You have to try many arrangements before even 50% density can work. If you start with even 60% density, the chances of success with most random arrangements falls dramatically, causing it to churn futilely.
The strength of the current algorithm is that it is VERY general purpose and still always returns the number of circles requested. We are asking a lot from it. It must handle ANY weird container shape and ANY arbitrary list of relative values. Given all that, for tasks like filling a heart shape with lots of different sized hearts, I think it works pretty well.
If we were to constrain the ask, I think it could do a better job.
One thing we both like about the new version is we now have an option. If you don't need a list of relative values and just want a certain number of uniform circles, you can just omit the values list. But currently the algorithm works the same either way. If it knew we only need uniform circles, maybe it could take a different approach that would result in higher densities.
Or maybe it could be more clever about the random scatter it uses for initial placement. If it used a more sophisticated distribution for its scatter, it might converge on better solutions much more quickly.
Another possible way to improve density would be to add a second phase. Once it comes up with a set of circles that satisfies the requirements, maybe it could use that as a base level and then improve it. If you look at 15 circles in the square, as a human you could easily improve the packing by jostling the circles around a bit (so that they were more evenly distributed) and then gradually increase the circle size until the padding limit was reached. This would often make a significant difference, but is harder for a computer to do and may become too time intensive if there are many circles. It would be interesting to see how well Claude could do this.
Another thing. Sometimes I don't care about having an exact number of circles of particular proportions and just want to completely fill the space.
One way of doing that would be to add another option: "Add Circles". This would normally be 0, but if you increased it to, say, 12, the node could add 12 more circles - of any size - to fill the remaining space. It would find the biggest open space and then add s circle big enough to fill the space up to the padding limit. It would then find the next biggest space and add a second circle. The more circles you add, the smaller each new circle gets, but the less wasted space. You could keep increasing this value until the container was full enough to suit your taste.
This would give you a lot of control. You could use a value list or just a fixed number of uniform circles to get a promising starting arrangement, and then fill in the rest from there. Or leave Add Circles at 0 if you need a specific number of circles.
It's hard to know when we are done if we don't have a clear idea of exactly what we want. When I google for "circle packing art" I see many different things. Some our current node can do, others it cannot.
Do you, Floris, have some specific effects you are trying to achieve? How well does this latest version do? Are there other specific things you want to do but still cannot achieve? Anyone else?
Let's play with this version for a few days and then consider if we want to try for a v3 that would have better overall density and maybe an option to fill the space with more circles.
Let the playing begin!
Support Staff 18 Posted by john on 14 May, 2025 08:41 AM
In the spirit of playing, last night I used our circle_pack node to make a quick visualization of world population by country from 1970 to 2022.
The node worked perfectly! I loaded a CSV file, did a lookup on population, fed that into the values port and VOILA! An instant chart of 234 countries, which I was then able to label, color code, and even animate.
I posted the animation on my Instagram account. I have also attached it here, along with a PDF. It's fun to zoom into the PDF and spot all the tiniest countries.
So far so good.