Scriptographer.org - Efficient overlap checking

The goal: ability to create dense clusters of non-overlapping paths.
The progress so far: using intersects() function it is easy to check for overlap. Certain gain in speed is possible by placing intended paths on temporary spiral path (Archimedian spiral works well).
The problem: It takes too long for the script to check 100 or more objects.
The core of the problem: The script checks for overlap with ALL previously created paths, instead of discarding the areas where overlap is certain.
Possible solution: Create array of all previous placed path positions and sort it, note the size of largest possible path, when checking for overlap note the position of the last path and check the array for other paths withing the radius derived from the size of the largest object. Check overlap with only those paths.

Help: while the possible solution may work, I am not familiar enough with JavaScript to quickly test it. I will appreciate any advise or additional clues on how to approach the problem.

Hi,
this sounds like some classic box/circle packing algorithm. A lot of papers, blogs and whatnot of the subject matter have been published on the net. From what I can understand this is a very complicated field (mathematically, not with brute force). Unfortunately I am not skilled enough to take on this problem but perhaps Jonathan can do it. That is if he is not too occupied with other projects and feels that he's up to it...
Good luck anyway, I have been looking for a good circlepacking script for a long time and would really benefit from any of your possible upcomming solutions!

Best regards
/ Håkan

I see that this is common design problem with many solutions available privatly (ex. Wordle). Places like Shutterstock or iStockphoto are full of designs done with this approach.

I wish somebody would be generous enough to release the script for Illustrator to do the task with groups - solving it once and for all for all future designers.

We all live of each others work anyway - stealing Edisons are remembered and creative Teslas forgotten - but Tesla is The Man.

i have a rough circle packing tool in scriptographer, if there's enough interest i could make it a bit more robust and release it here

i'm also (slowly) working on a script to pack irregular shapes, but as håkan mentioned that is no easy task.

Ken

Wow, that look great!
Does it look for an optimum solution or are they (the circles) just arbitrarily tangential? I was just going to start up on my own CP-script. Got some info on a clever algorithm. As I see it there are different levels of difficulty when it comes to CP.
To just fill a square area with a defined number of circles where the circle size vary seem to be the easiest task. On the other side of the spectrum I'd venture a guess that filling a randomly (either concave or convex) shaped area with a set number of circles with fixed (or at least predefined) sizes is quite the undertaking.
Anyhow, as I said I will probably try to write my own script (just for the fun of the challenge) but I'd be more than happy if you'd post your take on the problem.

I'm also excited to see your other version you're working on.

Good work!

I am certainly interested in it. It could provide solution for many design problems. Providing efficient packing solutions for irregular shapes such as letters and numbers would engrave your name in my book of fame... Good luck!

Also very much interested. I'd love to be able to use such a thing for my designs. Have you seen the perculator app for ipad/iphone? That's image-based circle packing with a lot of options.

Scripts

08.08.14, 15:24

15.05.14, 14:23

02.03.14, 19:16

18.11.13, 14:48

22.03.13, 03:05