geometry

Kind	kit
Categories	math graphics
Keywords	geometry math 2d 3d vectors bounds

Basic geometric types and operations for 2D and 3D space

Files

File	Description
`kit.toml`	Package manifest with metadata and dependencies
`src/lod-tree.kit`	Quadtree-based level of detail tree for adaptive spatial subdivision
`src/package.kit`	Core 2D/3D points, bounds, circles, spheres, and rectangles
`tests/geometry.test.kit`	Tests for points, bounds, circles, rects, and vector ops
`examples/basic.kit`	2D/3D point operations and bounding box containment
`LICENSE`	MIT license file

Dependencies

No Kit package dependencies.

Installation

kit add gitlab.com/kit-lang/packages/kit-geometry.git

Usage

import Kit.Geometry

License

MIT License - see LICENSE for details.

Exported Functions & Types

`Point2D`

A point in 2D Cartesian space.

Represents a position or vector in 2D space with x and y coordinates. Can be used for both positions and direction vectors.

Fields: - x: The x-coordinate (horizontal) - y: The y-coordinate (vertical)

Variants

Point2D {x, y}

`point2d`

Create a 2D point from x and y coordinates.

Parameters:

Returns:

Float -> Float -> Point2D

p = point2d 3.0 4.0  # Point at (3, 4)

`point2d-x`

Get the x-coordinate of a 2D point.

Parameters:

Returns:

Point2D -> Float

`point2d-y`

Get the y-coordinate of a 2D point.

Parameters:

Returns:

Point2D -> Float

`point2d-add`

Add two 2D points using vector addition.

Computes the component-wise sum: $(x_1 + x_2, y_1 + y_2)$

Parameters:

Returns:

Point2D -> Point2D -> Point2D

`point2d-sub`

Subtract two 2D points using vector subtraction.

Computes the component-wise difference: $(x_1 - x_2, y_1 - y_2)$

Parameters:

Returns:

Point2D -> Point2D -> Point2D

`point2d-scale`

Scale a 2D point by a scalar multiplier.

Multiplies both components by the scalar: $(sx, sy)$

Parameters:

Returns:

Point2D -> Float -> Point2D

`point2d-distance`

Calculate the Euclidean distance between two 2D points.

Uses the distance formula: $d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$

Parameters:

Returns:

Point2D -> Point2D -> Float

`point2d-distance-squared`

Calculate the squared distance between two 2D points.

Computes: $d^2 = (x_2 - x_1)^2 + (y_2 - y_1)^2$

This is more efficient than point2d-distance when only comparing distances, as it avoids the expensive square root operation.

Parameters:

Returns:

Point2D -> Point2D -> Float

`point2d-dot`

Calculate the dot product of two 2D vectors.

Computes: $\mathbf{p_1} \cdot \mathbf{p_2} = x_1 x_2 + y_1 y_2$

The dot product is useful for: - Testing if vectors are perpendicular (dot product = 0) - Finding the angle between vectors - Projecting one vector onto another

Parameters:

Returns:

Point2D -> Point2D -> Float

`point2d-length`

Calculate the length (magnitude) of a 2D vector from the origin.

Computes: $|\mathbf{p}| = \sqrt{x^2 + y^2}$

Parameters:

Returns:

Point2D -> Float

`point2d-normalize`

Normalize a 2D vector to unit length.

Computes: $\hat{\mathbf{p}} = \frac{\mathbf{p}}{|\mathbf{p}|}$

If the vector has zero length, returns the original vector unchanged.

Parameters:

Returns:

Point2D -> Point2D

`point2d-lerp`

Linearly interpolate between two 2D points.

Computes: $\mathbf{p} = (1-t)\mathbf{p_1} + t\mathbf{p_2}$

Parameters:

Returns:

Point2D -> Point2D -> Float -> Point2D

`point2d-eq?`

Check if two 2D points are exactly equal.

Parameters:

