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 distToSegmentSquared(point, lineStart, lineEnd) {
  var l2 = distanceSquared(lineStart, lineEnd)
  if (l2 === 0) return distanceSquared(point, lineStart)
  var t =
    ((point[0] - lineStart[0]) * (lineEnd[0] - lineStart[0]) +
      (point[1] - lineStart[1]) * (lineEnd[1] - lineStart[1])) /
    l2
  t = Math.max(0, Math.min(1, t))
  return distanceSquared(point, [
    lineStart[0] + t * (lineEnd[0] - lineStart[0]),
    lineStart[1] + t * (lineEnd[1] - lineStart[1]),
  ])
}

function distToSegment(point, lineStart, lineEnd) {
  return Math.sqrt(distToSegmentSquared(point, lineStart, lineEnd))
}

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

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

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 cap01(x) {
  return Math.max(0, Math.min(1, x))
}

function erasureInterval(lineStart, lineEnd, erasureCenter, erasureRadius) {
  const lineLength = distance(lineStart, lineEnd)
  const distToLine = distanceToLine(lineStart, lineEnd, erasureCenter)
  if (lineLength === 0) {
    return distToLine <= erasureRadius ? [0, 1] : [0, 0]
  }

  const projectionPoint = interpolate(
    lineStart,
    lineEnd,
    project(lineStart, lineEnd, erasureCenter),
  )
  const touchFromStartDist = distance(lineStart, projectionPoint)
  const halfLength = Math.sqrt(sqr(erasureRadius) - sqr(distToLine))

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