std/geometry

The shapes of the plane and of space, with the half-open rule that makes a row of rectangles a tiling and the ray tests that answer a distance.

Die generierte Referenz von std/geometry zeigt jede öffentliche Deklaration mit Signatur, Doc-Kommentar und Beispielen.

std/geometry is the shapes and what they answer about each other: what contains a point, what two of them share, how far apart they are, which axis-aligned box holds one, and what a ray hits. In the plane: Rectangle, Circle, Segment2, Ray2, Triangle2, Polygon. In space: Box, Sphere, Ray3, Plane, Triangle3.

Every shape is generic over its scalar the way std/linear's vectors are: a Rectangle<Int> is the pixel or tile rectangle and a Rectangle is the continuous one, and the tests that need a square root or an angle live under Real while everything else works with whole numbers. It is a pure value library and depends on std/linear and nothing else.

Import#

use Rectangle, Circle, Segment2, Ray2, Triangle2, Polygon from "std/geometry"
use Box, Sphere, Ray3, Plane, Triangle3 from "std/geometry"

use Vector2 from "std/linear"
use Rectangle from "std/geometry"

const tile = Rectangle Vector2(0, 0), Vector2(8, 8)
print "{tile.contains(Vector2(0, 0))} {tile.contains(Vector2(8, 0))} {tile.area()}"

The half-open rule#

The minimum edge of a Rectangle or a Box is inside it and the maximum edge is outside. A point is in a rectangle when minimum.x <= point.x and point.x < maximum.x, on every axis and for every scalar. That is what makes a row of them a tiling: Rectangle(Vector2(0, 0), Vector2(8, 8)) and Rectangle(Vector2(8, 0), Vector2(8, 8)) share the column x == 8 in neither of them, so a pixel belongs to exactly one tile and a hit test never answers twice.

A Circle and a Sphere are closed instead - their boundary is inside - because they do not tile: nothing is lost by counting a boundary twice, and a great deal is lost by leaving a touching point out of both of two touching circles.

bounds and covering answer the closed hull of what they are given, so a corner of a shape can lie exactly on the maximum edge of that shape's own bounding rectangle and contains then answers false for it. A bound is a bound; the half-open rule is about tiling.

Declarations#

`Rectangle`, `Box`#

type Rectangle<Scalar: Numeric = Float> {
  origin: Vector2<Scalar>
  size: Vector2<Scalar>
  static fn between(first: Vector2<Scalar>, second: Vector2<Scalar>): Self
  fn minimum(): Vector2<Scalar>
  fn maximum(): Vector2<Scalar>
  fn isEmpty(): Bool
  fn area(): Scalar
  fn contains(point: Vector2<Scalar>): Bool
  fn encloses(other: Self): Bool
  fn intersects(other: Self): Bool
  fn intersection(other: Self): Self
  fn combined(other: Self): Self
  fn covering(point: Vector2<Scalar>): Self
  fn translated(by: Vector2<Scalar>): Self
  fn grown(by: Vector2<Scalar>): Self
  fn withSize(value: Vector2<Scalar>): Self
  fn closestPoint(to: Vector2<Scalar>): Vector2<Scalar>
  fn bounds(): Self
}
extend<Scalar: Signed> Rectangle<Scalar> {
  fn manhattanDistanceTo(point: Vector2<Scalar>): Scalar
}
extend<Scalar: Real> Rectangle<Scalar> {
  static fn centered(at: Vector2<Scalar>, size: Vector2<Scalar>): Self
  fn center(): Vector2<Scalar>
  fn distanceTo(point: Vector2<Scalar>): Scalar
  fn distanceSquaredTo(point: Vector2<Scalar>): Scalar
}
type Box<Scalar: Numeric = Float> {
  origin: Vector3<Scalar>
  size: Vector3<Scalar>
  static fn between(first: Vector3<Scalar>, second: Vector3<Scalar>): Self
  fn minimum(): Vector3<Scalar>
  fn maximum(): Vector3<Scalar>
  fn isEmpty(): Bool
  fn volume(): Scalar
  fn contains(point: Vector3<Scalar>): Bool
  fn encloses(other: Self): Bool
  fn intersects(other: Self): Bool
  fn intersection(other: Self): Self
  fn combined(other: Self): Self
  fn covering(point: Vector3<Scalar>): Self
  fn translated(by: Vector3<Scalar>): Self
  fn grown(by: Vector3<Scalar>): Self
  fn closestPoint(to: Vector3<Scalar>): Vector3<Scalar>
  fn bounds(): Self
}
extend<Scalar: Signed> Box<Scalar> {
  fn manhattanDistanceTo(point: Vector3<Scalar>): Scalar
}
extend<Scalar: Real> Box<Scalar> {
  static fn centered(at: Vector3<Scalar>, size: Vector3<Scalar>): Self
  fn center(): Vector3<Scalar>
  fn distanceTo(point: Vector3<Scalar>): Scalar
  fn distanceSquaredTo(point: Vector3<Scalar>): Scalar
}

