Skip to content

Virtual whiteboard for sketching hand-drawn like diagrams

5.6 KB
Raw Blame
import { pointsEqual } from "./point";
import { PRECISION } from "./utils";

import type { GlobalPoint, LocalPoint, Polygon } from "./types";

export function polygon<Point extends GlobalPoint | LocalPoint>(
  ...points: Point[]
) {
  return polygonClose(points) as Polygon<Point>;
}

export function polygonFromPoints<Point extends GlobalPoint | LocalPoint>(
  points: Point[],
) {
  return polygonClose(points) as Polygon<Point>;
}

export const polygonIncludesPoint = <Point extends LocalPoint | GlobalPoint>(
  point: Point,
  polygon: Polygon<Point>,
) => {
  const x = point[0];
  const y = point[1];
  let inside = false;

  for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
    const xi = polygon[i][0];
    const yi = polygon[i][1];
    const xj = polygon[j][0];
    const yj = polygon[j][1];

    if (
      ((yi > y && yj <= y) || (yi <= y && yj > y)) &&
      x < ((xj - xi) * (y - yi)) / (yj - yi) + xi
    ) {
      inside = !inside;
    }
  }

  return inside;
};

export const polygonIncludesPointNonZero = <Point extends [number, number]>(
  point: Point,
  polygon: Point[],
): boolean => {
  const [x, y] = point;
  let windingNumber = 0;

  for (let i = 0; i < polygon.length; i++) {
    const j = (i + 1) % polygon.length;
    const [xi, yi] = polygon[i];
    const [xj, yj] = polygon[j];

    if (yi <= y) {
      if (yj > y) {
        if ((xj - xi) * (y - yi) - (x - xi) * (yj - yi) > 0) {
          windingNumber++;
        }
      }
    } else if (yj <= y) {
      if ((xj - xi) * (y - yi) - (x - xi) * (yj - yi) < 0) {
        windingNumber--;
      }
    }
  }

  return windingNumber !== 0;
};

function polygonClose<Point extends LocalPoint | GlobalPoint>(
  polygon: Point[],
) {
  return polygonIsClosed(polygon)
    ? polygon
    : ([...polygon, polygon[0]] as Polygon<Point>);
}

export function polygonIsClosed<Point extends LocalPoint | GlobalPoint>(
  polygon: readonly Point[],
  tolerance: number = PRECISION,
) {
  return pointsEqual(polygon[0], polygon[polygon.length - 1], tolerance);
}

/**
 * The signed area of a polygon via the shoelace formula. Positive when the
 * vertices wind counter-clockwise in a y-down coordinate system.
 *
 * The polygon may be given open or closed; a closing vertex
 */
export function polygonSignedArea<Point extends LocalPoint | GlobalPoint>(
  polygon: readonly Point[],
  tolerance: number = PRECISION,
): number {
  const pts = polygonIsClosed(polygon, tolerance)
    ? polygon.slice(0, -1)
    : polygon;
  let sum = 0;
  for (let i = 0, j = pts.length - 1; i < pts.length; j = i++) {
    sum += pts[j][0] * pts[i][1] - pts[i][0] * pts[j][1];
  }
  return sum / 2;
}

export function polygonArea<Point extends LocalPoint | GlobalPoint>(
  polygon: readonly Point[],
  tolerance: number = PRECISION,
): number {
  return Math.abs(polygonSignedArea(polygon, tolerance));
}

/**
 * The convex hull of a point set via Andrew's monotone chain.
 *
 * @returns The hull vertices in counter-clockwise order (y-down), without a
 * repeated closing vertex.
 */
export function convexHull<Point extends LocalPoint | GlobalPoint>(
  points: readonly Point[],
): Point[] {
  if (points.length < 3) {
    return [...points];
  }

  const sorted = [...points].sort((a, b) =>
    a[0] === b[0] ? a[1] - b[1] : a[0] - b[0],
  );

  // Cross product of OA x OB. Negative means the turn O->A->B is clockwise.
  const cross = (o: Point, a: Point, b: Point) =>
    (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);

  const half = (pts: Point[]) => {
    const chain: Point[] = [];
    for (const p of pts) {
      while (
        chain.length >= 2 &&
        cross(chain[chain.length - 2], chain[chain.length - 1], p) <= 0
      ) {
        chain.pop();
      }
      chain.push(p);
    }
    chain.pop(); // shared with the other half's first vertex
    return chain;
  };

  const hull = [...half(sorted), ...half([...sorted].reverse())];

  return hull.length >= 3 ? hull : [...points];
}

/**
 * Drop the points of a convex polygon that only contribute a shallow turn,
 * merging each run of near-collinear points into one.
 *
 * @param polygon A convex polygon, as returned by `convexHull`.
 * @param angleThreshold Minimum accumulated turn (radians) for a vertex to be
 * kept.
 */
export function simplifyConvexPolygon<Point extends LocalPoint | GlobalPoint>(
  polygon: readonly Point[],
  angleThreshold: number,
): Point[] {
  if (polygon.length < 3) {
    return [...polygon];
  }

  const turnAt = (i: number) => {
    const prev = polygon[(i - 1 + polygon.length) % polygon.length];
    const curr = polygon[i];
    const next = polygon[(i + 1) % polygon.length];
    const inAngle = Math.atan2(curr[1] - prev[1], curr[0] - prev[0]);
    const outAngle = Math.atan2(next[1] - curr[1], next[0] - curr[0]);
    return Math.abs(normalizeTurn(outAngle - inAngle));
  };

  // Walk the hull accumulating turn, emitting a vertex whenever enough of it
  // has built up. Starting at the sharpest vertex keeps the result stable: a
  // real corner always ends a run rather than being split across the seam.
  let start = 0;
  for (let i = 1; i < polygon.length; i++) {
    if (turnAt(i) > turnAt(start)) {
      start = i;
    }
  }

  const simplified: Point[] = [];
  let accumulated = 0;
  for (let k = 0; k < polygon.length; k++) {
    const i = (start + k) % polygon.length;
    accumulated += turnAt(i);
    if (accumulated >= angleThreshold) {
      simplified.push(polygon[i]);
      accumulated = 0;
    }
  }

  return simplified.length >= 3 ? simplified : [...polygon];
}

function normalizeTurn(angle: number): number {
  let a = angle;
  while (a > Math.PI) {
    a -= 2 * Math.PI;
  }
  while (a < -Math.PI) {
    a += 2 * Math.PI;
  }
  return a;
}