Chapter I.

Math

ear.math

An origami math library wil contain a fair bit of geometry and linear algebra; as it turns out a lot of time is spent calculating the intersection of shapes. The core of the math engine is accessible through ~10 math primitives.

Vector / Point

ear.vector

Vectors can be any dimension with some methods that treat them like vectors, some like points, and some specifically for 2D and 3D.

var vec = ear.vector(0.5, 0.666)
vec.normalize()

2D and 3D specific methods often end in numbers like cross2 and cross3.

blue1 = red1.lerp(red2, t)
blue2 = red2.lerp(red3, t)
yellow = blue1.lerp(blue2, t)

The vector object is a Javascript array of numbers. A number can be accessed using either brackets [ ] or dot notation with x, y, z. Brackets are required beyond 3-dimensions.

vector.x  // the x value
vector[0] // also, the x value

This vector object is immutable; each method returns a new, transformed vector.

MATRIX

Matrices are powerful representations of geometric transformations. Inside of one matrix can contain instructions for any number of rotations, translations, reflections, scaling, shearing; and it can tell you things like whether a polygon has been flipped over.

A 3x4 matrix encodes 3D space, its columns from left to right:

Each matrix us also a one-dimensional Javascript array, each component can be accessed with square brackets using the indices above.

Matrices are stored column-major, which lines up vector components so each basis vector is contiguous (eg. translation is indices 9, 10, 11).

Folding

An example of a matrix in action is a simulation of fold, using a reflection matrix.

Given a fold line, divide the polygon into two parts (split_convex_polygon) and build a reflection matrix from this fold line. Transform the folding polygon with this matrix.

This library makes it as easy as possible to generate a reflection matrix. Any line type (line, ray, segment) can be turned into a reflection matrix.

var segment = ear.segment(point1, point2)
var matrix = segment.reflectionMatrix()

Unlike vectors and most objects, matrices are mutable; each method modifies the matrix.

multiply(matrix)
determinant()
inverse()
translate(x, y, z)
rotate(radians, vector, origin)
scale(amount)
reflectZ(vector, origin)
transform(vector or line)

Lines, Rays, Segments

lines extend infinitely in both directions

rays extend infinitely in one direction

line segments are bound by two endpoints

Lines and rays are created by specifying a direction vector and an origin. Segments are initialized with two endpoints.

ear.line(vector, origin)
ear.ray(vector, origin)
ear.segment(point, point)

If you leave out the origin argument it is assumed to be (0, 0, 0). Also, it may be easier to create lines and rays with the static method: fromPoints.

ear.line.fromPoints()
ear.ray.fromPoints()
ear.segment()

When a method requires more than one point, points are grouped using arrays.

Lines, rays, and segments all share a common prototype, thus share some properties and methods, like the method nearestPoint.

var point = segment.nearestPoint()

All three have an origin and vector property, which is what a line requires for initialization.

var segment = ear.segment(1, 0, 2, -1)
var line = ear.line(segment)

A segment being converted into a line (infinite length).

In Origami and Geometric Constructions Robert Lang outlines a line parameterization that is incredibly useful and will become more relevant in Chapter IV.

Lines can be uniquely defined by a unit normal vector u and the shortest distance to the origin d.

Polygons

Polygons are created from an ordered set of points which define the boundary. It's possible to create non-convex and self-intersecting polygons.

ear.polygon(points)

Many of the methods in this library are built for convex polygons.

Convex Polygon

ear.polygon.convexHull(...points)

Convex hull is a static initializer that will also fix any winding issues in an ordered set of points.

polygon.straightSkeleton()

The straight skeleton is an operation on a polygon that creates a flat-foldable crease pattern, and when folded, the boundary becomes collinear.

Rect

ear.rect(width, height)
ear.rect(x, y, width, height)

The rect also inherits the polygon prototype. All polygon types have these methods:

polygon.area()
polygon.centroid()
polygon.enclosingRectangle()
polygon.straightSkeleton()
polygon.nearest(point)
polygon.scale(magnitude, centerPoint)
polygon.rotate(angle, centerPoint)
polygon.translate(vector)
polygon.transform(matrix)
polygon.intersect(anyShape)
polygon.overlap(anyShape)
polygon.split(line)
polygon.clip(anyLine)
polygon.svgPath()

Circle

ear.circle(radius)
ear.circle(x, y, radius)
ear.circle(origin, radius)

Circle does not inherit the polygon methods, it has its own methods.

circle.nearestPoint(point)
circle.intersect(any_shape)
circle.points(count = 128)
circle.polygon()
circle.segments()
circle.svgPath()

Remember, objects are immutable. If you call a object's method expecting a change, check the return value for a new modified object.

Intersections

Epsilon

The epsilon is the small number used to decide whether floating point numbers are equal.

This library intends to be useful at any scale; the sketches here demonstrate this. The epsilons on this page have been increased so large to the point of being visible.

When a method uses an epsilon, the final parameter is the optional epsilon parameter, with a default value of 1e-6.

Collinearity

Is a point collinear to a line (line, ray, segment)?

var point = ear.vector()
var line = ear.line()
point.overlap(line)
line.overlap(point)

Endpoints can be treated as inclusive or exclusive, which includes or excludes the area around their endpoints.