Returns:

Point2D -> Point2D -> Bool

`point2d-origin`

The origin point at coordinates (0, 0).

Point2D

`Point3D`

A point in 3D space

Variants

Point3D {x, y, z}

`point3d`

Create a 3D point

Float -> Float -> Float -> Point3D

`point3d-x`

Get x coordinate of a 3D point

Point3D -> Float

`point3d-y`

Get y coordinate of a 3D point

Point3D -> Float

`point3d-z`

Get z coordinate of a 3D point

Point3D -> Float

`point3d-add`

Add two 3D points (vector addition)

Point3D -> Point3D -> Point3D

`point3d-sub`

Subtract two 3D points (vector subtraction)

Point3D -> Point3D -> Point3D

`point3d-scale`

Scale a 3D point by a scalar

Point3D -> Float -> Point3D

`point3d-distance`

Euclidean distance between two 3D points

Point3D -> Point3D -> Float

`point3d-distance-squared`

Squared distance between two 3D points (avoids sqrt for comparisons)

Point3D -> Point3D -> Float

`point3d-dot`

Dot product of two 3D points (as vectors)

Point3D -> Point3D -> Float

`point3d-cross`

Cross product of two 3D points (as vectors)

Point3D -> Point3D -> Point3D

`point3d-length`

Length/magnitude of a 3D point (as vector from origin)

Point3D -> Float

`point3d-normalize`

Normalize a 3D point to unit length

Point3D -> Point3D

`point3d-lerp`

Linear interpolation between two 3D points (t=0 returns p1, t=1 returns p2)

Point3D -> Point3D -> Float -> Point3D

`point3d-eq?`

Check if two 3D points are equal

Point3D -> Point3D -> Bool

`point3d-origin`

Origin point (0, 0, 0)

Point3D

`Bounds2D`

Axis-aligned bounding box in 2D (min corner, max corner)

Variants

Bounds2D {x1, y1, x2, y2}

`bounds2d`

Create a 2D bounding box from min/max coordinates

Float -> Float -> Float -> Float -> Bounds2D

`bounds2d-from-points`

Create a 2D bounding box from two points

Point2D -> Point2D -> Bounds2D

`bounds2d-center`

Get the center point of a 2D bounding box

Bounds2D -> Point2D

`bounds2d-width`

Get the width of a 2D bounding box

Bounds2D -> Float

`bounds2d-height`

Get the height of a 2D bounding box

Bounds2D -> Float

`bounds2d-area`

Get the area of a 2D bounding box

Bounds2D -> Float

`bounds2d-contains?`

Check if a point is inside a 2D bounding box

Bounds2D -> Point2D -> Bool

`bounds2d-intersects?`

Check if two 2D bounding boxes intersect

Bounds2D -> Bounds2D -> Bool

`Bounds3D`

Axis-aligned bounding box in 3D (min corner, max corner)

Variants

Bounds3D {x1, y1, z1, x2, y2, z2}

`bounds3d`

Create a 3D bounding box from min/max coordinates

Float -> Float -> Float -> Float -> Float -> Float -> Bounds3D

`bounds3d-from-points`

Create a 3D bounding box from two points

Point3D -> Point3D -> Bounds3D

`bounds3d-center`

Get the center point of a 3D bounding box

Bounds3D -> Point3D

`bounds3d-width`

Get the width (x dimension) of a 3D bounding box

Bounds3D -> Float

`bounds3d-height`

Get the height (y dimension) of a 3D bounding box

Bounds3D -> Float

`bounds3d-depth`

Get the depth (z dimension) of a 3D bounding box

Bounds3D -> Float

`bounds3d-volume`

Get the volume of a 3D bounding box

Bounds3D -> Float

`bounds3d-contains?`

Check if a point is inside a 3D bounding box

Bounds3D -> Point3D -> Bool

`bounds3d-intersects?`

Check if two 3D bounding boxes intersect

