A while back, the following question was posed: how can I try to fit a label in a slice of a pie chart? So, I did the obligatory Googling, but alas, I came up empty handed. I proceeded to come up with a solution on my own. I will explain what I came up with, and I hope that this will be helpful to someone else down the line. I also hope that someone will improve upon this and let me know what changes they made. Note: I did my best to make this framework-agnostic, which is why you will see this “Labelizer” object taking in so many parameters. If this were to be adapted in some framework, I would hope that several parameters could be extrapolated from object instances that already exist.
Also, this implementation only tries to fit the labels inside of the pie slices. If it fails to find a suitable place in the slice, the label is discarded. This leaves the problem of how to position the labels outside of the pie, which would involve some collision detection. Perhaps another time.
Assumptions that were made:
- The pie is a perfect circle. If one wanted to modify this for a more flexible ellipse, such as in the case of a 3D pie chart, it could certainly be done.
- The slices of the pie add up to 100%.
- The labels will not rotate to fit.
- The ideal placement for the labels would be as close to the edge of the pie as possible.*
Let’s start with the inputs. What do we need to know?
- We need some information about our pie. The base information is the x and y coordinates of the origin of the circle, as well as its radius.
- We need to have the width and height of the label we want to try to position. We don’t really care about the label itself, be it an image or text — just that it has dimensions.
- We need some definition around what slice of the pie we’re working with. Therefore, we need to know the starting and ending angles of the pie slice.
The very first thing we need to do is verify our starting and ending angles. If we end up in a case where our starting angle is greater than our ending angle, we should abort the labeling attempt. This is a very basic early-escape check so that we don’t do unnecessary calculations. Another check that we can do is to make sure that our label has even the possibility of fitting:
- Take the ending angle minus the starting angle. We’ll call this the “opening angle”.
- We now need to find out what the maximum length of our label could be, so:
- if the opening angle is less than 90 degrees, our label cannot be bigger than the pie’s radius.
- if the opening angle is greater than 180 degrees, our label cannot be bigger than the pie’s diameter
- if the opening angle is in between those two ranges, we need to find the coordinates where the starting and ending angles of our slice intersect with the edge of the pie. The line that connects those two points will be our maximum length.
- We now take our label dimensions (the width and the height) and find its hypotenuse. If this hypotenuse length is greater than our maximum value, we know that the label cannot possibly fit.
Now that we’ve exhausted all of the tests for saving ourselves the work of finding where to place this label, it’s time to find the sweet spot. Note: I have spent many, many hours trying to come up with an approach that is not iterative, but apparently my geometry is too rusty.
The approach I took started by finding the middle angle (halfway between the starting and ending angle) and placing the appropriate corner against the edge of the pie. The “appropriate” corner of the label is dependent on the quadrant that this middle angle fell in. On a Cartesian coordinate system, Quadrant I would be the top-right corner, Quadrant II would be the top-left, Quadrant III would be the bottom-left, and Quadrant IV would be the bottom-right. At this point, we check a couple things:
- any line drawn from the origin of the pie to a corner of the label would be an angle between the starting and ending angles of the slice
- any line drawn from the origin of the pie to a corner of the label would have a length less than the radius of the pie
As soon as either of these conditions are not met, we should abandon trying to fit the label in that spot and move on. We repeat the process by moving the “label” along the edge of the pie, within the bounds of that slice. I provided an extra parameter (delta) to the Labelizer object that would allow the user to specify the iteration step. While the default is to check every 1 degree, for larger charts, this may not be granular enough.
If no suitable coordinate for the label is found, the Labelizer will return ‘false’. At this stage, the label could perhaps be thrown into a mechanism for placing the labels around the pie.
* if the labels could fit closer to the origin of the pie, a second set of iterations could be performed to try to find a more ideal spot.
Please see a demo here (and since I’m too lazy to go and add in ExCanvas, you will need to use a decent browser that supports canvas natively). I hope that this was helpful, and I’m looking forward to hearing your thoughts on this. Especially if someone has another solution in lieu of my iterative approach (I just can’t shake the code smell). I’m sure there’s a formula that will do it much more elegantly, but I’m not familiar enough with net areas and intersections (and I imagine there are probably even integrals involved in there somewhere).
And here’s the code:
Labelizer = (function() {
/*
Labelizer is designed to determine if a text label will fit
into a slice of a pie chart. The pie chart must be a perfect
circle (pie.width = pie.height) at this point
It is helpful to pad your label text with a couple spaces on
either side for display purposes. This will help push the label
away from the edges of the circle.
oArgs = {
pie : {
x : REQUIRED - origin x of the pie
y : REQUIRED - origin y of the pie
r : REQUIRED - radius of the pie
}
labelwidth: REQUIRED - width of label to be positioned
labelheight: REQUIRED - height of label to be positioned
start: REQUIRED - Slice starting angle (radians)
end: REQUIRED - Slice ending angle (radians)
dt: OPTIONAL - Delta Theta in Radians will determine the iteration
distance for .testLabel(). Defaults to PI/180 (every 1 degree)
}
*/
var Labelizer = function(oArgs) { this.init(oArgs); }
Labelizer.prototype = {
dt : Math.PI/180,
init : function(oArgs) {
var requiredInputs = this._verifyInputs(oArgs);
if(!requiredInputs) {
this.error("Required Parameters Missing.");
return;
}
this.label_width = oArgs.labelwidth;
this.label_height = oArgs.labelheight;
this.diameter = oArgs.pie.r*2;
this.savedorigin = new LabelUtils.Point(oArgs.pie.x, oArgs.pie.y);
this.p_origin = new LabelUtils.Point(0,0);
var coord_startx = (oArgs.pie.r*Math.cos(oArgs.start)) + oArgs.pie.x; //Math.round(oArgs.pie.edgeX(oArgs.start));
var coord_starty = (oArgs.pie.r*Math.sin(oArgs.start)) + oArgs.pie.y; //Math.round(oArgs.pie.edgeY(oArgs.start));
var coord_endx = (oArgs.pie.r*Math.cos(oArgs.end)) + oArgs.pie.x; //Math.round(oArgs.pie.edgeX(oArgs.end));
var coord_endy = (oArgs.pie.r*Math.sin(oArgs.end)) + oArgs.pie.y; //Math.round(oArgs.pie.edgeY(oArgs.end));
var startx = coord_startx - oArgs.pie.x;
var starty = oArgs.pie.y - coord_starty;
var endx = coord_endx - oArgs.pie.x;
var endy = oArgs.pie.y - coord_endy;
this.p_start = new LabelUtils.Point(startx, starty);
this.p_end = new LabelUtils.Point(endx, endy);
this.l_start = new LabelUtils.Line(this.p_origin, this.p_start);
this.l_end = new LabelUtils.Line(this.p_origin, this.p_end);
if(this.l_start.getAngle() > this.l_end.getAngle()) {
this.l_end.addAngleRevolution();
}
if(this.l_start.getAngle() > this.l_end.getAngle()) {
this.error("Label could not be attached.");
return;
}
this.showTrace = oArgs.showTrace;
this.dt = oArgs.dt || this.dt;
},
_verifyInputs : function(oArgs) {
if(!oArgs.labelheight ||
!oArgs.labelwidth ||
!oArgs.pie ||
oArgs.start == undefined ||
oArgs.end == undefined) {
return false;
}
return true;
},
error : function(err) {
if(err) {
this.err = err;
this.errorCounter = this.errorCounter || 0;
this.errorCounter++;
}
return this.err;
},
checkOpening : function() {
var label = new LabelUtils.Label(this.label_height, this.label_width);
var openingAngle = this.l_end.getAngle() - this.l_start.getAngle();
var maxLength;
if(openingAngle < (Math.PI/2)) { maxLength = this.diameter/2; }
else if(openingAngle < Math.PI) {
var cap = new LabelUtils.Line(this.l_end.p2, this.l_start.p2);
maxLength = cap.getLength();
}
else { maxLength = this.diameter; }
if(label.getHypotenuse() > maxLength) { return false; }
return true;
},
calculate : function() {
if(this.error()) { console.log(this.err); return false; }
if(!this.checkOpening()) { return false; }
var label = this.placeLabel(this.l_start, this.l_end);
if(!label) { return false; }
var points = label.corners;
var attacher = points.tl;
return {
x: this.savedorigin.x + attacher.x,
y: this.savedorigin.y - attacher.y
}
},
getPointFromAngle : function(theta) {
//TODO:
// Add ability to calculate coordinate if pie.width and
// pie.height are not equal
var x_theta = Math.cos(theta)*(this.diameter/2);
var y_theta = Math.sin(theta)*(this.diameter/2);
return new LabelUtils.Point(x_theta, y_theta);
},
testLabel : function(l_start, l_end, theta) {
var p_theta = this.getPointFromAngle(theta);
var label = new LabelUtils.Label(this.label_height, this.label_width);
var success = label.attach(p_theta);
if(!success) {
this.error("Label could not be attached.");
return false;
}
var verdict = label.verify(this.diameter/2, l_start, l_end);
if(verdict) { return label; }
return false;
},
placeLabel : function(l_start, l_end) {
var result;
var midTheta = (l_start.getAngle() + l_end.getAngle())/2;
for(thetaLow = midTheta, thetaHigh = midTheta; thetaLow>l_start.getAngle() || thetaHigh<l_end.getAngle(); thetaLow-=this.dt, thetaHigh+=this.dt) {
if(thetaLow > l_start.getAngle()) {
result = this.testLabel(l_start,l_end,thetaLow);
if(result) { return result; }
}
if(thetaHigh < l_end.getAngle()) {
result = this.testLabel(l_start,l_end,thetaHigh);
if(result) { return result; }
}
}
return false;
}
}
/*
Utility Objects Collection Used by Labelizer
*/
var LabelUtils = {
/*
Point is used to store an x-y coordinate and
calculate information about that point
*/
Point : function(x,y) {
this.x = x;
this.y = y;
this.getQuadrant = function() {
var q = false;
if(this.x >= 0 && this.y >= 0) { q = 1; }
else if(this.x < 0 && this.y > 0) { q = 2; }
else if(this.x <= 0 && this.y <= 0) { q = 3; }
else if(this.x > 0 && this.y < 0) { q = 4; }
this.getQuadrant = function() { return q; }
return this.getQuadrant();
};
},
/*
Line is comprised of two Points and can
calculate information about its geometry
*/
Line : function(p1,p2) {
this.p1 = p1;
this.p2 = p2;
this.getAngle = function() {
var opposite = this.p2.y - this.p1.y;
var adjacent = this.p2.x - this.p1.x;
var theta = Math.atan(opposite/adjacent);
if(theta < 0) { theta += (2*Math.PI); }
switch(this.p2.getQuadrant()) {
case 1: break;
case 2: theta -= Math.PI; break;
case 3: theta += Math.PI; break;
case 4: break;
}
this.getAngle = function() { return theta; }
return this.getAngle();
};
this.addAngleRevolution = function() {
var angle = this.getAngle();
angle += (2*Math.PI);
this.getAngle = function() { return angle; }
return this.getAngle();
};
this.getLength = function() {
var distance = Math.abs(
Math.sqrt(
Math.pow(this.p2.x - this.p1.x,2) +
Math.pow(this.p2.y - this.p1.y,2)
)
);
this.getLength = function() { return distance; }
return this.getLength();
};
},
/*
Label is a collection of Points that represent
the bounding box for the label that will be placed.
The label will attach to a coordinate on the pie
(placement dependent on quadrant) and then verify
that it falls within the bounds of the slice.
*/
Label : function(height, width) {
this.height = height;
this.width = width;
this.getHypotenuse = function() {
// a^2 + b^2 = c^2
var length = Math.abs(
Math.sqrt(
Math.pow(this.width,2) +
Math.pow(this.height,2)
)
);
this.getHypotenuse = function() { return length; }
return this.getHypotenuse();
};
this.attach = function(p) {
var tr, tl, bl, br; //top-right, top-left, bottom-left, bottom-right
var px = p.x, py = p.y;
switch(p.getQuadrant()) {
case 1:
tr = p;
tl = new LabelUtils.Point(px - this.width, py);
bl = new LabelUtils.Point(px - this.width, py - this.height);
br = new LabelUtils.Point(px, py - this.height);
break;
case 2:
tl = p;
tr = new LabelUtils.Point(px + this.width, py)
br = new LabelUtils.Point(px + this.width, py - this.height);
bl = new LabelUtils.Point(px, py - this.height);
break;
case 3:
bl = p;
br = new LabelUtils.Point(px + this.width, py);
tr = new LabelUtils.Point(px + this.width, py + this.height);
tl = new LabelUtils.Point(px, py + this.height);
break;
case 4:
br = p;
bl = new LabelUtils.Point(px - this.width, py);
tl = new LabelUtils.Point(px - this.width, py + this.height);
tr = new LabelUtils.Point(px, py + this.height);
break;
}
if(!tr || !tl || !bl || !br) { return false; }
this.corners = { tr: tr, tl: tl, bl: bl, br: br }
return true;
};
this.verify = function(radius,l_start,l_end) {
//TODO:
// Add ability to calculate radius based on angle if
// pie.width and pie.height are not equal
var corner, line;
var origin = new LabelUtils.Point(0,0);
for(var i in this.corners) {
corner = this.corners[i];
if(!this._checkInBounds(
new LabelUtils.Line(origin,corner),
l_start,
l_end,
radius)
) { return false; }
}
return true;
};
this._checkInBounds = function(line,start,end,radius) {
var startAngle = start.getAngle(),
endAngle = end.getAngle();
var allowRevolution = (endAngle >= (2*Math.PI))
if(line.getAngle() < startAngle && line.getAngle() < endAngle && allowRevolution) {
line.addAngleRevolution();
}
if(line.getAngle() < startAngle && line.getAngle() < endAngle) { return false }
if(line.getAngle() > startAngle && line.getAngle() > endAngle) { return false }
if(line.getLength() > radius) { return false; }
return true;
};
},
/*
rad2deg: Helper function useful for translating
radians to degrees (for display purposes and
debugging, since radians -- at least for me --
are not intuitive)
*/
rad2deg : function(rad) { return (rad * (180/Math.PI)); }
};
return Labelizer;
})();
0 Comments.