CHAPTER II.

GRAPHS

A graph is a collection of vertices, edges, and faces. 

var graph = ear.graph()

When two lines meet at a common location, we want this point to be shared between them. When one endpoint moves, the other follows. This is just one of the many reasons we use a graph.

Adjacency

adjacent vertices 

graph.vertices[].vertices
graph.edges[].vertices

adjacent edges 

graph.vertices[].edges
graph.edges[].edges

We will embed our graphs in 2D (crease pattern) or 3D space (folded forms) to model origami.

Components 

graph.vertices
graph.edges
graph.faces

Edges are defined by the vertices they connect. Faces can be defined by either their edges or vertices.

Components are referenced by their integer indices (as opposed to a memory pointer). 

var nearest = graph.nearest(point)
{ vertex: undefined
  edge: undefined
  face: undefined
  vertices_coords: undefined
  edges_assignment: undefined
  ... }

Adjacency refers to edge-adjacency. "Nearest" in this case refers to nearest in Euclidean space.

FOLD

In 2016, a file format was developed specifically for origami: the FOLD format. The benefit of this JSON-based format is that it integrates seamlessly into this Javascript library. 

FOLD graph
┃
┃ // vertices
┣━ vertices_coords
┣━ vertices_vertices
┣━ vertices_edges
┣━ vertices_faces
┃
┃ // edges
┣━ edges_vertices
┣━ edges_faces
┃
┃ // faces
┣━ faces_vertices
┗━ faces_edges
┗━ faces_faces

FOLD is JSON-based, it's human-readable and it's possible to peek inside and modify the contents manually. 

{
  vertices_coords: [[0, 0], [1, 0], [1, 1], [0, 1]],
  edges_vertices: [[0, 1], [1, 2], [2, 3], [3, 0], [0, 2]],
  edges_assignment: ["B", "B", "B", "B", "M"]
}

But you don't have to learn to read FOLD format. This library has methods for adding and modifying existing vertices, edges, and faces.

Creating Graphs

The graph itself is simply a Javascript object. 

var myGraph = {}

Each method has its own requirements for which fields need to be populated, but for many, a completely empty "graph" like above is valid.

Graph methods are found under this key: 

ear.graph

Graph methods tend to follow a similar form: the first parameter is the graph object, additional parameters follow, if they exist. 

ear.graph.populate(graph)
ear.graph.translate(graph, x, y)

Alternatively, this library offers an object-oriented style: create a graph object, a child of a graph prototype which contains member functions. 

var myGraph = ear.graph()

Rabbit Ear graph methods are bound such that the first parameter (specify the graph) can now be left out, as it is understood to be this object. 

var myGraph = ear.graph()
myGraph.populate()
myGraph.translate(2, 1)
var myGraph = {}
ear.graph.populate(myGraph)
ear.graph.translate(myGraph, 2, 1)

Going forward, this page will introduce methods using the general (not object-oriented) syntax. Just know that this approach exists as well.

Static Initializers

When modeling origami you tend to start with a boundary. Any regular polygon boundary can be made with this initializer. 

var myGraph = ear.graph.polygon(6) // hexagon

Adding Components

Vertices

addVertices makes sure that no two vertices exist in the same space, within an adjustable epsilon. 

graph.addVertices([[x, y], [x, y], ...])

If anything goes wrong (like from manual editing, or file-import) you can call removeDuplicateVertices to clean up vertices.

Edges

splitEdge adds one new vertex and carefully rebuilds the graph around it, adding new edges and updating any adjacent faces. 

graph.splitEdge(edge, coords)

Give an edge index and coordinates for a new vertex. If no coordinates are given, it will be split at the midpoint.

Faces

Splitting a face is more complex; the number of all three component is altered. 

graph.splitFace(face, line)
graph.splitFace(face, vector, origin)

Give a face index and a line by specifying the line's vector and origin.

Populating arrays

Without modifying the geometry of a graph we can construct more arrays that express relationships between components, such as adjacencies. 

graph.populate()

This is useful when importing a graph from other places, you can specify only the edges, and this method will build all the faces. 

vertices_coords: [[0,0], [1,0], [1,1], [0,1]]
edges_vertices: [[0,1], [1,2], [2,3], [3,0], [0,2]]
edges_assignment: ["B", "B", "B", "B", "M"]

The graph above becomes: 

