Typescript tests for Convex Hull Algorithm

convex-hull.test.ts

/** Typescript tests for https://www.nayuki.io/page/convex-hull-algorithm */
import { convexhull, Point } from "./convex-hull";

describe("convexhull", () => {
  /*---- Fixed test vectors ----*/

  test("empty", () => {
    const points: Point[] = [];
    const actual = convexhull.makeHull(points);
    const expected: Point[] = [];
    expect(actual).toEqual(expected);
  });

  test("one", () => {
    const points: Point[] = [{ x: 3, y: 1 }];
    const actual = convexhull.makeHull(points);
    const expected = points;
    expect(actual).toEqual(expected);
  });

  test("two duplicate", () => {
    const points: Point[] = [
      { x: 0, y: 0 },
      { x: 0, y: 0 },
    ];
    const actual = convexhull.makeHull(points);
    const expected: Point[] = [{ x: 0, y: 0 }];
    expect(actual).toEqual(expected);
  });

  test("two horizontal 0", () => {
    const points: Point[] = [
      { x: 2, y: 0 },
      { x: 5, y: 0 },
    ];
    const actual = convexhull.makeHull(points);
    const expected = points;
    expect(actual).toEqual(expected);
  });

  test("two horizontal 1", () => {
    const points: Point[] = [
      { x: -6, y: -3 },
      { x: -8, y: -3 },
    ];
    const actual = convexhull.makeHull(points);
    const expected: Point[] = [
      { x: -8, y: -3 },
      { x: -6, y: -3 },
    ];
    expect(actual).toEqual(expected);
  });

  test("two vertical 0", () => {
    const points: Point[] = [
      { x: 1, y: -4 },
      { x: 1, y: 4 },
    ];
    const actual = convexhull.makeHull(points);
    const expected = points;
    expect(actual).toEqual(expected);
  });

  test("two vertical 1", () => {
    const points: Point[] = [
      { x: -1, y: 2 },
      { x: -1, y: -3 },
    ];
    const actual = convexhull.makeHull(points);
    const expected: Point[] = [
      { x: -1, y: -3 },
      { x: -1, y: 2 },
    ];
    expect(actual).toEqual(expected);
  });

  test("two diagonal 0", () => {
    const points: Point[] = [
      { x: -2, y: -3 },
      { x: 2, y: 0 },
    ];
    const actual = convexhull.makeHull(points);
    const expected = points;
    expect(actual).toEqual(expected);
  });

  test("two diagonal 1", () => {
    const points: Point[] = [
      { x: -2, y: 3 },
      { x: 2, y: 0 },
    ];
    const actual = convexhull.makeHull(points);
    const expected = points;
    expect(actual).toEqual(expected);
  });

  test("rectangle", () => {
    const points: Point[] = [
      { x: -3, y: 2 },
      { x: 1, y: 2 },
      { x: 1, y: -4 },
      { x: -3, y: -4 },
    ];
    const actual = convexhull.makeHull(points);
    const expected: Point[] = [
      { x: -3, y: -4 },
      { x: -3, y: 2 },
      { x: 1, y: 2 },
      { x: 1, y: -4 },
    ];
    expect(actual).toEqual(expected);
  });

  /*---- Randomized testing ----*/

  test("horizontal randomly", () => {
    const TRIALS = 10000;
    for (let i = 0; i < TRIALS; i++) {
      const len = randomInt(30) + 1;
      const points: Point[] = [];
      if (Math.random() < 0.5) {
        const y = randomGaussian();
        for (let i = 0; i < len; i++) points.push({ x: randomGaussian(), y });
      } else {
        const y = randomInt(20) - 10;
        for (let i = 0; i < len; i++) points.push({ x: randomInt(30), y });
      }
      const actual = convexhull.makeHull(points);
      const expected: Point[] = [];
      const min = pointsMin(points);
      const max = pointsMax(points);
      expected.push(min);
      if (!pointsEqual(min, max)) {
        expected.push(max);
      }
      expect(actual).toEqual(expected);
    }
  });

  test("vertical randomly", () => {
    const TRIALS = 10000;
    for (let i = 0; i < TRIALS; i++) {
      const len = randomInt(30) + 1;
      const points: Point[] = [];
      if (Math.random() < 0.5) {
        const x = randomGaussian();
        for (let i = 0; i < len; i++) points.push({ x, y: randomGaussian() });
      } else {
        const x = randomInt(20) - 10;
        for (let i = 0; i < len; i++) points.push({ x, y: randomInt(30) });
      }
      const actual = convexhull.makeHull(points);
      const expected: Point[] = [];
      const min = pointsMin(points);
      const max = pointsMax(points);
      expected.push(min);
      if (!pointsEqual(min, max)) {
        expected.push(max);
      }
      expect(actual).toEqual(expected);
    }
  });

  test("vs naive randomly", () => {
    const TRIALS = 1000;
    for (let i = 0; i < TRIALS; i++) {
      const len = randomInt(100);
      const points: Point[] = [];
      if (Math.random() < 0.5) {
        for (let i = 0; i < len; i++) points.push({ x: randomGaussian(), y: randomGaussian() });
      } else {
        for (let i = 0; i < len; i++) points.push({ x: randomInt(10), y: randomInt(10) });
      }
      const actual = convexhull.makeHull(points);
      const expected = makeHullNaive(points);
      expect(actual).toEqual(expected);
    }
  });

  test("hull properties randomly", () => {
    const TRIALS = 1000;
    for (let i = 0; i < TRIALS; i++) {
      // Generate random points
      const len = randomInt(100);
      const points: Point[] = [];
      if (Math.random() < 0.5) {
        for (let i = 0; i < len; i++) points.push({ x: randomGaussian(), y: randomGaussian() });
      } else {
        for (let i = 0; i < len; i++) points.push({ x: randomInt(10), y: randomInt(10) });
      }

      // Compute hull and check properties
      const hull = convexhull.makeHull(points);
      expect(isPolygonConvex(hull)).toBe(true);
      for (const p of points) expect(isPointInConvexPolygon(hull, p)).toBe(true);

      // Add duplicate points and check new hull
      if (points.length > 0) {
        const dupe = randomInt(10) + 1;
        for (let j = 0; j < dupe; j++) points.push(points[randomInt(points.length)]);
        const nextHull = convexhull.makeHull(points);
        expect(hull).toEqual(nextHull);
      }
    }
  });

  function makeHullNaive(points: Point[]): Point[] {
    if (points.length <= 1) {
      return points.slice();
    }
    const result: Point[] = [];

    // Jarvis march / gift wrapping algorithm
    let point = pointsMin(points);
    do {
      result.push(point);
      let next = points[0];
      for (const p of points) {
        const ax = next.x - point.x;
        const ay = next.y - point.y;
        const bx = p.x - point.x;
        const by = p.y - point.y;
        const cross = ax * by - ay * bx;
        if (cross > 0 || (cross == 0 && bx * bx + by * by > ax * ax + ay * ay)) next = p;
      }
      point = next;
    } while (!pointsEqual(point, result[0]));
    return result;
  }

  function isPolygonConvex(points: Point[]): boolean {
    let signum = 0;
    for (let i = 0; i + 2 < points.length; i++) {
      const p = points[i + 0];
      const q = points[i + 1];
      const r = points[i + 2];
      const sign = Math.sign((q.x - p.x) * (r.y - q.y) - (q.y - p.y) * (r.x - q.x));
      if (sign == 0) continue;
      else if (signum == 0) signum = sign;
      else if (sign != signum) return false;
    }
    return true;
  }

  function isPointInConvexPolygon(polygon: Point[], point: Point): boolean {
    let signum = 0;
    for (let i = 0; i < polygon.length; i++) {
      const p = polygon[i];
      const q = polygon[(i + 1) % polygon.length];
      const sign = Math.sign((q.x - p.x) * (point.y - q.y) - (q.y - p.y) * (point.x - q.x));
      if (sign == 0) continue;
      else if (signum == 0) signum = sign;
      else if (sign != signum) return false;
    }
    return true;
  }

  function pointsEqual(a: Point, b: Point): boolean {
    return a.x === b.x && a.y === b.y;
  }

  function pointsMin(points: Point[]): Point {
    return points.reduce((a, b) => (a.x < b.x || (a.x === b.x && a.y < b.y) ? a : b));
  }

  function pointsMax(points: Point[]): Point {
    return points.reduce((a, b) => (a.x > b.x || (a.x === b.x && a.y > b.y) ? a : b));
  }

  function randomGaussian(): number {
    let u = 0;
    let v = 0;
    while (u === 0) u = Math.random();
    while (v === 0) v = Math.random();
    return Math.sqrt(-2.0 * Math.log(u)) * Math.cos(2.0 * Math.PI * v);
  }

  function randomInt(maxValue: number): number {
    return Math.floor(Math.random() * maxValue);
  }
});