CHAPTER II.

GRAPHS

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

var graph = ear.graph()

Graphs don't need to exist in 2D space (or any space), they are an abstract map showing connections between vertices.

Adjacency

adjacent vertices

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

adjacent edges

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

Components

graph.vertices
graph.edges
graph.faces

Components are referred to by their indices.

Component queries will return an integer; this is the component's index in its arrays.

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

...including all FOLD arrays in the graph, more about these below.

FOLD

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

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 not impossible 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"]
}

This library makes it so you don't have to learn the FOLD format. We have methods to add vertices, edges, and faces.

Creating Graphs

Our graph is simply a Javascript object.

var myGraph = {}

Every method that operates on graphs is found under this key:

ear.graph

Every graph method takes a similar form where the first parameter is the graph; if there are more parameters they come after.

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

There is also an object-oriented approach. The top-level graph key is also a constructor:

var myGraph = ear.graph()

If you prefer the object-oriented approach, all the methods exist on your object, allowing you to leave out the first parameter.

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

Static Initializers

When modeling origami you tend to start with a boundary. All of the regular polygons have named static initializers.

var myGraph = ear.graph.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 you import a FOLD file with already existing vertices, you can call remove_duplicate_vertices at any time 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.

graph.populate()

The populate method will fill out the graph to the best of its ability.

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"]

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. Prerequisites for each method vary.

var array = ear.graph.make_vertices_vertices(graph)

Unlike populate, these methods do not modify the input graph; they construct and return a new array, it's up to you to assign it to the graph if you wish.

ear.graph.make_vertices_edges()
ear.graph.make_vertices_vertices()
ear.graph.make_vertices_faces()
ear.graph.make_vertices_to_edge_bidirectional()
ear.graph.make_vertices_to_edge()
ear.graph.make_vertices_vertices_vector()
ear.graph.make_vertices_sectors()
ear.graph.make_vertices_coords_folded()
ear.graph.make_edges_vertices()
ear.graph.make_edges_edges()
ear.graph.make_edges_faces()
ear.graph.make_edges_foldAngle()
ear.graph.make_edges_assignment()
ear.graph.make_edges_vector()
ear.graph.make_edges_length()
ear.graph.make_edges_collinear_vertices()
ear.graph.make_planar_faces()
ear.graph.make_faces_vertices()
ear.graph.make_faces_edges()
ear.graph.make_faces_faces()
ear.graph.make_face_spanning_tree()
ear.graph.make_faces_matrix()
ear.graph.make_faces_center()
ear.graph.make_faces_coloring_from_matrix()
ear.graph.make_faces_coloring()

More Methods

Minimum Spanning Tree

graph.faceSpanningTree(5)

A minimum face spanning tree finds edge-adjacent faces; any face can be the starting face.

Boundary

Polygons are defined as a sorted array of vertices/edges; required for calculations like intersections.

Because edges are stored in no particular order, finding the boundary requires a sort. This method walks boundary edges until a cycle is found.

graph.boundary()
ear.graph.get_boundary(graph)

Both edges and vertices are included, 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)

We can transform graphs with matrices to rotate, scale, translate the entire graph. But things get more interesting if we apply transformation matrices to subsets of the graph.

graph.folded()
ear.graph.make_faces_matrix(graph)
ear.graph.make_vertices_coords_folded(graph)

Explode Faces

graph.explodeFaces()

Because neighboring faces share vertices, separating faces requires cloning vertices, one unique occurence for every face.

Counting Components

Because the geometry is stored in flat, separate arrays, it's possible that the faces are defined in faces_edges but not faces_vertices; and querying the number of faces by checking faces_vertices will break. Count will search all the keys that begin with "faces_" and return the longest one.

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, a search for vertices will look inside things like "faces_vertices" for the largest index.

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

It's possible that arrays get out of sync, in which case, the longest might not be the correct one. It's very important to watch carefully and never let a component's arrays become unsynchronized.

Rebuilding Graphs

This library supports importing a crease pattern from any vector-based drawing program; but some clean-up is necessary.

Clean

ear.graph.clean(graph)

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

The method supports cleaning vertices too; the second parameter is options.

ear.graph.clean(graph, {
  edges: true,
  vertices: true
})

Clean is meant to modify the graph as little as possible; more information on remove operations after the next section.

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:

Fragment

The fragment method converts a graph into a planar graph by solving the first issue: lines crossing other lines.

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 very precise (1e-6). When importing crease patterns that were made in some vector drawing program you will want to increase this.

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

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; it's not good with higher dimensions. Notice how faces can be built even if edges are crossing.

Merge Vertices

ear.graph.remove_duplicate_vertices(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.

Tracking Changes

Imagine adding a crease to a crease pattern but the crease became three edges due to planar overlaps. 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 them.

Removing Components

This library contains methods for removing bad geometry from graphs.

ear.graph.remove_circular_edges(graph)
ear.graph.remove_duplicate_edges(graph)
ear.graph.remove_isolated_vertices(graph)
ear.graph.remove_duplicate_vertices(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.invert_map([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.merge_nextmaps(...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.merge_nextmaps(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.add_vertices(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.remove_circular_edges(graph)
ear.graph.remove_duplicate_edges(graph)
ear.graph.remove_isolated_vertices(graph)
ear.graph.remove_duplicate_vertices(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.add_vertices(graph, ...)
ear.graph.add_edges(graph, ...)
[4, 2]

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

ear.graph.split_edge(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.split_face(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.