vertices_coords: [[0,0], [1,0], [1,1], [0,1]]
vertices_vertices: [[1,2,3], [2,0], [0,1,3], [0,2]]
vertices_edges: [[0,3,4], [0,1], [1,2,4], [2,3]]
vertices_faces: [[0,1], [0], [0,1], [1]]
edges_vertices: [[0,1], [1,2], [2,3], [3,0], [0,2]]
edges_edges: [[3,4,1], [0,2,4], [1,4,3], [2,0,4], [0,3,1,2]]
edges_faces: [[0], [0], [1], [1], [0,1]]
edges_foldAngle: [0, 0, 0, 0, -180]
edges_assignment: ["B", "B", "B", "B", "M"]
faces_vertices: [[2,0,1], [3,0,2]]
faces_edges: [[4,0,1], [3,4,2]]
faces_faces: [[1], [0]]

Individual Methods

Populate calls a bunch of methods, each of which is also available for you to call individually. However, unlike populate, these methods will not modify the input graph; they return the requested data as an array. 

ear.graph.makeVerticesVertices(graph)
ear.graph.makeVerticesEdges(graph)
ear.graph.makeVerticesEdgesUnsorted(graph)
ear.graph.makeVerticesFaces(graph)
ear.graph.makeVerticesFacesUnsorted(graph)
ear.graph.makeEdgesEdges(graph)
ear.graph.makeEdgesFaces(graph)
ear.graph.makeEdgesFacesUnsorted(graph)
ear.graph.makeEdgesFoldAngle(graph)
ear.graph.makeEdgesAssignment(graph)
ear.graph.makeFacesVerticesFromEdges(graph)
ear.graph.makeFacesEdgesFromVertices(graph)
ear.graph.makePlanarFaces(graph)
ear.graph.makePlanarFacesVertices(graph)
ear.graph.makePlanarFacesEdges(graph)
ear.graph.makeFacesFaces(graph)

ear.graph.makeVerticesToEdge(graph)
ear.graph.makeVerticesToEdgeBidirectional(graph)
ear.graph.makeVerticesToFace(graph)
ear.graph.makeVerticesVerticesVector(graph)
ear.graph.makeVerticesSectors(graph)
ear.graph.makeVerticesCoordsFolded(graph, rootFace)
ear.graph.makeVerticesCoordsFlatFolded(graph, rootFace)
ear.graph.makeEdgesCoords(graph)
ear.graph.makeEdgesVector(graph)
ear.graph.makeEdgesLength(graph)
ear.graph.makeEdgesCoords(graph)
ear.graph.makeEdgesEdgesParallel(graph, epsilon)
ear.graph.makeEdgesEdgesCrossing(graph, epsilon)
ear.graph.makeEdgesEdgesIntersection(graph, epsilon)
ear.graph.makeEdgesEdgesParallelOverlap(graph, epsilon)
ear.graph.makeEdgesIsFlatFolded(graph)
ear.graph.makeEdgesFacesOverlap(graph, epsilon)
ear.graph.makeFacesFacesOverlap(graph, epsilon)
ear.graph.makeFacesCenter(graph)
ear.graph.makeFacesCenterQuick(graph)
ear.graph.makeFacesMatrix(graph, rootFace)
ear.graph.makeFacesMatrix2(graph, rootFace)
ear.graph.makeFacesWinding(graph)
ear.graph.makeFacesWindingFromMatrix(faces_matrix)
ear.graph.makeFacesWindingFromMatrix2(faces_matrix2)

Additional Methods

Minimum Spanning Tree 

graph.faceSpanningTree(5)

A minimum face spanning tree builds a tree from a root face which visits every other face exactly once. Any face can be the starting face.

This will be useful for folding a crease pattern.

Boundary

Polygons are defined by their vertices; and these vertices must be sorted.

Because edges are stored in their arrays in no particular order, finding the boundary requires walking around the boundary edges until the algorithm ends up where it began. 

graph.boundary()
ear.graph.getBoundary(graph)

This method returns both edges and vertices, sorted clockwise / counter-clockwise.

todo: support for multiple boundaries; a method that tests connected vertices.

Transformations 

ear.graph.translate(graph, x, y, z)
ear.graph.scale(graph, scale, origin)
ear.graph.rotateZ(graph, radians)
ear.graph.transform(graph, matrix)

Affine transformations include rotate, scale, and translate, and only operate on the vertices of the graph.

The folding method is a more complex operation that applies different transforms to different vertices. But still, only the vertices are changed. 

ear.graph.makeVerticesCoordsFolded(graph)
ear.graph.makeVerticesCoordsFlatFolded(graph)

Explode Faces 

graph.explodeFaces()

This effect requires constructing an entirely new graph. As adjacent faces normally share vertices, each vertex must be cloned for every face it touches.

Counting Components 

ear.graph.count(graph, "vertices")