An axis-aligned box: where it starts (origin, the corner with the smaller coordinates) and how big it is (size). A size with a negative or zero component describes no points, and isEmpty says so - intersection answers an empty one rather than None, so that a chain of them stays a rectangle.

between (from two corners), minimum, maximum, area/volume, contains, encloses, intersects, intersection, combined, covering, translated, grown, withSize, closestPoint, bounds and manhattanDistanceTo need only Numeric; centered, center, distanceTo and distanceSquaredTo halve or take a root and therefore need Real.

Nothing here says top or bottom. Whether a viewer sees the minimum corner as the top or the bottom is the program's own business.

`Circle`, `Sphere`#

type Circle<Scalar: Real = Float> {
  center: Vector2<Scalar>
  radius: Scalar
  fn isEmpty(): Bool
  fn contains(point: Vector2<Scalar>): Bool
  fn encloses(other: Self): Bool
  fn intersects(other: Self): Bool
  fn intersectsRectangle(other: Rectangle<Scalar>): Bool
  fn closestPoint(to: Vector2<Scalar>): Vector2<Scalar>
  fn distanceTo(point: Vector2<Scalar>): Scalar
  fn translated(by: Vector2<Scalar>): Self
  fn grown(by: Scalar): Self
  fn bounds(): Rectangle<Scalar>
  fn area(): Scalar
  fn circumference(): Scalar
}
type Sphere<Scalar: Real = Float> {
  center: Vector3<Scalar>
  radius: Scalar
  static fn around(box: Box<Scalar>): Self
  fn isEmpty(): Bool
  fn contains(point: Vector3<Scalar>): Bool
  fn encloses(other: Self): Bool
  fn intersects(other: Self): Bool
  fn intersectsBox(other: Box<Scalar>): Bool
  fn closestPoint(to: Vector3<Scalar>): Vector3<Scalar>
  fn distanceTo(point: Vector3<Scalar>): Scalar
  fn translated(by: Vector3<Scalar>): Self
  fn grown(by: Scalar): Self
  fn bounds(): Box<Scalar>
  fn combined(other: Self): Self
}

A disc or a ball: a center and a radius, with the boundary inside. contains, encloses, intersects, intersectsRectangle/intersectsBox (a test against the nearest point of the box), closestPoint, distanceTo, translated, grown, bounds, combined, and for a circle area and circumference. Sphere.around(box) is the ball through the corners of a box.

`Segment2`, `Ray2`, `Ray3`#

type Segment2<Scalar: Numeric = Float> {
  from: Vector2<Scalar>
  to: Vector2<Scalar>
  fn step(): Vector2<Scalar>
  fn sideOf(point: Vector2<Scalar>): Scalar
  fn bounds(): Rectangle<Scalar>
  fn intersects(other: Self): Bool
}
extend<Scalar: Signed> Segment2<Scalar> {
  fn manhattanLength(): Scalar
}
extend<Scalar: Real> Segment2<Scalar> {
  fn length(): Scalar
  fn direction(): Vector2<Scalar>
  fn center(): Vector2<Scalar>
  fn at(factor: Scalar): Vector2<Scalar>
  fn closestPoint(to: Vector2<Scalar>): Vector2<Scalar>
  fn distanceTo(point: Vector2<Scalar>): Scalar
  fn intersection(other: Self): Vector2<Scalar>?
}
type Ray2<Scalar: Real = Float> {
  origin: Vector2<Scalar>
  direction: Vector2<Scalar>
  static fn towards(from: Vector2<Scalar>, to: Vector2<Scalar>): Self
  fn at(distance: Scalar): Vector2<Scalar>
  fn hits(circle: Circle<Scalar>): Scalar?
  fn hitsRectangle(rectangle: Rectangle<Scalar>): Scalar?
  fn hitsSegment(segment: Segment2<Scalar>): Scalar?
}
type Ray3<Scalar: Real = Float> {
  origin: Vector3<Scalar>
  direction: Vector3<Scalar>
  static fn towards(from: Vector3<Scalar>, to: Vector3<Scalar>): Self
  fn at(distance: Scalar): Vector3<Scalar>
  fn hits(sphere: Sphere<Scalar>): Scalar?
  fn hitsPlane(plane: Plane<Scalar>): Scalar?
  fn hitsBox(box: Box<Scalar>): Scalar?
  fn hitsTriangle(triangle: Triangle3<Scalar>): Scalar?
}

A Segment2 is the straight piece of line between two points, with both ends belonging to it: step, sideOf, bounds and intersects under Numeric, and length, direction, center, at, closestPoint, distanceTo and intersection (the crossing point) under Real.

A ray is a half-line, and every hit test answers how far along the ray the hit is, measured in the length of direction - not the point. That is what a caller compares to find the nearest of several hits, and ray.at(distance) turns it back into a point. A ray with a direction of length one therefore answers distances. Ray2 hits a Circle, a Rectangle (the slab test) and a Segment2; Ray3 hits a Sphere, a Plane, a Box and a Triangle3. A ray that starts inside a shape answers 0, and a ray with no direction answers None.

