Algorithms

Geometry

Rectangles, polygons and directions: what contains a point, what meets what, the order things are read in and the nearest one each way.

Behaviour

Rectangles

Two corners make the same rectangle whichever way round they are given, never of negative size

fc.assert(
  fc.property(point, point, (a, b) => {
    const one = rectFrom(a, b);
    return one.width >= 0 && one.height >= 0 && JSON.stringify(one) === JSON.stringify(rectFrom(b, a));
  }),
);

A rectangle contains its corners and its edges, and nothing beyond them

const box = { x: 0, y: 0, width: 10, height: 5 };
expect(rectContainsPoint(box, { x: 0, y: 0 })).toBe(true);
expect(rectContainsPoint(box, { x: 10, y: 5 })).toBe(true);
expect(rectContainsPoint(box, { x: 10.1, y: 5 })).toBe(false);
expect(rectContainsPoint(box, { x: 5, y: -0.1 })).toBe(false);

Rectangles that share a point intersect, and so do ones that only touch

const box = { x: 0, y: 0, width: 10, height: 10 };
expect(rectsIntersect(box, { x: 10, y: 10, width: 5, height: 5 })).toBe(true);
expect(rectsIntersect(box, { x: 11, y: 0, width: 5, height: 5 })).toBe(false);

Intersecting does not depend on which rectangle is asked of which

fc.assert(fc.property(rect, rect, (a, b) => rectsIntersect(a, b) === rectsIntersect(b, a)));

The union of rectangles contains each of them, and is the smallest that does

fc.assert(
  fc.property(fc.array(rect, { minLength: 1, maxLength: 6 }), (rects) => {
    const union = rectUnion(rects)!;
    const touches = (edge: (r: { x: number; y: number; width: number; height: number }) => number) =>
      rects.some((r) => edge(r) === edge(union));
    return (
      rects.every((r) => rectContains(union, r)) &&
      touches((r) => r.x) &&
      touches((r) => r.y) &&
      touches((r) => r.x + r.width) &&
      touches((r) => r.y + r.height)
    );
  }),
);

The union of no rectangles is none

expect(rectUnion([])).toBeNull();

A rectangle contains itself, and one it contains intersects it

fc.assert(
  fc.property(
    rect,
    rect,
    (a, b) => rectContains(a, a) && (!rectContains(a, b) || rectsIntersect(a, b)),
  ),
);

Moving a rectangle moves its corner and keeps its size; by no distance, it is the same rectangle

const box = { x: 1, y: 2, width: 3, height: 4 };
expect(rectTranslate(box, 10, -2)).toEqual({ x: 11, y: 0, width: 3, height: 4 });
expect(rectTranslate(box, 0, 0)).toBe(box);

Two rectangles are equal when corner and size are, whether or not they are the same object

const box = { x: 1, y: 2, width: 3, height: 4 };
expect(rectsEqual(box, { ...box })).toBe(true);
for (const side of ["x", "y", "width", "height"] as const) {
  expect(rectsEqual(box, { ...box, [side]: 9 })).toBe(false);
}

Polygons

A point within the corners is inside, and one beyond them is outside

expect(pointInPolygon({ x: 5, y: 5 }, square)).toBe(true);
expect(pointInPolygon({ x: 15, y: 5 }, square)).toBe(false);
expect(pointInPolygon({ x: 5, y: -1 }, square)).toBe(false);

The answer does not depend on which way round the corners are given

fc.assert(
  fc.property(
    fc.double({ min: -5, max: 15, noNaN: true }),
    fc.double({ min: -5, max: 15, noNaN: true }),
    (x, y) => pointInPolygon({ x, y }, square) === pointInPolygon({ x, y }, square.toReversed()),
  ),
);

A notch cut into a shape is outside it

// An L: the square with its top-right quarter removed.
const shape = [
  { x: 0, y: 0 },
  { x: 5, y: 0 },
  { x: 5, y: 5 },
  { x: 10, y: 5 },
  { x: 10, y: 10 },
  { x: 0, y: 10 },
];
expect(pointInPolygon({ x: 7, y: 2 }, shape)).toBe(false);
expect(pointInPolygon({ x: 7, y: 7 }, shape)).toBe(true);
expect(pointInPolygon({ x: 2, y: 2 }, shape)).toBe(true);