var segment = ear.segment()
segment.inclusive()
// or
segment.exclusive()

Vectors, rays, segments, and polygons (rect, circle) can be made inclusive and exclusive.

Inclusivity for polygons includes or excludes the boundary. This is useful when asking if points are inside or outside, and it's important to include or ignore points on the boundary.

var poly = ear.polygon()
polygon.inclusive()
polygon.overlap(point)

Polygons boundaries in black, including and excluding the area around them.

Remember the epsilon in these sketches have been heavily magnified. These calculations are typically happening at an imperceptable scale.

Overlap, Intersections, and Clipping

Overlap

ear.overlap(a, b)

The overlap method is accessible from the top level, or as a member function on primitives.

var segment1 = math.segment().inclusive()
var segment2 = math.segment().exclusive()
segment1.overlap(segment2)

Inclusive and exclusive overlap

Overlap methods are just intersection methods that return a boolean instead of a point. In some cases this calculation is faster.

polygon1.overlap(polygon2)

These are the algorithms that get called behind the curtain. They are available to be called directly, and require more parameters than the other interface.

ear.math.overlap_convex_polygon_point(poly, point, func, epsilon)
ear.math.overlap_convex_polygons(poly1, poly2, fn_line, fn_point, epsilon)
ear.math.overlap_line_line(aVector, aOrigin, bVector, bOrigin, aFunction, bFunction, epsilon)
ear.math.overlap_line_point(vector, origin, point, func, epsilon)

The overlap algorithms

Some of these parameters are domain functions. These functions mark the span of an acceptable result against the vector of the primitive, including determining inclusivity. These functions are also available:

ear.math.exclude
ear.math.exclude_l
ear.math.exclude_r
ear.math.exclude_s
ear.math.include
ear.math.include_l
ear.math.include_r
ear.math.include_s

The inclusive and exclusive domain functions for general case, lines, rays, or segments.

Intersect

ear.intersect(a, b)

The intersect function will accept most combinations of pairs of primitives, like lines, circles, polygons, also available at the top level or as methods on objects.

polygon.intersect(segment)
circle.intersect(segment)
circle1.intersect(circle2)

Intersections involving convex polygons results in 0, 1, or 2 points, they return an array of points.

Intersections limited to lines only result in 0 or 1 point, they do not return an array, just a point or undefined.

Again, this method is calling other methods under the hood. These are available to you as well.

ear.math.intersect_convex_polygon_line(poly, vector, origin, fn_poly, fn_line, epsilon)
ear.math.intersect_circle_circle(c1_radius, c1_origin, c2_radius, c2_origin, epsilon)
ear.math.intersect_circle_line(circle_radius, circle_origin, line_vector, line_origin, line_func, epsilon)
ear.math.intersect_line_line(aVector, aOrigin, bVector, bOrigin, aFunction, bFunction, epsilon)

Clip

Clip is only available on polygons right now, and it only operates on lines, rays, and segments.

Splitting a line by a convex polygon will result in a smaller segment.

poly.clip(line)
poly.clip(ray)
poly.clip(segment)

Increasing the epsilon on the clip method demonstrates the priorities. In both inclusive cases the resulting segment must not be shorter than 2 * epsilon.

The inclusive result can extend beyond the polygon within one epsilon unit, and the exclusive cases removes parallel edges by testing exclusive polygon-point overlap with the segment's midpoint.

Angles and Winding-order

ear.math.is_counter_clockwise_between(circle, angle1, angle2)

The space between two vectors creates two interior angles. It's important to distinguish between vectors a and b the clockwise or the counter-clockwise interior angle.

Currently there is no object-style interface to angle calculations, for now you need to call back end math functions directly.

Get the interior angle between two radians/vectors.

ear.math.clockwise_angle_radians(angle1, angle2)
ear.math.counter_clockwise_angle_radians(angle1, angle2)
ear.math.clockwise_angle2(vector1, vector2)
ear.math.counter_clockwise_angle2(vector1, vector2)

When operating on angles, these methods seamlessly wrap around from 2π to 0 and include negative radians as similar to their positive counterparts.

Sorting

ear.math.counter_clockwise_vector_order(...vectors)
ear.math.counter_clockwise_radians_order(...angles_in_radians)

Sort an array of vectors or angles, but return the result as an array of indices instead of modifying the array.

The first argument serves as the "origin" angle that other vectors are sorted around". Index 0 will always be 0.

Sorting is required for such simple things as measuring the interior angles between consecutive vectors.

The red line is the first in the vector array; you can tell the algorithm sorts around it as the sector colors shift more when it is moved.

Bisect

ear.math.clockwise_bisect2(vector1, vector2)
ear.math.counter_clockwise_bisect2(vector1, vector2)

A bisection could refer to the smaller or the larger angle; these methods return one solution by clarifying clockwise or counter-clockwise.

Bisecting two lines is effectively origami axiom #3, and results in two solutions unless the lines are parallel.

lineA.bisect(lineB)

The parallel case maintains the index position of each line. The lines are sorted based on if the parameter lines are running in the same direction or not (dot product > 0).

For trisections and beyond, use the general subsect methods.

ear.math.counter_clockwise_subsect2(divisions, vectorA, vectorB)
ear.math.counter_clockwise_subsect_radians(divisions, angleA, angleB)