This block is a continuation of a previous one.
This sequel experiments a way to vizualise the distribution of things (whatever it is) in a horizontal way (ie. along the x-axis), where constraints/objectives are:
Compared to the previous block, this algorithm is ~2 times faster, because:
The algorithm is:
<!DOCTYPE html>
<meta charset="utf-8">
<style>
#under-construction {
display: none;
position: absolute;
top: 200px;
left: 300px;
font-size: 40px;
}
circle {
stroke-width: 1.5px;
}
line {
stroke: #999;
}
</style>
<body>
<div id="under-construction">
UNDER CONSTRUCTION
</div>
<script src="https://d3js.org/d3.v3.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/dat-gui/0.5.1/dat.gui.min.js"></script>
<script>
var width = 960,
height = 500;
var trendData = [];
var config = {
radius: 4,
manyPoints: false
};
insertControls();
var fill = d3.scale.linear().domain([1,150]).range(['lightgreen', 'pink']);
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
svg.append("line")
.attr("id", "x-axis")
.attr("x1", 0)
.attr("y1", height/2)
.attr("x2", width)
.attr("y2", height/2)
.style("stroke", "lightgrey");
var nodeContainer = svg.append("g").attr("id", "node-container");
var informationPanel, computationTimeInfo, dataLengthInfo, posibleCollidersInfo, placementInfo, visitedCollidersInfo;
prepareInformationPanel();
var tooltip, stem, rank, value;
prepareTooltip();
var minDistanceBetweenCircles,
minSquareDistanceBetweenCircles,
AAD,
totalPossibleCollders, maxPossibleColliders,
totalTestedPlacements,
visitedColliderCount, totalVisitedColliders, maxVisitedColliders;
function initPlacement() {
minDistanceBetweenCircles = 2*config.radius;
minSquareDistanceBetweenCircles = Math.pow(minDistanceBetweenCircles, 2);
AAD = []; //already arranged data; window for collision detection
//-->for metrics purpose
totalPossibleColliders = maxPossibleColliders = 0;
totalTestedPlacements = 0;
visitedColliderCount = totalVisitedColliders = maxVisitedColliders =0;
//<--for metrics purpose
};
function findPossibleColliders (datum) {
//remove circles from AAD that are far away from datum
var indexesToRemove = 0;
AAD.every(function (aad) {
if (Math.abs(datum.x-aad.x)>minDistanceBetweenCircles) {
indexesToRemove++;
return true;
}
return false;
});
AAD.splice(0,indexesToRemove);
//-->for metrics purpose
totalPossibleColliders += AAD.length;
if (AAD.length > maxPossibleColliders) {
maxPossibleColliders = AAD.length;
}
//<--for metrics purpose
}
function isBetterPlacement(datum, bestYPosition) {
return Math.abs(datum.y) < Math.abs(bestYPosition);
}
function yPosRelativeToAad(aad, d) {
// handle Float approximation with +1E-6
return Math.sqrt(minSquareDistanceBetweenCircles-Math.pow(d.x-aad.x,2))+1E-6;
}
function placeBelow(d, aad, relativeYPos) {
d.y = aad.y - relativeYPos;
}
function placeAbove(d, aad, relativeYPos) {
d.y = aad.y + relativeYPos;
}
function areCirclesColliding(d0, d1) {
visitedColliderCount++ //for metrics prupose
//first simple check (vertical positions)
if (Math.abs(d1.y - d0.y) > minDistanceBetweenCircles) return false;
//more advanced check
var squareDistanceBetweenCircles = Math.pow(d1.y-d0.y, 2) + Math.pow(d1.x-d0.x, 2);
return squareDistanceBetweenCircles < minSquareDistanceBetweenCircles;
}
function collidesWithOther (data) {
return AAD.some(function(aad) {
return areCirclesColliding(aad, data);
});
}
function placeCircles (data) {
initPlacement();
data.forEach(function (d) {
var bestYPosition = -Infinity,
relativeYPos;
findPossibleColliders(d);
if (AAD.length===0) {
bestYPosition = 0;
} else {
AAD.forEach(function(aad) {
relativeYPos = yPosRelativeToAad(aad, d);
placeBelow(d, aad, relativeYPos);
if (isBetterPlacement(d, bestYPosition) && !collidesWithOther(d)) {
bestYPosition = d.y;
}
//-->for metrics purpose
totalVisitedColliders += visitedColliderCount;
if (visitedColliderCount > maxVisitedColliders) {
maxVisitedColliders = visitedColliderCount;
}
visitedColliderCount = 0;
//<--for metrics purpose
placeAbove(d, aad, relativeYPos);
if (isBetterPlacement(d, bestYPosition) && !collidesWithOther(d)) {
bestYPosition = d.y;
}
//-->for metrics purpose
totalVisitedColliders += visitedColliderCount;
if (visitedColliderCount > maxVisitedColliders) {
maxVisitedColliders = visitedColliderCount;
}
visitedColliderCount = 0;
//<--for metrics purpose
totalTestedPlacements += 2; //for metrics purpose
})
};
d.y = bestYPosition;
AAD.push(d);
});
}
function showCircles (data) {
nodeContainer.selectAll("circle").remove();
var node = nodeContainer.selectAll("circle")
.data(data)
.enter().append("circle")
.attr("r", config.radius-0.75)
.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return height/2 + d.y; })
.style("fill", function(d) { return fill(d.rank); })
.style("stroke", function(d) { return d3.rgb(fill(d.rank)).darker(); })
.on("mouseenter", function(d) {
stem.text(d.stem);
rank.text(d.rank);
value.text(d.trend);
tooltip.transition().duration(0).style("opacity", 1); // remove fade out transition on mouseleave
})
.on("mouseleave", function(d) {
tooltip.transition().duration(1000).style("opacity", 0);
});
}
function drawBeeswarm() {
var data = config.manyPoints? quadruple(trendData) : trendData;
var startTime = Date.now();
placeCircles(data);
showMetrics(data, (Date.now()-startTime));
showCircles(data);
}
function dottype(d) {
d.id = d.stem;
d.stem = d.stem;
d.rank = +d.rank;
d.trend = +d.trend;
d.x = width/2+d.trend*6000;
d.y = 0;
trendData.push(d);
return d;
}
d3.csv("data.csv", dottype, function(error, data) {
if (error) throw error;
drawBeeswarm()
});
function quadruple(data) {
// Quadruples data while maintaining order and uniq id
var quadrupledData = [],
i;
data.forEach(function(d) {
for (i=0; i<3; i++) {
quadrupledData.push({
id: d.id+"_"+i,
stem: d.stem,
rank: d.rank,
trend: d.trend,
x: d.x+i*1E-4,
y: d.y
})
}
quadrupledData.push(d);
})
return quadrupledData;
}
function insertControls () {
var ctrls = new dat.GUI({width: 200});
radiusCtrl = ctrls.add(config, "radius", 1, 20);
radiusCtrl.onChange(function(value) {
drawBeeswarm(trendData);
});
manyPointsCtrl = ctrls.add(config, "manyPoints");
manyPointsCtrl.onChange(function(value) {
drawBeeswarm();
});
}
function prepareTooltip() {
tooltip = svg.append("g")
.attr("id", "tooltip")
.attr("transform", "translate("+[width/2, 50]+")")
.style("opacity", 0);
var titles = tooltip.append("g").attr("transform", "translate("+[-5,0]+")")
titles.append("text").attr("text-anchor", "end").text("stem(fr):");
titles.append("text")
.attr("text-anchor", "end")
.attr("transform", "translate("+[0,15]+")")
.text("rank:");
titles.append("text")
.attr("text-anchor", "end")
.attr("transform", "translate("+[0,30]+")")
.text("x-value:");
var values = tooltip.append("g").attr("transform", "translate("+[5,0]+")")
stem = values.append("text")
.attr("text-anchor", "start");
rank = values.append("text")
.attr("text-anchor", "start")
.attr("transform", "translate("+[0,15]+")");
value = values.append("text")
.attr("text-anchor", "start")
.attr("transform", "translate("+[0,30]+")");
}
function prepareInformationPanel() {
var i=4;
informationPanel = svg.append("g")
.attr("id", "infomation-panel")
.attr("transform", "translate("+[width-20, height-20]+")");
computationTimeInfo = informationPanel.append("text")
.attr("text-anchor", "end")
.attr("transform", "translate("+[0,-15*i--]+")");
dataLengthInfo = informationPanel.append("text")
.attr("text-anchor", "end")
.attr("transform", "translate("+[0,-15*i--]+")");
possibleCollidersInfo = informationPanel.append("text")
.attr("text-anchor", "end")
.attr("transform", "translate("+[0,-15*i--]+")");
placementInfo = informationPanel.append("text")
.attr("text-anchor", "end")
.attr("transform", "translate("+[0,-15*i--]+")");
visitedCollidersInfo = informationPanel.append("text")
.attr("text-anchor", "end");
}
function showMetrics(data, elapsed) {
computationTimeInfo.text("Arrangement took: "+elapsed+" ms");
dataLengthInfo.text("# data: "+data.length);
possibleCollidersInfo.text("# possible colliders: ~"+Math.round(totalPossibleColliders/data.length)+" per data ("+maxPossibleColliders+" max, "+totalPossibleColliders+" total)");
placementInfo.text("# tested placements: ~"+Math.round(totalTestedPlacements/data.length)+" per data ("+(maxPossibleColliders*2)+" max, "+totalTestedPlacements+" total)");
visitedCollidersInfo.text("# collision checks: ~"+Math.round(totalVisitedColliders/totalTestedPlacements)+" per placement ("+maxVisitedColliders+" max, "+totalVisitedColliders+" total)")
}
</script>
</body>stem,rank,trend
jean,1,0.0221834557
excelent,2,0.0172573247
bon,3,0.0152706367
conseil,4,0.0142771343
part,5,0.0139849763
ecout,6,0.0125657668
promotion,7,0.0116647465
disponibilit,8,0.0107923086
serviabl,9,0.0099251458
acesoir,10,0.0098934332
haut,11,0.009431776
pantalon,12,0.0093578819
bele,13,0.0092871115
aceuil,14,0.0092121588
nouveaut,15,0.0090155204
achat,16,0.008722844
promo,17,0.0086278463
tendanc,18,0.0085356217
manqu,19,0.0084932708
parfait,20,0.0083623534
done,21,0.008355304
feme,22,0.0083248405
vent,23,0.0083132016
avoi,24,0.0080424169
chaleureu,25,0.0078822066
comand,26,0.0075604839
quelqu,27,0.0074075752
tenu,28,0.0072492987
chausur,29,0.00711808
disponibl,30,0.0068948326
person,31,0.0068073546
originalit,32,0.0067217905
vendeu,33,0.0067063822
rien,34,0.0067047717
esay,35,0.0067006641
satisfait,36,0.006684763
cher,37,0.0066836778
acueil,38,0.0066314869
colection,39,0.0064813458
metr,40,0.0064580388
tre,41,0.0064376867
servic,42,0.0063193197
sympath,43,0.0061779954
être,44,0.0061047823
sup,45,0.0060575513
dispos,46,0.0060483871
goût,47,0.0059637097
ador,48,0.0059467335
boutiqu,49,0.0059089954
beau,50,0.0058717403
regulier,51,0.0057329804
certain,52,0.005686449
ofre,53,0.005585669
gentil,54,0.0055481446
styl,55,0.005431152
fidelit,56,0.005398658
foi,57,0.0053355415
propos,58,0.00518158
profesion,59,0.0051523297
game,60,0.0051314774
cart,61,0.0050913638
chos,62,0.0050861437
coup,63,0.0050283014
souriant,64,0.0049009439
tail,65,0.004843215
raport,66,0.0048075105
autr,67,0.0046451013
general,68,0.0046430266
reduction,69,0.0046182266
mode,70,0.004570462
achet,71,0.0045116366
amelior,72,0.0045047883
present,73,0.004487011
elev,74,0.0044661415
rest,75,0.0044256491
jol,76,0.0043042359
acueilant,77,0.0041950808
marqu,78,0.0040932108
produit,79,0.0039764739
diferent,80,0.0039120302
modern,81,0.0038882488
enseign,82,0.0038190136
agreabl,83,0.0037894
trouv,84,0.0037702036
parfoi,85,0.0036276761
port,86,0.0035256142
magasin,87,0.0034050179
chang,88,0.0031922043
agenc,89,0.003190358
clai,90,0.0031812945
ainsi,91,0.0031549695
choi,92,0.0030694137
rayon,93,0.0030580465
client,94,0.0029360714
vête,95,0.0028722762
dire,96,0.0027721774
qualit,97,0.0027403058
var,98,0.0026126169
personel,99,0.0025779703
aimabl,100,0.0025749765
internet,101,0.0025134409
pri,102,0.00238414
sai,103,0.0023536115
abordabl,104,0.0022652921
bone,105,0.0022487593
matier,106,0.0021982583
promod,107,0.0020265214
larg,108,0.0018647201
stock,109,0.0018290033
sympa,110,0.0018003201
corect,111,0.0017615927
vraiment,112,0.0016633065
petit,113,0.0016439206
aime,114,0.0015219369
model,115,0.0014867544
equip,116,0.0011670831
couleu,117,0.0011177858
seul,118,0.0010356827
bais,119,0.0010036041
renouvel,120,0.0009602366
nouvel,121,0.0009557945
niveau,122,0.0004725302
articl,123,0.0003851409
vete,124,0.000353736
domag,125,0.0002193117
raisonabl,126,-0.0001944124
esayag,127,-0.00025102
valeu,128,-0.0002974617
site,129,-0.00040451
amabilit,130,-0.0005457864
grand,131,-0.0008885675
original,132,-0.0009822167
acesibl,133,-0.0010942806
sourir,134,-0.0011092602
diversit,135,-0.001424439
tisu,136,-0.0016639137
cabin,137,-0.0025446106
ane,138,-0.0032602282
propr,139,-0.0039869126
joli,140,-0.0051917043
clas,141,-0.0052463184
variet,142,-0.007044379
atractif,143,-0.0072967461
cais,144,-0.0080716152
rang,145,-0.0081059257
robe,146,-0.0084245392
espac,147,-0.0087132705
atent,148,-0.0109695748
interesant,149,-0.0113475782
sold,150,-0.0611010533