Faces, for example, can be defined by their edges or vertices. You can't depend on one or the other existing.

Querying the number of components in the graph is simple, it just has to be performed on every relevant array. The count method searches these arrays and returns the longest length if there are competing results. 

ear.graph.count.faces(graph)
ear.graph.count.edges(graph)
ear.graph.count.vertices(graph)

The implied count is useful for things like abstract graphs, where a search for vertices will look inside things like "faces_vertices" for the largest index. 

ear.graph.countImplied.faces(graph)
ear.graph.countImplied.edges(graph)
ear.graph.countImplied.vertices(graph)

Rebuilding Graphs

Many people will have an origami crease pattern drawn in a vector-image drafting software. To import these files into FOLD format, some cleanup will be necessary.

Clean 

ear.graph.clean(graph)

Clean is a fast method that fixes simple issues with validity, it removes:

Clean does not, notably, split overlapping edges and place a vertex at their intersection. This is a planar graph, and building a planar graph takes a bit more care.

Planar Graphs

In planar graphs, it's a violation for two edges to cross.

These are the typical planar graph violations that need addressing when importing from other software:

An origami does not need to be a planar graph (a folded origami exists in 3D), but a crease pattern does.

Fragment

The fragment method converts a graph into a planar graph by solving the first issue: lines crossing other lines. It also walks all edges and constructs all valid faces.

Faces can have leaf edges poking inside, this is still considered valid.

edge

face

ear.graph.fragment(graph)

Fragment substitutes overlapping edges with 4 edges and a new vertex, it splits an edge if another endpoint lies collinear along it, and merges duplicate vertices.

epsilon

An edge is split if vertices are collinear within an epsilon.

The final parameter in many of these methods is an optional epsilon. By default it is precise (1e-6). When importing crease patterns that were made in some vector drawing program you might want to decrease the precision. 

ear.graph.fragment(graph, epsilon = 1e-6)
ear.graph.removeDuplicateVertices(graph, epsilon = 1e-6)

Fragment is necessary when importing a pattern from an outside environment, but it is expensive and destructive too (rebuilds all faces).

Planar Segment

Once your graph is already planar, or if you are starting from scratch, use addPlanarSegment to add a segment. This method only modifies what is necessary. 

ear.graph.addPlanarSegment(graph, point1, point2)

Add a segment between two points (point1, point2)

The edges-segment intersection test uses a bounding box to filter possible candidates to uncover intersections.

Face-Finding

The face-finding algorithm walks from edge to edge turning at each corner. This requires vertices be merged, without them corners don't exist.

epsilon

This library can build faces in 2D only, and can only be guaranteed if no edges are crossing. 

ear.graph.makePlanarFaces(graph)

This method ensures the faces are counter-clockwise and will exclude the one face which winds backwards around the entire boundary.

Or, can call these subroutines directly: 

ear.graph.counterClockwiseWalk(graph, vertex0, vertex1)
ear.graph.planarVertexWalk(graph)

counterClockwiseWalk will look for a single face by starting at vertex0 and begin walking to vertex1, and planarVertexWalk will give you all faces including the outer boundary.

Merge Vertices 

ear.graph.removeDuplicateVertices(graph)

Removing duplicate vertices will search all the component arrays and make sure the removed vertices are now pointing to the one remaining vertex.

Let's take a closer look at this remove operation.

Advanced: Graph Changes

Imagine adding a crease to a crease pattern, and this one crease becomes three graph edges having been split across existing lines. If you intend to update mountain/valley assignments for example, you need those three indices. This section explains how indices shift and how to keep track of changes even after many operations have taken place.

Removing Components

This library contains methods for removing bad geometry from graphs. 

ear.graph.removeCircularEdges(graph)
ear.graph.removeDuplicateEdges(graph)
ear.graph.removeIsolatedVertices(graph)
ear.graph.removeDuplicateVertices(graph, epsilon)

Each of these methods calls the remove method: 

ear.graph.remove(graph, key, indices)

Remove

Consider this, the removal of edges at index 2 and 4. 

edges_vertices: {
  [[0,1], [2,3], XXXX, [5,2], XXXX, [1,3]]
}

When a component is removed the following array elements shift up which breaks all references in other arrays. The remove method takes care of this. 

ear.graph.remove(graph, "edges", [2, 4])

Calling the method modifies the input graph and returns a summary of changes as an array that relates each index to its new location. 

[0, 1, undefined, 2, undefined, 3]

Notice how the length matches the size of the array before the change. The values in the array answer the question:

"What is the new location of the old component?"

I've been calling these arrays maps.

Maps

