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 && erasureCenter)) return undefined

  if (!lineEnd) {
    const dist2ToSingularity = distanceSquared(erasureCenter, lineStart)
    return dist2ToSingularity <= erasureRadius ** 2 ? [0, 0] : undefined
  }

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

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

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

export 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
}

export 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 }
}

export function spreadErasureIntervals(intervals) {
  const spread = {}

  intervals.forEach(([l, u]) => {
    if (u > l) {
      for (let li = Math.floor(l); li < u; li++) {
        const list = spread[li] || []

        const [il, iu] = [Math.max(li, l), Math.min(li + 1, u)]

        list.push([il % 1, iu == li + 1 ? 1 : iu % 1])

        spread[li] = list
      }
    } else {
      spread[Math.floor(l)] = [[l % 1, u % 1]]
    }
  })

  return spread
}

export function flattenErasureIntervals(intervals) {
  const flatten = []

  for (const idx in intervals) {
    if (intervals[idx])
      flatten.push(
        intervals[idx].map(([l, u]) => [parseInt(idx) + l, parseInt(idx) + u]),
      )
  }

  return flatten.flat()
}