4

My goal is to generate a circle pack that mimics this: (don't pay attention on numbers, and colors at all, at the moment I am interested in circle positions and radiuses only)

enter image description here

Based on an example from d3js.org, I created this jsfiddle, with result:

enter image description here

I tried circle pack layouts, but results were even worse, lots of empty space...

How can I get something that looks like the first pic?

EDIT: This example seems closer to what I want, I just noticed.

EDIT 2: Inspired by @AmeliaBR idea, codepen. Not yet final. Preview:

enter image description here

Then I decreased max radius:

enter image description here

The latest and greatest: max rad 12 min rad 3

enter image description here

VividD
  • 10,456
  • 6
  • 64
  • 111
  • A tweaked [force layout](http://bl.ocks.org/mbostock/1747543)? – Lars Kotthoff Jan 11 '14 at 21:37
  • Yes, that example I am based on. Just the case of a single group. I tried a lot to tweak it further, but its very hard. Very hard to get that neat look of the first pic. This might be really difficult problem, that my feeling. – VividD Jan 11 '14 at 21:38
  • Not sure what you mean exactly. Looks to me like the main difference is that the circles in the first picture are bigger on average. – Lars Kotthoff Jan 11 '14 at 21:40
  • In the first picture, circles of all sizes are evenly distributed across the large circular area, while in the second one, smaller circles tend to be in the interior, and larger on the periphery of the area, with an exception of a large circle close to the center. And also overall shape is not close enough to circular, for the second picture. The absolute size is not crucial. – VividD Jan 11 '14 at 21:42
  • Hmm, sounds like that's what would happen "naturally" with the force layout. I think you would need to roll your own for this. The [word cloud layout](https://github.com/jasondavies/d3-cloud) may help. – Lars Kotthoff Jan 11 '14 at 21:46
  • On a general note, I'm not sure if this question is suitable for SO. Please don't take this the wrong way -- I just mean that implementing something like this would, as you say yourself, require significant effort and that we're all volunteers here and doing this in our spare time. You have demonstrated that you're capable of figuring something like this out on your own, so I'm not sure what you're expecting as an answer here. The D3 mailing list is also better for getting people's opinions/pointers to relevant things. – Lars Kotthoff Jan 11 '14 at 22:06
  • As far as why the circles end up unevenly distributed, I think it's simply a matter that the small circles are better able to "slip through the cracks" of larger ones, so they fall to the "gravitational centre" while larger circles are excluded. You could try arranging the initial pack more evenly by adding largest circles first to a quadtree, like in [this example](http://bl.ocks.org/mbostock/6224050). – AmeliaBR Jan 12 '14 at 00:28
  • The results do look good -- I assume you're still using the force layout to deal with overlap or spaces? The solutions you're getting over on the [Mathematica site](http://mathematica.stackexchange.com/questions/40334/generating-visually-pleasing-circle-packs) are more exact, but might be slower since they manually check for collisions. (P.S. Put your results in an answer, so this doesn't show up as an uanswered D3.js question anymore!) – AmeliaBR Jan 13 '14 at 23:27
  • P.P.S. How to load d3.js on Codepen without putting a script tag in the HTML: http://blog.codepen.io/documentation/editor/adding-external-resources/#how-to ; type "d3" in the "external file" field at it will auto-fill for you. – AmeliaBR Jan 13 '14 at 23:30
  • @AmeliaBR Great! Both your comments... I was going to send link to Mathematica to you, but you were faster! No, its not force layout at all. Its gradual adding circles in random position, starting from largest and slowly moving to smallest, and checking if they fill empty space or not, with quadtree... – VividD Jan 13 '14 at 23:35
  • Yep, I figured that out after I commented, when I opened up the codepen. It would be more complicated if you wanted the radii to match up with a dataset, which is what I thought you were trying to do, but if you just want to generate that type of pattern it works wonders. – AmeliaBR Jan 14 '14 at 01:05
  • @AmeliaBR, maybe you can review the code from codepen, connect all dots, and add some comments, and then enter it as the answer to this question - since this really originated from your hint. You are spiritual author of the answer, and I wouldn't be comfortable entering it as if I was the author. So... :) – VividD Jan 14 '14 at 01:20
  • @AmeliaBR, could you perhaps help me about this: (http://stackoverflow.com/questions/21206081/gradient-along-links-in-d3-sankey-diagram)? – VividD Jan 18 '14 at 15:49

1 Answers1

5

See comments to the main question for how this developed...

Mike Bostock has created a couple of different visualizations of Mitchell's best-candidate sampling algorithm:

The original purpose of Mitchell's algorithm is to sample a range of values, in a way that doesn't create repetitive patterns, but also isn't prone to creating clusters and gaps like a true random sample.

Bostock's demonstrations combine the sampling algorithm with the d3 quadtree data structure, which sorts data points into a tree structure that is divided into just as many branches as are needed to put each data point into its own node. With the quadtree, Bostock can quickly tell how much space there is around each new point added to the graph, and therefore how large a circle can fit in that space. The program starts by drawing circles of a chosen maximum radius, and keeps going until it repeatedly fails to find enough room to draw circles of the minimum radius.

Bostock's examples used a rectangular space in which to draw the circles, but as Vivid D demonstrated, it can be adapted to other shapes.

AmeliaBR
  • 27,344
  • 6
  • 86
  • 119