shapes.js

function dtor(a) {
  return (Math.PI * a) / 180
}
function cos(a) {
  return Math.cos(dtor(a))
}
function sin(a) {
  return Math.sin(dtor(a))
}

const rhoStep = 5
const angleStep = 10
const numAngleCells = 180 / angleStep
const rhoMax = 1000

function findMaxInHough(accum, threshold) {
  let max = 0
  //   let bestRho = 0
  let bestTheta = 0
  for (let i = 0; i < numAngleCells; i++) {
    if (!accum[i]) continue
    for (let j = 0; j < accum[i].length; j++) {
      if (accum[i][j] > max) {
        max = accum[i][j]
        // bestRho = j
        bestTheta = i
      }
    }
  }
  //   bestRho <<= 1
  //   bestRho -= rhoMax
  //   bestRho *= rhoStep
  bestTheta *= angleStep

  if (max > threshold) {
    return bestTheta
  }
  return undefined
}

function constructHoughAccumulator(accumulator, x, y) {
  for (let thetaIndex = 0; thetaIndex < numAngleCells; thetaIndex++) {
    const theta = thetaIndex * angleStep
    let rho = x * cos(theta) + y * sin(theta)
    rho = Math.floor(rho)
    rho += rhoMax
    rho >>= 1
    rho /= rhoStep
    rho = Math.floor(rho)
    if (accumulator[thetaIndex] == undefined) accumulator[thetaIndex] = []
    if (accumulator[thetaIndex][rho] == undefined) {
      accumulator[thetaIndex][rho] = 1
    } else {
      accumulator[thetaIndex][rho]++
    }
  }
}

function recognizeFromPoints(points) {
  if (!(points && points.length)) return {}
  const accum = Array(numAngleCells)
  points.forEach((x) => constructHoughAccumulator(accum, ...x))
  const angle = findMaxInHough(accum, points.length - 1)

  if (angle !== undefined) {
    return {
      shape: Shapes.line,
      angle: 90 - angle,
      hough: accum,
      points,
    }
  }

  return {}
}

export const Shapes = {
  rectangle: "rect",
  line: "line",
}

export default recognizeFromPoints