A triangle contains exactly the points on the inner side of all three edges

const triangle = [
  { x: 0, y: 0 },
  { x: 10, y: 0 },
  { x: 0, y: 10 },
];
fc.assert(
  fc.property(fc.integer({ min: -3, max: 13 }), fc.integer({ min: -3, max: 13 }), (x, y) => {
    // Points on an edge are left out: either answer is allowed there.
    fc.pre(x !== 0 && y !== 0 && x + y !== 10);
    return pointInPolygon({ x, y }, triangle) === (x > 0 && y > 0 && x + y < 10);
  }),
);

Fewer than three corners enclose nothing

expect(pointInPolygon({ x: 0, y: 0 }, [])).toBe(false);
expect(
  pointInPolygon({ x: 1, y: 1 }, [
    { x: 0, y: 0 },
    { x: 2, y: 2 },
  ]),
).toBe(false);

Reading order

Rectangles are read in rows from the top, and along each row from the left

//  [1]   [3]
//  [0]   [2]
expect([...readingOrder([at(0, 100), at(0, 0), at(100, 100), at(100, 0)])]).toEqual([1, 3, 0, 2]);

A rectangle whose top is above the middle of the one its row began with is in that row

// The second starts lower than the first but beside it; the third is below both.
expect([...readingOrder([at(100, 0), at(0, 19), at(50, 20)])]).toEqual([1, 0, 2]);

Right to left, each row is read from the right edge

expect([...readingOrder([at(0, 0), at(100, 0, 10), at(60, 0, 100), at(0, 100)], "rtl")]).toEqual([
  2, 1, 0, 3,
]);

Rectangles in the same place are read in the order they were given

expect([...readingOrder([at(5, 5), at(5, 5), at(5, 5)])]).toEqual([0, 1, 2]);
expect([...readingOrder([at(5, 5), at(5, 5), at(5, 5)], "rtl")]).toEqual([0, 1, 2]);

Every rectangle is read exactly once

fc.assert(
  fc.property(
    fc.array(rect, { maxLength: 40 }),
    fc.constantFrom("ltr" as const, "rtl" as const),
    (rects, way) => {
      const order = [...readingOrder(rects, way)];
      return order.length === rects.length && new Set(order).size === rects.length;
    },
  ),
);

In a column of rectangles one below another, each is read after the one above it

fc.assert(
  fc.property(
    fc.array(fc.integer({ min: 1, max: 50 }), { maxLength: 30 }),
    coordinate,
    (heights, x) => {
      let y = 0;
      const column = heights.map((height) => {
        const each = at(x, y, 40, height);
        y += height;
        return each;
      });
      return [...readingOrder(column)].every((each, place) => each === place);
    },
  ),
);

Ordering ten thousand rectangles compares each a few dozen times, not each with every other

const many = counted(
  Array.from({ length: 10_000 }, (_, index) =>
    at((index * 7919) % 5000, (index * 104_729) % 5000, 10, 10),
  ),
);
readingOrder(many.array);
// n log n, with room: far below the hundred million of n squared.
expect(many.accesses()).toBeLessThan(10_000 * Math.log2(10_000) * 8);

The nearest in a direction

From a rectangle, the nearest in a direction is the one whose middle is nearest among those within 45° of it

//    [1]
//
//  [0]        [2]   [3]
const rects = [at(0, 100), at(40, -40), at(200, 100), at(400, 100)];
expect(nearestInDirection(rects, 0, "right")).toBe(2);
expect(nearestInDirection(rects, 2, "right")).toBe(3);
expect(nearestInDirection(rects, 2, "left")).toBe(0);
expect(nearestInDirection(rects, 0, "up")).toBe(1);
expect(nearestInDirection(rects, 1, "down")).toBe(0);

With nothing within 45°, it is the nearest that lies that way at all; with nothing that way, there is none

