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 boundingCoords(points) {
  const xs = points.map((p) => p[0])
  const ys = points.map((p) => p[1])
  return {
    maxX: Math.max(...xs),
    minX: Math.min(...xs),
    maxY: Math.max(...ys),
    minY: Math.min(...ys),
  }
}

const MATRIX_SIZE = 3

function mArray(min, max) {
  const step = (max - min) / MATRIX_SIZE
  return Array(MATRIX_SIZE)
    .fill(min)
    .map((x, i) => x + step * (i + 1))
}

function getCluster([x, y], xBounds, yBounds) {
  return {
    x: xBounds.findIndex((bound) => x <= bound),
    y: yBounds.findIndex((bound) => y <= bound),
  }
}

function computeClusters(points, xBounds, yBounds) {
  const clusters = Array(MATRIX_SIZE)
    .fill(0)
    .map(() =>
      Array(MATRIX_SIZE)
        .fill()
        .map(() => []),
    )
  points.forEach((point) => {
    const { x, y } = getCluster(point, xBounds, yBounds)
    clusters[x][y].push(point)
  })
  return clusters
}

function clusterCoefficients(clusters, points) {
  return clusters.map((rowCluster) =>
    rowCluster.map((cluster) => cluster.length / points.length),
  )
}

export function computeMatrixCoefficients(points) {
  const { maxX, minX, maxY, minY } = boundingCoords(points)
  const xBounds = mArray(minX, maxX)
  const yBounds = mArray(minY, maxY)
  const clusters = computeClusters(points, xBounds, yBounds)
  const coefficients = clusterCoefficients(clusters, points)
  return coefficients
}

function couldBeLine(points) {
  return points.length >= 2
}

const RECT_THRESHOLD_CENTER = 0.05
const RECT_THRESHOLD_SIDE_VARIANCE = 0.2

function couldBeRect(points) {
  if (points.length < 4) return false
  const matrixCoefficients = computeMatrixCoefficients(points)

  let [maxC, minC] = [0, 1]
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (!(i === j && j === 1)) {
        maxC = Math.max(maxC, matrixCoefficients[i][j])
        minC = Math.min(minC, matrixCoefficients[i][j])
      }
    }
  }

  if (
    matrixCoefficients[1][1] < RECT_THRESHOLD_CENTER &&
    maxC - minC < RECT_THRESHOLD_SIDE_VARIANCE
  ) {
    return true
  }
  return false
}

function recognizeRect(points) {
  return { points }
}

function recognizeLine(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 {}
}

function recognizeFromPoints(points) {
  if (couldBeRect(points)) {
    return recognizeRect(points)
  } else if (couldBeLine(points)) {
    return recognizeLine(points)
  }

  return {}
}

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

export default recognizeFromPoints