d3.js spreading labels for pie charts

As @The Old County discovered, the previous answer I posted fails in firefox because it relies on the SVG method .getIntersectionList() to find conflicts, and that method hasn’t been implemented yet in Firefox.

That just means we have to keep track of label positions and test for conflicts ourselves. With d3, the most efficient way to check for layout conflicts involves using a quadtree data structure to store positions, that way you don’t have to check every label for overlap, just those in a similar area of the visualization.

The second part of the code from the previous answer gets replaced with:

        /* check whether the default position 
           overlaps any other labels*/
        var conflicts = [];
        labelLayout.visit(function(node, x1, y1, x2, y2){
            //recurse down the tree, adding any overlapping labels
            //to the conflicts array

            //node is the node in the quadtree, 
            //node.point is the value that we added to the tree
            //x1,y1,x2,y2 are the bounds of the rectangle that
            //this node covers

            if (  (x1 > d.r + maxLabelWidth/2) 
                    //left edge of node is to the right of right edge of label
                ||(x2 < d.l - maxLabelWidth/2) 
                    //right edge of node is to the left of left edge of label
                ||(y1 > d.b + maxLabelHeight/2)
                    //top (minY) edge of node is greater than the bottom of label
                ||(y2 < d.t - maxLabelHeight/2 ) )
                    //bottom (maxY) edge of node is less than the top of label

                  return true; //don't bother visiting children or checking this node

            var p = node.point;
            var v = false, h = false;
            if ( p ) { //p is defined, i.e., there is a value stored in this node
                h =  ( ((p.l > d.l) && (p.l <= d.r))
                   || ((p.r > d.l) && (p.r <= d.r)) 
                   || ((p.l < d.l)&&(p.r >=d.r) ) ); //horizontal conflict

                v =  ( ((p.t > d.t) && (p.t <= d.b))
                   || ((p.b > d.t) && (p.b <= d.b))  
                   || ((p.t < d.t)&&(p.b >=d.b) ) ); //vertical conflict

                if (h&&v)
                    conflicts.push(p); //add to conflict list
            }

        });

        if (conflicts.length) {
            console.log(d, " conflicts with ", conflicts);  
            var rightEdge = d3.max(conflicts, function(d2) {
                return d2.r;
            });

            d.l = rightEdge;
            d.x = d.l + bbox.width / 2 + 5;
            d.r = d.l + bbox.width + 10;
        }
        else console.log("no conflicts for ", d);

        /* add this label to the quadtree, so it will show up as a conflict
           for future labels.  */
        labelLayout.add( d );
        var maxLabelWidth = Math.max(maxLabelWidth, bbox.width+10);
        var maxLabelHeight = Math.max(maxLabelHeight, bbox.height+10);

Note that I’ve changed the parameter names for the edges of the label to l/r/b/t (left/right/bottom/top) to keep everything logical in my mind.

Live fiddle here: http://jsfiddle.net/Qh9X5/1249/

An added benefit of doing it this way is that you can check for conflicts based on the final position of the labels, before actually setting the position. Which means that you can use transitions for moving the labels into position after figuring out the positions for all the labels.