function distance([x1, y1], [x2, y2]) {
  return Math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
}

function sqr(x) {
  return x * x
}

function dist2(v, w) {
  return sqr(v[0] - w[0]) + sqr(v[1] - w[1])
}

// p - point
// v - start point of segment
// w - end point of segment
function distToSegmentSquared(p, v, w) {
  var l2 = dist2(v, w)
  if (l2 === 0) return dist2(p, v)
  var t = ((p[0] - v[0]) * (w[0] - v[0]) + (p[1] - v[1]) * (w[1] - v[1])) / l2
  t = Math.max(0, Math.min(1, t))
  return dist2(p, [v[0] + t * (w[0] - v[0]), v[1] + t * (w[1] - v[1])])
}

// p - point
// v - start point of segment
// w - end point of segment
function distToSegment(p, v, w) {
  return Math.sqrt(distToSegmentSquared(p, v, w))
}

function distanceToLine(lineStart, lineEnd, point) {
  return distToSegment(point, lineStart, lineEnd)
}

function shouldAddErasureInterval(
  point,
  nextPoint,
  erasureCenter,
  erasureRadius,
) {
  if (!nextPoint) return false
  return distanceToLine(point, nextPoint, erasureCenter) <= erasureRadius
}

function interpolate([x1, y1], [x2, y2], t) {
  return [x1 + (x2 - x1) * t, y1 + (y2 - y1) * t]
}

function project([x1, y1], [x2, y2], [x3, y3]) {
  const x21 = x2 - x1,
    y21 = y2 - y1
  const x31 = x3 - x1,
    y31 = y3 - y1
  return (x31 * x21 + y31 * y21) / (x21 * x21 + y21 * y21)
}

function cap0(x) {
  return Math.max(0, x)
}

function cap1(x) {
  return Math.min(1, x)
}

function erasureInterval(lineStart, lineEnd, erasureCenter, erasureRadius) {
  const [cx, cy] = interpolate(
    lineStart,
    lineEnd,
    project(lineStart, lineEnd, erasureCenter),
  )
  const d = distanceToLine(lineStart, lineEnd, erasureCenter)
  const halfLength = Math.sqrt(erasureRadius ** 2 - d ** 2)
  const lineLength = distance(lineStart, lineEnd)

  const touchFromStartDist = distance(lineStart, [cx, cy])
  const touchBeginFromStarDist = touchFromStartDist - halfLength
  const touchEndFromStarDist = touchFromStartDist + halfLength
  return [
    cap0(touchBeginFromStarDist / lineLength),
    cap1(touchEndFromStarDist / lineLength),
  ]
}

function computeErasureIntervals(points, erasureCenter, erasureRadius) {
  return points
    .map((point, i) => ({ point, i }))
    .filter(({ point, i }) =>
      shouldAddErasureInterval(
        point,
        points[i + 1],
        erasureCenter,
        erasureRadius,
      ),
    )
    .reduce(
      (acc, { point, i }) => ({
        ...acc,
        [i]: [
          erasureInterval(point, points[i + 1], erasureCenter, erasureRadius),
        ],
      }),
      {},
    )
}

function overlaps([s1, e1], [, e2]) {
  return s1 <= e2 && s1 <= e1
}

function mergeIntervals(...intervals) {
  if (!intervals.length) return []

  const sorted = intervals.sort(([a], [b]) => a > b)
  let stack = [sorted[0]]
  sorted.forEach((x) => {
    const top = stack[stack.length - 1]
    if (overlaps(x, top)) {
      if (x[1] > top[1]) top[1] = x[1]
    } else {
      stack.push(x)
    }
  })
  return stack
}

function combineErasureIntervals(i1, i2) {
  const _i1 = { ...i1 }
  Object.keys(i1).forEach((key) => {
    if (i2[key]) {
      _i1[key] = mergeIntervals(...i1[key], ...i2[key])
    }
  })
  return { ...i2, ..._i1 }
}

module.exports = {
  computeErasureIntervals,
  combineErasureIntervals,
}