// The second is far below and only a little to the right.
const rects = [at(0, 0), at(30, 500)];
expect(nearestInDirection(rects, 0, "right")).toBe(1);
expect(nearestInDirection(rects, 0, "left")).toBe(-1);
expect(nearestInDirection(rects, 0, "up")).toBe(-1);
expect(nearestInDirection([at(0, 0)], 0, "down")).toBe(-1);
expect(nearestInDirection([], 0, "down")).toBe(-1);

One within 45° is chosen over a nearer one that is not

// The second is nearer, but more below than to the right.
const rects = [at(0, 0), at(40, 60), at(200, 0)];
expect(nearestInDirection(rects, 0, "right")).toBe(2);
expect(nearestInDirection(rects, 0, "down")).toBe(1);

What is found always lies that way, and nothing within 45° is nearer; something is found whenever anything lies that way

fc.assert(
  fc.property(
    fc.array(rect, { minLength: 1, maxLength: 12 }),
    fc.nat(11),
    fc.constantFrom(...ways),
    (rects, pick, way) => {
      const from = pick % rects.length;
      const origin = middle(rects[from]!);
      const level = way === "left" || way === "right";
      const sign = way === "left" || way === "up" ? -1 : 1;
      const along = (index: number) =>
        ((level ? middle(rects[index]!).x : middle(rects[index]!).y) - (level ? origin.x : origin.y)) *
        sign;
      const aside = (index: number) =>
        Math.abs(
          (level ? middle(rects[index]!).y : middle(rects[index]!).x) - (level ? origin.y : origin.x),
        );
      const far = (index: number) => along(index) ** 2 + aside(index) ** 2;
      const found = nearestInDirection(rects, from, way);
      const others = rects.map((_, index) => index).filter((index) => index !== from);
      if (found === -1) return others.every((index) => !(along(index) > 0));
      if (!(along(found) > 0)) return false;
      const ahead = others.filter((index) => along(index) > 0 && aside(index) <= along(index));
      return (
        ahead.length === 0 ||
        (ahead.includes(found) && ahead.every((index) => far(index) >= far(found)))
      );
    },
  ),
);

React

Install

npx shadcn@latest add https://ui.publictheta.com/r/geometry.json

Source

src/algorithms/geometry.ts

/**
 * Points, rectangles and polygons, and the few questions asked of them
 * everywhere. A rectangle is its corner and its size, never negative in either:
 * a function that makes one makes it that way round.
 */
export interface Point {
  readonly x: number;
  readonly y: number;
}

export interface Size {
  readonly width: number;
  readonly height: number;
}

export interface Rect extends Point, Size {}

/** The rectangle with two points at opposite corners, whichever way round they are given. */
export function rectFrom(a: Point, b: Point): Rect {
  return {
    x: Math.min(a.x, b.x),
    y: Math.min(a.y, b.y),
    width: Math.abs(a.x - b.x),
    height: Math.abs(a.y - b.y),
  };
}

/** Whether a point is in a rectangle, its edges included. */
export function rectContainsPoint(rect: Rect, point: Point): boolean {
  return (
    point.x >= rect.x &&
    point.x <= rect.x + rect.width &&
    point.y >= rect.y &&
    point.y <= rect.y + rect.height
  );
}

/** Whether the whole of `inner` is within `outer`. */
export function rectContains(outer: Rect, inner: Rect): boolean {
  return (
    inner.x >= outer.x &&
    inner.y >= outer.y &&
    inner.x + inner.width <= outer.x + outer.width &&
    inner.y + inner.height <= outer.y + outer.height
  );
}

/** Whether two rectangles share any point; ones that only touch do. */
export function rectsIntersect(a: Rect, b: Rect): boolean {
  return a.x <= b.x + b.width && b.x <= a.x + a.width && a.y <= b.y + b.height && b.y <= a.y + a.height;
}

/** The smallest rectangle that holds every one given, or `null` for none. */
export function rectUnion(rects: Iterable<Rect>): Rect | null {
  let left = Infinity;
  let top = Infinity;
  let right = -Infinity;
  let bottom = -Infinity;
  for (const rect of rects) {
    left = Math.min(left, rect.x);
    top = Math.min(top, rect.y);
    right = Math.max(right, rect.x + rect.width);
    bottom = Math.max(bottom, rect.y + rect.height);
  }
  return right < left ? null : { x: left, y: top, width: right - left, height: bottom - top };
}

