From 6ec259a0e71174651bae95d4628138bf6fd68742 Mon Sep 17 00:00:00 2001 From: kj_sh604 Date: Sun, 15 Mar 2026 16:19:35 -0400 Subject: refactor: packages/ --- packages/math/CHANGELOG.md | 0 packages/math/README.md | 21 ++++ packages/math/angle.ts | 50 ++++++++ packages/math/curve.test.ts | 101 +++++++++++++++ packages/math/curve.ts | 282 ++++++++++++++++++++++++++++++++++++++++++ packages/math/ellipse.test.ts | 126 +++++++++++++++++++ packages/math/ellipse.ts | 230 ++++++++++++++++++++++++++++++++++ packages/math/global.d.ts | 3 + packages/math/index.ts | 12 ++ packages/math/line.test.ts | 31 +++++ packages/math/line.ts | 38 ++++++ packages/math/package.json | 59 +++++++++ packages/math/point.test.ts | 24 ++++ packages/math/point.ts | 231 ++++++++++++++++++++++++++++++++++ packages/math/polygon.ts | 72 +++++++++++ packages/math/range.test.ts | 51 ++++++++ packages/math/range.ts | 82 ++++++++++++ packages/math/rectangle.ts | 23 ++++ packages/math/segment.test.ts | 21 ++++ packages/math/segment.ts | 174 ++++++++++++++++++++++++++ packages/math/triangle.ts | 28 +++++ packages/math/tsconfig.json | 24 ++++ packages/math/types.ts | 140 +++++++++++++++++++++ packages/math/utils.ts | 33 +++++ packages/math/vector.test.ts | 12 ++ packages/math/vector.ts | 145 ++++++++++++++++++++++ 26 files changed, 2013 insertions(+) create mode 100644 packages/math/CHANGELOG.md create mode 100644 packages/math/README.md create mode 100644 packages/math/angle.ts create mode 100644 packages/math/curve.test.ts create mode 100644 packages/math/curve.ts create mode 100644 packages/math/ellipse.test.ts create mode 100644 packages/math/ellipse.ts create mode 100644 packages/math/global.d.ts create mode 100644 packages/math/index.ts create mode 100644 packages/math/line.test.ts create mode 100644 packages/math/line.ts create mode 100644 packages/math/package.json create mode 100644 packages/math/point.test.ts create mode 100644 packages/math/point.ts create mode 100644 packages/math/polygon.ts create mode 100644 packages/math/range.test.ts create mode 100644 packages/math/range.ts create mode 100644 packages/math/rectangle.ts create mode 100644 packages/math/segment.test.ts create mode 100644 packages/math/segment.ts create mode 100644 packages/math/triangle.ts create mode 100644 packages/math/tsconfig.json create mode 100644 packages/math/types.ts create mode 100644 packages/math/utils.ts create mode 100644 packages/math/vector.test.ts create mode 100644 packages/math/vector.ts (limited to 'packages/math') diff --git a/packages/math/CHANGELOG.md b/packages/math/CHANGELOG.md new file mode 100644 index 0000000..e69de29 diff --git a/packages/math/README.md b/packages/math/README.md new file mode 100644 index 0000000..eaa1630 --- /dev/null +++ b/packages/math/README.md @@ -0,0 +1,21 @@ +# @excalidraw/math + +## Install + +```bash +npm install @excalidraw/math +``` + +If you prefer Yarn over npm, use this command to install the Excalidraw utils package: + +```bash +yarn add @excalidraw/math +``` + +With PNPM, similarly install the package with this command: + +```bash +pnpm add @excalidraw/math +``` + +## API diff --git a/packages/math/angle.ts b/packages/math/angle.ts new file mode 100644 index 0000000..8d473cf --- /dev/null +++ b/packages/math/angle.ts @@ -0,0 +1,50 @@ +import type { + Degrees, + GlobalPoint, + LocalPoint, + PolarCoords, + Radians, +} from "./types"; +import { PRECISION } from "./utils"; + +// TODO: Simplify with modulo and fix for angles beyond 4*Math.PI and - 4*Math.PI +export const normalizeRadians = (angle: Radians): Radians => { + if (angle < 0) { + return (angle + 2 * Math.PI) as Radians; + } + if (angle >= 2 * Math.PI) { + return (angle - 2 * Math.PI) as Radians; + } + return angle; +}; + +/** + * Return the polar coordinates for the given cartesian point represented by + * (x, y) for the center point 0,0 where the first number returned is the radius, + * the second is the angle in radians. + */ +export const cartesian2Polar =

