erasure.js

function sqr(x) {
  return x ** 2
}

function hypotenuseSquared(a, b) {
  return sqr(a) + sqr(b)
}

function distanceSquared([x0, y0], [x1, y1]) {
  return hypotenuseSquared(x0 - x1, y0 - y1)
}

function distance(point0, point1) {
  return Math.sqrt(distanceSquared(point0, point1))
}

function cap01(x) {
  return Math.max(0, Math.min(1, x))
}

function distToSegmentSquared(lineStart, lineEnd, point) {
  const l2 = distanceSquared(lineStart, lineEnd)
  if (l2 === 0) return distanceSquared(point, lineStart)
  let t =
    ((point[0] - lineStart[0]) * (lineEnd[0] - lineStart[0]) +
      (point[1] - lineStart[1]) * (lineEnd[1] - lineStart[1])) /
    l2
  t = cap01(t)
  return distanceSquared(point, [
    lineStart[0] + t * (lineEnd[0] - lineStart[0]),
    lineStart[1] + t * (lineEnd[1] - lineStart[1]),
  ])
}

function interpolate([x0, y0], [x1, y1], t) {
  return [x0 + (x1 - x0) * t, y0 + (y1 - y0) * 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 erasureInterval(lineStart, lineEnd, erasureCenter, erasureRadius) {
  if (!(lineStart && lineEnd && erasureCenter)) return

  const distToSegment2 = distToSegmentSquared(lineStart, lineEnd, erasureCenter)
  if (erasureRadius ** 2 < distToSegment2) return

  const lineLength = distance(lineStart, lineEnd)
  if (lineLength === 0) {
    return distToSegment2 <= erasureRadius ** 2 ? [0, 1] : [0, 0]
  }

  const projT = project(lineStart, lineEnd, erasureCenter)
  const projectionPoint = interpolate(lineStart, lineEnd, projT)

  const d2 = distance(erasureCenter, projectionPoint)
  const halfLength = Math.sqrt(Math.abs(sqr(erasureRadius) - sqr(d2)))
  if (halfLength === 0) return undefined

  let touchFromStartDist = distance(lineStart, projectionPoint)
  if (projT < 0) touchFromStartDist = -touchFromStartDist

  const touchBeginFromStarDist = touchFromStartDist - halfLength
  const touchEndFromStarDist = touchFromStartDist + halfLength

  return [
    cap01(touchBeginFromStarDist / lineLength),
    cap01(touchEndFromStarDist / lineLength),
  ]
}

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

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)
  const 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,
}