D3 Venn Diagram Example
<!doctype html> | |
<head> | |
<title>Audience Comparison</title> | |
<meta charset="utf-8"> | |
<meta http-equiv="X-UA-Compatible" content="IE=edge"> | |
<meta name="viewport" content="width=device-width, initial-scale=1"> | |
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.6/d3.min.js" charset="utf-8"></script> | |
<link href='https://fonts.googleapis.com/css?family=Quicksand:400,700' rel='stylesheet' type='text/css'> | |
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.5/css/bootstrap.min.css"> | |
<script src="venn.js"></script> | |
<style> | |
body { | |
font-family: 'Quicksand', sans-serif; | |
font-weight: 700; | |
font-size : 14px; | |
margin: 2% 2% 2% 2%; | |
} | |
.venntooltip { | |
font-size : 14px; | |
position: absolute; | |
text-align: center; | |
width: 128px; | |
height: 85px; | |
background: #333; | |
color: #fff; | |
padding: 2px; | |
border: 0px; | |
border-radius: 8px; | |
opacity: 0; | |
} | |
</style> | |
</head> | |
<body> | |
<div id="container"> | |
<h1>Audience Comparison</h1> | |
<p>Venn Diagram created with Ben Federickson's "<a href="http://www.benfrederickson.com/better-venn-diagrams/">A Better Algorithm for Area Proportional Venn and Euler Diagrams</a>"</p> | |
<div id="venn_one" style=float:left> | |
<h3>Audience One</h3> | |
</div> | |
<div id="venn_two" style=float:left> | |
<h3>Audience Two</h3> | |
</div> | |
<script> | |
var sets = [ | |
{sets:["Audio"], figure: 8.91, label: "Audio", size: 8.91}, | |
{sets:["Direct Buy"], figure: 34.53, label: "Direct Buy", size: 34.53}, | |
{sets:["Branded Takeover"], figure: 40.9, label: "Branded Takeover", size: 40.9}, | |
{sets: ["Audio", "Direct Buy"], figure: 5.05, label: "Audio and Direct Buy", size: 5.05}, | |
{sets: ["Audio", "Branded Takeover"], figure: 3.65, label: "Audio and Branded Takeover", size: 3.65}, | |
{sets: ["Direct Buy", "Branded Takeover"], figure: 4.08, label: "Direct Buy and Branded Takeover", size: 4.08}, | |
{sets: ["Audio", "Direct Buy", "Branded Takeover"], figure: 2.8, label: "Audio, Direct Buy, and Branded Takeover", size: 2.8} | |
]; | |
var chart = venn.VennDiagram() | |
.width(500) | |
.height(400) | |
var div = d3.select("#venn_one").datum(sets).call(chart); | |
div.selectAll("text").style("fill", "white"); | |
div.selectAll(".venn-circle path") | |
.style("fill-opacity", .8) | |
.style("stroke-width", 1) | |
.style("stroke-opacity", 1) | |
.style("stroke", "fff"); | |
var tooltip = d3.select("#venn_one").append("div") | |
.attr("class", "venntooltip"); | |
div.selectAll("g") | |
.on("mouseover", function(d, i) { | |
// sort all the areas relative to the current item | |
venn.sortAreas(div, d); | |
// Display a tooltip with the current size | |
tooltip.transition().duration(40).style("opacity", 1); | |
tooltip.text(d.size + "% of Audience One saw " + d.label); | |
// highlight the current path | |
// highlight the current path | |
var selection = d3.select(this).transition("tooltip").duration(400); | |
selection.select("path") | |
.style("stroke-width", 3) | |
.style("fill-opacity", d.sets.length == 1 ? .8 : 0) | |
.style("stroke-opacity", 1); | |
}) | |
.on("mousemove", function() { | |
tooltip.style("left", (d3.event.pageX) + "px") | |
.style("top", (d3.event.pageY - 28) + "px"); | |
}) | |
.on("mouseout", function(d, i) { | |
tooltip.transition().duration(2000).style("opacity", 0); | |
var selection = d3.select(this).transition("tooltip").duration(400); | |
selection.select("path") | |
.style("stroke-width", 3) | |
.style("fill-opacity", d.sets.length == 1 ? .8 : 0) | |
.style("stroke-opacity", 1); | |
}); | |
var sets = [ | |
{sets:["Audio"], figure: 27.92, label: "Audio", size: 27.92}, | |
{sets:["Direct Buy"], figure: 55.28, label: "Direct Buy", size: 55.28}, | |
{sets:["Branded Takeover"], figure: 7.62, label: "Branded Takeover", size: 7.62}, | |
{sets: ["Audio", "Direct Buy"], figure: 3.03, label: "Audio and Direct Buy", size: 3.03}, | |
{sets: ["Audio", "Branded Takeover"], figure: 1.66, label: "Audio and Branded Takeover", size: 1.66}, | |
{sets: ["Direct Buy", "Branded Takeover"], figure: 2.40, label: "Direct Buy and Branded Takeover", size: 2.40}, | |
{sets: ["Audio", "Direct Buy", "Branded Takeover"], figure: 1.08, label: "Audio, Direct Buy, and Branded Takeover", size: 1.08} | |
]; | |
var chart = venn.VennDiagram() | |
.width(500) | |
.height(400) | |
var div2 = d3.select("#venn_two").datum(sets).call(chart); | |
div2.selectAll("text").style("fill", "white"); | |
div2.selectAll(".venn-circle path") | |
.style("fill-opacity", .8) | |
.style("stroke-width", 1) | |
.style("stroke-opacity", 1) | |
.style("stroke", "fff"); | |
var tooltip = d3.select("body").append("div") | |
.attr("class", "venntooltip"); | |
div2.selectAll("g") | |
.on("mouseover", function(d, i) { | |
// sort all the areas relative to the current item | |
venn.sortAreas(div2, d); | |
// Display a tooltip with the current size | |
tooltip.transition().duration(40).style("opacity", 1); | |
tooltip.text(d.size + "% of Audience Two saw " + d.label); | |
// highlight the current path | |
var selection = d3.select(this).transition("tooltip").duration(400); | |
selection.select("path") | |
.style("stroke-width", 3) | |
.style("fill-opacity", d.sets.length == 1 ? .8 : 0) | |
.style("stroke-opacity", 1); | |
}) | |
.on("mousemove", function() { | |
tooltip.style("left", (d3.event.pageX) + "px") | |
.style("top", (d3.event.pageY - 28) + "px"); | |
}) | |
.on("mouseout", function(d, i) { | |
tooltip.transition().duration(2500).style("opacity", 0); | |
var selection = d3.select(this).transition("tooltip").duration(400); | |
selection.select("path") | |
.style("stroke-width", 3) | |
.style("fill-opacity", d.sets.length == 1 ? .8 : 0) | |
.style("stroke-opacity", 1); | |
}); | |
//https://github.com/benfred/venn.js/issues/22 | |
</script> | |
</div> | |
</body> | |
</html> |
var venn = venn || {'version' : '0.2.5'}; | |
(function(venn) { | |
"use strict"; | |
venn.VennDiagram = function() { | |
var width = 800, | |
height = 650, | |
padding = 15, | |
duration = 1000, | |
orientation = Math.PI / 2, | |
normalize = true, | |
wrap = true, | |
styled = true, | |
fontSize = null, | |
colours = d3.scale.ordinal() | |
.range(["#0a2756","#e60024","#45CFD7","#a173d1", "#0FF66A3","#00FFFF","#6ab975","#5687d1", "#F5E94B", "bbbbbb", "#00B8E6"]), | |
layoutFunction = venn.venn; | |
function chart(selection) { | |
var data = selection.datum(); | |
var solution = layoutFunction(data); | |
if (normalize) { | |
solution = venn.normalizeSolution(solution, orientation); | |
} | |
var circles = venn.scaleSolution(solution, width, height, padding); | |
var textCentres = computeTextCentres(circles, data); | |
// draw out a svg | |
var svg = selection.selectAll("svg").data([circles]); | |
svg.enter().append("svg"); | |
svg.attr("width", width) | |
.attr("height", height); | |
// to properly transition intersection areas, we need the | |
// previous circles locations. load from elements | |
var previous = {}, hasPrevious = false; | |
svg.selectAll("g").each(function (d) { | |
var path = d3.select(this).select("path").attr("d"); | |
if ((d.sets.length == 1) && path) { | |
hasPrevious = true; | |
previous[d.sets[0]] = venn.circleFromPath(path); | |
} | |
}); | |
// interpolate intersection area paths between previous and | |
// current paths | |
var pathTween = function(d) { | |
return function(t) { | |
var c = d.sets.map(function(set) { | |
var start = previous[set], end = circles[set]; | |
if (!start) { | |
start = {x : width/2, y : height/2, radius : 1}; | |
} | |
if (!end) { | |
end = {x : width/2, y : height/2, radius : 1}; | |
} | |
return {'x' : start.x * (1 - t) + end.x * t, | |
'y' : start.y * (1 - t) + end.y * t, | |
'radius' : start.radius * (1 - t) + end.radius * t}; | |
}); | |
return venn.intersectionAreaPath(c); | |
}; | |
}; | |
// update data, joining on the set ids | |
var nodes = svg.selectAll("g") | |
.data(data, function(d) { return d.sets; }); | |
// create new nodes | |
var enter = nodes.enter() | |
.append('g') | |
.attr("class", function(d) { | |
return "venn-area venn-" + | |
(d.sets.length == 1 ? "circle" : "intersection"); | |
}) | |
.attr("data-venn-sets", function(d) { | |
return d.sets.join("_"); | |
}); | |
var enterPath = enter.append("path"), | |
enterText = enter.append("text") | |
.attr("class", "label") | |
.text(function (d) { return label(d); } ) | |
.attr("text-anchor", "middle") | |
.attr("dy", ".35em") | |
.attr("x", width/2) | |
.attr("y", height/2); | |
// apply minimal style if wanted | |
if (styled) { | |
enterPath.style("fill-opacity", "0") | |
.filter(function (d) { return d.sets.length == 1; } ) | |
.style("fill", function(d) { return colours(label(d)); }) | |
.style("fill-opacity", ".25"); | |
enterText | |
.style("fill", function(d) { return d.sets.length == 1 ? colours(label(d)) : "#444"; }); | |
} | |
// update existing | |
var update = nodes.transition("venn").duration(hasPrevious ? duration : 0); | |
update.select("path") | |
.attrTween("d", pathTween); | |
var updateText = update.select("text") | |
.text(function (d) { return label(d); } ) | |
.attr("x", function(d) { | |
return Math.floor(textCentres[d.sets].x); | |
}) | |
.attr("y", function(d) { | |
return Math.floor(textCentres[d.sets].y); | |
}); | |
if (wrap) { | |
updateText.each("end", venn.wrapText(circles, label)); | |
} | |
// remove old | |
var exit = nodes.exit().transition('venn').duration(duration).remove(); | |
exit.select("path") | |
.attrTween("d", pathTween); | |
var exitText = exit.select("text") | |
.text(function (d) { return label(d); } ) | |
.attr("x", width/2) | |
.attr("y", height/2); | |
// if we've been passed a fontSize explicitly, use it to | |
// transition | |
if (fontSize !== null) { | |
enterText.style("font-size", "0px"); | |
updateText.style("font-size", fontSize); | |
exitText.style("font-size", "0px"); | |
} | |
return {'circles': circles, | |
'textCentres': textCentres, | |
'nodes': nodes, | |
'enter': enter, | |
'update': update, | |
'exit': exit}; | |
} | |
function label(d) { | |
if (d.sets.length == 1) { | |
return '' + d.sets[0]; | |
} | |
} | |
chart.wrap = function(_) { | |
if (!arguments.length) return wrap; | |
wrap = _; | |
return chart; | |
}; | |
chart.width = function(_) { | |
if (!arguments.length) return width; | |
width = _; | |
return chart; | |
}; | |
chart.height = function(_) { | |
if (!arguments.length) return height; | |
height = _; | |
return chart; | |
}; | |
chart.padding = function(_) { | |
if (!arguments.length) return padding; | |
padding = _; | |
return chart; | |
}; | |
chart.colours = function(_) { | |
if (!arguments.length) return colours; | |
colours = _; | |
return chart; | |
}; | |
chart.fontSize = function(_) { | |
if (!arguments.length) return fontSize; | |
fontSize = _; | |
return chart; | |
}; | |
chart.duration = function(_) { | |
if (!arguments.length) return duration; | |
duration = _; | |
return chart; | |
}; | |
chart.layoutFunction = function(_) { | |
if (!arguments.length) return layoutFunction; | |
layoutFunction = _; | |
return chart; | |
}; | |
chart.normalize = function(_) { | |
if (!arguments.length) return normalize; | |
normalize = _; | |
return chart; | |
}; | |
chart.styled = function(_) { | |
if (!arguments.length) return styled; | |
styled = _; | |
return chart; | |
}; | |
chart.orientation = function(_) { | |
if (!arguments.length) return orientation; | |
orientation = _; | |
return chart; | |
}; | |
return chart; | |
}; | |
// sometimes text doesn't fit inside the circle, if thats the case lets wrap | |
// the text here such that it fits | |
// todo: looks like this might be merged into d3 ( | |
// https://github.com/mbostock/d3/issues/1642), | |
// also worth checking out is | |
// http://engineering.findthebest.com/wrapping-axis-labels-in-d3-js/ | |
// this seems to be one of those things that should be easy but isn't | |
venn.wrapText = function(circles, labeller) { | |
return function() { | |
var text = d3.select(this), | |
data = text.datum(), | |
width = circles[data.sets[0]].radius || 50, | |
label = labeller(data) || ''; | |
var words = label.split(/\s+/).reverse(), | |
maxLines = 3, | |
minChars = (label.length + words.length) / maxLines, | |
word = words.pop(), | |
line = [word], | |
joined, | |
lineNumber = 0, | |
lineHeight = 1.1, // ems | |
tspan = text.text(null).append("tspan").text(word); | |
while (true) { | |
word = words.pop(); | |
if (!word) break; | |
line.push(word); | |
joined = line.join(" "); | |
tspan.text(joined); | |
if (joined.length > minChars && tspan.node().getComputedTextLength() > width) { | |
line.pop(); | |
tspan.text(line.join(" ")); | |
line = [word]; | |
tspan = text.append("tspan").text(word); | |
lineNumber++; | |
} | |
} | |
var initial = 0.35 - lineNumber * lineHeight / 2, | |
x = text.attr("x"), | |
y = text.attr("y"); | |
text.selectAll("tspan") | |
.attr("x", x) | |
.attr("y", y) | |
.attr("dy", function(d, i) { | |
return (initial + i * lineHeight) + "em"; | |
}); | |
}; | |
}; | |
function circleMargin(current, interior, exterior) { | |
var margin = interior[0].radius - venn.distance(interior[0], current), i, m; | |
for (i = 1; i < interior.length; ++i) { | |
m = interior[i].radius - venn.distance(interior[i], current); | |
if (m <= margin) { | |
margin = m; | |
} | |
} | |
for (i = 0; i < exterior.length; ++i) { | |
m = venn.distance(exterior[i], current) - exterior[i].radius; | |
if (m <= margin) { | |
margin = m; | |
} | |
} | |
return margin; | |
} | |
// compute the center of some circles by maximizing the margin of | |
// the center point relative to the circles (interior) after subtracting | |
// nearby circles (exterior) | |
function computeTextCentre(interior, exterior) { | |
// get an initial estimate by sampling around the interior circles | |
// and taking the point with the biggest margin | |
var points = [], i; | |
for (i = 0; i < interior.length; ++i) { | |
var c = interior[i]; | |
points.push({x: c.x, y: c.y}); | |
points.push({x: c.x + c.radius/2, y: c.y}); | |
points.push({x: c.x - c.radius/2, y: c.y}); | |
points.push({x: c.x, y: c.y + c.radius/2}); | |
points.push({x: c.x, y: c.y - c.radius/2}); | |
} | |
var initial = points[0], margin = circleMargin(points[0], interior, exterior); | |
for (i = 1; i < points.length; ++i) { | |
var m = circleMargin(points[i], interior, exterior); | |
if (m >= margin) { | |
initial = points[i]; | |
margin = m; | |
} | |
} | |
// maximize the margin numerically | |
var solution = venn.fmin( | |
function(p) { return -1 * circleMargin({x: p[0], y: p[1]}, interior, exterior); }, | |
[initial.x, initial.y], | |
{maxIterations:500, minErrorDelta:1e-10}).solution; | |
var ret = {x: solution[0], y: solution[1]}; | |
// check solution, fallback as needed (happens if fully overlapped | |
// etc) | |
var valid = true; | |
for (i = 0; i < interior.length; ++i) { | |
if (venn.distance(ret, interior[i]) > interior[i].radius) { | |
valid = false; | |
break; | |
} | |
} | |
for (i = 0; i < exterior.length; ++i) { | |
if (venn.distance(ret, exterior[i]) < exterior[i].radius) { | |
valid = false; | |
break; | |
} | |
} | |
if (!valid) { | |
if (interior.length == 1) { | |
ret = {x: interior[0].x, y: interior[0].y}; | |
} else { | |
var areaStats = {}; | |
venn.intersectionArea(interior, areaStats); | |
if (areaStats.arcs.length === 0) { | |
ret = {'x': 0, 'y': -1000, disjoint:true}; | |
} else if (areaStats.arcs.length == 1) { | |
ret = {'x': areaStats.arcs[0].circle.x, | |
'y': areaStats.arcs[0].circle.y}; | |
} else if (exterior.length) { | |
// try again without other circles | |
ret = computeTextCentre(interior, []); | |
} else { | |
// take average of all the points in the intersection | |
// polygon. this should basically never happen | |
// and has some issues: | |
// https://github.com/benfred/venn.js/issues/48#issuecomment-146069777 | |
ret = venn.getCenter(areaStats.arcs.map(function (a) { return a.p1; })); | |
} | |
} | |
} | |
return ret; | |
} | |
venn.computeTextCentre = computeTextCentre; | |
// given a dictionary of {setid : circle}, returns | |
// a dictionary of setid to list of circles that completely overlap it | |
function getOverlappingCircles(circles) { | |
var ret = {}, circleids = []; | |
for (var circleid in circles) { | |
circleids.push(circleid); | |
ret[circleid] = []; | |
} | |
for (var i = 0; i < circleids.length; i++) { | |
var a = circles[circleids[i]]; | |
for (var j = i + 1; j < circleids.length; ++j) { | |
var b = circles[circleids[j]], | |
d = venn.distance(a, b); | |
if (d + b.radius <= a.radius + 1e-10) { | |
ret[circleids[j]].push(circleids[i]); | |
} else if (d + a.radius <= b.radius + 1e-10) { | |
ret[circleids[i]].push(circleids[j]); | |
} | |
} | |
} | |
return ret; | |
} | |
function computeTextCentres(circles, areas) { | |
var ret = {}, overlapped = getOverlappingCircles(circles); | |
for (var i = 0; i < areas.length; ++i) { | |
var area = areas[i].sets, areaids = {}, exclude = {}; | |
for (var j = 0; j < area.length; ++j) { | |
areaids[area[j]] = true; | |
var overlaps = overlapped[area[j]]; | |
// keep track of any circles that overlap this area, | |
// and don't consider for purposes of computing the text | |
// centre | |
for (var k = 0; k < overlaps.length; ++k) { | |
exclude[overlaps[k]] = true; | |
} | |
} | |
var interior = [], exterior = []; | |
for (var setid in circles) { | |
if (setid in areaids) { | |
interior.push(circles[setid]); | |
} else if (!(setid in exclude)) { | |
exterior.push(circles[setid]); | |
} | |
} | |
var centre = computeTextCentre(interior, exterior); | |
ret[area] = centre; | |
if (centre.disjoint && (areas[i].size > 0)) { | |
console.log("WARNING: area " + area + " not represented on screen"); | |
} | |
} | |
return ret; | |
} | |
venn.computeTextCentres = computeTextCentres; | |
// sorts all areas in the venn diagram, so that | |
// a particular area is on top (relativeTo) - and | |
// all other areas are so that the smallest areas are on top | |
venn.sortAreas = function(div, relativeTo) { | |
// figure out sets that are completly overlapped by relativeTo | |
var overlaps = getOverlappingCircles(div.selectAll("svg").datum()); | |
var exclude = {}; | |
for (var i = 0; i < relativeTo.sets.length; ++i) { | |
var check = relativeTo.sets[i]; | |
for (var setid in overlaps) { | |
var overlap = overlaps[setid]; | |
for (var j = 0; j < overlap.length; ++j) { | |
if (overlap[j] == check) { | |
exclude[setid] = true; | |
break; | |
} | |
} | |
} | |
} | |
// checks that all sets are in exclude; | |
function shouldExclude(sets) { | |
for (var i = 0; i < sets.length; ++i) { | |
if (!(sets[i] in exclude)) { | |
return false; | |
} | |
} | |
return true; | |
} | |
// need to sort div's so that Z order is correct | |
div.selectAll("g").sort(function (a, b) { | |
// highest order set intersections first | |
if (a.sets.length != b.sets.length) { | |
return a.sets.length - b.sets.length; | |
} | |
if (a == relativeTo) { | |
return shouldExclude(b.sets) ? -1 : 1; | |
} | |
if (b == relativeTo) { | |
return shouldExclude(a.sets) ? 1 : -1; | |
} | |
// finally by size | |
return b.size - a.size; | |
}); | |
}; | |
venn.circlePath = function(x, y, r) { | |
var ret = []; | |
ret.push("\nM", x, y); | |
ret.push("\nm", -r, 0); | |
ret.push("\na", r, r, 0, 1, 0, r *2, 0); | |
ret.push("\na", r, r, 0, 1, 0,-r *2, 0); | |
return ret.join(" "); | |
}; | |
// inverse of the circlePath function, returns a circle object from an svg path | |
venn.circleFromPath = function(path) { | |
var tokens = path.split(' '); | |
return {'x' : parseFloat(tokens[1]), | |
'y' : parseFloat(tokens[2]), | |
'radius' : -parseFloat(tokens[4]) | |
}; | |
}; | |
/** returns a svg path of the intersection area of a bunch of circles */ | |
venn.intersectionAreaPath = function(circles) { | |
var stats = {}; | |
venn.intersectionArea(circles, stats); | |
var arcs = stats.arcs; | |
if (arcs.length === 0) { | |
return "M 0 0"; | |
} else if (arcs.length == 1) { | |
var circle = arcs[0].circle; | |
return venn.circlePath(circle.x, circle.y, circle.radius); | |
} else { | |
// draw path around arcs | |
var ret = ["\nM", arcs[0].p2.x, arcs[0].p2.y]; | |
for (var i = 0; i < arcs.length; ++i) { | |
var arc = arcs[i], r = arc.circle.radius, wide = arc.width > r; | |
ret.push("\nA", r, r, 0, wide ? 1 : 0, 1, | |
arc.p1.x, arc.p1.y); | |
} | |
return ret.join(" "); | |
} | |
}; | |
})(venn); | |
(function(venn) { | |
"use strict"; | |
/** given a list of set objects, and their corresponding overlaps. | |
updates the (x, y, radius) attribute on each set such that their positions | |
roughly correspond to the desired overlaps */ | |
venn.venn = function(areas, parameters) { | |
parameters = parameters || {}; | |
parameters.maxIterations = parameters.maxIterations || 500; | |
var lossFunction = parameters.lossFunction || venn.lossFunction; | |
var initialLayout = parameters.initialLayout || venn.bestInitialLayout; | |
var fmin = parameters.fmin || venn.fmin; | |
// add in missing pairwise areas as having 0 size | |
areas = addMissingAreas(areas); | |
// initial layout is done greedily | |
var circles = initialLayout(areas); | |
// transform x/y coordinates to a vector to optimize | |
var initial = [], setids = [], setid; | |
for (setid in circles) { | |
if (circles.hasOwnProperty(setid)) { | |
initial.push(circles[setid].x); | |
initial.push(circles[setid].y); | |
setids.push(setid); | |
} | |
} | |
// optimize initial layout from our loss function | |
var totalFunctionCalls = 0; | |
var solution = fmin( | |
function(values) { | |
totalFunctionCalls += 1; | |
var current = {}; | |
for (var i = 0; i < setids.length; ++i) { | |
var setid = setids[i]; | |
current[setid] = {x: values[2 * i], | |
y: values[2 * i + 1], | |
radius : circles[setid].radius, | |
// size : circles[setid].size | |
}; | |
} | |
return lossFunction(current, areas); | |
}, | |
initial, | |
parameters); | |
// transform solution vector back to x/y points | |
var positions = solution.solution; | |
for (var i = 0; i < setids.length; ++i) { | |
setid = setids[i]; | |
circles[setid].x = positions[2 * i]; | |
circles[setid].y = positions[2 * i + 1]; | |
} | |
return circles; | |
}; | |
var SMALL = 1e-10; | |
/** Returns the distance necessary for two circles of radius r1 + r2 to | |
have the overlap area 'overlap' */ | |
venn.distanceFromIntersectArea = function(r1, r2, overlap) { | |
// handle complete overlapped circles | |
if (Math.min(r1, r2) * Math.min(r1,r2) * Math.PI <= overlap + SMALL) { | |
return Math.abs(r1 - r2); | |
} | |
return venn.bisect(function(distance) { | |
return venn.circleOverlap(r1, r2, distance) - overlap; | |
}, 0, r1 + r2); | |
}; | |
/** Missing pair-wise intersection area data can cause problems: | |
treating as an unknown means that sets will be laid out overlapping, | |
which isn't what people expect. To reflect that we want disjoint sets | |
here, set the overlap to 0 for all missing pairwise set intersections */ | |
function addMissingAreas(areas) { | |
areas = areas.slice(); | |
// two circle intersections that aren't defined | |
var ids = [], pairs = {}, i, j, a, b; | |
for (i = 0; i < areas.length; ++i) { | |
var area = areas[i]; | |
if (area.sets.length == 1) { | |
ids.push(area.sets[0]); | |
} else if (area.sets.length == 2) { | |
a = area.sets[0]; | |
b = area.sets[1]; | |
pairs[[a, b]] = true; | |
pairs[[b, a]] = true; | |
} | |
} | |
ids.sort(function(a, b) { return a > b; }); | |
for (i = 0; i < ids.length; ++i) { | |
a = ids[i]; | |
for (j = i + 1; j < ids.length; ++j) { | |
b = ids[j]; | |
if (!([a, b] in pairs)) { | |
areas.push({'sets': [a, b], | |
'size': 0}); | |
} | |
} | |
} | |
return areas; | |
} | |
/// Returns two matrices, one of the euclidean distances between the sets | |
/// and the other indicating if there are subset or disjoint set relationships | |
venn.getDistanceMatrices = function(areas, sets, setids) { | |
// initialize an empty distance matrix between all the points | |
var distances = venn.zerosM(sets.length, sets.length), | |
constraints = venn.zerosM(sets.length, sets.length); | |
// compute required distances between all the sets such that | |
// the areas match | |
areas.filter(function(x) { return x.sets.length == 2; }) | |
.map(function(current) { | |
var left = setids[current.sets[0]], | |
right = setids[current.sets[1]], | |
r1 = Math.sqrt(sets[left].size / Math.PI), | |
r2 = Math.sqrt(sets[right].size / Math.PI), | |
distance = venn.distanceFromIntersectArea(r1, r2, current.size); | |
distances[left][right] = distances[right][left] = distance; | |
// also update constraints to indicate if its a subset or disjoint | |
// relationship | |
var c = 0; | |
if (current.size + 1e-10 >= Math.min(sets[left].size, | |
sets[right].size)) { | |
c = 1; | |
} else if (current.size <= 1e-10) { | |
c = -1; | |
} | |
constraints[left][right] = constraints[right][left] = c; | |
}); | |
return {distances: distances, constraints: constraints}; | |
}; | |
/// computes the gradient and loss simulatenously for our constrained MDS optimizer | |
function constrainedMDSGradient(x, fxprime, distances, constraints) { | |
var loss = 0, i; | |
for (i = 0; i < fxprime.length; ++i) { | |
fxprime[i] = 0; | |
} | |
for (i = 0; i < distances.length; ++i) { | |
var xi = x[2 * i], yi = x[2 * i + 1]; | |
for (var j = i + 1; j < distances.length; ++j) { | |
var xj = x[2 * j], yj = x[2 * j + 1], | |
dij = distances[i][j], | |
constraint = constraints[i][j]; | |
var squaredDistance = (xj - xi) * (xj - xi) + (yj - yi) * (yj - yi), | |
distance = Math.sqrt(squaredDistance), | |
delta = squaredDistance - dij * dij; | |
if (((constraint > 0) && (distance <= dij)) || | |
((constraint < 0) && (distance >= dij))) { | |
continue; | |
} | |
loss += 2 * delta * delta; | |
fxprime[2*i] += 4 * delta * (xi - xj); | |
fxprime[2*i + 1] += 4 * delta * (yi - yj); | |
fxprime[2*j] += 4 * delta * (xj - xi); | |
fxprime[2*j + 1] += 4 * delta * (yj - yi); | |
} | |
} | |
return loss; | |
} | |
/// takes the best working variant of either constrained MDS or greedy | |
venn.bestInitialLayout = function(areas, params) { | |
var initial = venn.greedyLayout(areas, params); | |
// greedylayout is sufficient for all 2/3 circle cases. try out | |
// constrained MDS for higher order problems, take its output | |
// if it outperforms. (greedy is aesthetically better on 2/3 circles | |
// since it axis aligns) | |
if (areas.length >= 8) { | |
var constrained = venn.constrainedMDSLayout(areas, params), | |
constrainedLoss = venn.lossFunction(constrained, areas), | |
greedyLoss = venn.lossFunction(initial, areas); | |
if (constrainedLoss + 1e-8 < greedyLoss) { | |
initial = constrained; | |
} | |
} | |
return initial; | |
}; | |
/// use the constrained MDS variant to generate an initial layout | |
venn.constrainedMDSLayout = function(areas, params) { | |
params = params || {}; | |
var restarts = params.restarts || 10; | |
// bidirectionally map sets to a rowid (so we can create a matrix) | |
var sets = [], setids = {}, i; | |
for (i = 0; i < areas.length; ++i ) { | |
var area = areas[i]; | |
if (area.sets.length == 1) { | |
setids[area.sets[0]] = sets.length; | |
sets.push(area); | |
} | |
} | |
var matrices = venn.getDistanceMatrices(areas, sets, setids), | |
distances = matrices.distances, | |
constraints = matrices.constraints; | |
// keep distances bounded, things get messed up otherwise. | |
// TODO: proper preconditioner? | |
var norm = venn.norm2(distances.map(venn.norm2))/(distances.length); | |
distances = distances.map(function (row) { | |
return row.map(function (value) { return value / norm; });}); | |
var obj = function(x, fxprime) { | |
return constrainedMDSGradient(x, fxprime, distances, constraints); | |
}; | |
var best, current; | |
for (i = 0; i < restarts; ++i) { | |
var initial = venn.zeros(distances.length*2).map(Math.random); | |
current = venn.minimizeConjugateGradient(obj, initial, params); | |
if (!best || (current.fx < best.fx)) { | |
best = current; | |
} | |
} | |
var positions = best.x; | |
// translate rows back to (x,y,radius) coordinates | |
var circles = {}; | |
for (i = 0; i < sets.length; ++i) { | |
var set = sets[i]; | |
circles[set.sets[0]] = { | |
x: positions[2*i] * norm, | |
y: positions[2*i + 1] * norm, | |
radius: Math.sqrt(set.size / Math.PI) | |
}; | |
} | |
if (params.history) { | |
for (i = 0; i < params.history.length; ++i) { | |
venn.multiplyBy(params.history[i].x, norm); | |
} | |
} | |
return circles; | |
}; | |
/** Lays out a Venn diagram greedily, going from most overlapped sets to | |
least overlapped, attempting to position each new set such that the | |
overlapping areas to already positioned sets are basically right */ | |
venn.greedyLayout = function(areas) { | |
// define a circle for each set | |
var circles = {}, setOverlaps = {}, set; | |
for (var i = 0; i < areas.length; ++i) { | |
var area = areas[i]; | |
if (area.sets.length == 1) { | |
set = area.sets[0]; | |
circles[set] = {x: 1e10, y: 1e10, | |
rowid: circles.length, | |
size: area.size, | |
radius: Math.sqrt(area.size / Math.PI)}; | |
setOverlaps[set] = []; | |
} | |
} | |
areas = areas.filter(function(a) { return a.sets.length == 2; }); | |
// map each set to a list of all the other sets that overlap it | |
for (i = 0; i < areas.length; ++i) { | |
var current = areas[i]; | |
var weight = current.hasOwnProperty('weight') ? current.weight : 1.0; | |
var left = current.sets[0], right = current.sets[1]; | |
// completely overlapped circles shouldn't be positioned early here | |
if (current.size + SMALL >= Math.min(circles[left].size, | |
circles[right].size)) { | |
weight = 0; | |
} | |
setOverlaps[left].push ({set:right, size:current.size, weight:weight}); | |
setOverlaps[right].push({set:left, size:current.size, weight:weight}); | |
} | |
// get list of most overlapped sets | |
var mostOverlapped = []; | |
for (set in setOverlaps) { | |
if (setOverlaps.hasOwnProperty(set)) { | |
var size = 0; | |
for (i = 0; i < setOverlaps[set].length; ++i) { | |
size += setOverlaps[set][i].size * setOverlaps[set][i].weight; | |
} | |
mostOverlapped.push({set: set, size:size}); | |
} | |
} | |
// sort by size desc | |
function sortOrder(a,b) { | |
return b.size - a.size; | |
} | |
mostOverlapped.sort(sortOrder); | |
// keep track of what sets have been laid out | |
var positioned = {}; | |
function isPositioned(element) { | |
return element.set in positioned; | |
} | |
// adds a point to the output | |
function positionSet(point, index) { | |
circles[index].x = point.x; | |
circles[index].y = point.y; | |
positioned[index] = true; | |
} | |
// add most overlapped set at (0,0) | |
positionSet({x: 0, y: 0}, mostOverlapped[0].set); | |
// get distances between all points. TODO, necessary? | |
// answer: probably not | |
// var distances = venn.getDistanceMatrices(circles, areas).distances; | |
for (i = 1; i < mostOverlapped.length; ++i) { | |
var setIndex = mostOverlapped[i].set, | |
overlap = setOverlaps[setIndex].filter(isPositioned); | |
set = circles[setIndex]; | |
overlap.sort(sortOrder); | |
if (overlap.length === 0) { | |
// this shouldn't happen anymore with addMissingAreas | |
throw "ERROR: missing pairwise overlap information"; | |
} | |
var points = []; | |
for (var j = 0; j < overlap.length; ++j) { | |
// get appropriate distance from most overlapped already added set | |
var p1 = circles[overlap[j].set], | |
d1 = venn.distanceFromIntersectArea(set.radius, p1.radius, | |
overlap[j].size); | |
// sample positions at 90 degrees for maximum aesthetics | |
points.push({x : p1.x + d1, y : p1.y}); | |
points.push({x : p1.x - d1, y : p1.y}); | |
points.push({y : p1.y + d1, x : p1.x}); | |
points.push({y : p1.y - d1, x : p1.x}); | |
// if we have at least 2 overlaps, then figure out where the | |
// set should be positioned analytically and try those too | |
for (var k = j + 1; k < overlap.length; ++k) { | |
var p2 = circles[overlap[k].set], | |
d2 = venn.distanceFromIntersectArea(set.radius, p2.radius, | |
overlap[k].size); | |
var extraPoints = venn.circleCircleIntersection( | |
{ x: p1.x, y: p1.y, radius: d1}, | |
{ x: p2.x, y: p2.y, radius: d2}); | |
for (var l = 0; l < extraPoints.length; ++l) { | |
points.push(extraPoints[l]); | |
} | |
} | |
} | |
// we have some candidate positions for the set, examine loss | |
// at each position to figure out where to put it at | |
var bestLoss = 1e50, bestPoint = points[0]; | |
for (j = 0; j < points.length; ++j) { | |
circles[setIndex].x = points[j].x; | |
circles[setIndex].y = points[j].y; | |
var loss = venn.lossFunction(circles, areas); | |
if (loss < bestLoss) { | |
bestLoss = loss; | |
bestPoint = points[j]; | |
} | |
} | |
positionSet(bestPoint, setIndex); | |
} | |
return circles; | |
}; | |
/// Uses multidimensional scaling to approximate a first layout here | |
venn.classicMDSLayout = function(areas) { | |
// bidirectionally map sets to a rowid (so we can create a matrix) | |
var sets = [], setids = {}; | |
for (var i = 0; i < areas.length; ++i ) { | |
var area = areas[i]; | |
if (area.sets.length == 1) { | |
setids[area.sets[0]] = sets.length; | |
sets.push(area); | |
} | |
} | |
// get the distance matrix, and use to position sets | |
var distances = venn.getDistanceMatrices(areas, sets, setids).distances; | |
var positions = mds.classic(distances); | |
// translate rows back to (x,y,radius) coordinates | |
var circles = {}; | |
for (i = 0; i < sets.length; ++i) { | |
var set = sets[i]; | |
circles[set.sets[0]] = { | |
x: positions[i][0], | |
y: positions[i][1], | |
radius: Math.sqrt(set.size / Math.PI) | |
}; | |
} | |
return circles; | |
}; | |
/** Given a bunch of sets, and the desired overlaps between these sets - computes | |
the distance from the actual overlaps to the desired overlaps. Note that | |
this method ignores overlaps of more than 2 circles */ | |
venn.lossFunction = function(sets, overlaps) { | |
var output = 0; | |
function getCircles(indices) { | |
return indices.map(function(i) { return sets[i]; }); | |
} | |
for (var i = 0; i < overlaps.length; ++i) { | |
var area = overlaps[i], overlap; | |
if (area.sets.length == 1) { | |
continue; | |
} else if (area.sets.length == 2) { | |
var left = sets[area.sets[0]], | |
right = sets[area.sets[1]]; | |
overlap = venn.circleOverlap(left.radius, right.radius, | |
venn.distance(left, right)); | |
} else { | |
overlap = venn.intersectionArea(getCircles(area.sets)); | |
} | |
var weight = area.hasOwnProperty('weight') ? area.weight : 1.0; | |
output += weight * (overlap - area.size) * (overlap - area.size); | |
} | |
return output; | |
}; | |
// orientates a bunch of circles to point in orientation | |
function orientateCircles(circles, orientation) { | |
// sort circles by size | |
circles.sort(function (a, b) { return b.radius - a.radius; }); | |
var i; | |
// shift circles so largest circle is at (0, 0) | |
if (circles.length > 0) { | |
var largestX = circles[0].x, | |
largestY = circles[0].y; | |
for (i = 0; i < circles.length; ++i) { | |
circles[i].x -= largestX; | |
circles[i].y -= largestY; | |
} | |
} | |
// rotate circles so that second largest is at an angle of 'orientation' | |
// from largest | |
if (circles.length > 1) { | |
var rotation = Math.atan2(circles[1].x, circles[1].y) - orientation, | |
c = Math.cos(rotation), | |
s = Math.sin(rotation), x, y; | |
for (i = 0; i < circles.length; ++i) { | |
x = circles[i].x; | |
y = circles[i].y; | |
circles[i].x = c * x - s * y; | |
circles[i].y = s * x + c * y; | |
} | |
} | |
// mirror solution if third solution is above plane specified by | |
// first two circles | |
if (circles.length > 2) { | |
var angle = Math.atan2(circles[2].x, circles[2].y) - orientation; | |
while (angle < 0) { angle += 2* Math.PI; } | |
while (angle > 2*Math.PI) { angle -= 2* Math.PI; } | |
if (angle > Math.PI) { | |
var slope = circles[1].y / (1e-10 + circles[1].x); | |
for (i = 0; i < circles.length; ++i) { | |
var d = (circles[i].x + slope * circles[i].y) / (1 + slope*slope); | |
circles[i].x = 2 * d - circles[i].x; | |
circles[i].y = 2 * d * slope - circles[i].y; | |
} | |
} | |
} | |
} | |
venn.disjointCluster = function(circles) { | |
// union-find clustering to get disjoint sets | |
circles.map(function(circle) { circle.parent = circle; }); | |
// path compression step in union find | |
function find(circle) { | |
if (circle.parent !== circle) { | |
circle.parent = find(circle.parent); | |
} | |
return circle.parent; | |
} | |
function union(x, y) { | |
var xRoot = find(x), yRoot = find(y); | |
xRoot.parent = yRoot; | |
} | |
// get the union of all overlapping sets | |
for (var i = 0; i < circles.length; ++i) { | |
for (var j = i + 1; j < circles.length; ++j) { | |
var maxDistance = circles[i].radius + circles[j].radius; | |
if (venn.distance(circles[i], circles[j]) + 1e-10 < maxDistance) { | |
union(circles[j], circles[i]); | |
} | |
} | |
} | |
// find all the disjoint clusters and group them together | |
var disjointClusters = {}, setid; | |
for (i = 0; i < circles.length; ++i) { | |
setid = find(circles[i]).parent.setid; | |
if (!(setid in disjointClusters)) { | |
disjointClusters[setid] = []; | |
} | |
disjointClusters[setid].push(circles[i]); | |
} | |
// cleanup bookkeeping | |
circles.map(function(circle) { delete circle.parent; }); | |
// return in more usable form | |
var ret = []; | |
for (setid in disjointClusters) { | |
if (disjointClusters.hasOwnProperty(setid)) { | |
ret.push(disjointClusters[setid]); | |
} | |
} | |
return ret; | |
}; | |
function getBoundingBox(circles) { | |
var minMax = function(d) { | |
var hi = Math.max.apply(null, circles.map( | |
function(c) { return c[d] + c.radius; } )), | |
lo = Math.min.apply(null, circles.map( | |
function(c) { return c[d] - c.radius;} )); | |
return {max:hi, min:lo}; | |
}; | |
return {xRange: minMax('x'), yRange: minMax('y')}; | |
} | |
venn.normalizeSolution = function(solution, orientation) { | |
orientation = orientation || Math.PI/2; | |
// work with a list instead of a dictionary, and take a copy so we | |
// don't mutate input | |
var circles = [], i, setid; | |
for (setid in solution) { | |
if (solution.hasOwnProperty(setid)) { | |
var previous = solution[setid]; | |
circles.push({x: previous.x, | |
y: previous.y, | |
radius: previous.radius, | |
setid: setid}); | |
} | |
} | |
// get all the disjoint clusters | |
var clusters = venn.disjointCluster(circles); | |
// orientate all disjoint sets, get sizes | |
for (i = 0; i < clusters.length; ++i) { | |
orientateCircles(clusters[i], orientation); | |
var bounds = getBoundingBox(clusters[i]); | |
clusters[i].size = (bounds.xRange.max - bounds.xRange.min) * (bounds.yRange.max - bounds.yRange.min); | |
clusters[i].bounds = bounds; | |
} | |
clusters.sort(function(a, b) { return b.size - a.size; }); | |
// orientate the largest at 0,0, and get the bounds | |
circles = clusters[0]; | |
var returnBounds = circles.bounds; | |
var spacing = (returnBounds.xRange.max - returnBounds.xRange.min)/50; | |
function addCluster(cluster, right, bottom) { | |
if (!cluster) return; | |
var bounds = cluster.bounds, xOffset, yOffset, centreing; | |
if (right) { | |
xOffset = returnBounds.xRange.max - bounds.xRange.min + spacing; | |
} else { | |
xOffset = returnBounds.xRange.max - bounds.xRange.max - spacing; | |
centreing = (bounds.xRange.max - bounds.xRange.min) / 2 - | |
(returnBounds.xRange.max - returnBounds.xRange.min) / 2; | |
if (centreing < 0) xOffset += centreing; | |
} | |
if (bottom) { | |
yOffset = returnBounds.yRange.max - bounds.yRange.min + spacing; | |
} else { | |
yOffset = returnBounds.yRange.max - bounds.yRange.max - spacing; | |
centreing = (bounds.yRange.max - bounds.yRange.min) / 2 - | |
(returnBounds.yRange.max - returnBounds.yRange.min) / 2; | |
if (centreing < 0) yOffset += centreing; | |
} | |
for (var j = 0; j < cluster.length; ++j) { | |
cluster[j].x += xOffset; | |
cluster[j].y += yOffset; | |
circles.push(cluster[j]); | |
} | |
} | |
var index = 1; | |
while (index < clusters.length) { | |
addCluster(clusters[index], true, false); | |
addCluster(clusters[index+1], false, true); | |
addCluster(clusters[index+2], true, true); | |
index += 3; | |
// have one cluster (in top left). lay out next three relative | |
// to it in a grid | |
returnBounds = getBoundingBox(circles); | |
} | |
// convert back to solution form | |
var ret = {}; | |
for (i = 0; i < circles.length; ++i) { | |
ret[circles[i].setid] = circles[i]; | |
} | |
return ret; | |
}; | |
/** Scales a solution from venn.venn or venn.greedyLayout such that it fits in | |
a rectangle of width/height - with padding around the borders. also | |
centers the diagram in the available space at the same time */ | |
venn.scaleSolution = function(solution, width, height, padding) { | |
var circles = [], setids = []; | |
for (var setid in solution) { | |
if (solution.hasOwnProperty(setid)) { | |
setids.push(setid); | |
circles.push(solution[setid]); | |
} | |
} | |
width -= 2*padding; | |
height -= 2*padding; | |
var bounds = getBoundingBox(circles), | |
xRange = bounds.xRange, | |
yRange = bounds.yRange, | |
xScaling = width / (xRange.max - xRange.min), | |
yScaling = height / (yRange.max - yRange.min), | |
scaling = Math.min(yScaling, xScaling), | |
// while we're at it, center the diagram too | |
xOffset = (width - (xRange.max - xRange.min) * scaling) / 2, | |
yOffset = (height - (yRange.max - yRange.min) * scaling) / 2; | |
var scaled = {}; | |
for (var i = 0; i < circles.length; ++i) { | |
var circle = circles[i]; | |
scaled[setids[i]] = { | |
radius: scaling * circle.radius, | |
x: padding + xOffset + (circle.x - xRange.min) * scaling, | |
y: padding + yOffset + (circle.y - yRange.min) * scaling, | |
}; | |
} | |
return scaled; | |
}; | |
})(venn); | |
(function(venn) { | |
"use strict"; | |
/** finds the zeros of a function, given two starting points (which must | |
* have opposite signs */ | |
venn.bisect = function(f, a, b, parameters) { | |
parameters = parameters || {}; | |
var maxIterations = parameters.maxIterations || 100, | |
tolerance = parameters.tolerance || 1e-10, | |
fA = f(a), | |
fB = f(b), | |
delta = b - a; | |
if (fA * fB > 0) { | |
throw "Initial bisect points must have opposite signs"; | |
} | |
if (fA === 0) return a; | |
if (fB === 0) return b; | |
for (var i = 0; i < maxIterations; ++i) { | |
delta /= 2; | |
var mid = a + delta, | |
fMid = f(mid); | |
if (fMid * fA >= 0) { | |
a = mid; | |
} | |
if ((Math.abs(delta) < tolerance) || (fMid === 0)) { | |
return mid; | |
} | |
} | |
return a + delta; | |
}; | |
// need some basic operations on vectors, rather than adding a dependency, | |
// just define here | |
function zeros(x) { var r = new Array(x); for (var i = 0; i < x; ++i) { r[i] = 0; } return r; } | |
function zerosM(x,y) { return zeros(x).map(function() { return zeros(y); }); } | |
venn.zerosM = zerosM; | |
venn.zeros = zeros; | |
function dot(a, b) { | |
var ret = 0; | |
for (var i = 0; i < a.length; ++i) { | |
ret += a[i] * b[i]; | |
} | |
return ret; | |
} | |
function norm2(a) { | |
return Math.sqrt(dot(a, a)); | |
} | |
venn.norm2 = norm2; | |
function multiplyBy(a, c) { | |
for (var i = 0; i < a.length; ++i) { | |
a[i] *= c; | |
} | |
} | |
venn.multiplyBy = multiplyBy; | |
function weightedSum(ret, w1, v1, w2, v2) { | |
for (var j = 0; j < ret.length; ++j) { | |
ret[j] = w1 * v1[j] + w2 * v2[j]; | |
} | |
} | |
/** minimizes a function using the downhill simplex method */ | |
venn.fmin = function(f, x0, parameters) { | |
parameters = parameters || {}; | |
var maxIterations = parameters.maxIterations || x0.length * 200, | |
nonZeroDelta = parameters.nonZeroDelta || 1.1, | |
zeroDelta = parameters.zeroDelta || 0.001, | |
minErrorDelta = parameters.minErrorDelta || 1e-6, | |
rho = parameters.rho || 1, | |
chi = parameters.chi || 2, | |
psi = parameters.psi || -0.5, | |
sigma = parameters.sigma || 0.5, | |
callback = parameters.callback, | |
temp; | |
// initialize simplex. | |
var N = x0.length, | |
simplex = new Array(N + 1); | |
simplex[0] = x0; | |
simplex[0].fx = f(x0); | |
for (var i = 0; i < N; ++i) { | |
var point = x0.slice(); | |
point[i] = point[i] ? point[i] * nonZeroDelta : zeroDelta; | |
simplex[i+1] = point; | |
simplex[i+1].fx = f(point); | |
} | |
var sortOrder = function(a, b) { return a.fx - b.fx; }; | |
var centroid = x0.slice(), | |
reflected = x0.slice(), | |
contracted = x0.slice(), | |
expanded = x0.slice(); | |
for (var iteration = 0; iteration < maxIterations; ++iteration) { | |
simplex.sort(sortOrder); | |
if (callback) { | |
callback(simplex); | |
} | |
if (Math.abs(simplex[0].fx - simplex[N].fx) < minErrorDelta) { | |
break; | |
} | |
// compute the centroid of all but the worst point in the simplex | |
for (i = 0; i < N; ++i) { | |
centroid[i] = 0; | |
for (var j = 0; j < N; ++j) { | |
centroid[i] += simplex[j][i]; | |
} | |
centroid[i] /= N; | |
} | |
// reflect the worst point past the centroid and compute loss at reflected | |
// point | |
var worst = simplex[N]; | |
weightedSum(reflected, 1+rho, centroid, -rho, worst); | |
reflected.fx = f(reflected); | |
// if the reflected point is the best seen, then possibly expand | |
if (reflected.fx <= simplex[0].fx) { | |
weightedSum(expanded, 1+chi, centroid, -chi, worst); | |
expanded.fx = f(expanded); | |
if (expanded.fx < reflected.fx) { | |
temp = simplex[N]; | |
simplex[N] = expanded; | |
expanded = temp; | |
} else { | |
temp = simplex[N]; | |
simplex[N] = reflected; | |
reflected = temp; | |
} | |
} | |
// if the reflected point is worse than the second worst, we need to | |
// contract | |
else if (reflected.fx >= simplex[N-1].fx) { | |
var shouldReduce = false; | |
if (reflected.fx <= worst.fx) { | |
// do an inside contraction | |
weightedSum(contracted, 1+psi, centroid, -psi, worst); | |
contracted.fx = f(contracted); | |
if (contracted.fx < worst.fx) { | |
temp = simplex[N]; | |
simplex[N] = contracted; | |
contracted = temp; | |
} else { | |
shouldReduce = true; | |
} | |
} else { | |
// do an outside contraction | |
weightedSum(contracted, 1-psi * rho, centroid, psi*rho, worst); | |
contracted.fx = f(contracted); | |
if (contracted.fx <= reflected.fx) { | |
temp = simplex[N]; | |
simplex[N] = contracted; | |
contracted = temp; | |
} else { | |
shouldReduce = true; | |
} | |
} | |
if (shouldReduce) { | |
// do reduction. doesn't actually happen that often | |
for (i = 1; i < simplex.length; ++i) { | |
weightedSum(simplex[i], 1 - sigma, simplex[0], sigma - 1, simplex[i]); | |
simplex[i].fx = f(simplex[i]); | |
} | |
} | |
} else { | |
temp = simplex[N]; | |
simplex[N] = reflected; | |
reflected = temp; | |
} | |
} | |
simplex.sort(sortOrder); | |
return {f : simplex[0].fx, | |
solution : simplex[0]}; | |
}; | |
venn.minimizeConjugateGradient = function(f, initial, params) { | |
// allocate all memory up front here, keep out of the loop for perfomance | |
// reasons | |
var current = {x: initial.slice(), fx: 0, fxprime: initial.slice()}, | |
next = {x: initial.slice(), fx: 0, fxprime: initial.slice()}, | |
yk = initial.slice(), | |
pk, temp, | |
a = 1, | |
maxIterations; | |
params = params || {}; | |
maxIterations = params.maxIterations || initial.length * 5; | |
current.fx = f(current.x, current.fxprime); | |
pk = current.fxprime.slice(); | |
multiplyBy(pk, -1); | |
for (var i = 0; i < maxIterations; ++i) { | |
if (params.history) { | |
params.history.push({x: current.x.slice(), | |
fx: current.fx, | |
fxprime: current.fxprime.slice()}); | |
} | |
a = venn.wolfeLineSearch(f, pk, current, next, a); | |
if (!a) { | |
// faiiled to find point that satifies wolfe conditions. | |
// reset direction for next iteration | |
for (var j = 0; j < pk.length; ++j) { | |
pk[j] = -1 * current.fxprime[j]; | |
} | |
} else { | |
// update direction using Polak–Ribiere CG method | |
weightedSum(yk, 1, next.fxprime, -1, current.fxprime); | |
var delta_k = dot(current.fxprime, current.fxprime), | |
beta_k = Math.max(0, dot(yk, next.fxprime) / delta_k); | |
weightedSum(pk, beta_k, pk, -1, next.fxprime); | |
temp = current; | |
current = next; | |
next = temp; | |
} | |
if (norm2(current.fxprime) <= 1e-5) { | |
break; | |
} | |
} | |
if (params.history) { | |
params.history.push({x: current.x.slice(), | |
fx: current.fx, | |
fxprime: current.fxprime.slice()}); | |
} | |
return current; | |
}; | |
var c1 = 1e-6, c2 = 0.1; | |
/// searches along line 'pk' for a point that satifies the wolfe conditions | |
/// See 'Numerical Optimization' by Nocedal and Wright p59-60 | |
venn.wolfeLineSearch = function(f, pk, current, next, a) { | |
var phi0 = current.fx, phiPrime0 = dot(current.fxprime, pk), | |
phi = phi0, phi_old = phi0, | |
phiPrime = phiPrime0, | |
a0 = 0; | |
a = a || 1; | |
function zoom(a_lo, a_high, phi_lo) { | |
for (var iteration = 0; iteration < 16; ++iteration) { | |
a = (a_lo + a_high)/2; | |
weightedSum(next.x, 1.0, current.x, a, pk); | |
phi = next.fx = f(next.x, next.fxprime); | |
phiPrime = dot(next.fxprime, pk); | |
if ((phi > (phi0 + c1 * a * phiPrime0)) || | |
(phi >= phi_lo)) { | |
a_high = a; | |
} else { | |
if (Math.abs(phiPrime) <= -c2 * phiPrime0) { | |
return a; | |
} | |
if (phiPrime * (a_high - a_lo) >=0) { | |
a_high = a_lo; | |
} | |
a_lo = a; | |
phi_lo = phi; | |
} | |
} | |
return 0; | |
} | |
for (var iteration = 0; iteration < 10; ++iteration) { | |
weightedSum(next.x, 1.0, current.x, a, pk); | |
phi = next.fx = f(next.x, next.fxprime); | |
phiPrime = dot(next.fxprime, pk); | |
if ((phi > (phi0 + c1 * a * phiPrime0)) || | |
(iteration && (phi >= phi_old))) { | |
return zoom(a0, a, phi_old); | |
} | |
if (Math.abs(phiPrime) <= -c2 * phiPrime0) { | |
return a; | |
} | |
if (phiPrime >= 0 ) { | |
return zoom(a, a0, phi); | |
} | |
phi_old = phi; | |
a0 = a; | |
a *= 2; | |
} | |
return 0; | |
}; | |
})(venn); | |
(function(venn) { | |
"use strict"; | |
var SMALL = 1e-10; | |
/** Returns the intersection area of a bunch of circles (where each circle | |
is an object having an x,y and radius property) */ | |
venn.intersectionArea = function(circles, stats) { | |
// get all the intersection points of the circles | |
var intersectionPoints = getIntersectionPoints(circles); | |
// filter out points that aren't included in all the circles | |
var innerPoints = intersectionPoints.filter(function (p) { | |
return venn.containedInCircles(p, circles); | |
}); | |
var arcArea = 0, polygonArea = 0, arcs = [], i; | |
// if we have intersection points that are within all the circles, | |
// then figure out the area contained by them | |
if (innerPoints.length > 1) { | |
// sort the points by angle from the center of the polygon, which lets | |
// us just iterate over points to get the edges | |
var center = venn.getCenter(innerPoints); | |
for (i = 0; i < innerPoints.length; ++i ) { | |
var p = innerPoints[i]; | |
p.angle = Math.atan2(p.x - center.x, p.y - center.y); | |
} | |
innerPoints.sort(function(a,b) { return b.angle - a.angle;}); | |
// iterate over all points, get arc between the points | |
// and update the areas | |
var p2 = innerPoints[innerPoints.length - 1]; | |
for (i = 0; i < innerPoints.length; ++i) { | |
var p1 = innerPoints[i]; | |
// polygon area updates easily ... | |
polygonArea += (p2.x + p1.x) * (p1.y - p2.y); | |
// updating the arc area is a little more involved | |
var midPoint = {x : (p1.x + p2.x) / 2, | |
y : (p1.y + p2.y) / 2}, | |
arc = null; | |
for (var j = 0; j < p1.parentIndex.length; ++j) { | |
if (p2.parentIndex.indexOf(p1.parentIndex[j]) > -1) { | |
// figure out the angle halfway between the two points | |
// on the current circle | |
var circle = circles[p1.parentIndex[j]], | |
a1 = Math.atan2(p1.x - circle.x, p1.y - circle.y), | |
a2 = Math.atan2(p2.x - circle.x, p2.y - circle.y); | |
var angleDiff = (a2 - a1); | |
if (angleDiff < 0) { | |
angleDiff += 2*Math.PI; | |
} | |
// and use that angle to figure out the width of the | |
// arc | |
var a = a2 - angleDiff/2, | |
width = venn.distance(midPoint, { | |
x : circle.x + circle.radius * Math.sin(a), | |
y : circle.y + circle.radius * Math.cos(a) | |
}); | |
// pick the circle whose arc has the smallest width | |
if ((arc === null) || (arc.width > width)) { | |
arc = { circle : circle, | |
width : width, | |
p1 : p1, | |
p2 : p2}; | |
} | |
} | |
} | |
arcs.push(arc); | |
arcArea += venn.circleArea(arc.circle.radius, arc.width); | |
p2 = p1; | |
} | |
} else { | |
// no intersection points, is either disjoint - or is completely | |
// overlapped. figure out which by examining the smallest circle | |
var smallest = circles[0]; | |
for (i = 1; i < circles.length; ++i) { | |
if (circles[i].radius < smallest.radius) { | |
smallest = circles[i]; | |
} | |
} | |
// make sure the smallest circle is completely contained in all | |
// the other circles | |
var disjoint = false; | |
for (i = 0; i < circles.length; ++i) { | |
if (venn.distance(circles[i], smallest) > Math.abs(smallest.radius - circles[i].radius)) { | |
disjoint = true; | |
break; | |
} | |
} | |
if (disjoint) { | |
arcArea = polygonArea = 0; | |
} else { | |
arcArea = smallest.radius * smallest.radius * Math.PI; | |
arcs.push({circle : smallest, | |
p1: { x: smallest.x, y : smallest.y + smallest.radius}, | |
p2: { x: smallest.x - SMALL, y : smallest.y + smallest.radius}, | |
width : smallest.radius * 2 }); | |
} | |
} | |
polygonArea /= 2; | |
if (stats) { | |
stats.area = arcArea + polygonArea; | |
stats.arcArea = arcArea; | |
stats.polygonArea = polygonArea; | |
stats.arcs = arcs; | |
stats.innerPoints = innerPoints; | |
stats.intersectionPoints = intersectionPoints; | |
} | |
return arcArea + polygonArea; | |
}; | |
/** returns whether a point is contained by all of a list of circles */ | |
venn.containedInCircles = function(point, circles) { | |
for (var i = 0; i < circles.length; ++i) { | |
if (venn.distance(point, circles[i]) > circles[i].radius + SMALL) { | |
return false; | |
} | |
} | |
return true; | |
}; | |
/** Gets all intersection points between a bunch of circles */ | |
function getIntersectionPoints(circles) { | |
var ret = []; | |
for (var i = 0; i < circles.length; ++i) { | |
for (var j = i + 1; j < circles.length; ++j) { | |
var intersect = venn.circleCircleIntersection(circles[i], | |
circles[j]); | |
for (var k = 0; k < intersect.length; ++k) { | |
var p = intersect[k]; | |
p.parentIndex = [i,j]; | |
ret.push(p); | |
} | |
} | |
} | |
return ret; | |
} | |
venn.circleIntegral = function(r, x) { | |
var y = Math.sqrt(r * r - x * x); | |
return x * y + r * r * Math.atan2(x, y); | |
}; | |
/** Returns the area of a circle of radius r - up to width */ | |
venn.circleArea = function(r, width) { | |
return venn.circleIntegral(r, width - r) - venn.circleIntegral(r, -r); | |
}; | |
/** euclidean distance between two points */ | |
venn.distance = function(p1, p2) { | |
return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + | |
(p1.y - p2.y) * (p1.y - p2.y)); | |
}; | |
/** Returns the overlap area of two circles of radius r1 and r2 - that | |
have their centers separated by distance d. Simpler faster | |
circle intersection for only two circles */ | |
venn.circleOverlap = function(r1, r2, d) { | |
// no overlap | |
if (d >= r1 + r2) { | |
return 0; | |
} | |
// completely overlapped | |
if (d <= Math.abs(r1 - r2)) { | |
return Math.PI * Math.min(r1, r2) * Math.min(r1, r2); | |
} | |
var w1 = r1 - (d * d - r2 * r2 + r1 * r1) / (2 * d), | |
w2 = r2 - (d * d - r1 * r1 + r2 * r2) / (2 * d); | |
return venn.circleArea(r1, w1) + venn.circleArea(r2, w2); | |
}; | |
/** Given two circles (containing a x/y/radius attributes), | |
returns the intersecting points if possible. | |
note: doesn't handle cases where there are infinitely many | |
intersection points (circles are equivalent):, or only one intersection point*/ | |
venn.circleCircleIntersection = function(p1, p2) { | |
var d = venn.distance(p1, p2), | |
r1 = p1.radius, | |
r2 = p2.radius; | |
// if to far away, or self contained - can't be done | |
if ((d >= (r1 + r2)) || (d <= Math.abs(r1 - r2))) { | |
return []; | |
} | |
var a = (r1 * r1 - r2 * r2 + d * d) / (2 * d), | |
h = Math.sqrt(r1 * r1 - a * a), | |
x0 = p1.x + a * (p2.x - p1.x) / d, | |
y0 = p1.y + a * (p2.y - p1.y) / d, | |
rx = -(p2.y - p1.y) * (h / d), | |
ry = -(p2.x - p1.x) * (h / d); | |
return [{ x: x0 + rx, y : y0 - ry }, | |
{ x: x0 - rx, y : y0 + ry }]; | |
}; | |
/** Returns the center of a bunch of points */ | |
venn.getCenter = function(points) { | |
var center = { x: 0, y: 0}; | |
for (var i =0; i < points.length; ++i ) { | |
center.x += points[i].x; | |
center.y += points[i].y; | |
} | |
center.x /= points.length; | |
center.y /= points.length; | |
return center; | |
}; | |
})(venn); | |
(function(lib) { | |
if (typeof module === "undefined" || typeof module.exports === "undefined") { | |
window.venn = lib; | |
} else { | |
module.exports = lib; | |
} | |
})(venn); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment