{"version":3,"file":"circleintersection.js","sourceRoot":"","sources":["../../../../src/plots/venn/layout/circleintersection.ts"],"names":[],"mappings":";;;AAAA,IAAM,KAAK,GAAG,KAAK,CAAC;AAEpB;mDACmD;AACnD,SAAgB,gBAAgB,CAAC,OAAO,EAAE,KAAW;IACnD,iDAAiD;IACjD,IAAM,kBAAkB,GAAG,qBAAqB,CAAC,OAAO,CAAC,CAAC;IAE1D,4DAA4D;IAC5D,IAAM,WAAW,GAAG,kBAAkB,CAAC,MAAM,CAAC,UAAU,CAAC;QACvD,OAAO,kBAAkB,CAAC,CAAC,EAAE,OAAO,CAAC,CAAC;IACxC,CAAC,CAAC,CAAC;IAEH,IAAI,OAAO,GAAG,CAAC,EACb,WAAW,GAAG,CAAC,EACf,CAAC,CAAC;IACJ,IAAM,IAAI,GAAG,EAAE,CAAC;IAChB,kEAAkE;IAClE,6CAA6C;IAC7C,IAAI,WAAW,CAAC,MAAM,GAAG,CAAC,EAAE;QAC1B,sEAAsE;QACtE,+CAA+C;QAC/C,IAAM,MAAM,GAAG,SAAS,CAAC,WAAW,CAAC,CAAC;QACtC,KAAK,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,WAAW,CAAC,MAAM,EAAE,EAAE,CAAC,EAAE;YACvC,IAAM,CAAC,GAAG,WAAW,CAAC,CAAC,CAAC,CAAC;YACzB,CAAC,CAAC,KAAK,GAAG,IAAI,CAAC,KAAK,CAAC,CAAC,CAAC,CAAC,GAAG,MAAM,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,GAAG,MAAM,CAAC,CAAC,CAAC,CAAC;SACtD;QACD,WAAW,CAAC,IAAI,CAAC,UAAU,CAAC,EAAE,CAAC;YAC7B,OAAO,CAAC,CAAC,KAAK,GAAG,CAAC,CAAC,KAAK,CAAC;QAC3B,CAAC,CAAC,CAAC;QAEH,sDAAsD;QACtD,uBAAuB;QACvB,IAAI,EAAE,GAAG,WAAW,CAAC,WAAW,CAAC,MAAM,GAAG,CAAC,CAAC,CAAC;QAC7C,KAAK,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,WAAW,CAAC,MAAM,EAAE,EAAE,CAAC,EAAE;YACvC,IAAM,EAAE,GAAG,WAAW,CAAC,CAAC,CAAC,CAAC;YAE1B,kCAAkC;YAClC,WAAW,IAAI,CAAC,EAAE,CAAC,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC,GAAG,CAAC,EAAE,CAAC,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC,CAAC;YAE7C,kDAAkD;YAClD,IAAM,QAAQ,GAAG,EAAE,CAAC,EAAE,CAAC,EAAE,CAAC,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE,CAAC,EAAE,CAAC,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC,GAAG,CAAC,EAAE,CAAC;YAChE,IAAI,GAAG,GAAG,IAAI,CAAC;YAEf,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,EAAE,CAAC,WAAW,CAAC,MAAM,EAAE,EAAE,CAAC,EAAE;gBAC9C,IAAI,EAAE,CAAC,WAAW,CAAC,OAAO,CAAC,EAAE,CAAC,WAAW,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC,EAAE;oBAClD,sDAAsD;oBACtD,wBAAwB;oBACxB,IAAM,MAAM,GAAG,OAAO,CAAC,EAAE,CAAC,WAAW,CAAC,CAAC,CAAC,CAAC,EACvC,EAAE,GAAG,IAAI,CAAC,KAAK,CAAC,EAAE,CAAC,CAAC,GAAG,MAAM,CAAC,CAAC,EAAE,EAAE,CAAC,CAAC,GAAG,MAAM,CAAC,CAAC,CAAC,EACjD,EAAE,GAAG,IAAI,CAAC,KAAK,CAAC,EAAE,CAAC,CAAC,GAAG,MAAM,CAAC,CAAC,EAAE,EAAE,CAAC,CAAC,GAAG,MAAM,CAAC,CAAC,CAAC,CAAC;oBAEpD,IAAI,SAAS,GAAG,EAAE,GAAG,EAAE,CAAC;oBACxB,IAAI,SAAS,GAAG,CAAC,EAAE;wBACjB,SAAS,IAAI,CAAC,GAAG,IAAI,CAAC,EAAE,CAAC;qBAC1B;oBAED,oDAAoD;oBACpD,MAAM;oBACN,IAAM,CAAC,GAAG,EAAE,GAAG,SAAS,GAAG,CAAC,CAAC;oBAC7B,IAAI,KAAK,GAAG,QAAQ,CAAC,QAAQ,EAAE;wBAC7B,CAAC,EAAE,MAAM,CAAC,CAAC,GAAG,MAAM,CAAC,MAAM,GAAG,IAAI,CAAC,GAAG,CAAC,CAAC,CAAC;wBACzC,CAAC,EAAE,MAAM,CAAC,CAAC,GAAG,MAAM,CAAC,MAAM,GAAG,IAAI,CAAC,GAAG,CAAC,CAAC,CAAC;qBAC1C,CAAC,CAAC;oBAEH,oDAAoD;oBACpD,sDAAsD;oBACtD,IAAI,KAAK,GAAG,MAAM,CAAC,MAAM,GAAG,CAAC,EAAE;wBAC7B,KAAK,GAAG,MAAM,CAAC,MAAM,GAAG,CAAC,CAAC;qBAC3B;oBAED,mDAAmD;oBACnD,IAAI,GAAG,KAAK,IAAI,IAAI,GAAG,CAAC,KAAK,GAAG,KAAK,EAAE;wBACrC,GAAG,GAAG,EAAE,MAAM,EAAE,MAAM,EAAE,KAAK,EAAE,KAAK,EAAE,EAAE,EAAE,EAAE,EAAE,EAAE,EAAE,EAAE,EAAE,CAAC;qBACxD;iBACF;aACF;YAED,IAAI,GAAG,KAAK,IAAI,EAAE;gBAChB,IAAI,CAAC,IAAI,CAAC,GAAG,CAAC,CAAC;gBACf,OAAO,IAAI,UAAU,CAAC,GAAG,CAAC,MAAM,CAAC,MAAM,EAAE,GAAG,CAAC,KAAK,CAAC,CAAC;gBACpD,EAAE,GAAG,EAAE,CAAC;aACT;SACF;KACF;SAAM;QACL,gEAAgE;QAChE,gEAAgE;QAChE,IAAI,QAAQ,GAAG,OAAO,CAAC,CAAC,CAAC,CAAC;QAC1B,KAAK,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,OAAO,CAAC,MAAM,EAAE,EAAE,CAAC,EAAE;YACnC,IAAI,OAAO,CAAC,CAAC,CAAC,CAAC,MAAM,GAAG,QAAQ,CAAC,MAAM,EAAE;gBACvC,QAAQ,GAAG,OAAO,CAAC,CAAC,CAAC,CAAC;aACvB;SACF;QAED,+DAA+D;QAC/D,oBAAoB;QACpB,IAAI,QAAQ,GAAG,KAAK,CAAC;QACrB,KAAK,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,OAAO,CAAC,MAAM,EAAE,EAAE,CAAC,EAAE;YACnC,IAAI,QAAQ,CAAC,OAAO,CAAC,CAAC,CAAC,EAAE,QAAQ,CAAC,GAAG,IAAI,CAAC,GAAG,CAAC,QAAQ,CAAC,MAAM,GAAG,OAAO,CAAC,CAAC,CAAC,CAAC,MAAM,CAAC,EAAE;gBAClF,QAAQ,GAAG,IAAI,CAAC;gBAChB,MAAM;aACP;SACF;QAED,IAAI,QAAQ,EAAE;YACZ,OAAO,GAAG,WAAW,GAAG,CAAC,CAAC;SAC3B;aAAM;YACL,OAAO,GAAG,QAAQ,CAAC,MAAM,GAAG,QAAQ,CAAC,MAAM,GAAG,IAAI,CAAC,EAAE,CAAC;YACtD,IAAI,CAAC,IAAI,CAAC;gBACR,MAAM,EAAE,QAAQ;gBAChB,EAAE,EAAE,EAAE,CAAC,EAAE,QAAQ,CAAC,CAAC,EAAE,CAAC,EAAE,QAAQ,CAAC,CAAC,GAAG,QAAQ,CAAC,MAAM,EAAE;gBACtD,EAAE,EAAE,EAAE,CAAC,EAAE,QAAQ,CAAC,CAAC,GAAG,KAAK,EAAE,CAAC,EAAE,QAAQ,CAAC,CAAC,GAAG,QAAQ,CAAC,MAAM,EAAE;gBAC9D,KAAK,EAAE,QAAQ,CAAC,MAAM,GAAG,CAAC;aAC3B,CAAC,CAAC;SACJ;KACF;IAED,WAAW,IAAI,CAAC,CAAC;IACjB,IAAI,KAAK,EAAE;QACT,KAAK,CAAC,IAAI,GAAG,OAAO,GAAG,WAAW,CAAC;QACnC,KAAK,CAAC,OAAO,GAAG,OAAO,CAAC;QACxB,KAAK,CAAC,WAAW,GAAG,WAAW,CAAC;QAChC,KAAK,CAAC,IAAI,GAAG,IAAI,CAAC;QAClB,KAAK,CAAC,WAAW,GAAG,WAAW,CAAC;QAChC,KAAK,CAAC,kBAAkB,GAAG,kBAAkB,CAAC;KAC/C;IAED,OAAO,OAAO,GAAG,WAAW,CAAC;AAC/B,CAAC;AA5HD,4CA4HC;AAED,uEAAuE;AACvE,SAAgB,kBAAkB,CAAC,KAAK,EAAE,OAAO;IAC/C,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,OAAO,CAAC,MAAM,EAAE,EAAE,CAAC,EAAE;QACvC,IAAI,QAAQ,CAAC,KAAK,EAAE,OAAO,CAAC,CAAC,CAAC,CAAC,GAAG,OAAO,CAAC,CAAC,CAAC,CAAC,MAAM,GAAG,KAAK,EAAE;YAC3D,OAAO,KAAK,CAAC;SACd;KACF;IACD,OAAO,IAAI,CAAC;AACd,CAAC;AAPD,gDAOC;AAED,8DAA8D;AAC9D,SAAS,qBAAqB,CAAC,OAAO;IACpC,IAAM,GAAG,GAAG,EAAE,CAAC;IACf,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,OAAO,CAAC,MAAM,EAAE,EAAE,CAAC,EAAE;QACvC,KAAK,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,OAAO,CAAC,MAAM,EAAE,EAAE,CAAC,EAAE;YAC3C,IAAM,SAAS,GAAG,wBAAwB,CAAC,OAAO,CAAC,CAAC,CAAC,EAAE,OAAO,CAAC,CAAC,CAAC,CAAC,CAAC;YACnE,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,SAAS,CAAC,MAAM,EAAE,EAAE,CAAC,EAAE;gBACzC,IAAM,CAAC,GAAQ,SAAS,CAAC,CAAC,CAAC,CAAC;gBAC5B,CAAC,CAAC,WAAW,GAAG,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC;gBACvB,GAAG,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC;aACb;SACF;KACF;IACD,OAAO,GAAG,CAAC;AACb,CAAC;AAED,+FAA+F;AAC/F,SAAgB,UAAU,CAAC,CAAC,EAAE,KAAK;IACjC,OAAO,CAAC,GAAG,CAAC,GAAG,IAAI,CAAC,IAAI,CAAC,CAAC,GAAG,KAAK,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,KAAK,CAAC,GAAG,IAAI,CAAC,IAAI,CAAC,KAAK,GAAG,CAAC,CAAC,GAAG,CAAC,GAAG,KAAK,CAAC,CAAC,CAAC;AAC7F,CAAC;AAFD,gCAEC;AAED,4CAA4C;AAC5C,SAAgB,QAAQ,CAAC,EAAE,EAAE,EAAE;IAC7B,OAAO,IAAI,CAAC,IAAI,CAAC,CAAC,EAAE,CAAC,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC,GAAG,CAAC,EAAE,CAAC,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC,GAAG,CAAC,EAAE,CAAC,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC,GAAG,CAAC,EAAE,CAAC,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC,CAAC,CAAC;AAClF,CAAC;AAFD,4BAEC;AAED;;2CAE2C;AAC3C,SAAgB,aAAa,CAAC,EAAE,EAAE,EAAE,EAAE,CAAC;IACrC,aAAa;IACb,IAAI,CAAC,IAAI,EAAE,GAAG,EAAE,EAAE;QAChB,OAAO,CAAC,CAAC;KACV;IAED,wBAAwB;IACxB,IAAI,CAAC,IAAI,IAAI,CAAC,GAAG,CAAC,EAAE,GAAG,EAAE,CAAC,EAAE;QAC1B,OAAO,IAAI,CAAC,EAAE,GAAG,IAAI,CAAC,GAAG,CAAC,EAAE,EAAE,EAAE,CAAC,GAAG,IAAI,CAAC,GAAG,CAAC,EAAE,EAAE,EAAE,CAAC,CAAC;KACtD;IAED,IAAM,EAAE,GAAG,EAAE,GAAG,CAAC,CAAC,GAAG,CAAC,GAAG,EAAE,GAAG,EAAE,GAAG,EAAE,GAAG,EAAE,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,EACnD,EAAE,GAAG,EAAE,GAAG,CAAC,CAAC,GAAG,CAAC,GAAG,EAAE,GAAG,EAAE,GAAG,EAAE,GAAG,EAAE,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,CAAC;IAClD,OAAO,UAAU,CAAC,EAAE,EAAE,EAAE,CAAC,GAAG,UAAU,CAAC,EAAE,EAAE,EAAE,CAAC,CAAC;AACjD,CAAC;AAdD,sCAcC;AAED;;;+EAG+E;AAC/E,SAAgB,wBAAwB,CAAC,EAAE,EAAE,EAAE;IAC7C,IAAM,CAAC,GAAG,QAAQ,CAAC,EAAE,EAAE,EAAE,CAAC,EACxB,EAAE,GAAG,EAAE,CAAC,MAAM,EACd,EAAE,GAAG,EAAE,CAAC,MAAM,CAAC;IAEjB,oDAAoD;IACpD,IAAI,CAAC,IAAI,EAAE,GAAG,EAAE,IAAI,CAAC,IAAI,IAAI,CAAC,GAAG,CAAC,EAAE,GAAG,EAAE,CAAC,EAAE;QAC1C,OAAO,EAAE,CAAC;KACX;IAED,IAAM,CAAC,GAAG,CAAC,EAAE,GAAG,EAAE,GAAG,EAAE,GAAG,EAAE,GAAG,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,EAC7C,CAAC,GAAG,IAAI,CAAC,IAAI,CAAC,EAAE,GAAG,EAAE,GAAG,CAAC,GAAG,CAAC,CAAC,EAC9B,EAAE,GAAG,EAAE,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,EAAE,CAAC,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,EACnC,EAAE,GAAG,EAAE,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,EAAE,CAAC,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,EACnC,EAAE,GAAG,CAAC,CAAC,EAAE,CAAC,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,EAC7B,EAAE,GAAG,CAAC,CAAC,EAAE,CAAC,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC,GAAG,CAAC,CAAC,CAAC;IAEhC,OAAO;QACL,EAAE,CAAC,EAAE,EAAE,GAAG,EAAE,EAAE,CAAC,EAAE,EAAE,GAAG,EAAE,EAAE;QAC1B,EAAE,CAAC,EAAE,EAAE,GAAG,EAAE,EAAE,CAAC,EAAE,EAAE,GAAG,EAAE,EAAE;KAC3B,CAAC;AACJ,CAAC;AArBD,4DAqBC;AAED,8CAA8C;AAC9C,SAAgB,SAAS,CAAC,MAAM;IAC9B,IAAM,MAAM,GAAG,EAAE,CAAC,EAAE,CAAC,EAAE,CAAC,EAAE,CAAC,EAAE,CAAC;IAC9B,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,MAAM,CAAC,MAAM,EAAE,EAAE,CAAC,EAAE;QACtC,MAAM,CAAC,CAAC,IAAI,MAAM,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;QACxB,MAAM,CAAC,CAAC,IAAI,MAAM,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;KACzB;IACD,MAAM,CAAC,CAAC,IAAI,MAAM,CAAC,MAAM,CAAC;IAC1B,MAAM,CAAC,CAAC,IAAI,MAAM,CAAC,MAAM,CAAC;IAC1B,OAAO,MAAM,CAAC;AAChB,CAAC;AATD,8BASC","sourcesContent":["const SMALL = 1e-10;\n\n/** Returns the intersection area of a bunch of circles (where each circle\n is an object having an x,y and radius property) */\nexport function intersectionArea(circles, stats?: any) {\n  // get all the intersection points of the circles\n  const intersectionPoints = getIntersectionPoints(circles);\n\n  // filter out points that aren't included in all the circles\n  const innerPoints = intersectionPoints.filter(function (p) {\n    return containedInCircles(p, circles);\n  });\n\n  let arcArea = 0,\n    polygonArea = 0,\n    i;\n  const arcs = [];\n  // if we have intersection points that are within all the circles,\n  // then figure out the area contained by them\n  if (innerPoints.length > 1) {\n    // sort the points by angle from the center of the polygon, which lets\n    // us just iterate over points to get the edges\n    const center = getCenter(innerPoints);\n    for (i = 0; i < innerPoints.length; ++i) {\n      const p = innerPoints[i];\n      p.angle = Math.atan2(p.x - center.x, p.y - center.y);\n    }\n    innerPoints.sort(function (a, b) {\n      return b.angle - a.angle;\n    });\n\n    // iterate over all points, get arc between the points\n    // and update the areas\n    let p2 = innerPoints[innerPoints.length - 1];\n    for (i = 0; i < innerPoints.length; ++i) {\n      const p1 = innerPoints[i];\n\n      // polygon area updates easily ...\n      polygonArea += (p2.x + p1.x) * (p1.y - p2.y);\n\n      // updating the arc area is a little more involved\n      const midPoint = { x: (p1.x + p2.x) / 2, y: (p1.y + p2.y) / 2 };\n      let arc = null;\n\n      for (let j = 0; j < p1.parentIndex.length; ++j) {\n        if (p2.parentIndex.indexOf(p1.parentIndex[j]) > -1) {\n          // figure out the angle halfway between the two points\n          // on the current circle\n          const circle = circles[p1.parentIndex[j]],\n            a1 = Math.atan2(p1.x - circle.x, p1.y - circle.y),\n            a2 = Math.atan2(p2.x - circle.x, p2.y - circle.y);\n\n          let angleDiff = a2 - a1;\n          if (angleDiff < 0) {\n            angleDiff += 2 * Math.PI;\n          }\n\n          // and use that angle to figure out the width of the\n          // arc\n          const a = a2 - angleDiff / 2;\n          let width = distance(midPoint, {\n            x: circle.x + circle.radius * Math.sin(a),\n            y: circle.y + circle.radius * Math.cos(a),\n          });\n\n          // clamp the width to the largest is can actually be\n          // (sometimes slightly overflows because of FP errors)\n          if (width > circle.radius * 2) {\n            width = circle.radius * 2;\n          }\n\n          // pick the circle whose arc has the smallest width\n          if (arc === null || arc.width > width) {\n            arc = { circle: circle, width: width, p1: p1, p2: p2 };\n          }\n        }\n      }\n\n      if (arc !== null) {\n        arcs.push(arc);\n        arcArea += circleArea(arc.circle.radius, arc.width);\n        p2 = p1;\n      }\n    }\n  } else {\n    // no intersection points, is either disjoint - or is completely\n    // overlapped. figure out which by examining the smallest circle\n    let smallest = circles[0];\n    for (i = 1; i < circles.length; ++i) {\n      if (circles[i].radius < smallest.radius) {\n        smallest = circles[i];\n      }\n    }\n\n    // make sure the smallest circle is completely contained in all\n    // the other circles\n    let disjoint = false;\n    for (i = 0; i < circles.length; ++i) {\n      if (distance(circles[i], smallest) > Math.abs(smallest.radius - circles[i].radius)) {\n        disjoint = true;\n        break;\n      }\n    }\n\n    if (disjoint) {\n      arcArea = polygonArea = 0;\n    } else {\n      arcArea = smallest.radius * smallest.radius * Math.PI;\n      arcs.push({\n        circle: smallest,\n        p1: { x: smallest.x, y: smallest.y + smallest.radius },\n        p2: { x: smallest.x - SMALL, y: smallest.y + smallest.radius },\n        width: smallest.radius * 2,\n      });\n    }\n  }\n\n  polygonArea /= 2;\n  if (stats) {\n    stats.area = arcArea + polygonArea;\n    stats.arcArea = arcArea;\n    stats.polygonArea = polygonArea;\n    stats.arcs = arcs;\n    stats.innerPoints = innerPoints;\n    stats.intersectionPoints = intersectionPoints;\n  }\n\n  return arcArea + polygonArea;\n}\n\n/** returns whether a point is contained by all of a list of circles */\nexport function containedInCircles(point, circles) {\n  for (let i = 0; i < circles.length; ++i) {\n    if (distance(point, circles[i]) > circles[i].radius + SMALL) {\n      return false;\n    }\n  }\n  return true;\n}\n\n/** Gets all intersection points between a bunch of circles */\nfunction getIntersectionPoints(circles) {\n  const ret = [];\n  for (let i = 0; i < circles.length; ++i) {\n    for (let j = i + 1; j < circles.length; ++j) {\n      const intersect = circleCircleIntersection(circles[i], circles[j]);\n      for (let k = 0; k < intersect.length; ++k) {\n        const p: any = intersect[k];\n        p.parentIndex = [i, j];\n        ret.push(p);\n      }\n    }\n  }\n  return ret;\n}\n\n/** Circular segment area calculation. See http://mathworld.wolfram.com/CircularSegment.html */\nexport function circleArea(r, width) {\n  return r * r * Math.acos(1 - width / r) - (r - width) * Math.sqrt(width * (2 * r - width));\n}\n\n/** euclidean distance between two points */\nexport function distance(p1, p2) {\n  return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));\n}\n\n/** Returns the overlap area of two circles of radius r1 and r2 - that\nhave their centers separated by distance d. Simpler faster\ncircle intersection for only two circles */\nexport function circleOverlap(r1, r2, d) {\n  // no overlap\n  if (d >= r1 + r2) {\n    return 0;\n  }\n\n  // completely overlapped\n  if (d <= Math.abs(r1 - r2)) {\n    return Math.PI * Math.min(r1, r2) * Math.min(r1, r2);\n  }\n\n  const w1 = r1 - (d * d - r2 * r2 + r1 * r1) / (2 * d),\n    w2 = r2 - (d * d - r1 * r1 + r2 * r2) / (2 * d);\n  return circleArea(r1, w1) + circleArea(r2, w2);\n}\n\n/** Given two circles (containing a x/y/radius attributes),\nreturns the intersecting points if possible.\nnote: doesn't handle cases where there are infinitely many\nintersection points (circles are equivalent):, or only one intersection point*/\nexport function circleCircleIntersection(p1, p2) {\n  const d = distance(p1, p2),\n    r1 = p1.radius,\n    r2 = p2.radius;\n\n  // if to far away, or self contained - can't be done\n  if (d >= r1 + r2 || d <= Math.abs(r1 - r2)) {\n    return [];\n  }\n\n  const a = (r1 * r1 - r2 * r2 + d * d) / (2 * d),\n    h = Math.sqrt(r1 * r1 - a * a),\n    x0 = p1.x + (a * (p2.x - p1.x)) / d,\n    y0 = p1.y + (a * (p2.y - p1.y)) / d,\n    rx = -(p2.y - p1.y) * (h / d),\n    ry = -(p2.x - p1.x) * (h / d);\n\n  return [\n    { x: x0 + rx, y: y0 - ry },\n    { x: x0 - rx, y: y0 + ry },\n  ];\n}\n\n/** Returns the center of a bunch of points */\nexport function getCenter(points) {\n  const center = { x: 0, y: 0 };\n  for (let i = 0; i < points.length; ++i) {\n    center.x += points[i].x;\n    center.y += points[i].y;\n  }\n  center.x /= points.length;\n  center.y /= points.length;\n  return center;\n}\n"]}