shapes.js

const getDistance = (a, b) => {
  if (!(a && b)) return 0
  return Math.sqrt(
    (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]),
  )
}

// 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 angleStep = 90
// const numAngleCells = 180 / angleStep
// const rhoMax = 10000

// 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]
//         bestTheta = i
//       }
//     }
//   }
//   bestTheta *= angleStep

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

// function constructHoughAccumulator(config, 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 /= config.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),
  }
}

function vectorLength([x, y]) {
  return Math.hypot(x, y)
}

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

function angleBetweenVectors(p1, p2) {
  const [[x0, y0], [x1, y1]] = [p1, p2]
  return Math.acos((x0 * x1 + y0 * y1) / (vectorLength(p1) * vectorLength(p2)))
}

const LINE_ANGLE_THRESHOLD = Math.PI / 6
const VECTOR_LEN_THRESHOLD_FRACTION = 0.3

function couldBeLine(points) {
  if (points.length < 2) return false
  const vectorThreshold = Math.floor(
    points.length * VECTOR_LEN_THRESHOLD_FRACTION,
  )
  const pivot = points[0]
  let cumulativeThreshold = 0
  for (let i = 2; i < points.length; i++) {
    const p1 = points[i - 1]
    const p2 = points[i]
    const d1 = diffVector(pivot, p1)
    const d2 = diffVector(p1, p2)

    const d2Len = vectorLength(d2)

    const angle = angleBetweenVectors(d1, d2)
    if (Math.abs(angle) > LINE_ANGLE_THRESHOLD) {
      if (cumulativeThreshold < vectorThreshold && d2Len < vectorThreshold) {
        cumulativeThreshold += d2Len
        continue
      }
      return false
    }
  }
  return true
}

const MATRIX_SIZE = 3
const MATRIX_CENTER_RATIO = 0.65

function mArray(min, max) {
  const d = max - min
  const centerSegmentSize = d * MATRIX_CENTER_RATIO
  const smallStep = (d - centerSegmentSize) / 2
  const p = [min + smallStep, min + smallStep + centerSegmentSize, max]
  return p
}

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(() => ({ arr: [], sum: 0 })),
    )
  const intervals = points.map((point, i) => ({
    point,
    dist: getDistance(point, points[i + 1]),
  }))

  let totalSum = 0
  intervals.forEach((interval) => {
    const { x, y } = getCluster(interval.point, xBounds, yBounds)
    clusters[x][y].arr.push(interval)
    clusters[x][y].sum += interval.dist
    totalSum += interval.dist
  })

  return { arr: clusters, totalSum }
}

function clusterCoefficients(clusters) {
  return clusters.arr.map((rowCluster) =>
    rowCluster.map((cluster) => cluster.sum / clusters.totalSum),
  )
}

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

const RECT_THRESHOLD_CENTER = 0
const RECT_THRESHOLD_SIDE_VARIANCE = 0.25

function couldBeRect(points) {
  if (points.length < 4) return false

  const boundingRect = boundingCoords(points)
  const matrixCoefficients = computeMatrixCoefficients(points, boundingRect)

  let [maxC, minC] = [0, 1]
  for (let i = 0; i < MATRIX_SIZE; i++) {
    for (let j = 0; j < MATRIX_SIZE; 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 { coefficients: matrixCoefficients, boundingRect }
  }
  return undefined
}

function recognizeRect(points, rectDetectionData) {
  const { minX, minY, maxX, maxY } = rectDetectionData.boundingRect
  return {
    boundingRect: rectDetectionData.boundingRect,
    boundingPoints: [
      [minX, minY],
      [minX, maxY],
      [maxX, maxY],
      [maxX, minY],
      [minX, minY],
    ],
    shape: Shapes.rectangle,
    points,
  }
}

function recognizeLine(points) {
  const [p1, p2] = [points[0], points[points.length - 1]]
  const angle =
    (angleBetweenVectors(diffVector(p2, p1), [1, 0]) / Math.PI) * 180
  return {
    shape: Shapes.line,
    angle,
    points,
    length: getDistance(p1, p2),
    lastPoint: p2.slice(0, 2),
  }
}
// const MAX_RHO_STEP = 50
// const MIN_RHO_STEP = 5

// function rhoStepForPoints(points) {
//   return points.length > 50 ? MAX_RHO_STEP : MIN_RHO_STEP
// }

// function recognizeLineHough(points) {
//   if (!(points && points.length)) return {}
//   const accum = Array(numAngleCells)
//   const houghConfig = {
//     rhoStep: rhoStepForPoints(points),
//   }
//   points.forEach((x) => constructHoughAccumulator(houghConfig, accum, ...x))
//   const angle = findMaxInHough(accum, points.length - 10)

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

//   return {}
// }

function recognizeFromPoints(points) {
  const rectDetectData = couldBeRect(points)
  if (rectDetectData) {
    return recognizeRect(points, rectDetectData)
  } else if (couldBeLine(points)) {
    return recognizeLine(points)
  }

  return {}
}

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

export default recognizeFromPoints