Circle packing sometimes overlaps circles.

[mbostock]

From d3/d3#3045, @sheldon-white writes:

I've reproduced this with a couple of large datasets; there's some unexpected overlaps in some of the circles. I haven't been able to recreate this with a small dataset so far. I've attached a screenshot, a datafile and example page that shows the issue.

bugreport.zip

[mbostock]

There is a bug in d3.pack here, but it is being triggered by a bug in your code. Specifically here, where you say:

root.sort(function(a, b) { return b.lines - a.lines; });

Unlike node.sum, which passes the accessor function the node’s data, node.sort passes the comparator function two nodes (not two data!). This is because node.sort typically operates on the sum computed by node.sum. So your comparator returns NaN when sorting two non-leaf nodes, and that means that the behavior of array.sort (and by extension node.sort) is undefined and may vary across browsers.

You should instead say:

root.sort(function(a, b) { return b.value - a.value; });

And this indeed fixes the problem. Before:

After:

I think the problem here is that the circle-packing layout is initially placing a few very small circles and there is numerical instability because the circles are so small. It’s possible that this is impractical to fix in the library, or that we’ll need a cludgy workaround like treating all circles smaller than ε as zero.

I reduced your test case here: http://bl.ocks.org/mbostock/1eb59d8139b3bea5c71e46afee440f9e

[mbostock]

Reduced to the following input:

{"path":"/","children":[
  {"path":"/a","value":3},
  {"path":"/b","value":30},
  {"path":"/d","value":50},
  {"path":"/c","value":400},
  {"path":"/e","value":600}
]}

[mbostock]

This one also fails, in a different way:

{"path": "/", "children":[
  {"path": "/a", "value": 3},
  {"path": "/b", "value": 70},
  {"path": "/d", "value": 100},
  {"path": "/c", "value": 200},
  {"path": "/e", "value": 500}
]}

[thomasp85]

I can reproduce these errors in my C++ implementation in ggraph. Naively I would guess that it is related to bad overlap checking when one circle completely encloses the other... I will get back once I've squashed the bug in ggraph

[mbostock]

The problem with my implementation is that in these cases it splices the wrong part of the front chain; the overlapping circle is found, but it is not clear whether the offending circle is “in front” or “in back” of the two tangent circles that were used to place the new circle. These terms are not defined in the paper.

Splicing the front chain should always make the front chain polygon bigger, so the fix I will attempt when I ever get a free moment is to compare the area of the front chain that would be added by splicing in either direction, and always splice the direction where this area is positive. Only one direction should be positive, I think… though if that is not the case then I will have to try another strategy.

[thomasp85]

FWIW preferring to check backwards first has solved all your proposed minimal cases. While I can understand why this is for the small examples you gave I have a bit of a hard time understanding if it should generalise...

[mbostock]

If you check backwards first, but reverse the order of circles in the above test cases, does the overlap reappear? I’d also try futzing with the orders of the circles more to further test your proposed change.

[thomasp85]

I tried a few permutations without problems but since the test case is so small I'll just run all sorting orders and see if there's any problems- I'll get back

[thomasp85]

My bad - problems still crop up...

[mbostock]

I appear to have fixed this bug! 🎉