-
Notifications
You must be signed in to change notification settings - Fork 315
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Circle packing sometimes overlaps circles. #74
Comments
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 |
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 |
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. |
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... |
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. |
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 |
@mbostock I'm just curious, how did you create that high resolution image? Is it an SVG exported from the browser then rasterized to a PNG? |
@curran I used SVG Crowbar to save from the browser and then graphicsmagick to convert to PNG, and optipng to optimize it. |
@mbostock Sweet! Thanks for the reply. Interesting tools. |
modify the chain traversal and intersection tests according to the solution to the same bug in D3 as proposed in d3/d3-hierarchy#74 The short example provided in #2 is working now.
From d3/d3#3045, @sheldon-white writes:
The text was updated successfully, but these errors were encountered: