shapes.js

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

const RECT_MATRIX_SIZE = 3
const RECT_MATRIX_CENTER_RATIO = 0.65

const RECT_THRESHOLD_CENTER = 0
const RECT_THRESHOLD_SIDE_VARIANCE = 0.25

function getDistance([x0, y0], [x1, y1]) {
  return Math.hypot(x1 - x0, y1 - y0)
}

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

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 matrixBoundsArray(min, max) {
  const d = max - min
  const centerSegmentSize = d * RECT_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(RECT_MATRIX_SIZE)
    .fill(0)
    .map(() =>
      Array(RECT_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 = matrixBoundsArray(minX, maxX)
  const yBounds = matrixBoundsArray(minY, maxY)
  const clusters = computeClusters(points, xBounds, yBounds)
  const coefficients = clusterCoefficients(clusters, points)
  return coefficients
}

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 < RECT_MATRIX_SIZE; i++) {
    for (let j = 0; j < RECT_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 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
}

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

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