Bounds3D -> Bounds3D -> Bool

`pi`

Pi constant

Float

`tau`

Tau (2 * pi)

Float

`deg-to-rad`

Convert degrees to radians

Float -> Float

`rad-to-deg`

Convert radians to degrees

Float -> Float

`normalize-angle`

Normalize angle to [0, 2*pi) range

Float -> Float

`Line2D`

A line segment from start to end point

Variants

Line2D {start, end}

`line2d`

Create a 2D line segment

Point2D -> Point2D -> Line2D

`line2d-start`

Get the start point of a line

Line2D -> Point2D

`line2d-end`

Get the end point of a line

Line2D -> Point2D

`line2d-length`

Get the length of a line segment

Line2D -> Float

`line2d-midpoint`

Get the midpoint of a line segment

Line2D -> Point2D

`line2d-point-at`

Get a point along the line at parameter t (0=start, 1=end)

Line2D -> Float -> Point2D

`line2d-direction`

Get the direction vector of a line (normalized)

Line2D -> Point2D

`Circle`

A circle defined by center and radius

Variants

Circle {center, radius}

`circle`

Create a circle

Point2D -> Float -> Circle

`circle-from-coords`

Create a circle from center coordinates and radius

Float -> Float -> Float -> Circle

`circle-center`

Get the center of a circle

Circle -> Point2D

`circle-radius`

Get the radius of a circle

Circle -> Float

`circle-diameter`

Get the diameter of a circle

Circle -> Float

`circle-circumference`

Get the circumference of a circle

Circle -> Float

`circle-area`

Get the area of a circle

Circle -> Float

`circle-contains?`

Check if a point is inside a circle

Circle -> Point2D -> Bool

`circle-intersects?`

Check if two circles intersect

Circle -> Circle -> Bool

`circle-point-at-angle`

Get a point on the circle at a given angle (in radians)

Circle -> Float -> Point2D

`circle-bounds`

Get the bounding box of a circle

Circle -> Bounds2D

`Sphere`

A sphere defined by center and radius

Variants

Sphere {center, radius}

`sphere`

Create a sphere

Point3D -> Float -> Sphere

`sphere-from-coords`

Create a sphere from center coordinates and radius

Float -> Float -> Float -> Float -> Sphere

`sphere-center`

Get the center of a sphere

Sphere -> Point3D

`sphere-radius`

Get the radius of a sphere

Sphere -> Float

`sphere-diameter`

Get the diameter of a sphere

Sphere -> Float

`sphere-surface-area`

Get the surface area of a sphere

Sphere -> Float

`sphere-volume`

Get the volume of a sphere

Sphere -> Float

`sphere-contains?`

Check if a point is inside a sphere

Sphere -> Point3D -> Bool

`sphere-intersects?`

Check if two spheres intersect

Sphere -> Sphere -> Bool

`sphere-bounds`

Get the bounding box of a sphere

Sphere -> Bounds3D

`Rect`

A rectangle defined by position (top-left) and size

Variants

Rect {x, y, width, height}

`rect`

Create a rectangle from position and size

Float -> Float -> Float -> Float -> Rect

`rect-from-points`

Create a rectangle from two corner points

Point2D -> Point2D -> Rect

`rect-x`

Get the x position of a rectangle

Rect -> Float

`rect-y`

Get the y position of a rectangle

Rect -> Float

`rect-width`

Get the width of a rectangle

Rect -> Float

`rect-height`

Get the height of a rectangle

Rect -> Float

`rect-area`

Get the area of a rectangle

Rect -> Float

`rect-perimeter`

Get the perimeter of a rectangle

Rect -> Float

`rect-center`

Get the center point of a rectangle

Rect -> Point2D

`rect-top-left`

Get the top-left corner of a rectangle

Rect -> Point2D

`rect-top-right`

Get the top-right corner of a rectangle

Rect -> Point2D

