### Chapter I.

# Math

An origami math library contains a fair bit of geometry and linear algebra, as it turns out a lot of time is spent calculating the intersection of shapes. A lot of these intersections are edge-cases (collinear, parallel) so we should have decent control over the epsilon.

`ear.`math

Every method discussed here is found under the "math" key except for about 10 object-oriented style primitives, these are at the top-level; let's begin with a few of these.

## 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.

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

var vec = ear.vector (0.5 , 0.666 )

vec.normalize ()

↳

`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:

- x-axis basis vector
- y-axis basis vector
- z-axis basis vector
- translation vector

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).

## 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 ()

`ear.math.`straight_skeleton (points )

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 )

### Circle

`ear.`circle (radius )

ear.circle (x , y , radius )

ear.circle (origin , radius )

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

`ear.math.`point_on_ {line/ray/segment }_ {inclusive/exclusive }

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

Endpoints can be treated as **inclusive** or **exclusive**, which includes or excludes the area around their endpoints, valid for rays and segments but not lines.

`ear.math.`point_in_convex_poly_inclusive (point , poly )

ear.math.point_in_convex_poly_exclusive (point , poly )

Inclusive and exclusive methods on polygons treat the boundary outset or inset respectively.

Unlike other geometry-heavy fields, like game development, origami designs are filled with symmetry and collinearity. For example, being able to exclude an edge that lies along a polygon's edge is necessary; handling epsilons with great care is how this library achieves this.

### Overlap, Intersections, and Clipping

**overlap**returns true or false**intersect**returns points, or undefined if no intersection**clip**returns segments, or undefined if no intersection

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.

`ear.math.`overlap_line_ray_inclusive (vectorA , originA , vectorB , originB )
ear.math.overlap_ray_segment_exclusive (vector , origin , segA1 , segA2 )
ear.math.overlap_segment_segment_exclusive (a1 , a2 , b1 , b2 )

Not a complete list

Any combination of line/ray/segment followed by either "inclusive" or "exclusive"; there are 12 methods. Each of these is really just a wrapper around the overlap algorithm, which you can call directly:

The overlap algorithm

`ear.math.`overlap_lines (aVector , aOrigin , bVector , bOrigin , compA , compB )

To call this method you need to convert segments into vector-origin form, and provide two comparison functions. This gives you the freedom to compare one inclusive against an one exclusive.

`ear.math.exclude_l`

ear.math.exclude_r

ear.math.exclude_s

`ear.math.include_l`

ear.math.include_r

ear.math.include_s

The inclusive and exclusive comparison functions for lines, rays, or segments.

`polygon1.`overlaps (polygon2)

### Intersect

`ear.`intersect (a , b )

The **intersect** function will accept most combinations of pairs of primitives, like lines, circles, polygons; this is the most accessible interface to intersections.

`polygon.`intersect (segment)

circle.intersect (segment)

The function also exists as a method property on objects. This interface treats intersections as **exclusive**. For the other options see below.

`circle1.`intersect (circle2)

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

// polygon
convex_poly_line_exclusive(poly , vector , origin )
convex_poly_line_inclusive(poly , vector , origin )
convex_poly_ray_exclusive(poly , vector , origin )
convex_poly_ray_inclusive(poly , vector , origin )
convex_poly_segment_exclusive(poly , vector , origin )
convex_poly_segment_inclusive(poly , vector , origin )
// circle
circle_circle(circleA , circleB )
circle_line(circle , line )
circle_ray(circle , ray )
circle_segment(circle , segment )
// lines
intersect_line_seg_exclude(vector , origin , pt0 , pt1 )
intersect_line_seg_include(vector , origin , pt0 , pt1 )
intersect_ray_seg_exclude(vector , origin , pt0 , pt1 )
intersect_ray_seg_include(vector , origin , pt0 , pt1 )
intersect_seg_seg_exclude(a0 , a1 , b0 , b1 )
intersect_seg_seg_include(a0 , a1 , b0 , b1 )

Even *further* under the hood are the actual intersect algorithms. Just like overlap, these require you pass in line/ray/segment comparison functions.

`ear.math.`intersect_lines (aVector , aOrigin , bVector , bOrigin , compA , compB )

`ear.math.`intersect_circle_line (circleRadius , circleOrigin , vector , origin , comparisonFunc )

The line-line and circle-line intersect algorithms

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.

### Clip

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

`poly.`clipLine (line )

poly.clipRay (ray )

poly.clipSegment (segment )

## 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.

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.

`ear.math.`bisect_lines2 (vectorA , originA , vectorB , originB )

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 )