`Triangle2`, `Triangle3`#

type Triangle2<Scalar: Numeric = Float> {
  first: Vector2<Scalar>
  second: Vector2<Scalar>
  third: Vector2<Scalar>
  fn signedArea(): Scalar
  fn bounds(): Rectangle<Scalar>
  fn edges(): List<Segment2<Scalar>>
  fn contains(point: Vector2<Scalar>): Bool
  fn translated(by: Vector2<Scalar>): Self
}
extend<Scalar: Signed> Triangle2<Scalar> {
  fn doubledArea(): Scalar
}
extend<Scalar: Real> Triangle2<Scalar> {
  fn area(): Scalar
  fn center(): Vector2<Scalar>
  fn closestPoint(to: Vector2<Scalar>): Vector2<Scalar>
  fn distanceTo(point: Vector2<Scalar>): Scalar
}
type Triangle3<Scalar: Numeric = Float> {
  first: Vector3<Scalar>
  second: Vector3<Scalar>
  third: Vector3<Scalar>
  fn firstEdge(): Vector3<Scalar>
  fn secondEdge(): Vector3<Scalar>
  fn doubledAreaVector(): Vector3<Scalar>
  fn bounds(): Box<Scalar>
  fn translated(by: Vector3<Scalar>): Self
}
extend<Scalar: Real> Triangle3<Scalar> {
  fn normal(): Vector3<Scalar>
  fn area(): Scalar
  fn plane(): Plane<Scalar>
  fn center(): Vector3<Scalar>
  fn weightsOf(point: Vector3<Scalar>): (first: Scalar, second: Scalar, third: Scalar)
  fn contains(point: Vector3<Scalar>): Bool
}

Three corners. The winding is not fixed: signedArea is positive where the corners run from the first axis towards the second and negative the other way, and contains works for both. In space the normal follows the right-handed order of the corners, plane answers the plane they lie in, and weightsOf writes a point as a mix of the three corners - which is what says whether a crossing of the plane is a crossing of the face.

`Polygon`#

type Polygon<Scalar: Numeric = Float> {
  corners: List<Vector2<Scalar>>
  static fn ofTriangle(triangle: Triangle2<Scalar>): Self
  static fn ofRectangle(rectangle: Rectangle<Scalar>): Self
  fn isEmpty(): Bool
  fn edges(): List<Segment2<Scalar>>
  fn signedDoubledArea(): Scalar
  fn bounds(): Rectangle<Scalar>
  fn isConvex(): Bool
  fn containsConvex(point: Vector2<Scalar>): Bool
  fn contains(point: Vector2<Scalar>): Bool
  fn intersectsConvex(other: Self): Bool
  fn translated(by: Vector2<Scalar>): Self
}
extend<Scalar: Signed> Polygon<Scalar> {
  fn doubledArea(): Scalar
}
extend<Scalar: Real> Polygon<Scalar> {
  fn area(): Scalar
}

A closed chain of corners, the last joined back to the first. The convex tests are the ones to reach for - containsConvex is a side test per edge and intersectsConvex is the separating axis test - and isConvex is what a program establishes once instead of per query. contains works for any polygon, including one with a dent, by counting the crossings of a ray. Fewer than three corners describe no area, and every test answers false for such a polygon.

`Plane`#

type Plane<Scalar: Real = Float> {
  normal: Vector3<Scalar>
  distance: Scalar
  static fn through(point: Vector3<Scalar>, normal: Vector3<Scalar>): Self
  static fn ofPoints(first: Vector3<Scalar>, second: Vector3<Scalar>, third: Vector3<Scalar>): Self
  fn signedDistanceTo(point: Vector3<Scalar>): Scalar
  fn distanceTo(point: Vector3<Scalar>): Scalar
  fn isInFront(point: Vector3<Scalar>): Bool
  fn closestPoint(to: Vector3<Scalar>): Vector3<Scalar>
  fn mirrored(point: Vector3<Scalar>): Vector3<Scalar>
  fn flipped(): Self
}

A flat surface in space, as the normal that points away from its front and the distance along that normal. signedDistanceTo is positive in front and negative behind, and which of the two a program calls "outside" is the program's own business. through, ofPoints, distanceTo, isInFront, closestPoint, mirrored and flipped.

std/linear - the vectors every shape is made of, and Fixed, the scalar that makes these tests bit-identical everywhere.
std/number - Numeric and Real, the two bounds the shapes layer along.

Import#

The half-open rule#

Declarations#

Rectangle, Box#

Circle, Sphere#

Segment2, Ray2, Ray3#

Triangle2, Triangle3#

Polygon#

Plane#

Related#

`Rectangle`, `Box`#

`Circle`, `Sphere`#

`Segment2`, `Ray2`, `Ray3`#

`Triangle2`, `Triangle3`#

`Polygon`#

`Plane`#