`rect-bottom-left`

Get the bottom-left corner of a rectangle

Rect -> Point2D

`rect-bottom-right`

Get the bottom-right corner of a rectangle

Rect -> Point2D

`rect-contains?`

Check if a point is inside a rectangle

Rect -> Point2D -> Bool

`rect-intersects?`

Check if two rectangles intersect

Rect -> Rect -> Bool

`rect-to-bounds`

Convert a rectangle to a bounding box

Rect -> Bounds2D

`point2d-rotate`

Rotate a 2D point around the origin by an angle (in radians)

Point2D -> Float -> Point2D

`point2d-rotate-around`

Rotate a 2D point around a center point by an angle (in radians)

Point2D -> Point2D -> Float -> Point2D

`point2d-perpendicular`

Get the perpendicular vector (rotate 90 degrees counter-clockwise)

Point2D -> Point2D

`point2d-angle`

Get the angle of a vector (in radians, from positive x-axis)

Point2D -> Float

`point2d-angle-between`

Get the angle between two vectors (in radians)

Point2D -> Point2D -> Float

`point2d-reflect`

Reflect a vector off a surface with the given normal

Point2D -> Point2D -> Point2D

`point2d-project`

Project vector a onto vector b

Point2D -> Point2D -> Point2D

`clamp`

Clamp a value between min and max

Float -> Float -> Float -> Float

`lerp`

Linear interpolation between two values

Float -> Float -> Float -> Float

`inverse-lerp`

Inverse linear interpolation (get t from value)

Float -> Float -> Float -> Float

`remap`

Remap a value from one range to another

Float -> Float -> Float -> Float -> Float -> Float

`smoothstep`

Smoothstep interpolation (smooth ease in/out)

Float -> Float -> Float -> Float

`LodTree`

LOD Tree node - either a leaf or a branch with 4 children.

Variants

Leaf {bounds, center, width}

A terminal node with no children. bounds: The 2D rectangular bounds of this leaf region. center: The geometric center point of the bounds. width: The width of the bounds (cached for performance).

Branch {bounds, center, width, q1, q2, q3, q4}

An interior node with 4 children. bounds: The 2D rectangular bounds of this branch region. center: The geometric center point of the bounds. width: The width of the bounds (cached for performance). q1: Northwest quadrant child node. q2: Northeast quadrant child node. q3: Southwest quadrant child node. q4: Southeast quadrant child node.

`point`

Create a 2D point.

Parameters:

Returns:

Float -> Float -> Point2D

`point-x`

Get x coordinate of a point.

Parameters:

Returns:

Point2D -> Float

`point-y`

Get y coordinate of a point.

Parameters:

Returns:

Point2D -> Float

`bounds`

Create bounds from coordinates.

Parameters:

Returns:

Float -> Float -> Float -> Float -> Bounds2D

`center`

Calculate center point of bounds.

Parameters:

Returns:

Bounds2D -> Point2D

`width`

Calculate width of bounds.

Parameters:

Returns:

Bounds2D -> Float

`height`

Calculate height of bounds.

Parameters:

Returns:

Bounds2D -> Float

`distance`

Euclidean distance between two points.

Parameters:

Returns:

Point2D -> Point2D -> Float

`distance-to-center`

Distance from a point to the center of bounds.

Parameters:

Returns:

Point2D -> Bounds2D -> Float

`make-leaf`

Create a leaf node from bounds.

Parameters:

Returns:

Bounds2D -> LodTree

`make-node`

Create a leaf node from coordinates.

Parameters:

Returns:

Float -> Float -> Float -> Float -> LodTree

`should-split?`

Check if a node should split based on focus distance and minimum size.

A node splits if: 1. The focus point is closer than the node's width (needs more detail) 2. The node is larger than the minimum allowed size

Mathematically: $d(\mathbf{f}, \mathbf{c}) < w \land w > w_{\min}$

Parameters:

Returns:

