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