1(function (global, factory) { 2 typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('d3-selection'), require('d3-transition')) : 3 typeof define === 'function' && define.amd ? define(['exports', 'd3-selection', 'd3-transition'], factory) : 4 (factory((global.venn = {}),global.d3,global.d3)); 5}(this, (function (exports,d3Selection,d3Transition) { 'use strict'; 6 7 var SMALL = 1e-10; 8 9 /** Returns the intersection area of a bunch of circles (where each circle 10 is an object having an x,y and radius property) */ 11 function intersectionArea(circles, stats) { 12 // get all the intersection points of the circles 13 var intersectionPoints = getIntersectionPoints(circles); 14 15 // filter out points that aren't included in all the circles 16 var innerPoints = intersectionPoints.filter(function (p) { 17 return containedInCircles(p, circles); 18 }); 19 20 var arcArea = 0, polygonArea = 0, arcs = [], i; 21 22 // if we have intersection points that are within all the circles, 23 // then figure out the area contained by them 24 if (innerPoints.length > 1) { 25 // sort the points by angle from the center of the polygon, which lets 26 // us just iterate over points to get the edges 27 var center = getCenter(innerPoints); 28 for (i = 0; i < innerPoints.length; ++i ) { 29 var p = innerPoints[i]; 30 p.angle = Math.atan2(p.x - center.x, p.y - center.y); 31 } 32 innerPoints.sort(function(a,b) { return b.angle - a.angle;}); 33 34 // iterate over all points, get arc between the points 35 // and update the areas 36 var p2 = innerPoints[innerPoints.length - 1]; 37 for (i = 0; i < innerPoints.length; ++i) { 38 var p1 = innerPoints[i]; 39 40 // polygon area updates easily ... 41 polygonArea += (p2.x + p1.x) * (p1.y - p2.y); 42 43 // updating the arc area is a little more involved 44 var midPoint = {x : (p1.x + p2.x) / 2, 45 y : (p1.y + p2.y) / 2}, 46 arc = null; 47 48 for (var j = 0; j < p1.parentIndex.length; ++j) { 49 if (p2.parentIndex.indexOf(p1.parentIndex[j]) > -1) { 50 // figure out the angle halfway between the two points 51 // on the current circle 52 var circle = circles[p1.parentIndex[j]], 53 a1 = Math.atan2(p1.x - circle.x, p1.y - circle.y), 54 a2 = Math.atan2(p2.x - circle.x, p2.y - circle.y); 55 56 var angleDiff = (a2 - a1); 57 if (angleDiff < 0) { 58 angleDiff += 2*Math.PI; 59 } 60 61 // and use that angle to figure out the width of the 62 // arc 63 var a = a2 - angleDiff/2, 64 width = distance(midPoint, { 65 x : circle.x + circle.radius * Math.sin(a), 66 y : circle.y + circle.radius * Math.cos(a) 67 }); 68 69 // clamp the width to the largest is can actually be 70 // (sometimes slightly overflows because of FP errors) 71 if (width > circle.radius * 2) { 72 width = circle.radius * 2; 73 } 74 75 // pick the circle whose arc has the smallest width 76 if ((arc === null) || (arc.width > width)) { 77 arc = { circle : circle, 78 width : width, 79 p1 : p1, 80 p2 : p2}; 81 } 82 } 83 } 84 85 if (arc !== null) { 86 arcs.push(arc); 87 arcArea += circleArea(arc.circle.radius, arc.width); 88 p2 = p1; 89 } 90 } 91 } else { 92 // no intersection points, is either disjoint - or is completely 93 // overlapped. figure out which by examining the smallest circle 94 var smallest = circles[0]; 95 for (i = 1; i < circles.length; ++i) { 96 if (circles[i].radius < smallest.radius) { 97 smallest = circles[i]; 98 } 99 } 100 101 // make sure the smallest circle is completely contained in all 102 // the other circles 103 var disjoint = false;
104 for (i = 0; i < circles.length; ++i) { 105 if (distance(circles[i], smallest) > Math.abs(smallest.radius - circles[i].radius)) { 106 disjoint = true; 107 break; 108 } 109 } 110 111 if (disjoint) { 112 arcArea = polygonArea = 0; 113 114 } else { 115 arcArea = smallest.radius * smallest.radius * Math.PI; 116 arcs.push({circle : smallest, 117 p1: { x: smallest.x, y : smallest.y + smallest.radius}, 118 p2: { x: smallest.x - SMALL, y : smallest.y + smallest.radius}, 119 width : smallest.radius * 2 }); 120 } 121 } 122 123 polygonArea /= 2; 124 if (stats) { 125 stats.area = arcArea + polygonArea; 126 stats.arcArea = arcArea; 127 stats.polygonArea = polygonArea; 128 stats.arcs = arcs; 129 stats.innerPoints = innerPoints; 130 stats.intersectionPoints = intersectionPoints; 131 } 132 133 return arcArea + polygonArea; 134 } 135 136 /** returns whether a point is contained by all of a list of circles */ 137 function containedInCircles(point, circles) { 138 for (var i = 0; i < circles.length; ++i) { 139 if (distance(point, circles[i]) > circles[i].radius + SMALL) { 140 return false; 141 } 142 } 143 return true; 144 } 145 146 /** Gets all intersection points between a bunch of circles */ 147 function getIntersectionPoints(circles) { 148 var ret = []; 149 for (var i = 0; i < circles.length; ++i) { 150 for (var j = i + 1; j < circles.length; ++j) { 151 var intersect = circleCircleIntersection(circles[i], 152 circles[j]); 153 for (var k = 0; k < intersect.length; ++k) { 154 var p = intersect[k]; 155 p.parentIndex = [i,j]; 156 ret.push(p); 157 } 158 } 159 } 160 return ret; 161 } 162 163 /** Circular segment area calculation. See http://mathworld.wolfram.com/CircularSegment.html */ 164 function circleArea(r, width) { 165 return r * r * Math.acos(1 - width/r) - (r - width) * Math.sqrt(width * (2 * r - width)); 166 } 167 168 /** euclidean distance between two points */ 169 function distance(p1, p2) { 170 return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + 171 (p1.y - p2.y) * (p1.y - p2.y)); 172 } 173 174 175 /** Returns the overlap area of two circles of radius r1 and r2 - that 176 have their centers separated by distance d. Simpler faster 177 circle intersection for only two circles */ 178 function circleOverlap(r1, r2, d) { 179 // no overlap 180 if (d >= r1 + r2) { 181 return 0; 182 } 183 184 // completely overlapped 185 if (d <= Math.abs(r1 - r2)) { 186 return Math.PI * Math.min(r1, r2) * Math.min(r1, r2); 187 } 188 189 var w1 = r1 - (d * d - r2 * r2 + r1 * r1) / (2 * d), 190 w2 = r2 - (d * d - r1 * r1 + r2 * r2) / (2 * d); 191 return circleArea(r1, w1) + circleArea(r2, w2); 192 } 193 194 /** Given two circles (containing a x/y/radius attributes), 195 returns the intersecting points if possible. 196 note: doesn't handle cases where there are infinitely many 197 intersection points (circles are equivalent):, or only one intersection point*/ 198 function circleCircleIntersection(p1, p2) { 199 var d = distance(p1, p2), 200 r1 = p1.radius, 201 r2 = p2.radius; 202 203 // if to far away, or self contained - can't be done 204 if ((d >= (r1 + r2)) || (d <= Math.abs(r1 - r2))) { 205 return []; 206 } 207 208 var a = (r1 * r1 - r2 * r2 + d * d) / (2 * d), 209 h = Math.sqrt(r1 * r1 - a * a), 210 x0 = p1.x + a * (p2.x - p1.x) / d, 211 y0 = p1.y + a * (p2.y - p1.y) / d, 212 rx = -(p2.y - p1.y) * (h / d), 213 ry = -(p2.x - p1.x) * (h / d); 214 215 return [{x: x0 + rx, y : y0 - ry }, 216 {x: x0 - rx, y : y0 + ry }]; 217 } 218 219 /** Returns the center of a bunch of points */ 220 function getCenter(points) { 221 var center = {x: 0, y: 0}; 222 for (var i =0; i < points.length; ++i ) { 223 center.x += points[i].x; 224 center.y += points[i].y; 225 } 226 center.x /= points.length; 227 center.y /= points.length; 228 return center; 229 } 230 231 /** finds the zeros of a function, given two starting points (which must 232 * have opposite signs */ 233 function bisect(f, a, b, parameters) { 234 parameters = parameters || {}; 235 var maxIterations = parameters.maxIterations || 100, 236 tolerance = parameters.tolerance || 1e-10, 237 fA = f(a), 238 fB = f(b), 239 delta = b - a; 240 241 if (fA * fB > 0) { 242 throw "Initial bisect points must have opposite signs"; 243 } 244 245 if (fA === 0) return a; 246 if (fB === 0) return b; 247 248 for (var i = 0; i < maxIterations; ++i) { 249 delta /= 2; 250 var mid = a + delta, 251 fMid = f(mid); 252 253 if (fMid * fA >= 0) { 254 a = mid; 255 } 256 257 if ((Math.abs(delta) < tolerance) || (fMid === 0)) { 258 return mid; 259 } 260 } 261 return a + delta; 262 } 263 264 // need some basic operations on vectors, rather than adding a dependency, 265 // just define here 266 function zeros(x) { var r = new Array(x); for (var i = 0; i < x; ++i) { r[i] = 0; } return r; } 267 function zerosM(x,y) { return zeros(x).map(function() { return zeros(y); }); } 268 269 function dot(a, b) { 270 var ret = 0; 271 for (var i = 0; i < a.length; ++i) { 272 ret += a[i] * b[i]; 273 } 274 return ret; 275 } 276 277 function norm2(a) { 278 return Math.sqrt(dot(a, a)); 279 } 280 281 function scale(ret, value, c) { 282 for (var i = 0; i < value.length; ++i) { 283 ret[i] = value[i] * c; 284 } 285 } 286 287 function weightedSum(ret, w1, v1, w2, v2) { 288 for (var j = 0; j < ret.length; ++j) { 289 ret[j] = w1 * v1[j] + w2 * v2[j]; 290 } 291 } 292 293 /** minimizes a function using the downhill simplex method */ 294 function nelderMead(f, x0, parameters) { 295 parameters = parameters || {}; 296 297 var maxIterations = parameters.maxIterations || x0.length * 200, 298 nonZeroDelta = parameters.nonZeroDelta || 1.05, 299 zeroDelta = parameters.zeroDelta || 0.001, 300 minErrorDelta = parameters.minErrorDelta || 1e-6, 301 minTolerance = parameters.minErrorDelta || 1e-5, 302 rho = (parameters.rho !== undefined) ? parameters.rho : 1, 303 chi = (parameters.chi !== undefined) ? parameters.chi : 2, 304 psi = (parameters.psi !== undefined) ? parameters.psi : -0.5, 305 sigma = (parameters.sigma !== undefined) ? parameters.sigma : 0.5, 306 maxDiff; 307 308 // initialize simplex. 309 var N = x0.length, 310 simplex = new Array(N + 1); 311 simplex[0] = x0; 312 simplex[0].fx = f(x0); 313 simplex[0].id = 0; 314 for (var i = 0; i < N; ++i) { 315 var point = x0.slice(); 316 point[i] = point[i] ? point[i] * nonZeroDelta : zeroDelta; 317 simplex[i+1] = point; 318 simplex[i+1].fx = f(point); 319 simplex[i+1].id = i+1; 320 } 321 322 function updateSimplex(value) { 323 for (var i = 0; i < value.length; i++) { 324 simplex[N][i] = value[i]; 325 } 326 simplex[N].fx = value.fx; 327 } 328 329 var sortOrder = function(a, b) { return a.fx - b.fx; }; 330 331 var centroid = x0.slice(), 332 reflected = x0.slice(), 333 contracted = x0.slice(), 334 expanded = x0.slice(); 335 336 for (var iteration = 0; iteration < maxIterations; ++iteration) { 337 simplex.sort(sortOrder); 338 339 if (parameters.history) { 340 // copy the simplex (since later iterations will mutate) and 341 // sort it to have a consistent order between iterations 342 var sortedSimplex = simplex.map(function (x) { 343 var state = x.slice(); 344 state.fx = x.fx; 345 state.id = x.id; 346 return state; 347 }); 348 sortedSimplex.sort(function(a,b) { return a.id - b.id; }); 349 350 parameters.history.push({x: simplex[0].slice(), 351 fx: simplex[0].fx, 352 simplex: sortedSimplex}); 353 } 354 355 maxDiff = 0; 356 for (i = 0; i < N; ++i) { 357 maxDiff = Math.max(maxDiff, Math.abs(simplex[0][i] - simplex[1][i])); 358 } 359 360 if ((Math.abs(simplex[0].fx - simplex[N].fx) < minErrorDelta) && 361 (maxDiff < minTolerance)) { 362 break; 363 } 364 365 // compute the centroid of all but the worst point in the simplex 366 for (i = 0; i < N; ++i) { 367 centroid[i] = 0; 368 for (var j = 0; j < N; ++j) { 369 centroid[i] += simplex[j][i]; 370 } 371 centroid[i] /= N; 372 } 373 374 // reflect the worst point past the centroid and compute loss at reflected 375 // point 376 var worst = simplex[N]; 377 weightedSum(reflected, 1+rho, centroid, -rho, worst); 378 reflected.fx = f(reflected); 379 380 // if the reflected point is the best seen, then possibly expand 381 if (reflected.fx < simplex[0].fx) { 382 weightedSum(expanded, 1+chi, centroid, -chi, worst); 383 expanded.fx = f(expanded); 384 if (expanded.fx < reflected.fx) { 385 updateSimplex(expanded); 386 } else { 387 updateSimplex(reflected); 388 } 389 } 390 391 // if the reflected point is worse than the second worst, we need to 392 // contract 393 else if (reflected.fx >= simplex[N-1].fx) { 394 var shouldReduce = false;
395 396 if (reflected.fx > worst.fx) { 397 // do an inside contraction 398 weightedSum(contracted, 1+psi, centroid, -psi, worst); 399 contracted.fx = f(contracted); 400 if (contracted.fx < worst.fx) { 401 updateSimplex(contracted); 402 } else { 403 shouldReduce = true; 404 } 405 } else { 406 // do an outside contraction 407 weightedSum(contracted, 1-psi * rho, centroid, psi*rho, worst); 408 contracted.fx = f(contracted); 409 if (contracted.fx < reflected.fx) { 410 updateSimplex(contracted); 411 } else { 412 shouldReduce = true; 413 } 414 } 415 416 if (shouldReduce) { 417 // if we don't contract here, we're done 418 if (sigma >= 1) break; 419 420 // do a reduction 421 for (i = 1; i < simplex.length; ++i) { 422 weightedSum(simplex[i], 1 - sigma, simplex[0], sigma, simplex[i]); 423 simplex[i].fx = f(simplex[i]); 424 } 425 } 426 } else { 427 updateSimplex(reflected); 428 } 429 } 430 431 simplex.sort(sortOrder); 432 return {fx : simplex[0].fx, 433 x : simplex[0]}; 434 } 435 436 /// searches along line 'pk' for a point that satifies the wolfe conditions 437 /// See 'Numerical Optimization' by Nocedal and Wright p59-60 438 /// f : objective function 439 /// pk : search direction 440 /// current: object containing current gradient/loss 441 /// next: output: contains next gradient/loss 442 /// returns a: step size taken 443 function wolfeLineSearch(f, pk, current, next, a, c1, c2) { 444 var phi0 = current.fx, phiPrime0 = dot(current.fxprime, pk), 445 phi = phi0, phi_old = phi0, 446 phiPrime = phiPrime0, 447 a0 = 0; 448 449 a = a || 1; 450 c1 = c1 || 1e-6; 451 c2 = c2 || 0.1; 452 453 function zoom(a_lo, a_high, phi_lo) { 454 for (var iteration = 0; iteration < 16; ++iteration) { 455 a = (a_lo + a_high)/2; 456 weightedSum(next.x, 1.0, current.x, a, pk); 457 phi = next.fx = f(next.x, next.fxprime); 458 phiPrime = dot(next.fxprime, pk); 459 460 if ((phi > (phi0 + c1 * a * phiPrime0)) || 461 (phi >= phi_lo)) { 462 a_high = a; 463 464 } else { 465 if (Math.abs(phiPrime) <= -c2 * phiPrime0) { 466 return a; 467 } 468 469 if (phiPrime * (a_high - a_lo) >=0) { 470 a_high = a_lo; 471 } 472 473 a_lo = a; 474 phi_lo = phi; 475 } 476 } 477 478 return 0; 479 } 480 481 for (var iteration = 0; iteration < 10; ++iteration) { 482 weightedSum(next.x, 1.0, current.x, a, pk); 483 phi = next.fx = f(next.x, next.fxprime); 484 phiPrime = dot(next.fxprime, pk); 485 if ((phi > (phi0 + c1 * a * phiPrime0)) || 486 (iteration && (phi >= phi_old))) { 487 return zoom(a0, a, phi_old); 488 } 489 490 if (Math.abs(phiPrime) <= -c2 * phiPrime0) { 491 return a; 492 } 493 494 if (phiPrime >= 0 ) { 495 return zoom(a, a0, phi); 496 } 497 498 phi_old = phi; 499 a0 = a; 500 a *= 2; 501 } 502 503 return a; 504 } 505 506 function conjugateGradient(f, initial, params) { 507 // allocate all memory up front here, keep out of the loop for perfomance 508 // reasons 509 var current = {x: initial.slice(), fx: 0, fxprime: initial.slice()}, 510 next = {x: initial.slice(), fx: 0, fxprime: initial.slice()}, 511 yk = initial.slice(), 512 pk, temp, 513 a = 1, 514 maxIterations; 515 516 params = params || {}; 517 maxIterations = params.maxIterations || initial.length * 20; 518 519 current.fx = f(current.x, current.fxprime); 520 pk = current.fxprime.slice(); 521 scale(pk, current.fxprime,-1); 522 523 for (var i = 0; i < maxIterations; ++i) { 524 a = wolfeLineSearch(f, pk, current, next, a); 525 526 // todo: history in wrong spot? 527 if (params.history) { 528 params.history.push({x: current.x.slice(), 529 fx: current.fx, 530 fxprime: current.fxprime.slice(), 531 alpha: a}); 532 } 533 534 if (!a) {
535 // faiiled to find point that satifies wolfe conditions. 536 // reset direction for next iteration 537 scale(pk, current.fxprime, -1); 538 539 } else { 540 // update direction using Polak–Ribiere CG method 541 weightedSum(yk, 1, next.fxprime, -1, current.fxprime); 542 543 var delta_k = dot(current.fxprime, current.fxprime), 544 beta_k = Math.max(0, dot(yk, next.fxprime) / delta_k); 545 546 weightedSum(pk, beta_k, pk, -1, next.fxprime); 547 548 temp = current; 549 current = next; 550 next = temp; 551 } 552 553 if (norm2(current.fxprime) <= 1e-5) { 554 break; 555 } 556 } 557 558 if (params.history) { 559 params.history.push({x: current.x.slice(), 560 fx: current.fx, 561 fxprime: current.fxprime.slice(), 562 alpha: a}); 563 } 564 565 return current; 566 } 567 568 /** given a list of set objects, and their corresponding overlaps. 569 updates the (x, y, radius) attribute on each set such that their positions 570 roughly correspond to the desired overlaps */ 571 function venn(areas, parameters) { 572 parameters = parameters || {}; 573 parameters.maxIterations = parameters.maxIterations || 500; 574 var initialLayout = parameters.initialLayout || bestInitialLayout; 575 var loss = parameters.lossFunction || lossFunction; 576 577 // add in missing pairwise areas as having 0 size 578 areas = addMissingAreas(areas); 579 580 // initial layout is done greedily 581 var circles = initialLayout(areas, parameters); 582 583 // transform x/y coordinates to a vector to optimize 584 var initial = [], setids = [], setid; 585 for (setid in circles) { 586 if (circles.hasOwnProperty(setid)) { 587 initial.push(circles[setid].x); 588 initial.push(circles[setid].y); 589 setids.push(setid); 590 } 591 } 592 var solution = nelderMead( 593 function(values) { 594 var current = {}; 595 for (var i = 0; i < setids.length; ++i) { 596 var setid = setids[i]; 597 current[setid] = {x: values[2 * i], 598 y: values[2 * i + 1], 599 radius : circles[setid].radius, 600 // size : circles[setid].size 601 }; 602 } 603 return loss(current, areas); 604 }, 605 initial, 606 parameters); 607 608 // transform solution vector back to x/y points 609 var positions = solution.x; 610 for (var i = 0; i < setids.length; ++i) { 611 setid = setids[i]; 612 circles[setid].x = positions[2 * i]; 613 circles[setid].y = positions[2 * i + 1]; 614 } 615 616 return circles; 617 } 618 619 var SMALL$1 = 1e-10; 620 621 /** Returns the distance necessary for two circles of radius r1 + r2 to 622 have the overlap area 'overlap' */ 623 function distanceFromIntersectArea(r1, r2, overlap) { 624 // handle complete overlapped circles 625 if (Math.min(r1, r2) * Math.min(r1,r2) * Math.PI <= overlap + SMALL$1) { 626 return Math.abs(r1 - r2); 627 } 628 629 return bisect(function(distance$$1) { 630 return circleOverlap(r1, r2, distance$$1) - overlap; 631 }, 0, r1 + r2); 632 } 633 634 /** Missing pair-wise intersection area data can cause problems: 635 treating as an unknown means that sets will be laid out overlapping, 636 which isn't what people expect. To reflect that we want disjoint sets 637 here, set the overlap to 0 for all missing pairwise set intersections */ 638 function addMissingAreas(areas) { 639 areas = areas.slice(); 640 641 // two circle intersections that aren't defined 642 var ids = [], pairs = {}, i, j, a, b; 643 for (i = 0; i < areas.length; ++i) { 644 var area = areas[i]; 645 if (area.sets.length == 1) { 646 ids.push(area.sets[0]); 647 } else if (area.sets.length == 2) { 648 a = area.sets[0]; 649 b = area.sets[1]; 650 pairs[[a, b]] = true; 651 pairs[[b, a]] = true; 652 } 653 } 654 ids.sort(function(a, b) { return a > b; }); 655 656 for (i = 0; i < ids.length; ++i) { 657 a = ids[i]; 658 for (j = i + 1; j < ids.length; ++j) { 659 b = ids[j]; 660 if (!([a, b] in pairs)) { 661 areas.push({'sets': [a, b], 662 'size': 0}); 663 } 664 } 665 } 666 return areas; 667 } 668 669 /// Returns two matrices, one of the euclidean distances between the sets 670 /// and the other indicating if there are subset or disjoint set relationships 671 function getDistanceMatrices(areas, sets, setids) { 672 // initialize an empty distance matrix between all the points 673 var distances = zerosM(sets.length, sets.length), 674 constraints = zerosM(sets.length, sets.length); 675 676 // compute required distances between all the sets such that 677 // the areas match 678 areas.filter(function(x) { return x.sets.length == 2; }) 679 .map(function(current) { 680 var left = setids[current.sets[0]], 681 right = setids[current.sets[1]], 682 r1 = Math.sqrt(sets[left].size / Math.PI), 683 r2 = Math.sqrt(sets[right].size / Math.PI), 684 distance$$1 = distanceFromIntersectArea(r1, r2, current.size); 685 686 distances[left][right] = distances[right][left] = distance$$1; 687 688 // also update constraints to indicate if its a subset or disjoint 689 // relationship 690 var c = 0; 691 if (current.size + 1e-10 >= Math.min(sets[left].size, 692 sets[right].size)) { 693 c = 1; 694 } else if (current.size <= 1e-10) { 695 c = -1; 696 } 697 constraints[left][right] = constraints[right][left] = c; 698 }); 699 700 return {distances: distances, constraints: constraints}; 701 } 702 703 /// computes the gradient and loss simulatenously for our constrained MDS optimizer 704 function constrainedMDSGradient(x, fxprime, distances, constraints) { 705 var loss = 0, i; 706 for (i = 0; i < fxprime.length; ++i) { 707 fxprime[i] = 0; 708 } 709 710 for (i = 0; i < distances.length; ++i) { 711 var xi = x[2 * i], yi = x[2 * i + 1]; 712 for (var j = i + 1; j < distances.length; ++j) { 713 var xj = x[2 * j], yj = x[2 * j + 1], 714 dij = distances[i][j], 715 constraint = constraints[i][j]; 716 717 var squaredDistance = (xj - xi) * (xj - xi) + (yj - yi) * (yj - yi), 718 distance$$1 = Math.sqrt(squaredDistance), 719 delta = squaredDistance - dij * dij; 720 721 if (((constraint > 0) && (distance$$1 <= dij)) || 722 ((constraint < 0) && (distance$$1 >= dij))) { 723 continue; 724 } 725 726 loss += 2 * delta * delta; 727 728 fxprime[2*i] += 4 * delta * (xi - xj); 729 fxprime[2*i + 1] += 4 * delta * (yi - yj); 730 731 fxprime[2*j] += 4 * delta * (xj - xi); 732 fxprime[2*j + 1] += 4 * delta * (yj - yi); 733 } 734 } 735 return loss; 736 } 737 738 /// takes the best working variant of either constrained MDS or greedy 739 function bestInitialLayout(areas, params) { 740 var initial = greedyLayout(areas, params); 741 var loss = params.lossFunction || lossFunction; 742 743 // greedylayout is sufficient for all 2/3 circle cases. tr
743y out 744 // constrained MDS for higher order problems, take its output 745 // if it outperforms. (greedy is aesthetically better on 2/3 circles 746 // since it axis aligns) 747 if (areas.length >= 8) { 748 var constrained = constrainedMDSLayout(areas, params), 749 constrainedLoss = loss(constrained, areas), 750 greedyLoss = loss(initial, areas); 751 752 if (constrainedLoss + 1e-8 < greedyLoss) { 753 initial = constrained; 754 } 755 } 756 return initial; 757 } 758 759 /// use the constrained MDS variant to generate an initial layout 760 function constrainedMDSLayout(areas, params) { 761 params = params || {}; 762 var restarts = params.restarts || 10; 763 764 // bidirectionally map sets to a rowid (so we can create a matrix) 765 var sets = [], setids = {}, i; 766 for (i = 0; i < areas.length; ++i ) { 767 var area = areas[i]; 768 if (area.sets.length == 1) { 769 setids[area.sets[0]] = sets.length; 770 sets.push(area); 771 } 772 } 773 774 var matrices = getDistanceMatrices(areas, sets, setids), 775 distances = matrices.distances, 776 constraints = matrices.constraints; 777 778 // keep distances bounded, things get messed up otherwise. 779 // TODO: proper preconditioner? 780 var norm = norm2(distances.map(norm2))/(distances.length); 781 distances = distances.map(function (row) { 782 return row.map(function (value) { return value / norm; });}); 783 784 var obj = function(x, fxprime) { 785 return constrainedMDSGradient(x, fxprime, distances, constraints); 786 }; 787 788 var best, current; 789 for (i = 0; i < restarts; ++i) { 790 var initial = zeros(distances.length*2).map(Math.random); 791 792 current = conjugateGradient(obj, initial, params); 793 if (!best || (current.fx < best.fx)) { 794 best = current; 795 } 796 } 797 var positions = best.x; 798 799 // translate rows back to (x,y,radius) coordinates 800 var circles = {}; 801 for (i = 0; i < sets.length; ++i) { 802 var set = sets[i]; 803 circles[set.sets[0]] = { 804 x: positions[2*i] * norm, 805 y: positions[2*i + 1] * norm, 806 radius: Math.sqrt(set.size / Math.PI) 807 }; 808 } 809 810 if (params.history) { 811 for (i = 0; i < params.history.length; ++i) { 812 scale(params.history[i].x, norm); 813 } 814 } 815 return circles; 816 } 817 818 /** Lays out a Venn diagram greedily, going from most overlapped sets to 819 least overlapped, attempting to position each new set such that the 820 overlapping areas to already positioned sets are basically right */ 821 function greedyLayout(areas, params) { 822 var loss = params && params.lossFunction ? params.lossFunction : lossFunction; 823 // define a circle for each set 824 var circles = {}, setOverlaps = {}, set; 825 for (var i = 0; i < areas.length; ++i) { 826 var area = areas[i]; 827 if (area.sets.length == 1) { 828 set = area.sets[0]; 829 circles[set] = {x: 1e10, y: 1e10, 830 rowid: circles.length, 831 size: area.size, 832 radius: Math.sqrt(area.size / Math.PI)}; 833 setOverlaps[set] = []; 834 } 835 } 836 areas = areas.filter(function(a) { return a.sets.length == 2; }); 837 838 // map each set to a list of all the other sets that overlap it 839 for (i = 0; i < areas.length; ++i) { 840 var current = areas[i]; 841 var weight = current.hasOwnProperty('weight') ? current.weight : 1.0; 842 var left = current.sets[0], right = current.sets[1]; 843 844 // completely overlapped circles shouldn't be positioned early here 845 if (current.size + SMALL$1 >= Math.min(circles[left].size, 846 circles[right].size)) { 847 weight = 0; 848 } 849 850 setOverlaps[left].push ({set:right, size:current.size, weight:weight}); 851 setOverlaps[right].push({set:left, size:current.size, weight:weight}); 852 } 853 854 // get list of most overlapped sets 855 var mostOverlapped = []; 856 for (set in setOverlaps) { 857 if (setOverlaps.hasOwnProperty(set)) { 858 var size = 0; 859 for (i = 0; i < setOverlaps[set].length; ++i) { 860 size += setOverlaps[set][i].size * setOverlaps[set][i].weight; 861 } 862 863 mostOverlapped.push({set: set, size:size}); 864 } 865 } 866 867 // sort by size desc 868 function sortOrder(a,b) { 869 return b.size - a.size; 870 } 871 mostOverlapped.sort(sortOrder); 872 873 // keep track of what sets have been laid out 874 var positioned = {}; 875 function isPositioned(element) { 876 return element.set in positioned; 877 } 878 879 // adds a point to the output 880 function positionSet(point, index) { 881 circles[index].x = point.x; 882 circles[index].y = point.y; 883 positioned[index] = true; 884 } 885 886 // add most overlapped set at (0,0) 887 positionSet({x: 0, y: 0}, mostOverlapped[0].set); 888 889 // get distances between all points. TODO, necessary? 890 // answer: probably not 891 // var distances = venn.getDistanceMatrices(circles, areas).distances; 892 for (i = 1; i < mostOverlapped.length; ++i) { 893 var setIndex = mostOverlapped[i].set, 894 overlap = setOverlaps[setIndex].filter(isPositioned); 895 set = circles[setIndex]; 896 overlap.sort(sortOrder); 897 898 if (overlap.length === 0) { 899 // this shouldn't happen anymore with addMissingAreas 900 throw "ERROR: missing pairwise overlap information"; 901 } 902 903 var points = []; 904 for (var j = 0; j < overlap.length; ++j) { 905 // get appropriate distance from most overlapped already added set
906 var p1 = circles[overlap[j].set], 907 d1 = distanceFromIntersectArea(set.radius, p1.radius, 908 overlap[j].size); 909 910 // sample positions at 90 degrees for maximum aesthetics 911 points.push({x : p1.x + d1, y : p1.y}); 912 points.push({x : p1.x - d1, y : p1.y}); 913 points.push({y : p1.y + d1, x : p1.x}); 914 points.push({y : p1.y - d1, x : p1.x}); 915 916 // if we have at least 2 overlaps, then figure out where the 917 // set should be positioned analytically and try those too 918 for (var k = j + 1; k < overlap.length; ++k) { 919 var p2 = circles[overlap[k].set], 920 d2 = distanceFromIntersectArea(set.radius, p2.radius, 921 overlap[k].size); 922 923 var extraPoints = circleCircleIntersection( 924 { x: p1.x, y: p1.y, radius: d1}, 925 { x: p2.x, y: p2.y, radius: d2}); 926 927 for (var l = 0; l < extraPoints.length; ++l) { 928 points.push(extraPoints[l]); 929 } 930 } 931 } 932 933 // we have some candidate positions for the set, examine loss 934 // at each position to figure out where to put it at 935 var bestLoss = 1e50, bestPoint = points[0]; 936 for (j = 0; j < points.length; ++j) { 937 circles[setIndex].x = points[j].x; 938 circles[setIndex].y = points[j].y; 939 var localLoss = loss(circles, areas); 940 if (localLoss < bestLoss) { 941 bestLoss = localLoss; 942 bestPoint = points[j]; 943 } 944 } 945 946 positionSet(bestPoint, setIndex); 947 } 948 949 return circles; 950 } 951 952 /** Given a bunch of sets, and the desired overlaps between these sets - computes 953 the distance from the actual overlaps to the desired overlaps. Note that 954 this method ignores overlaps of more than 2 circles */ 955 function lossFunction(sets, overlaps) { 956 var output = 0; 957 958 function getCircles(indices) { 959 return indices.map(function(i) { return sets[i]; }); 960 } 961 962 for (var i = 0; i < overlaps.length; ++i) { 963 var area = overlaps[i], overlap; 964 if (area.sets.length == 1) { 965 continue; 966 } else if (area.sets.length == 2) { 967 var left = sets[area.sets[0]], 968 right = sets[area.sets[1]]; 969 overlap = circleOverlap(left.radius, right.radius, 970 distance(left, right)); 971 } else { 972 overlap = intersectionArea(getCircles(area.sets)); 973 } 974 975 var weight = area.hasOwnProperty('weight') ? area.weight : 1.0; 976 output += weight * (overlap - area.size) * (overlap - area.size); 977 } 978 979 return output; 980 } 981 982 // orientates a bunch of circles to point in orientation 983 function orientateCircles(circles, orientation, orientationOrder) { 984 if (orientationOrder === null) { 985 circles.sort(function (a, b) { return b.radius - a.radius; }); 986 } else { 987 circles.sort(orientationOrder); 988 } 989 990 var i; 991 // shift circles so largest circle is at (0, 0) 992 if (circles.length > 0) { 993 var largestX = circles[0].x, 994 largestY = circles[0].y; 995 996 for (i = 0; i < circles.length; ++i) { 997 circles[i].x -= largestX; 998 circles[i].y -= largestY; 999 } 1000 } 1001 1002 if (circles.length == 2) { 1003 // if the second circle is a subset of the first, arrange so that 1004 // it is off to one side. hack for https://github.com/benfred/venn.js/issues/120 1005 var dist = distance(circles[0], circles[1]); 1006 if (dist < Math.abs(circles[1].radius - circles[0].radius)) {
1007 circles[1].x = circles[0].x + circles[0].radius - circles[1].radius - 1e-10; 1008 circles[1].y = circles[0].y; 1009 } 1010 } 1011 1012 // rotate circles so that second largest is at an angle of 'orientation' 1013 // from largest 1014 if (circles.length > 1) { 1015 var rotation = Math.atan2(circles[1].x, circles[1].y) - orientation, 1016 c = Math.cos(rotation), 1017 s = Math.sin(rotation), x, y; 1018 1019 for (i = 0; i < circles.length; ++i) { 1020 x = circles[i].x; 1021 y = circles[i].y; 1022 circles[i].x = c * x - s * y; 1023 circles[i].y = s * x + c * y; 1024 } 1025 } 1026 1027 // mirror solution if third solution is above plane specified by 1028 // first two circles 1029 if (circles.length > 2) { 1030 var angle = Math.atan2(circles[2].x, circles[2].y) - orientation; 1031 while (angle < 0) { angle += 2* Math.PI; } 1032 while (angle > 2*Math.PI) { angle -= 2* Math.PI; } 1033 if (angle > Math.PI) { 1034 var slope = circles[1].y / (1e-10 + circles[1].x); 1035 for (i = 0; i < circles.length; ++i) { 1036 var d = (circles[i].x + slope * circles[i].y) / (1 + slope*slope); 1037 circles[i].x = 2 * d - circles[i].x; 1038 circles[i].y = 2 * d * slope - circles[i].y; 1039 } 1040 } 1041 } 1042 } 1043 1044 function disjointCluster(circles) { 1045 // union-find clustering to get disjoint sets 1046 circles.map(function(circle) { circle.parent = circle; }); 1047 1048 // path compression step in union find 1049 function find(circle) { 1050 if (circle.parent !== circle) { 1051 circle.parent = find(circle.parent); 1052 } 1053 return circle.parent; 1054 } 1055 1056 function union(x, y) { 1057 var xRoot = find(x), yRoot = find(y); 1058 xRoot.parent = yRoot; 1059 } 1060 1061 // get the union of all overlapping sets 1062 for (var i = 0; i < circles.length; ++i) { 1063 for (var j = i + 1; j < circles.length; ++j) { 1064 var maxDistance = circles[i].radius + circles[j].radius; 1065 if (distance(circles[i], circles[j]) + 1e-10 < maxDistance) { 1066 union(circles[j], circles[i]); 1067 } 1068 } 1069 } 1070 1071 // find all the disjoint clusters and group them together 1072 var disjointClusters = {}, setid; 1073 for (i = 0; i < circles.length; ++i) { 1074 setid = find(circles[i]).parent.setid; 1075 if (!(setid in disjointClusters)) { 1076 disjointClusters[setid] = []; 1077 } 1078 disjointClusters[setid].push(circles[i]); 1079 } 1080 1081 // cleanup bookkeeping 1082 circles.map(function(circle) { delete circle.parent; }); 1083 1084 // return in more usable form 1085 var ret = []; 1086 for (setid in disjointClusters) { 1087 if (disjointClusters.hasOwnProperty(setid)) { 1088 ret.push(disjointClusters[setid]); 1089 } 1090 } 1091 return ret; 1092 } 1093 1094 function getBoundingBox(circles) { 1095 var minMax = function(d) { 1096 var hi = Math.max.apply(null, circles.map( 1097 function(c) { return c[d] + c.radius; } )), 1098 lo = Math.min.apply(null, circles.map( 1099 function(c) { return c[d] - c.radius;} )); 1100 return {max:hi, min:lo}; 1101 }; 1102 1103 return {xRange: minMax('x'), yRange: minMax('y')}; 1104 } 1105 1106 function normalizeSolution(solution, orientation, orientationOrder) { 1107 if (orientation === null){ 1108 orientation = Math.PI/2; 1109 } 1110 1111 // work with a list instead of a dictionary, and take a copy so we 1112 // don't mutate input 1113 var circles = [], i, setid; 1114 for (setid in solution) { 1115 if (solution.hasOwnProperty(setid)) { 1116 var previous = solution[setid]; 1117 circles.push({x: previous.x, 1118 y: previous.y, 1119 radius: previous.radius, 1120 setid: setid}); 1121 } 1122 } 1123
1124 // get all the disjoint clusters 1125 var clusters = disjointCluster(circles); 1126 1127 // orientate all disjoint sets, get sizes 1128 for (i = 0; i < clusters.length; ++i) { 1129 orientateCircles(clusters[i], orientation, orientationOrder); 1130 var bounds = getBoundingBox(clusters[i]); 1131 clusters[i].size = (bounds.xRange.max - bounds.xRange.min) * (bounds.yRange.max - bounds.yRange.min); 1132 clusters[i].bounds = bounds; 1133 } 1134 clusters.sort(function(a, b) { return b.size - a.size; }); 1135 1136 // orientate the largest at 0,0, and get the bounds 1137 circles = clusters[0]; 1138 var returnBounds = circles.bounds; 1139 1140 var spacing = (returnBounds.xRange.max - returnBounds.xRange.min)/50; 1141 1142 function addCluster(cluster, right, bottom) { 1143 if (!cluster) return; 1144 1145 var bounds = cluster.bounds, xOffset, yOffset, centreing; 1146 1147 if (right) { 1148 xOffset = returnBounds.xRange.max - bounds.xRange.min + spacing; 1149 } else { 1150 xOffset = returnBounds.xRange.max - bounds.xRange.max; 1151 centreing = (bounds.xRange.max - bounds.xRange.min) / 2 - 1152 (returnBounds.xRange.max - returnBounds.xRange.min) / 2; 1153 if (centreing < 0) xOffset += centreing; 1154 } 1155 1156 if (bottom) { 1157 yOffset = returnBounds.yRange.max - bounds.yRange.min + spacing; 1158 } else { 1159 yOffset = returnBounds.yRange.max - bounds.yRange.max; 1160 centreing = (bounds.yRange.max - bounds.yRange.min) / 2 - 1161 (returnBounds.yRange.max - returnBounds.yRange.min) / 2; 1162 if (centreing < 0) yOffset += centreing; 1163 } 1164 1165 for (var j = 0; j < cluster.length; ++j) { 1166 cluster[j].x += xOffset; 1167 cluster[j].y += yOffset; 1168 circles.push(cluster[j]); 1169 } 1170 } 1171 1172 var index = 1; 1173 while (index < clusters.length) { 1174 addCluster(clusters[index], true, false); 1175 addCluster(clusters[index+1], false, true); 1176 addCluster(clusters[index+2], true, true); 1177 index += 3; 1178 1179 // have one cluster (in top left). lay out next three relative 1180 // to it in a grid 1181 returnBounds = getBoundingBox(circles); 1182 } 1183 1184 // convert back to solution form 1185 var ret = {}; 1186 for (i = 0; i < circles.length; ++i) { 1187 ret[circles[i].setid] = circles[i]; 1188 } 1189 return ret; 1190 } 1191 1192 /** Scales a solution from venn.venn or venn.greedyLayout such that it fits in 1193 a rectangle of width/height - with padding around the borders. also 1194 centers the diagram in the available space at the same time */ 1195 function scaleSolution(solution, width, height, padding) { 1196 var circles = [], setids = []; 1197 for (var setid in solution) { 1198 if (solution.hasOwnProperty(setid)) { 1199 setids.push(setid); 1200 circles.push(solution[setid]); 1201 } 1202 } 1203 1204 width -= 2*padding; 1205 height -= 2*padding; 1206 1207 var bounds = getBoundingBox(circles), 1208 xRange = bounds.xRange, 1209 yRange = bounds.yRange; 1210 1211 if ((xRange.max == xRange.min) || 1212 (yRange.max == yRange.min)) { 1213 console.log("not scaling solution: zero size detected"); 1214 return solution; 1215 } 1216 1217 var xScaling = width / (xRange.max - xRange.min), 1218 yScaling = height / (yRange.max - yRange.min), 1219 scaling = Math.min(yScaling, xScaling), 1220 1221 // while we're at it, center the diagram too 1222 xOffset = (width - (xRange.max - xRange.min) * scaling) / 2, 1223 yOffset = (height - (yRange.max - yRange.min) * scaling) / 2; 1224 1225 var scaled = {}; 1226 for (var i = 0; i < circles.length; ++i) { 1227 var circle = circles[i]; 1228 scaled[setids[i]] = { 1229 radius: scaling * circle.radius, 1230 x: padding + xOffset + (circle.x - xRange.min) * scaling, 1231 y: padding + yOffset + (circle.y - yRange.min) * scaling, 1232 }; 1233 } 1234 1235 return scaled; 1236 } 1237 1238 /*global console:true*/ 1239 1240 function VennDiagram() { 1241 var width = 600, 1242 height = 350, 1243 padding = 15, 1244 duration = 1000, 1245 orientation = Math.PI / 2, 1246 normalize = true, 1247 wrap = true, 1248 styled = true, 1249 fontSize = null, 1250 orientationOrder = null, 1251 1252 // mimic the behaviour of d3.scale.category10 from the previous 1253 // version of d3 1254 // colourMap = {}, 1255 1256 // so this is the same as d3.schemeCategory10, which is only defined in d3 4.0 1257 // since we can support older versions of d3 as long as we don't force this, 1258 // I'm hackily redefining below. TODO: remove this and change to d3.schemeCategory10 1259 // colourScheme = ["#1f77b4", "#ff7f0e", "#2ca02c", "#d62728", "#9467bd", "#8c564b", "#e377c2", "#7f7f7f", "#bcbd22", "#17becf"],
1260 colourScheme = ["#62d8fd", "#3680da"], 1261 colourIndex = 0, 1262 colours = function(key) { 1263 1264 if (key in colourMap) { 1265 return colourMap[key]; 1266 } 1267 var ret = colourMap[key] = colourScheme[colourIndex]; 1268 colourIndex += 1; 1269 if (colourIndex >= colourScheme.length) { 1270 colourIndex = 0; 1271 } 1272 1273 return ret; 1274 }, 1275 layoutFunction = venn, 1276 loss = lossFunction; 1277 1278 1279 function chart(selection) { 1280 var data = selection.datum(); 1281 1282 // handle 0-sized sets by removing from input 1283 var toremove = {}; 1284 data.forEach(function(datum) { 1285 if ((datum.size == 0) && datum.sets.length == 1) { 1286 toremove[datum.sets[0]] = 1; 1287 } 1288 }); 1289 data = data.filter(function(datum) { 1290 return !datum.sets.some(function(set) { return set in toremove; }); 1291 }); 1292 1293 var circles = {}; 1294 var textCentres = {}; 1295 1296 if (data.length > 0) { 1297 var solution = layoutFunction(data, {lossFunction: loss}); 1298 1299 if (normalize) { 1300 solution = normalizeSolution(solution, 1301 orientation, 1302 orientationOrder); 1303 } 1304 1305 circles = scaleSolution(solution, width, height, padding); 1306 textCentres = computeTextCentres(circles, data); 1307 } 1308 1309 // Figure out the current label for each set. These can change 1310 // and D3 won't necessarily update (fixes https://github.com/benfred/venn.js/issues/103) 1311 var labels = {}; 1312 data.forEach(function(datum) { 1313 if (datum.label) { 1314 labels[datum.sets] = datum.label; 1315 } 1316 }); 1317 1318 function label(d) {
1319 if (d.sets in labels) { 1320 return labels[d.sets]; 1321 } 1322 if (d.sets.length == 1) { 1323 return '' + d.sets[0]; 1324 } 1325 } 1326 1327 // create svg if not already existing 1328 selection.selectAll("svg").data([circles]).enter().append("svg"); 1329 1330 var svg = selection.select("svg") 1331 .attr("width", width) 1332 .attr("height", height); 1333 1334 // to properly transition intersection areas, we need the 1335 // previous circles locations. load from elements 1336 var previous = {}, hasPrevious = false; 1337 svg.selectAll(".venn-area path").each(function (d) { 1338 var path = d3Selection.select(this).attr("d"); 1339 if ((d.sets.length == 1) && path) { 1340 hasPrevious = true; 1341 previous[d.sets[0]] = circleFromPath(path); 1342 } 1343 }); 1344 1345 // interpolate intersection area paths between previous and 1346 // current paths 1347 var pathTween = function(d) { 1348 return function(t) { 1349 var c = d.sets.map(function(set) { 1350 var start = previous[set], end = circles[set]; 1351 if (!start) { 1352 start = {x : width/2, y : height/2, radius : 1}; 1353 } 1354 if (!end) { 1355 end = {x : width/2, y : height/2, radius : 1}; 1356 } 1357 return {'x' : start.x * (1 - t) + end.x * t, 1358 'y' : start.y * (1 - t) + end.y * t, 1359 'radius' : start.radius * (1 - t) + end.radius * t}; 1360 }); 1361 return intersectionAreaPath(c); 1362 }; 1363 }; 1364 1365 // update data, joining on the set ids 1366 var nodes = svg.selectAll(".venn-area") 1367 .data(data, function(d) { return d.sets; }); 1368 1369 // create new nodes 1370 var enter = nodes.enter() 1371 .append('g') 1372 .attr("class", function(d) { 1373 return "venn-area venn-" + 1374 (d.sets.length == 1 ? "circle" : "intersection"); 1375 }) 1376 .attr("data-venn-sets", function(d) { 1377 return d.sets.join("_"); 1378 }); 1379 1380 var enterPath = enter.append("path"), 1381 enterText = enter.append("text") 1382 .attr("class", "label") 1383 .text(function (d) { return label(d); } ) 1384 .attr("text-anchor", "middle") 1385 .attr("dy", ".35em") 1386 .attr("x", width/2) 1387 .attr("y", height/2); 1388 1389 1390 // apply minimal style if wanted 1391 if (styled) { 1392 enterPath.style("fill-opacity", "0") 1393 .filter(function (d) { return d.sets.length == 1; } ) 1394 .style("fill", function(d) { return colours(d.sets); }) 1395 .style("fill-opacity", ".25"); 1396 1397 enterText 1398 .style("fill", function(d) { return d.sets.length == 1 ? colours(d.sets) : "#444"; }); 1399 } 1400 1401 // update existing, using pathTween if necessary 1402 var update = selection; 1403 if (hasPrevious) { 1404 update = selection.transition("venn").duration(duration); 1405 update.selectAll("path") 1406 .attrTween("d", pathTween); 1407 } else { 1408 update.selectAll("path") 1409 .attr("d", function(d) { 1410 return intersectionAreaPath(d.sets.map(function (set) { return circles[set]; })); 1411 }); 1412 } 1413 1414 var updateText = update.selectAll("text") 1415 .filter(function (d) { return d.sets in textCentres; }) 1416 .text(function (d) { return label(d); } ) 1417 .attr("x", function(d) { return Math.floor(textCentres[d.sets].x);}) 1418 .attr("y", function(d) { return Math.floor(textCentres[d.sets].y);}); 1419 1420 if (wrap) { 1421 if (hasPrevious) { 1422 // d3 4.0 uses 'on' for events on transitions, 1423 // but d3 3.0 used 'each' instead. switch appropiately 1424 if ('on' in updateText) { 1425 updateText.on("end", wrapText(circles, label)); 1426 } else { 1427 updateText.each("end", wrapText(circles, label)); 1428 } 1429 } else { 1430 updateText.each(wrapText(circles, label)); 1431 } 1432 } 1433 1434 // remove old
1435 var exit = nodes.exit().transition('venn').duration(duration).remove(); 1436 exit.selectAll("path") 1437 .attrTween("d", pathTween); 1438 1439 var exitText = exit.selectAll("text") 1440 .attr("x", width/2) 1441 .attr("y", height/2); 1442 1443 // if we've been passed a fontSize explicitly, use it to 1444 // transition 1445 if (fontSize !== null) { 1446 enterText.style("font-size", "0px"); 1447 updateText.style("font-size", fontSize); 1448 exitText.style("font-size", "0px"); 1449 } 1450 1451 1452 return {'circles': circles, 1453 'textCentres': textCentres, 1454 'nodes': nodes, 1455 'enter': enter, 1456 'update': update, 1457 'exit': exit}; 1458 } 1459 1460 chart.wrap = function(_) { 1461 if (!arguments.length) return wrap; 1462 wrap = _; 1463 return chart; 1464 }; 1465 1466 chart.width = function(_) { 1467 if (!arguments.length) return width; 1468 width = _; 1469 return chart; 1470 }; 1471 1472 chart.height = function(_) { 1473 if (!arguments.length) return height; 1474 height = _; 1475 return chart; 1476 }; 1477 1478 chart.padding = function(_) { 1479 if (!arguments.length) return padding; 1480 padding = _; 1481 return chart; 1482 }; 1483 1484 chart.colours = function(_) { 1485 if (!arguments.length) return colours; 1486 colours = _; 1487 return chart; 1488 }; 1489 1490 chart.fontSize = function(_) { 1491 if (!arguments.length) return fontSize; 1492 fontSize = _; 1493 return chart; 1494 }; 1495 1496 chart.duration = function(_) { 1497 if (!arguments.length) return duration; 1498 duration = _; 1499 return chart; 1500 }; 1501 1502 chart.layoutFunction = function(_) { 1503 if (!arguments.length) return layoutFunction; 1504 layoutFunction = _; 1505 return chart; 1506 }; 1507 1508 chart.normalize = function(_) { 1509 if (!arguments.length) return normalize; 1510 normalize = _; 1511 return chart; 1512 }; 1513 1514 chart.styled = function(_) { 1515 if (!arguments.length) return styled; 1516 styled = _; 1517 return chart; 1518 }; 1519 1520 chart.orientation = function(_) { 1521 if (!arguments.length) return orientation; 1522 orientation = _; 1523 return chart; 1524 }; 1525 1526 chart.orientationOrder = function(_) { 1527 if (!arguments.length) return orientationOrder; 1528 orientationOrder = _; 1529 return chart; 1530 }; 1531 1532 chart.lossFunction = function(_) { 1533 if (!arguments.length) return loss;
1534 loss = _; 1535 return chart; 1536 }; 1537 1538 return chart; 1539 } 1540 // sometimes text doesn't fit inside the circle, if thats the case lets wrap 1541 // the text here such that it fits 1542 // todo: looks like this might be merged into d3 ( 1543 // https://github.com/mbostock/d3/issues/1642), 1544 // also worth checking out is 1545 // http://engineering.findthebest.com/wrapping-axis-labels-in-d3-js/ 1546 // this seems to be one of those things that should be easy but isn't 1547 function wrapText(circles, labeller) { 1548 return function() { 1549 var text = d3Selection.select(this), 1550 data = text.datum(), 1551 width = circles[data.sets[0]].radius || 50, 1552 label = labeller(data) || ''; 1553 1554 var words = label.split(/\s+/).reverse(), 1555 maxLines = 3, 1556 minChars = (label.length + words.length) / maxLines, 1557 word = words.pop(), 1558 line = [word], 1559 joined, 1560 lineNumber = 0, 1561 lineHeight = 1.1, // ems 1562 tspan = text.text(null).append("tspan").text(word); 1563 1564 while (true) { 1565 word = words.pop(); 1566 if (!word) break; 1567 line.push(word); 1568 joined = line.join(" "); 1569 tspan.text(joined); 1570 if (joined.length > minChars && tspan.node().getComputedTextLength() > width) { 1571 line.pop(); 1572 tspan.text(line.join(" ")); 1573 line = [word]; 1574 tspan = text.append("tspan").text(word); 1575 lineNumber++; 1576 } 1577 } 1578 1579 var initial = 0.35 - lineNumber * lineHeight / 2, 1580 x = text.attr("x"), 1581 y = text.attr("y"); 1582 1583 text.selectAll("tspan") 1584 .attr("x", x) 1585 .attr("y", y) 1586 .attr("dy", function(d, i) { 1587 return (initial + i * lineHeight) + "em"; 1588 }); 1589 }; 1590 } 1591 1592 function circleMargin(current, interior, exterior) { 1593 var margin = interior[0].radius - distance(interior[0], current), i, m; 1594 for (i = 1; i < interior.length; ++i) { 1595 m = interior[i].radius - distance(interior[i], current); 1596 if (m <= margin) { 1597 margin = m; 1598 } 1599 } 1600 1601 for (i = 0; i < exterior.length; ++i) { 1602 m = distance(exterior[i], current) - exterior[i].radius; 1603 if (m <= margin) { 1604 margin = m; 1605 } 1606 } 1607 return margin; 1608 } 1609 1610 // compute the center of some circles by maximizing the margin of 1611 // the center point relative to the circles (interior) after subtracting 1612 // nearby circles (exterior) 1613 function computeTextCentre(interior, exterior) { 1614 // get an initial estimate by sampling around the interior circles 1615 // and taking the point with the biggest margin 1616 var points = [], i; 1617 for (i = 0; i < interior.length; ++i) { 1618 var c = interior[i]; 1619 points.push({x: c.x, y: c.y}); 1620 points.push({x: c.x + c.radius/2, y: c.y}); 1621 points.push({x: c.x - c.radius/2, y: c.y}); 1622 points.push({x: c.x, y: c.y + c.radius/2}); 1623 points.push({x: c.x, y: c.y - c.radius/2}); 1624 } 1625 var initial = points[0], margin = circleMargin(points[0], interior, exterior); 1626 for (i = 1; i < points.length; ++i) { 1627 var m = circleMargin(points[i], interior, exterior); 1628 if (m >= margin) { 1629 initial = points[i]; 1630 margin = m; 1631 } 1632 } 1633 1634 // maximize the margin numerically 1635 var solution = nelderMead( 1636 function(p) { return -1 * circleMargin({x: p[0], y: p[1]}, interior, exterior); }, 1637 [initial.x, initial.y], 1638 {maxIterations:500, minErrorDelta:1e-10}).x; 1639 var ret = {x: solution[0], y: solution[1]}; 1640 1641 // check solution, fallback as needed (happens if fully overlapped 1642 // etc)
1643 var valid = true; 1644 for (i = 0; i < interior.length; ++i) { 1645 if (distance(ret, interior[i]) > interior[i].radius) { 1646 valid = false; 1647 break; 1648 } 1649 } 1650 1651 for (i = 0; i < exterior.length; ++i) { 1652 if (distance(ret, exterior[i]) < exterior[i].radius) { 1653 valid = false; 1654 break; 1655 } 1656 } 1657 1658 if (!valid) { 1659 if (interior.length == 1) { 1660 ret = {x: interior[0].x, y: interior[0].y}; 1661 } else { 1662 var areaStats = {}; 1663 intersectionArea(interior, areaStats); 1664 1665 if (areaStats.arcs.length === 0) { 1666 ret = {'x': 0, 'y': -1000, disjoint:true}; 1667 1668 } else if (areaStats.arcs.length == 1) { 1669 ret = {'x': areaStats.arcs[0].circle.x, 1670 'y': areaStats.arcs[0].circle.y}; 1671 1672 } else if (exterior.length) { 1673 // try again without other circles 1674 ret = computeTextCentre(interior, []); 1675 1676 } else { 1677 // take average of all the points in the intersection 1678 // polygon. this should basically never happen 1679 // and has some issues: 1680 // https://github.com/benfred/venn.js/issues/48#issuecomment-146069777 1681 ret = getCenter(areaStats.arcs.map(function (a) { return a.p1; })); 1682 } 1683 } 1684 } 1685 1686 return ret; 1687 } 1688 1689 // given a dictionary of {setid : circle}, returns 1690 // a dictionary of setid to list of circles that completely overlap it 1691 function getOverlappingCircles(circles) { 1692 var ret = {}, circleids = []; 1693 for (var circleid in circles) { 1694 circleids.push(circleid); 1695 ret[circleid] = []; 1696 } 1697 for (var i = 0; i < circleids.length; i++) { 1698 var a = circles[circleids[i]]; 1699 for (var j = i + 1; j < circleids.length; ++j) { 1700 var b = circles[circleids[j]], 1701 d = distance(a, b); 1702 1703 if (d + b.radius <= a.radius + 1e-10) { 1704 ret[circleids[j]].push(circleids[i]); 1705 1706 } else if (d + a.radius <= b.radius + 1e-10) { 1707 ret[circleids[i]].push(circleids[j]); 1708 } 1709 } 1710 } 1711 return ret; 1712 } 1713 1714 function computeTextCentres(circles, areas) { 1715 var ret = {}, overlapped = getOverlappingCircles(circles); 1716 for (var i = 0; i < areas.length; ++i) { 1717 var area = areas[i].sets, areaids = {}, exclude = {}; 1718 for (var j = 0; j < area.length; ++j) { 1719 areaids[area[j]] = true; 1720 var overlaps = overlapped[area[j]]; 1721 // keep track of any circles that overlap this area, 1722 // and don't consider for purposes of computing the text 1723 // centre 1724 for (var k = 0; k < overlaps.length; ++k) { 1725 exclude[overlaps[k]] = true; 1726 } 1727 } 1728 1729 var interior = [], exterior = []; 1730 for (var setid in circles) { 1731 if (setid in areaids) { 1732 interior.push(circles[setid]); 1733 } else if (!(setid in exclude)) { 1734 exterior.push(circles[setid]); 1735 } 1736 } 1737 var centre = computeTextCentre(interior, exterior); 1738 ret[area] = centre; 1739 if (centre.disjoint && (areas[i].size > 0)) { 1740 console.log("WARNING: area " + area + " not represented on screen"); 1741 } 1742 } 1743 return ret; 1744 } 1745 1746 // sorts all areas in the venn diagram, so that 1747 // a particular area is on top (relativeTo) - and 1748 // all other areas are so that the smallest areas are on top 1749 function sortAreas(div, relativeTo) { 1750 1751 // figure out sets that are completly overlapped by relativeTo 1752 var overlaps = getOverlappingCircles(div.selectAll("svg").datum()); 1753 var exclude = {}; 1754 for (var i = 0; i < relativeTo.sets.length; ++i) { 1755 var check = relativeTo.sets[i]; 1756 for (var setid in overlaps) { 1757 var overlap = overlaps[setid]; 1758 for (var j = 0; j < overlap.length; ++j) { 1759 if (overlap[j] == check) { 1760 exclude[setid] = true; 1761 break; 1762 } 1763 } 1764 } 1765 } 1766 1767 // checks that all sets are in exclude; 1768 function shouldExclude(sets) { 1769 for (var i = 0; i < sets.length; ++i) { 1770 if (!(sets[i] in exclude)) { 1771 return false;
1772 } 1773 } 1774 return true; 1775 } 1776 1777 // need to sort div's so that Z order is correct 1778 div.selectAll("g").sort(function (a, b) { 1779 // highest order set intersections first 1780 if (a.sets.length != b.sets.length) { 1781 return a.sets.length - b.sets.length; 1782 } 1783 1784 if (a == relativeTo) { 1785 return shouldExclude(b.sets) ? -1 : 1; 1786 } 1787 if (b == relativeTo) { 1788 return shouldExclude(a.sets) ? 1 : -1; 1789 } 1790 1791 // finally by size 1792 return b.size - a.size; 1793 }); 1794 } 1795 1796 function circlePath(x, y, r) { 1797 var ret = []; 1798 ret.push("\nM", x, y); 1799 ret.push("\nm", -r, 0); 1800 ret.push("\na", r, r, 0, 1, 0, r *2, 0); 1801 ret.push("\na", r, r, 0, 1, 0,-r *2, 0); 1802 return ret.join(" "); 1803 } 1804 1805 // inverse of the circlePath function, returns a circle object from an svg path 1806 function circleFromPath(path) { 1807 var tokens = path.split(' '); 1808 return {'x' : parseFloat(tokens[1]), 1809 'y' : parseFloat(tokens[2]), 1810 'radius' : -parseFloat(tokens[4]) 1811 }; 1812 } 1813 1814 /** returns a svg path of the intersection area of a bunch of circles */ 1815 function intersectionAreaPath(circles) { 1816 var stats = {}; 1817 intersectionArea(circles, stats); 1818 var arcs = stats.arcs; 1819 1820 if (arcs.length === 0) { 1821 return "M 0 0"; 1822 1823 } else if (arcs.length == 1) { 1824 var circle = arcs[0].circle; 1825 return circlePath(circle.x, circle.y, circle.radius); 1826 1827 } else { 1828 // draw path around arcs 1829 var ret = ["\nM", arcs[0].p2.x, arcs[0].p2.y]; 1830 for (var i = 0; i < arcs.length; ++i) { 1831 var arc = arcs[i], r = arc.circle.radius, wide = arc.width > r; 1832 ret.push("\nA", r, r, 0, wide ? 1 : 0, 1, 1833 arc.p1.x, arc.p1.y); 1834 } 1835 return ret.join(" "); 1836 } 1837 } 1838 1839 exports.intersectionArea = intersectionArea; 1840 exports.circleCircleIntersection = circleCircleIntersection; 1841 exports.circleOverlap = circleOverlap; 1842 exports.circleArea = circleArea; 1843 exports.distance = distance; 1844 exports.venn = venn; 1845 exports.greedyLayout = greedyLayout; 1846 exports.scaleSolution = scaleSolution; 1847 exports.normalizeSolution = normalizeSolution; 1848 exports.bestInitialLayout = bestInitialLayout; 1849 exports.lossFunction = lossFunction; 1850 exports.disjointCluster = disjointCluster; 1851 exports.distanceFromIntersectArea = distanceFromIntersectArea; 1852 exports.VennDiagram = VennDiagram; 1853 exports.wrapText = wrapText; 1854 exports.computeTextCentres = computeTextCentres; 1855 exports.computeTextCentre = computeTextCentre; 1856 exports.sortAreas = sortAreas; 1857 exports.circlePath = circlePath; 1858 exports.circleFromPath = circleFromPath; 1859 exports.intersectionAreaPath = intersectionAreaPath; 1860 1861 Object.defineProperty(exports, '__esModule', { value: true }); 1862 1863})));
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.