LodTree -> Point2D -> Float -> Bool

`split`

Split a leaf node into 4 children (NW, NE, SW, SE quadrants).

Divides the node at its midpoint into four equal-sized quadrants: - Q1 (NW): Northwest quadrant (upper-left) - Q2 (NE): Northeast quadrant (upper-right) - Q3 (SW): Southwest quadrant (lower-left) - Q4 (SE): Southeast quadrant (lower-right)

Parameters:

Returns:

LodTree -> LodTree

`build`

Recursively build/rebuild tree based on focus point.

This is the core algorithm - subdivides nodes that are close to the focus and collapses nodes that are far away. Recursively processes all children to maintain consistent detail levels throughout the tree.

Parameters:

Returns:

LodTree -> Point2D -> Float -> LodTree

focus = point 50.0 50.0
tree = make-node 0.0 0.0 100.0 100.0
detailed-tree = build tree focus 1.0

`create`

Create a new LOD tree with given bounds and build it for a focus point.

Convenience function that combines node creation and tree building.

Parameters:

Returns:

Float -> Float -> Float -> Float -> Point2D -> Float -> LodTree

focus = point 50.0 50.0
tree = create 0.0 0.0 100.0 100.0 focus 1.0

`leaf?`

Check if node is a leaf.

Parameters:

Returns:

LodTree -> Bool

`branch?`

Check if node is a branch.

Parameters:

Returns:

LodTree -> Bool

`get-bounds`

Get the bounds of a node.

Parameters:

Returns:

LodTree -> Bounds2D

`get-center`

Get the center of a node.

Parameters:

Returns:

LodTree -> Point2D

`get-width`

Get the width of a node.

Parameters:

Returns:

LodTree -> Float

`leaves`

Collect all leaf nodes (the visible/renderable nodes).

Recursively traverses the tree and collects all Leaf nodes into a list. These are typically the nodes that would be rendered or processed.

Parameters:

Returns:

LodTree -> List LodTree

tree = create 0.0 0.0 100.0 100.0 focus 1.0
renderable-nodes = leaves tree

`count-nodes`

Count total nodes in tree.

Counts both Leaf and Branch nodes throughout the entire tree.

Parameters:

Returns:

LodTree -> Int

`count-leaves`

Count leaf nodes only.

Counts only terminal Leaf nodes (excludes Branch nodes).

Parameters:

Returns:

LodTree -> Int

`max-depth`

Get maximum depth of tree.

Calculates the longest path from root to any leaf node.

Parameters:

Returns:

LodTree -> Int

`fold`

Fold over all nodes (pre-order traversal).

Applies a folding function to every node in the tree in pre-order (parent before children). Useful for aggregating information across the entire tree structure.

Parameters:

Returns:

LodTree -> a -> (a -> LodTree -> a) -> a

# Count all nodes using fold
count = fold tree 0 (fn(acc, _) => acc + 1)

`map-leaves`

Map a function over all leaf nodes, rebuilding the tree structure.

Applies a transformation function to every Leaf node while preserving the tree structure. Branch nodes maintain their structure but contain the transformed children.

Parameters:

Returns:

LodTree -> (LodTree -> a) -> a

# Transform all leaves (e.g., attach metadata)
tagged-tree = map-leaves tree (fn(leaf) => {node: leaf, tag: "visible"})

`contains?`

Check if a point is inside bounds.

Parameters:

Returns:

Bounds2D -> Point2D -> Bool

`find-leaf`

Find the leaf node containing a point.

Recursively searches the tree to find the leaf node that contains the given point. Returns None if the point is outside the tree bounds.

Parameters:

Returns:

LodTree -> Point2D -> Option LodTree

tree = create 0.0 0.0 100.0 100.0 focus 1.0
point = point 25.0 25.0
match find-leaf tree point
  | Some(leaf) -> write "Found containing leaf"
  | None -> write "Point outside tree"