([ + x, + y, +]: P): PolarCoords => [ + Math.hypot(x, y), + normalizeRadians(Math.atan2(y, x) as Radians), +]; + +export function degreesToRadians(degrees: Degrees): Radians { + return ((degrees * Math.PI) / 180) as Radians; +} + +export function radiansToDegrees(degrees: Radians): Degrees { + return ((degrees * 180) / Math.PI) as Degrees; +} + +/** + * Determines if the provided angle is a right angle. + * + * @param rads The angle to measure + * @returns TRUE if the provided angle is a right angle + */ +export function isRightAngleRads(rads: Radians): boolean { + return Math.abs(Math.sin(2 * rads)) < PRECISION; +} diff --git a/packages/math/curve.test.ts b/packages/math/curve.test.ts new file mode 100644 index 0000000..94670d7 --- /dev/null +++ b/packages/math/curve.test.ts @@ -0,0 +1,101 @@ +import "../utils/test-utils"; +import { + curve, + curveClosestPoint, + curveIntersectLineSegment, + curvePointDistance, +} from "./curve"; +import { pointFrom } from "./point"; +import { lineSegment } from "./segment"; + +describe("Math curve", () => { + describe("line segment intersection", () => { + it("point is found when control points are the same", () => { + const c = curve( + pointFrom(100, 0), + pointFrom(100, 100), + pointFrom(100, 100), + pointFrom(0, 100), + ); + const l = lineSegment(pointFrom(0, 0), pointFrom(200, 200)); + + expect(curveIntersectLineSegment(c, l)).toCloselyEqualPoints([ + [87.5, 87.5], + ]); + }); + + it("point is found when control points aren't the same", () => { + const c = curve( + pointFrom(100, 0), + pointFrom(100, 60), + pointFrom(60, 100), + pointFrom(0, 100), + ); + const l = lineSegment(pointFrom(0, 0), pointFrom(200, 200)); + + expect(curveIntersectLineSegment(c, l)).toCloselyEqualPoints([ + [72.5, 72.5], + ]); + }); + + it("points are found when curve is sliced at 3 points", () => { + const c = curve( + pointFrom(-50, -50), + pointFrom(10, -50), + pointFrom(10, 50), + pointFrom(50, 50), + ); + const l = lineSegment(pointFrom(0, 112.5), pointFrom(90, 0)); + + expect(curveIntersectLineSegment(c, l)).toCloselyEqualPoints([[50, 50]]); + }); + + it("can be detected where the determinant is overly precise", () => { + const c = curve( + pointFrom(41.028864759926016, 12.226249068355052), + pointFrom(41.028864759926016, 33.55958240168839), + pointFrom(30.362198093259348, 44.22624906835505), + pointFrom(9.028864759926016, 44.22624906835505), + ); + const l = lineSegment( + pointFrom(-82.30963544324186, -41.19949363038283), + + pointFrom(188.2149592542487, 134.75505940984908), + ); + + expect(curveIntersectLineSegment(c, l)).toCloselyEqualPoints([ + [34.4, 34.71], + ]); + }); + }); + + describe("point closest to other", () => { + it("point can be found", () => { + const c = curve( + pointFrom(-50, -50), + pointFrom(10, -50), + pointFrom(10, 50), + pointFrom(50, 50), + ); + const p = pointFrom(0, 0); + + expect([curveClosestPoint(c, p)]).toCloselyEqualPoints([ + [5.965462100367372, -3.04104878946646], + ]); + }); + }); + + describe("point shortest distance", () => { + it("can be determined", () => { + const c = curve( + pointFrom(-50, -50), + pointFrom(10, -50), + pointFrom(10, 50), + pointFrom(50, 50), + ); + const p = pointFrom(0, 0); + + expect(curvePointDistance(c, p)).toBeCloseTo(6.695873043213627); + }); + }); +}); diff --git a/packages/math/curve.ts b/packages/math/curve.ts new file mode 100644 index 0000000..9b275ce --- /dev/null +++ b/packages/math/curve.ts @@ -0,0 +1,282 @@ +import type { Bounds } from "../excalidraw/element/bounds"; +import { isPoint, pointDistance, pointFrom } from "./point"; +import { rectangle, rectangleIntersectLineSegment } from "./rectangle"; +import type { Curve, GlobalPoint, LineSegment, LocalPoint } from "./types"; + +/** + * + * @param a + * @param b + * @param c + * @param d + * @returns + */ +export function curve( + a: Point, + b: Point, + c: Point, + d: Point, +) { + return [a, b, c, d] as Curve; +} + +function gradient( + f: (t: number, s: number) => number, + t0: number, + s0: number, + delta: number = 1e-6, +): number[] { + return [ + (f(t0 + delta, s0) - f(t0 - delta, s0)) / (2 * delta), + (f(t0, s0 + delta) - f(t0, s0 - delta)) / (2 * delta), + ]; +} + +function solve( + f: (t: number, s: number) => [number, number], + t0: number, + s0: number, + tolerance: number = 1e-3, + iterLimit: number = 10, +): number[] | null { + let error = Infinity; + let iter = 0; + + while (error >= tolerance) { + if (iter >= iterLimit) { + return null; + } + + const y0 = f(t0, s0); + const jacobian = [ + gradient((t, s) => f(t, s)[0], t0, s0), + gradient((t, s) => f(t, s)[1], t0, s0), + ]; + const b = [[-y0[0]], [-y0[1]]]; + const det = + jacobian[0][0] * jacobian[1][1] - jacobian[0][1] * jacobian[1][0]; + + if (det === 0) { + return null; + } + + const iJ = [ + [jacobian[1][1] / det, -jacobian[0][1] / det], + [-jacobian[1][0] / det, jacobian[0][0] / det], + ]; + const h = [ + [iJ[0][0] * b[0][0] + iJ[0][1] * b[1][0]], + [iJ[1][0] * b[0][0] + iJ[1][1] * b[1][0]], + ]; + + t0 = t0 + h[0][0]; + s0 = s0 + h[1][0]; + + const [tErr, sErr] = f(t0, s0); + error = Math.max(Math.abs(tErr), Math.abs(sErr)); + iter += 1; + } + + return [t0, s0]; +} + +const bezierEquation = ( + c: Curve, + t: number, +) => + pointFrom( + (1 - t) ** 3 * c[0][0] + + 3 * (1 - t) ** 2 * t * c[1][0] + + 3 * (1 - t) * t ** 2 * c[2][0] + + t ** 3 * c[3][0], + (1 - t) ** 3 * c[0][1] + + 3 * (1 - t) ** 2 * t * c[1][1] + + 3 * (1 - t) * t ** 2 * c[2][1] + + t ** 3 * c[3][1], + ); + +/** + * Computes the intersection between a cubic spline and a line segment. + */ +export function curveIntersectLineSegment< + Point extends GlobalPoint | LocalPoint, +>(c: Curve, l: LineSegment): Point[] { + // Optimize by doing a cheap bounding box check first + const bounds = curveBounds(c); + if ( + rectangleIntersectLineSegment( + rectangle( + pointFrom(bounds[0], bounds[1]), + pointFrom(bounds[2], bounds[3]), + ), + l, + ).length === 0 + ) { + return []; + } + + const line = (s: number) => + pointFrom( + l[0][0] + s * (l[1][0] - l[0][0]), + l[0][1] + s * (l[1][1] - l[0][1]), + ); + + const initial_guesses: [number, number][] = [ + [0.5, 0], + [0.2, 0], + [0.8, 0], + ]; + + const calculate = ([t0, s0]: [number, number]) => { + const solution = solve( + (t: number, s: number) => { + const bezier_point = bezierEquation(c, t); + const line_point = line(s); + + return [ + bezier_point[0] - line_point[0], + bezier_point[1] - line_point[1], + ]; + }, + t0, + s0, + ); + + if (!solution) { + return null; + } + + const [t, s] = solution; + + if (t < 0 || t > 1 || s < 0 || s > 1) { + return null; + } + + return bezierEquation(c, t); + }; + + let solution = calculate(initial_guesses[0]); + if (solution) { + return [solution]; + } + + solution = calculate(initial_guesses[1]); + if (solution) { + return [solution]; + } + + solution = calculate(initial_guesses[2]); + if (solution) { + return [solution]; + } + + return []; +} + +/** + * Finds the closest point on the Bezier curve from another point + * + * @param x + * @param y + * @param P0 + * @param P1 + * @param P2 + * @param P3 + * @param tolerance + * @param maxLevel + * @returns + */ +export function curveClosestPoint( + c: Curve, + p: Point, + tolerance: number = 1e-3, +): Point | null { + const localMinimum = ( + min: number, + max: number, + f: (t: number) => number, + e: number = tolerance, + ) => { + let m = min; + let n = max; + let k; + + while (n - m > e) { + k = (n + m) / 2; + if (f(k - e) < f(k + e)) { + n = k; + } else { + m = k; + } + } + + return k; + }; + + const maxSteps = 30; + let closestStep = 0; + for (let min = Infinity, step = 0; step < maxSteps; step++) { + const d = pointDistance(p, bezierEquation(c, step / maxSteps)); + if (d < min) { + min = d; + closestStep = step; + } + } + + const t0 = Math.max((closestStep - 1) / maxSteps, 0); + const t1 = Math.min((closestStep + 1) / maxSteps, 1); + const solution = localMinimum(t0, t1, (t) => + pointDistance(p, bezierEquation(c, t)), + ); + + if (!solution) { + return null; + } + + return bezierEquation(c, solution); +} + +/** + * Determines the distance between a point and the closest point on the + * Bezier curve. + * + * @param c The curve to test + * @param p The point to measure from + */ +export function curvePointDistance( + c: Curve, + p: Point, +) { + const closest = curveClosestPoint(c, p); + + if (!closest) { + return 0; + } + + return pointDistance(p, closest); +} + +/** + * Determines if the parameter is a Curve + */ +export function isCurve

( + v: unknown, +): v is Curve

{ + return ( + Array.isArray(v) && + v.length === 4 && + isPoint(v[0]) && + isPoint(v[1]) && + isPoint(v[2]) && + isPoint(v[3]) + ); +} + +function curveBounds( + c: Curve, +): Bounds { + const [P0, P1, P2, P3] = c; + const x = [P0[0], P1[0], P2[0], P3[0]]; + const y = [P0[1], P1[1], P2[1], P3[1]]; + return [Math.min(...x), Math.min(...y), Math.max(...x), Math.max(...y)]; +} diff --git a/packages/math/ellipse.test.ts b/packages/math/ellipse.test.ts new file mode 100644 index 0000000..507cc5a --- /dev/null +++ b/packages/math/ellipse.test.ts @@ -0,0 +1,126 @@ +import { + ellipse, + ellipseSegmentInterceptPoints, + ellipseIncludesPoint, + ellipseTouchesPoint, + ellipseLineIntersectionPoints, +} from "./ellipse"; +import { line } from "./line"; +import { pointFrom } from "./point"; +import { lineSegment } from "./segment"; +import type { Ellipse, GlobalPoint } from "./types"; + +describe("point and ellipse", () => { + it("point on ellipse", () => { + const target: Ellipse = ellipse(pointFrom(1, 2), 2, 1); + [ + pointFrom(1, 3), + pointFrom(1, 1), + pointFrom(3, 2), + pointFrom(-1, 2), + ].forEach((p) => { + expect(ellipseTouchesPoint(p, target)).toBe(true); + }); + expect(ellipseTouchesPoint(pointFrom(-0.4, 2.7), target, 0.1)).toBe(true); + expect(ellipseTouchesPoint(pointFrom(-0.4, 2.71), target, 0.01)).toBe(true); + + expect(ellipseTouchesPoint(pointFrom(2.4, 2.7), target, 0.1)).toBe(true); + expect(ellipseTouchesPoint(pointFrom(2.4, 2.71), target, 0.01)).toBe(true); + + expect(ellipseTouchesPoint(pointFrom(2, 1.14), target, 0.1)).toBe(true); + expect(ellipseTouchesPoint(pointFrom(2, 1.14), target, 0.01)).toBe(true); + + expect(ellipseTouchesPoint(pointFrom(0, 1.14), target, 0.1)).toBe(true); + expect(ellipseTouchesPoint(pointFrom(0, 1.14), target, 0.01)).toBe(true); + + expect(ellipseTouchesPoint(pointFrom(0, 2.8), target)).toBe(false); + expect(ellipseTouchesPoint(pointFrom(2, 1.2), target)).toBe(false); + }); + + it("point in ellipse", () => { + const target: Ellipse = ellipse(pointFrom(0, 0), 2, 1); + [ + pointFrom(0, 1), + pointFrom(0, -1), + pointFrom(2, 0), + pointFrom(-2, 0), + ].forEach((p) => { + expect(ellipseIncludesPoint(p, target)).toBe(true); + }); + + expect(ellipseIncludesPoint(pointFrom(-1, 0.8), target)).toBe(true); + expect(ellipseIncludesPoint(pointFrom(1, -0.8), target)).toBe(true); + + // Point on outline + expect(ellipseIncludesPoint(pointFrom(2, 0), target)).toBe(true); + + expect(ellipseIncludesPoint(pointFrom(-1, 1), target)).toBe(false); + expect(ellipseIncludesPoint(pointFrom(-1.4, 0.8), target)).toBe(false); + }); +}); + +describe("segment and ellipse", () => { + it("detects outside segment", () => { + const e = ellipse(pointFrom(0, 0), 2, 2); + + expect( + ellipseSegmentInterceptPoints( + e, + lineSegment(pointFrom(-100, 0), pointFrom(-10, 0)), + ), + ).toEqual([]); + expect( + ellipseSegmentInterceptPoints( + e, + lineSegment(pointFrom(-10, 0), pointFrom(10, 0)), + ), + ).toEqual([pointFrom(-2, 0), pointFrom(2, 0)]); + expect( + ellipseSegmentInterceptPoints( + e, + lineSegment(pointFrom(-10, -2), pointFrom(10, -2)), + ), + ).toEqual([pointFrom(0, -2)]); + expect( + ellipseSegmentInterceptPoints( + e, + lineSegment(pointFrom(0, -1), pointFrom(0, 1)), + ), + ).toEqual([]); + }); +}); + +describe("line and ellipse", () => { + const e = ellipse(pointFrom(0, 0), 2, 2); + + it("detects outside line", () => { + expect( + ellipseLineIntersectionPoints( + e, + line(pointFrom(-10, -10), pointFrom(10, -10)), + ), + ).toEqual([]); + }); + it("detects line intersecting ellipse", () => { + expect( + ellipseLineIntersectionPoints( + e, + line(pointFrom(0, -1), pointFrom(0, 1)), + ), + ).toEqual([pointFrom(0, 2), pointFrom(0, -2)]); + expect( + ellipseLineIntersectionPoints( + e, + line(pointFrom(-100, 0), pointFrom(-10, 0)), + ).map(([x, y]) => pointFrom(Math.round(x), Math.round(y))), + ).toEqual([pointFrom(2, 0), pointFrom(-2, 0)]); + }); + it("detects line touching ellipse", () => { + expect( + ellipseLineIntersectionPoints( + e, + line(pointFrom(-2, -2), pointFrom(2, -2)), + ), + ).toEqual([pointFrom(0, -2)]); + }); +}); diff --git a/packages/math/ellipse.ts b/packages/math/ellipse.ts new file mode 100644 index 0000000..c32def0 --- /dev/null +++ b/packages/math/ellipse.ts @@ -0,0 +1,230 @@ +import { + pointFrom, + pointDistance, + pointFromVector, + pointsEqual, +} from "./point"; +import type { + Ellipse, + GlobalPoint, + Line, + LineSegment, + LocalPoint, +} from "./types"; +import { PRECISION } from "./utils"; +import { + vector, + vectorAdd, + vectorDot, + vectorFromPoint, + vectorScale, +} from "./vector"; + +/** + * Construct an Ellipse object from the parameters + * + * @param center The center of the ellipse + * @param angle The slanting of the ellipse in radians + * @param halfWidth Half of the width of a non-slanted version of the ellipse + * @param halfHeight Half of the height of a non-slanted version of the ellipse + * @returns The constructed Ellipse object + */ +export function ellipse( + center: Point, + halfWidth: number, + halfHeight: number, +): Ellipse { + return { + center, + halfWidth, + halfHeight, + } as Ellipse; +} + +/** + * Determines if a point is inside or on the ellipse outline + * + * @param p The point to test + * @param ellipse The ellipse to compare against + * @returns TRUE if the point is inside or on the outline of the ellipse + */ +export const ellipseIncludesPoint = ( + p: Point, + ellipse: Ellipse, +) => { + const { center, halfWidth, halfHeight } = ellipse; + const normalizedX = (p[0] - center[0]) / halfWidth; + const normalizedY = (p[1] - center[1]) / halfHeight; + + return normalizedX * normalizedX + normalizedY * normalizedY <= 1; +}; + +/** + * Tests whether a point lies on the outline of the ellipse within a given + * tolerance + * + * @param point The point to test + * @param ellipse The ellipse to compare against + * @param threshold The distance to consider a point close enough to be "on" the outline + * @returns TRUE if the point is on the ellise outline + */ +export const ellipseTouchesPoint = ( + point: Point, + ellipse: Ellipse, + threshold = PRECISION, +) => { + return ellipseDistanceFromPoint(point, ellipse) <= threshold; +}; + +/** + * Determine the shortest euclidean distance from a point to the + * outline of the ellipse + * + * @param p The point to consider + * @param ellipse The ellipse to calculate the distance to + * @returns The eucledian distance + */ +export const ellipseDistanceFromPoint = < + Point extends GlobalPoint | LocalPoint, +>( + p: Point, + ellipse: Ellipse, +): number => { + const { halfWidth, halfHeight, center } = ellipse; + const a = halfWidth; + const b = halfHeight; + const translatedPoint = vectorAdd( + vectorFromPoint(p), + vectorScale(vectorFromPoint(center), -1), + ); + + const px = Math.abs(translatedPoint[0]); + const py = Math.abs(translatedPoint[1]); + + let tx = 0.707; + let ty = 0.707; + + for (let i = 0; i < 3; i++) { + const x = a * tx; + const y = b * ty; + + const ex = ((a * a - b * b) * tx ** 3) / a; + const ey = ((b * b - a * a) * ty ** 3) / b; + + const rx = x - ex; + const ry = y - ey; + + const qx = px - ex; + const qy = py - ey; + + const r = Math.hypot(ry, rx); + const q = Math.hypot(qy, qx); + + tx = Math.min(1, Math.max(0, ((qx * r) / q + ex) / a)); + ty = Math.min(1, Math.max(0, ((qy * r) / q + ey) / b)); + const t = Math.hypot(ty, tx); + tx /= t; + ty /= t; + } + + const [minX, minY] = [ + a * tx * Math.sign(translatedPoint[0]), + b * ty * Math.sign(translatedPoint[1]), + ]; + + return pointDistance(pointFromVector(translatedPoint), pointFrom(minX, minY)); +}; + +/** + * Calculate a maximum of two intercept points for a line going throug an + * ellipse. + */ +export function ellipseSegmentInterceptPoints< + Point extends GlobalPoint | LocalPoint, +>(e: Readonly>, s: Readonly>): Point[] { + const rx = e.halfWidth; + const ry = e.halfHeight; + + const dir = vectorFromPoint(s[1], s[0]); + const diff = vector(s[0][0] - e.center[0], s[0][1] - e.center[1]); + const mDir = vector(dir[0] / (rx * rx), dir[1] / (ry * ry)); + const mDiff = vector(diff[0] / (rx * rx), diff[1] / (ry * ry)); + + const a = vectorDot(dir, mDir); + const b = vectorDot(dir, mDiff); + const c = vectorDot(diff, mDiff) - 1.0; + const d = b * b - a * c; + + const intersections: Point[] = []; + + if (d > 0) { + const t_a = (-b - Math.sqrt(d)) / a; + const t_b = (-b + Math.sqrt(d)) / a; + + if (0 <= t_a && t_a <= 1) { + intersections.push( + pointFrom( + s[0][0] + (s[1][0] - s[0][0]) * t_a, + s[0][1] + (s[1][1] - s[0][1]) * t_a, + ), + ); + } + + if (0 <= t_b && t_b <= 1) { + intersections.push( + pointFrom( + s[0][0] + (s[1][0] - s[0][0]) * t_b, + s[0][1] + (s[1][1] - s[0][1]) * t_b, + ), + ); + } + } else if (d === 0) { + const t = -b / a; + if (0 <= t && t <= 1) { + intersections.push( + pointFrom( + s[0][0] + (s[1][0] - s[0][0]) * t, + s[0][1] + (s[1][1] - s[0][1]) * t, + ), + ); + } + } + + return intersections; +} + +export function ellipseLineIntersectionPoints< + Point extends GlobalPoint | LocalPoint, +>( + { center, halfWidth, halfHeight }: Ellipse, + [g, h]: Line, +): Point[] { + const [cx, cy] = center; + const x1 = g[0] - cx; + const y1 = g[1] - cy; + const x2 = h[0] - cx; + const y2 = h[1] - cy; + const a = + Math.pow(x2 - x1, 2) / Math.pow(halfWidth, 2) + + Math.pow(y2 - y1, 2) / Math.pow(halfHeight, 2); + const b = + 2 * + ((x1 * (x2 - x1)) / Math.pow(halfWidth, 2) + + (y1 * (y2 - y1)) / Math.pow(halfHeight, 2)); + const c = + Math.pow(x1, 2) / Math.pow(halfWidth, 2) + + Math.pow(y1, 2) / Math.pow(halfHeight, 2) - + 1; + const t1 = (-b + Math.sqrt(Math.pow(b, 2) - 4 * a * c)) / (2 * a); + const t2 = (-b - Math.sqrt(Math.pow(b, 2) - 4 * a * c)) / (2 * a); + const candidates = [ + pointFrom(x1 + t1 * (x2 - x1) + cx, y1 + t1 * (y2 - y1) + cy), + pointFrom(x1 + t2 * (x2 - x1) + cx, y1 + t2 * (y2 - y1) + cy), + ].filter((p) => !isNaN(p[0]) && !isNaN(p[1])); + + if (candidates.length === 2 && pointsEqual(candidates[0], candidates[1])) { + return [candidates[0]]; + } + + return candidates; +} diff --git a/packages/math/global.d.ts b/packages/math/global.d.ts new file mode 100644 index 0000000..16ade7a --- /dev/null +++ b/packages/math/global.d.ts @@ -0,0 +1,3 @@ +/// +import "@excalidraw/excalidraw/global"; +import "@excalidraw/excalidraw/css"; diff --git a/packages/math/index.ts b/packages/math/index.ts new file mode 100644 index 0000000..d00ab46 --- /dev/null +++ b/packages/math/index.ts @@ -0,0 +1,12 @@ +export * from "./angle"; +export * from "./curve"; +export * from "./line"; +export * from "./point"; +export * from "./polygon"; +export * from "./range"; +export * from "./rectangle"; +export * from "./segment"; +export * from "./triangle"; +export * from "./types"; +export * from "./vector"; +export * from "./utils"; diff --git a/packages/math/line.test.ts b/packages/math/line.test.ts new file mode 100644 index 0000000..0e6bb1c --- /dev/null +++ b/packages/math/line.test.ts @@ -0,0 +1,31 @@ +import { line, linesIntersectAt } from "./line"; +import { pointFrom } from "./point"; + +describe("line-line intersections", () => { + it("should correctly detect intersection at origin", () => { + expect( + linesIntersectAt( + line(pointFrom(-5, -5), pointFrom(5, 5)), + line(pointFrom(5, -5), pointFrom(-5, 5)), + ), + ).toEqual(pointFrom(0, 0)); + }); + + it("should correctly detect intersection at non-origin", () => { + expect( + linesIntersectAt( + line(pointFrom(0, 0), pointFrom(10, 10)), + line(pointFrom(10, 0), pointFrom(0, 10)), + ), + ).toEqual(pointFrom(5, 5)); + }); + + it("should correctly detect parallel lines", () => { + expect( + linesIntersectAt( + line(pointFrom(0, 0), pointFrom(0, 10)), + line(pointFrom(10, 0), pointFrom(10, 10)), + ), + ).toBe(null); + }); +}); diff --git a/packages/math/line.ts b/packages/math/line.ts new file mode 100644 index 0000000..bcb4f6d --- /dev/null +++ b/packages/math/line.ts @@ -0,0 +1,38 @@ +import { pointFrom } from "./point"; +import type { GlobalPoint, Line, LocalPoint } from "./types"; + +/** + * Create a line from two points. + * + * @param points The two points lying on the line + * @returns The line on which the points lie + */ +export function line

(a: P, b: P): Line

{ + return [a, b] as Line

; +} + +/** + * Determines the intersection point (unless the lines are parallel) of two + * lines + * + * @param a + * @param b + * @returns + */ +export function linesIntersectAt( + a: Line, + b: Line, +): Point | null { + const A1 = a[1][1] - a[0][1]; + const B1 = a[0][0] - a[1][0]; + const A2 = b[1][1] - b[0][1]; + const B2 = b[0][0] - b[1][0]; + const D = A1 * B2 - A2 * B1; + if (D !== 0) { + const C1 = A1 * a[0][0] + B1 * a[0][1]; + const C2 = A2 * b[0][0] + B2 * b[0][1]; + return pointFrom((C1 * B2 - C2 * B1) / D, (A1 * C2 - A2 * C1) / D); + } + + return null; +} diff --git a/packages/math/package.json b/packages/math/package.json new file mode 100644 index 0000000..a60c971 --- /dev/null +++ b/packages/math/package.json @@ -0,0 +1,59 @@ +{ + "name": "@excalidraw/math", + "version": "0.1.0", + "type": "module", + "types": "./dist/types/math/index.d.ts", + "main": "./dist/prod/index.js", + "module": "./dist/prod/index.js", + "exports": { + ".": { + "development": "./dist/dev/index.js", + "production": "./dist/prod/index.js", + "default": "./dist/prod/index.js" + }, + "./*": { + "types": "./../math/dist/types/math/*" + } + }, + "files": [ + "dist/*" + ], + "description": "Excalidraw math functions", + "publishConfig": { + "access": "public" + }, + "license": "MIT", + "keywords": [ + "excalidraw", + "excalidraw-math", + "math", + "vector", + "algebra", + "2d" + ], + "browserslist": { + "production": [ + ">0.2%", + "not dead", + "not ie <= 11", + "not op_mini all", + "not safari < 12", + "not kaios <= 2.5", + "not edge < 79", + "not chrome < 70", + "not and_uc < 13", + "not samsung < 10" + ], + "development": [ + "last 1 chrome version", + "last 1 firefox version", + "last 1 safari version" + ] + }, + "bugs": "https://github.com/excalidraw/excalidraw/issues", + "repository": "https://github.com/excalidraw/excalidraw", + "scripts": { + "gen:types": "rm -rf types && tsc", + "build:esm": "rm -rf dist && node ../../scripts/buildMath.js && yarn gen:types" + } +} diff --git a/packages/math/point.test.ts b/packages/math/point.test.ts new file mode 100644 index 0000000..89cc4f8 --- /dev/null +++ b/packages/math/point.test.ts @@ -0,0 +1,24 @@ +import { pointFrom, pointRotateRads } from "./point"; +import type { Radians } from "./types"; + +describe("rotate", () => { + it("should rotate over (x2, y2) and return the rotated coordinates for (x1, y1)", () => { + const x1 = 10; + const y1 = 20; + const x2 = 20; + const y2 = 30; + const angle = (Math.PI / 2) as Radians; + const [rotatedX, rotatedY] = pointRotateRads( + pointFrom(x1, y1), + pointFrom(x2, y2), + angle, + ); + expect([rotatedX, rotatedY]).toEqual([30, 20]); + const res2 = pointRotateRads( + pointFrom(rotatedX, rotatedY), + pointFrom(x2, y2), + -angle as Radians, + ); + expect(res2).toEqual([x1, x2]); + }); +}); diff --git a/packages/math/point.ts b/packages/math/point.ts new file mode 100644 index 0000000..92df187 --- /dev/null +++ b/packages/math/point.ts @@ -0,0 +1,231 @@ +import { degreesToRadians } from "./angle"; +import type { + LocalPoint, + GlobalPoint, + Radians, + Degrees, + Vector, +} from "./types"; +import { PRECISION } from "./utils"; +import { vectorFromPoint, vectorScale } from "./vector"; + +/** + * Create a properly typed Point instance from the X and Y coordinates. + * + * @param x The X coordinate + * @param y The Y coordinate + * @returns The branded and created point + */ +export function pointFrom( + x: number, + y: number, +): Point { + return [x, y] as Point; +} + +/** + * Converts and remaps an array containing a pair of numbers to Point. + * + * @param numberArray The number array to check and to convert to Point + * @returns The point instance + */ +export function pointFromArray( + numberArray: number[], +): Point | undefined { + return numberArray.length === 2 + ? pointFrom(numberArray[0], numberArray[1]) + : undefined; +} + +/** + * Converts and remaps a pair of numbers to Point. + * + * @param pair A number pair to convert to Point + * @returns The point instance + */ +export function pointFromPair( + pair: [number, number], +): Point { + return pair as Point; +} + +/** + * Convert a vector to a point. + * + * @param v The vector to convert + * @returns The point the vector points at with origin 0,0 + */ +export function pointFromVector

( + v: Vector, + offset: P = pointFrom(0, 0), +): P { + return pointFrom

(offset[0] + v[0], offset[1] + v[1]); +} + +/** + * Checks if the provided value has the shape of a Point. + * + * @param p The value to attempt verification on + * @returns TRUE if the provided value has the shape of a local or global point + */ +export function isPoint(p: unknown): p is LocalPoint | GlobalPoint { + return ( + Array.isArray(p) && + p.length === 2 && + typeof p[0] === "number" && + !isNaN(p[0]) && + typeof p[1] === "number" && + !isNaN(p[1]) + ); +} + +/** + * Compare two points coordinate-by-coordinate and if + * they are closer than INVERSE_PRECISION it returns TRUE. + * + * @param a Point The first point to compare + * @param b Point The second point to compare + * @returns TRUE if the points are sufficiently close to each other + */ +export function pointsEqual( + a: Point, + b: Point, +): boolean { + const abs = Math.abs; + return abs(a[0] - b[0]) < PRECISION && abs(a[1] - b[1]) < PRECISION; +} + +/** + * Roate a point by [angle] radians. + * + * @param point The point to rotate + * @param center The point to rotate around, the center point + * @param angle The radians to rotate the point by + * @returns The rotated point + */ +export function pointRotateRads( + [x, y]: Point, + [cx, cy]: Point, + angle: Radians, +): Point { + return pointFrom( + (x - cx) * Math.cos(angle) - (y - cy) * Math.sin(angle) + cx, + (x - cx) * Math.sin(angle) + (y - cy) * Math.cos(angle) + cy, + ); +} + +/** + * Roate a point by [angle] degree. + * + * @param point The point to rotate + * @param center The point to rotate around, the center point + * @param angle The degree to rotate the point by + * @returns The rotated point + */ +export function pointRotateDegs( + point: Point, + center: Point, + angle: Degrees, +): Point { + return pointRotateRads(point, center, degreesToRadians(angle)); +} + +/** + * Translate a point by a vector. + * + * WARNING: This is not for translating Excalidraw element points! + * You need to account for rotation on base coordinates + * on your own. + * CONSIDER USING AN APPROPRIATE ELEMENT-AWARE TRANSLATE! + * + * @param p The point to apply the translation on + * @param v The vector to translate by + * @returns + */ +// TODO 99% of use is translating between global and local coords, which need to be formalized +export function pointTranslate< + From extends GlobalPoint | LocalPoint, + To extends GlobalPoint | LocalPoint, +>(p: From, v: Vector = [0, 0] as Vector): To { + return pointFrom(p[0] + v[0], p[1] + v[1]); +} + +/** + * Find the center point at equal distance from both points. + * + * @param a One of the points to create the middle point for + * @param b The other point to create the middle point for + * @returns The middle point + */ +export function pointCenter

(a: P, b: P): P { + return pointFrom((a[0] + b[0]) / 2, (a[1] + b[1]) / 2); +} + +/** + * Calculate the distance between two points. + * + * @param a First point + * @param b Second point + * @returns The euclidean distance between the two points. + */ +export function pointDistance

( + a: P, + b: P, +): number { + return Math.hypot(b[0] - a[0], b[1] - a[1]); +} + +/** + * Calculate the squared distance between two points. + * + * Note: Use this if you only compare distances, it saves a square root. + * + * @param a First point + * @param b Second point + * @returns The euclidean distance between the two points. + */ +export function pointDistanceSq

( + a: P, + b: P, +): number { + const xDiff = b[0] - a[0]; + const yDiff = b[1] - a[1]; + + return xDiff * xDiff + yDiff * yDiff; +} + +/** + * Scale a point from a given origin by the multiplier. + * + * @param p The point to scale + * @param mid The origin to scale from + * @param multiplier The scaling factor + * @returns + */ +export const pointScaleFromOrigin =

( + p: P, + mid: P, + multiplier: number, +) => pointTranslate(mid, vectorScale(vectorFromPoint(p, mid), multiplier)); + +/** + * Returns whether `q` lies inside the segment/rectangle defined by `p` and `r`. + * This is an approximation to "does `q` lie on a segment `pr`" check. + * + * @param p The first point to compare against + * @param q The actual point this function checks whether is in between + * @param r The other point to compare against + * @returns TRUE if q is indeed between p and r + */ +export const isPointWithinBounds =

( + p: P, + q: P, + r: P, +) => { + return ( + q[0] <= Math.max(p[0], r[0]) && + q[0] >= Math.min(p[0], r[0]) && + q[1] <= Math.max(p[1], r[1]) && + q[1] >= Math.min(p[1], r[1]) + ); +}; diff --git a/packages/math/polygon.ts b/packages/math/polygon.ts new file mode 100644 index 0000000..783bc4c --- /dev/null +++ b/packages/math/polygon.ts @@ -0,0 +1,72 @@ +import { pointsEqual } from "./point"; +import { lineSegment, pointOnLineSegment } from "./segment"; +import type { GlobalPoint, LocalPoint, Polygon } from "./types"; +import { PRECISION } from "./utils"; + +export function polygon( + ...points: Point[] +) { + return polygonClose(points) as Polygon; +} + +export function polygonFromPoints( + points: Point[], +) { + return polygonClose(points) as Polygon; +} + +export const polygonIncludesPoint = ( + point: Point, + polygon: Polygon, +) => { + 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 pointOnPolygon = ( + p: Point, + poly: Polygon, + threshold = PRECISION, +) => { + let on = false; + + for (let i = 0, l = poly.length - 1; i < l; i++) { + if (pointOnLineSegment(p, lineSegment(poly[i], poly[i + 1]), threshold)) { + on = true; + break; + } + } + + return on; +}; + +function polygonClose( + polygon: Point[], +) { + return polygonIsClosed(polygon) + ? polygon + : ([...polygon, polygon[0]] as Polygon); +} + +function polygonIsClosed( + polygon: Point[], +) { + return pointsEqual(polygon[0], polygon[polygon.length - 1]); +} diff --git a/packages/math/range.test.ts b/packages/math/range.test.ts new file mode 100644 index 0000000..fb4b6a3 --- /dev/null +++ b/packages/math/range.test.ts @@ -0,0 +1,51 @@ +import { rangeInclusive, rangeIntersection, rangesOverlap } from "./range"; + +describe("range overlap", () => { + const range1_4 = rangeInclusive(1, 4); + + it("should overlap when range a contains range b", () => { + expect(rangesOverlap(range1_4, rangeInclusive(2, 3))).toBe(true); + expect(rangesOverlap(range1_4, range1_4)).toBe(true); + expect(rangesOverlap(range1_4, rangeInclusive(1, 3))).toBe(true); + expect(rangesOverlap(range1_4, rangeInclusive(2, 4))).toBe(true); + }); + + it("should overlap when range b contains range a", () => { + expect(rangesOverlap(rangeInclusive(2, 3), range1_4)).toBe(true); + expect(rangesOverlap(rangeInclusive(1, 3), range1_4)).toBe(true); + expect(rangesOverlap(rangeInclusive(2, 4), range1_4)).toBe(true); + }); + + it("should overlap when range a and b intersect", () => { + expect(rangesOverlap(range1_4, rangeInclusive(2, 5))).toBe(true); + }); +}); + +describe("range intersection", () => { + const range1_4 = rangeInclusive(1, 4); + + it("should intersect completely with itself", () => { + expect(rangeIntersection(range1_4, range1_4)).toEqual(range1_4); + }); + + it("should intersect irrespective of order", () => { + expect(rangeIntersection(range1_4, rangeInclusive(2, 3))).toEqual([2, 3]); + expect(rangeIntersection(rangeInclusive(2, 3), range1_4)).toEqual([2, 3]); + expect(rangeIntersection(range1_4, rangeInclusive(3, 5))).toEqual( + rangeInclusive(3, 4), + ); + expect(rangeIntersection(rangeInclusive(3, 5), range1_4)).toEqual( + rangeInclusive(3, 4), + ); + }); + + it("should intersect at the edge", () => { + expect(rangeIntersection(range1_4, rangeInclusive(4, 5))).toEqual( + rangeInclusive(4, 4), + ); + }); + + it("should not intersect", () => { + expect(rangeIntersection(range1_4, rangeInclusive(5, 7))).toEqual(null); + }); +}); diff --git a/packages/math/range.ts b/packages/math/range.ts new file mode 100644 index 0000000..d90530c --- /dev/null +++ b/packages/math/range.ts @@ -0,0 +1,82 @@ +import { toBrandedType } from "@excalidraw/excalidraw/utils"; +import type { InclusiveRange } from "./types"; + +/** + * Create an inclusive range from the two numbers provided. + * + * @param start Start of the range + * @param end End of the range + * @returns + */ +export function rangeInclusive(start: number, end: number): InclusiveRange { + return toBrandedType([start, end]); +} + +/** + * Turn a number pair into an inclusive range. + * + * @param pair The number pair to convert to an inclusive range + * @returns The new inclusive range + */ +export function rangeInclusiveFromPair(pair: [start: number, end: number]) { + return toBrandedType(pair); +} + +/** + * Given two ranges, return if the two ranges overlap with each other e.g. + * [1, 3] overlaps with [2, 4] while [1, 3] does not overlap with [4, 5]. + * + * @param param0 One of the ranges to compare + * @param param1 The other range to compare against + * @returns TRUE if the ranges overlap + */ +export const rangesOverlap = ( + [a0, a1]: InclusiveRange, + [b0, b1]: InclusiveRange, +): boolean => { + if (a0 <= b0) { + return a1 >= b0; + } + + if (a0 >= b0) { + return b1 >= a0; + } + + return false; +}; + +/** + * Given two ranges,return ther intersection of the two ranges if any e.g. the + * intersection of [1, 3] and [2, 4] is [2, 3]. + * + * @param param0 The first range to compare + * @param param1 The second range to compare + * @returns The inclusive range intersection or NULL if no intersection + */ +export const rangeIntersection = ( + [a0, a1]: InclusiveRange, + [b0, b1]: InclusiveRange, +): InclusiveRange | null => { + const rangeStart = Math.max(a0, b0); + const rangeEnd = Math.min(a1, b1); + + if (rangeStart <= rangeEnd) { + return toBrandedType([rangeStart, rangeEnd]); + } + + return null; +}; + +/** + * Determine if a value is inside a range. + * + * @param value The value to check + * @param range The range + * @returns + */ +export const rangeIncludesValue = ( + value: number, + [min, max]: InclusiveRange, +): boolean => { + return value >= min && value <= max; +}; diff --git a/packages/math/rectangle.ts b/packages/math/rectangle.ts new file mode 100644 index 0000000..7dde15d --- /dev/null +++ b/packages/math/rectangle.ts @@ -0,0 +1,23 @@ +import { pointFrom } from "./point"; +import { lineSegment, lineSegmentIntersectionPoints } from "./segment"; +import type { GlobalPoint, LineSegment, LocalPoint, Rectangle } from "./types"; + +export function rectangle

( + topLeft: P, + bottomRight: P, +): Rectangle

{ + return [topLeft, bottomRight] as Rectangle

; +} + +export function rectangleIntersectLineSegment< + Point extends LocalPoint | GlobalPoint, +>(r: Rectangle, l: LineSegment): Point[] { + return [ + lineSegment(r[0], pointFrom(r[1][0], r[0][1])), + lineSegment(pointFrom(r[1][0], r[0][1]), r[1]), + lineSegment(r[1], pointFrom(r[0][0], r[1][1])), + lineSegment(pointFrom(r[0][0], r[1][1]), r[0]), + ] + .map((s) => lineSegmentIntersectionPoints(l, s)) + .filter((i): i is Point => !!i); +} diff --git a/packages/math/segment.test.ts b/packages/math/segment.test.ts new file mode 100644 index 0000000..4237a3c --- /dev/null +++ b/packages/math/segment.test.ts @@ -0,0 +1,21 @@ +import { pointFrom } from "./point"; +import { lineSegment, lineSegmentIntersectionPoints } from "./segment"; + +describe("line-segment intersections", () => { + it("should correctly detect intersection", () => { + expect( + lineSegmentIntersectionPoints( + lineSegment(pointFrom(0, 0), pointFrom(5, 0)), + lineSegment(pointFrom(2, -2), pointFrom(3, 2)), + ), + ).toEqual(pointFrom(2.5, 0)); + }); + it("should correctly detect non-intersection", () => { + expect( + lineSegmentIntersectionPoints( + lineSegment(pointFrom(0, 0), pointFrom(5, 0)), + lineSegment(pointFrom(3, 1), pointFrom(4, 4)), + ), + ).toEqual(null); + }); +}); diff --git a/packages/math/segment.ts b/packages/math/segment.ts new file mode 100644 index 0000000..60943aa --- /dev/null +++ b/packages/math/segment.ts @@ -0,0 +1,174 @@ +import { line, linesIntersectAt } from "./line"; +import { + isPoint, + pointCenter, + pointFromVector, + pointRotateRads, +} from "./point"; +import type { GlobalPoint, LineSegment, LocalPoint, Radians } from "./types"; +import { PRECISION } from "./utils"; +import { + vectorAdd, + vectorCross, + vectorFromPoint, + vectorScale, + vectorSubtract, +} from "./vector"; + +/** + * Create a line segment from two points. + * + * @param points The two points delimiting the line segment on each end + * @returns The line segment delineated by the points + */ +export function lineSegment

( + a: P, + b: P, +): LineSegment

{ + return [a, b] as LineSegment

; +} + +/** + * + * @param segment + * @returns + */ +export const isLineSegment = ( + segment: unknown, +): segment is LineSegment => + Array.isArray(segment) && + segment.length === 2 && + isPoint(segment[0]) && + isPoint(segment[0]); + +/** + * Return the coordinates resulting from rotating the given line about an origin by an angle in radians + * note that when the origin is not given, the midpoint of the given line is used as the origin. + * + * @param l + * @param angle + * @param origin + * @returns + */ +export const lineSegmentRotate = ( + l: LineSegment, + angle: Radians, + origin?: Point, +): LineSegment => { + return lineSegment( + pointRotateRads(l[0], origin || pointCenter(l[0], l[1]), angle), + pointRotateRads(l[1], origin || pointCenter(l[0], l[1]), angle), + ); +}; + +/** + * Calculates the point two line segments with a definite start and end point + * intersect at. + */ +export const segmentsIntersectAt = ( + a: Readonly>, + b: Readonly>, +): Point | null => { + const a0 = vectorFromPoint(a[0]); + const a1 = vectorFromPoint(a[1]); + const b0 = vectorFromPoint(b[0]); + const b1 = vectorFromPoint(b[1]); + const r = vectorSubtract(a1, a0); + const s = vectorSubtract(b1, b0); + const denominator = vectorCross(r, s); + + if (denominator === 0) { + return null; + } + + const i = vectorSubtract(vectorFromPoint(b[0]), vectorFromPoint(a[0])); + const u = vectorCross(i, r) / denominator; + const t = vectorCross(i, s) / denominator; + + if (u === 0) { + return null; + } + + const p = vectorAdd(a0, vectorScale(r, t)); + + if (t >= 0 && t < 1 && u >= 0 && u < 1) { + return pointFromVector(p); + } + + return null; +}; + +export const pointOnLineSegment = ( + point: Point, + line: LineSegment, + threshold = PRECISION, +) => { + const distance = distanceToLineSegment(point, line); + + if (distance === 0) { + return true; + } + + return distance < threshold; +}; + +export const distanceToLineSegment = ( + point: Point, + line: LineSegment, +) => { + const [x, y] = point; + const [[x1, y1], [x2, y2]] = line; + + const A = x - x1; + const B = y - y1; + const C = x2 - x1; + const D = y2 - y1; + + const dot = A * C + B * D; + const len_sq = C * C + D * D; + let param = -1; + if (len_sq !== 0) { + param = dot / len_sq; + } + + let xx; + let yy; + + if (param < 0) { + xx = x1; + yy = y1; + } else if (param > 1) { + xx = x2; + yy = y2; + } else { + xx = x1 + param * C; + yy = y1 + param * D; + } + + const dx = x - xx; + const dy = y - yy; + return Math.sqrt(dx * dx + dy * dy); +}; + +/** + * Returns the intersection point of a segment and a line + * + * @param l + * @param s + * @returns + */ +export function lineSegmentIntersectionPoints< + Point extends GlobalPoint | LocalPoint, +>(l: LineSegment, s: LineSegment): Point | null { + const candidate = linesIntersectAt(line(l[0], l[1]), line(s[0], s[1])); + + if ( + !candidate || + !pointOnLineSegment(candidate, s) || + !pointOnLineSegment(candidate, l) + ) { + return null; + } + + return candidate; +} diff --git a/packages/math/triangle.ts b/packages/math/triangle.ts new file mode 100644 index 0000000..bc74372 --- /dev/null +++ b/packages/math/triangle.ts @@ -0,0 +1,28 @@ +import type { GlobalPoint, LocalPoint, Triangle } from "./types"; + +// Types + +/** + * Tests if a point lies inside a triangle. This function + * will return FALSE if the point lies exactly on the sides + * of the triangle. + * + * @param triangle The triangle to test the point for + * @param p The point to test whether is in the triangle + * @returns TRUE if the point is inside of the triangle + */ +export function triangleIncludesPoint

( + [a, b, c]: Triangle

, + p: P, +): boolean { + const triangleSign = (p1: P, p2: P, p3: P) => + (p1[0] - p3[0]) * (p2[1] - p3[1]) - (p2[0] - p3[0]) * (p1[1] - p3[1]); + const d1 = triangleSign(p, a, b); + const d2 = triangleSign(p, b, c); + const d3 = triangleSign(p, c, a); + + const has_neg = d1 < 0 || d2 < 0 || d3 < 0; + const has_pos = d1 > 0 || d2 > 0 || d3 > 0; + + return !(has_neg && has_pos); +} diff --git a/packages/math/tsconfig.json b/packages/math/tsconfig.json new file mode 100644 index 0000000..f61b8d0 --- /dev/null +++ b/packages/math/tsconfig.json @@ -0,0 +1,24 @@ +{ + "compilerOptions": { + "outDir": "./dist/types", + "target": "ESNext", + "strict": true, + "skipLibCheck": true, + "declaration": true, + "allowSyntheticDefaultImports": true, + "module": "ESNext", + "moduleResolution": "Node", + "resolveJsonModule": true, + "jsx": "react-jsx", + "emitDeclarationOnly": true, + "paths": { + "@excalidraw/excalidraw": ["../excalidraw/index.tsx"], + "@excalidraw/utils": ["../utils/index.ts"], + "@excalidraw/math": ["../math/index.ts"], + "@excalidraw/excalidraw/*": ["../excalidraw/*"], + "@excalidraw/utils/*": ["../utils/*"], + "@excalidraw/math/*": ["../math/*"] + } + }, + "exclude": ["**/*.test.*", "tests", "types", "examples", "dist"] +} diff --git a/packages/math/types.ts b/packages/math/types.ts new file mode 100644 index 0000000..a2a575b --- /dev/null +++ b/packages/math/types.ts @@ -0,0 +1,140 @@ +// +// Measurements +// + +/** + * By definition one radian is the angle subtended at the centre + * of a circle by an arc that is equal in length to the radius. + */ +export type Radians = number & { _brand: "excalimath__radian" }; + +/** + * An angle measurement of a plane angle in which one full + * rotation is 360 degrees. + */ +export type Degrees = number & { _brand: "excalimath_degree" }; + +// +// Range +// + +/** + * A number range which includes the start and end numbers in the range. + */ +export type InclusiveRange = [number, number] & { _brand: "excalimath_degree" }; + +// +// Point +// + +/** + * Represents a 2D position in world or canvas space. A + * global coordinate. + */ +export type GlobalPoint = [x: number, y: number] & { + _brand: "excalimath__globalpoint"; +}; + +/** + * Represents a 2D position in whatever local space it's + * needed. A local coordinate. + */ +export type LocalPoint = [x: number, y: number] & { + _brand: "excalimath__localpoint"; +}; + +// Line + +/** + * A line is an infinitely long object with no width, depth, or curvature. + */ +export type Line

= [p: P, q: P] & { + _brand: "excalimath_line"; +}; + +/** + * In geometry, a line segment is a part of a straight + * line that is bounded by two distinct end points, and + * contains every point on the line that is between its endpoints. + */ +export type LineSegment

= [a: P, b: P] & { + _brand: "excalimath_linesegment"; +}; + +// +// Vector +// + +/** + * Represents a 2D vector + */ +export type Vector = [u: number, v: number] & { + _brand: "excalimath__vector"; +}; + +// Triangles + +/** + * A triangle represented by 3 points + */ +export type Triangle

= [ + a: P, + b: P, + c: P, +] & { + _brand: "excalimath__triangle"; +}; + +/** + * A rectangular shape represented by 4 points at its corners + */ +export type Rectangle

= [a: P, b: P] & { + _brand: "excalimath__rectangle"; +}; + +// +// Polygon +// + +/** + * A polygon is a closed shape by connecting the given points + * rectangles and diamonds are modelled by polygons + */ +export type Polygon = Point[] & { + _brand: "excalimath_polygon"; +}; + +// +// Curve +// + +/** + * Cubic bezier curve with four control points + */ +export type Curve = [ + Point, + Point, + Point, + Point, +] & { + _brand: "excalimath_curve"; +}; + +export type PolarCoords = [ + radius: number, + /** angle in radians */ + angle: number, +]; + +/** + An ellipse is specified by its center, angle, and its major and minor axes + but for the sake of simplicity, we've used halfWidth and halfHeight instead + in replace of semi major and semi minor axes + */ +export type Ellipse = { + center: Point; + halfWidth: number; + halfHeight: number; +} & { + _brand: "excalimath_ellipse"; +}; diff --git a/packages/math/utils.ts b/packages/math/utils.ts new file mode 100644 index 0000000..8807c27 --- /dev/null +++ b/packages/math/utils.ts @@ -0,0 +1,33 @@ +export const PRECISION = 10e-5; + +export const clamp = (value: number, min: number, max: number) => { + return Math.min(Math.max(value, min), max); +}; + +export const round = ( + value: number, + precision: number, + func: "round" | "floor" | "ceil" = "round", +) => { + const multiplier = Math.pow(10, precision); + + return Math[func]((value + Number.EPSILON) * multiplier) / multiplier; +}; + +export const roundToStep = ( + value: number, + step: number, + func: "round" | "floor" | "ceil" = "round", +): number => { + const factor = 1 / step; + return Math[func](value * factor) / factor; +}; + +export const average = (a: number, b: number) => (a + b) / 2; + +export const isFiniteNumber = (value: any): value is number => { + return typeof value === "number" && Number.isFinite(value); +}; + +export const isCloseTo = (a: number, b: number, precision = PRECISION) => + Math.abs(a - b) < precision; diff --git a/packages/math/vector.test.ts b/packages/math/vector.test.ts new file mode 100644 index 0000000..145c909 --- /dev/null +++ b/packages/math/vector.test.ts @@ -0,0 +1,12 @@ +import { isVector } from "."; + +describe("Vector", () => { + test("isVector", () => { + expect(isVector([5, 5])).toBe(true); + expect(isVector([-5, -5])).toBe(true); + expect(isVector([5, 0.5])).toBe(true); + expect(isVector(null)).toBe(false); + expect(isVector(undefined)).toBe(false); + expect(isVector([5, NaN])).toBe(false); + }); +}); diff --git a/packages/math/vector.ts b/packages/math/vector.ts new file mode 100644 index 0000000..2467220 --- /dev/null +++ b/packages/math/vector.ts @@ -0,0 +1,145 @@ +import type { GlobalPoint, LocalPoint, Vector } from "./types"; + +/** + * Create a vector from the x and y coordiante elements. + * + * @param x The X aspect of the vector + * @param y T Y aspect of the vector + * @returns The constructed vector with X and Y as the coordinates + */ +export function vector( + x: number, + y: number, + originX: number = 0, + originY: number = 0, +): Vector { + return [x - originX, y - originY] as Vector; +} + +/** + * Turn a point into a vector with the origin point. + * + * @param p The point to turn into a vector + * @param origin The origin point in a given coordiante system + * @returns The created vector from the point and the origin + */ +export function vectorFromPoint( + p: Point, + origin: Point = [0, 0] as Point, +): Vector { + return vector(p[0] - origin[0], p[1] - origin[1]); +} + +/** + * Cross product is a binary operation on two vectors in 2D space. + * It results in a vector that is perpendicular to both vectors. + * + * @param a One of the vectors to use for the directed area calculation + * @param b The other vector to use for the directed area calculation + * @returns The directed area value for the two vectos + */ +export function vectorCross(a: Vector, b: Vector): number { + return a[0] * b[1] - b[0] * a[1]; +} + +/** + * Dot product is defined as the sum of the products of the + * two vectors. + * + * @param a One of the vectors for which the sum of products is calculated + * @param b The other vector for which the sum of products is calculated + * @returns The sum of products of the two vectors + */ +export function vectorDot(a: Vector, b: Vector) { + return a[0] * b[0] + a[1] * b[1]; +} + +/** + * Determines if the value has the shape of a Vector. + * + * @param v The value to test + * @returns TRUE if the value has the shape and components of a Vectors + */ +export function isVector(v: unknown): v is Vector { + return ( + Array.isArray(v) && + v.length === 2 && + typeof v[0] === "number" && + !isNaN(v[0]) && + typeof v[1] === "number" && + !isNaN(v[1]) + ); +} + +/** + * Add two vectors by adding their coordinates. + * + * @param a One of the vectors to add + * @param b The other vector to add + * @returns The sum vector of the two provided vectors + */ +export function vectorAdd(a: Readonly, b: Readonly): Vector { + return [a[0] + b[0], a[1] + b[1]] as Vector; +} + +/** + * Add two vectors by adding their coordinates. + * + * @param start One of the vectors to add + * @param end The other vector to add + * @returns The sum vector of the two provided vectors + */ +export function vectorSubtract( + start: Readonly, + end: Readonly, +): Vector { + return [start[0] - end[0], start[1] - end[1]] as Vector; +} + +/** + * Scale vector by a scalar. + * + * @param v The vector to scale + * @param scalar The scalar to multiply the vector components with + * @returns The new scaled vector + */ +export function vectorScale(v: Vector, scalar: number): Vector { + return vector(v[0] * scalar, v[1] * scalar); +} + +/** + * Calculates the sqare magnitude of a vector. Use this if you compare + * magnitudes as it saves you an SQRT. + * + * @param v The vector to measure + * @returns The scalar squared magnitude of the vector + */ +export function vectorMagnitudeSq(v: Vector) { + return v[0] * v[0] + v[1] * v[1]; +} + +/** + * Calculates the magnitude of a vector. + * + * @param v The vector to measure + * @returns The scalar magnitude of the vector + */ +export function vectorMagnitude(v: Vector) { + return Math.sqrt(vectorMagnitudeSq(v)); +} + +/** + * Normalize the vector (i.e. make the vector magnitue equal 1). + * + * @param v The vector to normalize + * @returns The new normalized vector + */ +export const vectorNormalize = (v: Vector): Vector => { + const m = vectorMagnitude(v); + + if (m === 0) { + return vector(0, 0); + } + + return vector(v[0] / m, v[1] / m); +}; -- cgit v1.2.3