Maps are useful for keeping track of changes from outside the graph. Here's an example:

Imagine a game of dodge ball as a graph, where players are vertices and one of the vertices is a team leader. Players are removed after one round. The last line updates the team leader to its new index. 

var teamLeader = 5;
var changeMap = ear.graph.remove(graph, "vertices", playersHit);
teamLeader = changeMap[teamLeader];

Updating multiple pointers is also one line of code: 

leaders = leaders.map(i => changeMap[i]);

Types of maps

So far, we've only looked at methods that remove. An example of a method that adds components is the fragment method, in which a single edge can turn into multiple edges. A map to describe this change requires an array at every index. 

[ [0, 1, 2], [3, 4], [5], [6, 7, 8, 9] ]

Remember a map answers the question,

"What is the new location of the old component?"

and fragment converts one edge to multiple edges. However, it is possible to represent the inverse relationship, posing and answering the question:

"What is the old location of the new component?"

These arrays have a length that matches the geometry after the change, better at representing changes which add entries. This kind of map with the same example above looks like: 

[0, 0, 0, 1, 1, 2, 3, 3, 3, 3]

I've been calling this kind of map a backmap; it looks back in the history, it relates the current state to the state before the change. The first kind of map we talked about is a nextmap.

All methods in this library, by default, use nextmap.

Invert

The invert method will convert one nextmap to a backmap, or visa versa. 

ear.graph.invertMap([0, [1, 4], 6])
 -> [0, 1, undefined, 1, 2]

Combining Maps

What makes maps really powerful is the ability to track changes across multiple operations on a graph. 

ear.graph.mergeNextmaps(...maps)

If you perform multiple operations on a graph and save each map you can merge the maps to make one map reflecting the entire change from start to finish. 

// start with 7 components
[0, 1, 2, 3, 4, 5, 6]
// merge 2 duplicate edges
[0, 1, 2, 1, 3, 2, 4]
// fragment, adds 4 edges
[0, [1, 2], 3, [4, 5, 6], [7, 8]]
// merge 2 more edges
[0, 1, 2, 3, 0, 4, 3, 5, 6]

The merged map relates each index before the first change to after the final change. 

[0, [1, 2], 3, [1, 2], [0, 4, 3], 3, [5, 6]]

Parameters should be ordered from earliest to most recent, the first change in time should be first. 

ear.graph.mergeNextmaps(first, second, ..., final)

Method responses

Given a square graph with 4 vertices and edges,

attempting to add two vertices results in only one new unique vertex.

The response object is a map of your parameters from the method call.

Notice the second vertex parameter already existed at index 2. 

ear.addVertices(graph, [[0.5, 0.5], [1, 1]])
// returns
[4, 2]

All methods that modify a graph return a response object that summarizes the changes.

Each method has a unique summary.

These remove methods return an object containing a nextmap and the indices that were removed. The indices in the remove array relate to indices before the change. 

ear.graph.removeCircularEdges(graph)
ear.graph.removeDuplicateEdges(graph)
ear.graph.removeIsolatedVertices(graph)
ear.graph.removeDuplicateVertices(graph, epsilon)
{
  map: [0, 1, 2, 3, 1, 4, 3, 0, 5, 6]
  remove: [4, 6, 7]
}

todo: remove collinear vertices

These two add methods simply return a nextmap. Adding is generally more simple than removing. 

ear.graph.addVertices(graph, ...)
ear.graph.addEdges(graph, ...)
[4, 2]

Splitting an edge creates one new vertex, removes one edge, and provides one edge nextmap. 

ear.graph.splitEdge(graph, ...)
{
  vertex: 5,
  edges: {
    map: [0, 1, 2, [3, 4], 5, 6],
    remove: 3,
  }
}

Splitting a face creates two new vertices (or maps to one or two existing), removes one face and contains a nextmap containing two new faces, removes up to two edges, creates one new edge (which splits the face), and provides a nextmap which contains the up to four new edges that were made when splitting edges. 

ear.graph.splitFace(graph, ...)
{
  vertices: [8, 13],
  faces: {
    map: [0, [2, 3], 1],
    remove: 1,
  },
  edges: {
    map: [0, 1, 2, [6, 7], 3, 4, [8, 9], 5],
    new: 8,
    remove: [3, 6]
  }
}

Fragment returns a nextmap for edges. 

ear.graph.fragment(graph)
{
  edges: {
    map: [[0, 1], [2, 3, 4], [5, 6, 7], [8, 9, 10, 11]]
  }
}

todo: include vertices nextmap

Acknowledgements

Interactive graphs at the top of this page are force direct graphs from d3.js.