/** A rectangle moved by a distance. */
export function rectTranslate(rect: Rect, dx: number, dy: number): Rect {
  return dx === 0 && dy === 0
    ? rect
    : { x: rect.x + dx, y: rect.y + dy, width: rect.width, height: rect.height };
}

/** Whether two rectangles are the same rectangle: the same corner and the same size. */
export function rectsEqual(a: Rect, b: Rect): boolean {
  return a === b || (a.x === b.x && a.y === b.y && a.width === b.width && a.height === b.height);
}

/**
 * Whether a point lies inside a polygon, by counting the edges a ray from the
 * point crosses. The polygon is its corners in order, either way round; it need
 * not be convex. A point exactly on an edge may be reported either way.
 */
export function pointInPolygon(point: Point, polygon: readonly Point[]): boolean {
  let inside = false;
  for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i, i += 1) {
    const a = polygon[i]!;
    const b = polygon[j]!;
    if (a.y > point.y !== b.y > point.y && point.x < ((b.x - a.x) * (point.y - a.y)) / (b.y - a.y) + a.x) {
      inside = !inside;
    }
  }
  return inside;
}

/**
 * The order in which rectangles scattered on a plane are read: in rows from the
 * top, and along each row from the side reading starts at. A rectangle belongs
 * to a row when its top is above the middle of the rectangle the row began
 * with, so that things roughly side by side are read side by side. Returns the
 * rectangles' numbers. O(n log n).
 */
export function readingOrder(rects: ArrayLike<Rect>, direction: "ltr" | "rtl" = "ltr"): Uint32Array {
  // Sorted in place: the array is made here.
  // oxlint-disable-next-line unicorn/no-array-sort
  const order = Uint32Array.from({ length: rects.length }, (_, index) => index).sort(
    (a, b) => rects[a]!.y - rects[b]!.y || a - b,
  );
  // Along a row: by the edge reading starts from, and by number where two start together.
  const along =
    direction === "rtl"
      ? (a: number, b: number) => rects[b]!.x + rects[b]!.width - (rects[a]!.x + rects[a]!.width) || a - b
      : (a: number, b: number) => rects[a]!.x - rects[b]!.x || a - b;
  let start = 0;
  while (start < order.length) {
    const first = rects[order[start]!]!;
    const limit = first.y + first.height / 2;
    let end = start + 1;
    while (end < order.length && rects[order[end]!]!.y < limit) end += 1;
    // A view of the row's part of the array, sorted where it lies.
    // oxlint-disable-next-line unicorn/no-array-sort
    order.subarray(start, end).sort(along);
    start = end;
  }
  return order;
}

export type Direction = "left" | "right" | "up" | "down";

/**
 * Where one would go from a rectangle in a direction, among others scattered on
 * a plane: the nearest of those whose middle lies within 45° of that direction
 * from its own; failing any, the nearest of those whose middle lies that way at
 * all. Distances are between middles. Returns the rectangle's number, or -1
 * when nothing lies that way. O(n).
 */
export function nearestInDirection(rects: ArrayLike<Rect>, from: number, direction: Direction): number {
  const origin = rects[from];
  if (origin === undefined) return -1;
  const x = origin.x + origin.width / 2;
  const y = origin.y + origin.height / 2;
  const level = direction === "left" || direction === "right";
  const sign = direction === "left" || direction === "up" ? -1 : 1;
  let best = -1;
  let bestDistance = Infinity;
  let bestAhead = false;
  for (let index = 0; index < rects.length; index += 1) {
    if (index === from) continue;
    const rect = rects[index]!;
    const dx = rect.x + rect.width / 2 - x;
    const dy = rect.y + rect.height / 2 - y;
    const along = (level ? dx : dy) * sign;
    if (!(along > 0)) continue;
    const ahead = Math.abs(level ? dy : dx) <= along;
    const distance = dx * dx + dy * dy;
    if (ahead === bestAhead ? distance < bestDistance : ahead) {
      best = index;
      bestDistance = distance;
      bestAhead = ahead;
    }
  }
  return best;
}