search

d3 / d3-hierarchy

2D layout algorithms for visualizing hierarchical data.
https://d3js.org/d3-hierarchy
ISC License
1.13k stars 315 forks source link

circle packing layout #29

Closed pmenzel closed 8 years ago

pmenzel commented 8 years ago

Hi,

I was re-implementing the circle packing algorithm by Wang et al. in C, based on the old implementation in Protovis and noticed that you changed their algorithm so that each circle is put next to the previously placed circle instead of the location closest to the center of the plot. I assume it was intentional to keep nodes with the same color next to each other even so the final layout is less round, but more snail-shaped.
It's just a little modification to the code to change the placement according to the original algorithm, and I could provide it if desired (modified the big D3.js and it worked). Let me know..

Also: great work on D3 btw :)

cheers

mbostock commented 8 years ago

That was a mistake inherited from the Flare implementation on which the Protovis implementation was based. I’ve since completely rewritten the circle-packing layout for D3 4.0 in this repository and it no longer has this behavior.

mbostock commented 8 years ago

The Flare implementation (and by extension Protovis and D3 < 4) had another problem where the “closest” intersecting circle was measured topologically rather than based on the cumulative length of each segment in the front chain (see s2 < s1). The paper isn’t clear what “closest” means, but by measuring the traversed length of the front chain it appears to avoid some edge cases where the previous implementation can generate overlapping circles.

pmenzel commented 8 years ago

Alright, didn't see that the implementation is different here than in D3, sorry! Yeah, the location of intersecting circle is just denoted as "before" and "after" the currently placed circle in the paper, which is a bit confusing.