CHAPTER III.

GRAPHS

A graph is a collection of vertices and edges

.js
var graph = RabbitEar.graph()

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

One effect of organizing things this way is to calculate adjacency.

Adjacency

adjacent vertices

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

adjacent edges

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

Components

graph.vertices
graph.edges
graph.faces

Our graph keeps track of all of its components by index references.

An edge is represented by two integers: the index of each vertex in their vertices array.

This means that the vertices (and edges and faces) cannot move around in their array. If so, all of these index references in all the arrays needs to be carefully updated.

edges = [
  [4, 7],
  ...
]

We can count on every edge only containing two integers. Faces however can be made of any number of vertices, greater than or equal to three.

faces = [
[4, 0, 1, 7, 5],
...
]

FOLD Format

This library subscribes to the FOLD file format, which is a set of naming standards around this type of graph structure.

FOLD graph
┃
┃ // vertices
┣━ vertices_coords  // points, not indices
┣━ vertices_vertices
┣━ vertices_faces
┃
┃ // edges
┣━ edges_vertices
┣━ edges_faces
┃
┃ // faces
┣━ faces_vertices
┗━ faces_edges

vertices_coords is the only graph array that doesn't contain index references to an array. Each of its elements is a coordinate in Euclidean space.

Core Methods

The bulk of Rabbit Ear's engine are methods which modify FOLD objects. Here is an abbreviated list:

These methods validate and repair a FOLD object.

RabbitEar.core
┃
┣━ clean(graph)
┣━ populate(graph)
┣━ validate(graph)
┣━ rebuild(graph, epsilon)
┃
┃ // into a valid planar graph
┣━ fragment(graph, epsilon)

Methods for removing things.

// remove components
┣━ remove(graph, key, removeIndices)
┃
┃ // vertices left behind after edges removal
┣━ collinear_vertices(graph, point, vector)
┣━ collinear_edges(graph, point, vector)
┣━ remove_all_collinear_vertices(graph)
┣━ find_isolated_vertices(graph)
┃
┃ // additional clean up
┣━ get_collinear_vertices(graph)
┣━ get_isolated_vertices(graph)
┣━ get_duplicate_vertices(graph)
┣━ get_duplicate_edges(graph)
┣━ get_duplicate_edges_old(graph)
┣━ find_collinear_face_edges(edge, face_vertices, vertices_coords)

Methods for creating graph components.

// makers
┣━ make_vertices_edges(graph)
┣━ make_edges_vertices(graph)
┣━ make_faces_faces(graph)
┣━ make_edges_faces(graph)
┣━ make_edges_length(graph)
┣━ make_edges_foldAngle(graph)
┣━ make_vertex_pair_to_edge_map(graph)
┣━ make_vertices_faces(graph)
┣━ make_face_walk_tree(graph, root_face = 0)
┣━ make_faces_matrix(graph, root_face)
┣━ make_faces_matrix_inv(graph, root_face)
┣━ make_vertices_coords_folded(graph, face_stationary, faces_matrix)
┗━ make_vertices_isBoundary(graph)
make_faces_coloring_from_faces_matrix(faces_matrix)

Methods for counting a graph's components.

// query the component arrays
┣━ vertices_count(graph)
┣━ edges_count(graph)
┣━ faces_count(graph)
┃
┃ // search other arrays for evidence of components
┣━ implied_vertices_count(graph)
┣━ implied_edges_count(graph)
┣━ implied_faces_count(graph)

Search the graph.

// using vertices_coords and Euclidean distance
┣━ select_vertices(graph, poly_points)
┣━ select_edges(graph, poly_points)
┣━ nearest_vertex(graph, point)
┣━ nearest_edge(graph, point)
┣━ face_containing_point(graph, point)
┣━ folded_faces_containing_point(graph, point, faces_matrix)
┣━ faces_containing_point(graph, point)
┣━ topmost_face(graph, faces)

Kawasaki's theorem, sector math, angles around a vertex.

// sector angles and Kawasaki
┣━ alternating_sum(...numbers)
┣━ kawasaki_flatness(...sectorAngles)
┣━ vertex_adjacent_vectors(graph, vertex)
┣━ vertex_sectorAngles(graph, vertex)
┣━ vertex_kawasaki_flatness(graph, vertex)
┣━ make_vertices_sectorAngles(graph)
┣━ make_vertices_kawasaki_flatness(graph)
┣━ make_vertices_kawasaki(graph)
┣━ make_vertices_nudge_matrix(graph)
┣━ kawasaki_test(graph, EPSILON = math.core.EPSILON)
┣━ make_vertices_nudge(graph)
┣━ kawasaki_solutions_radians(...vectors_radians)
┣━ kawasaki_solutions(...vectors)
┣━ kawasaki_collapse(graph, vertex, face, crease_direction = "F")
// 
copy_without_marks: ƒ (graph)

add_edge: ƒ (graph, a, b, c, d, assignment = "U")
split_edge_run: ƒ ( graph, x, y, old_edge_index )
apply_run: ƒ (graph, diff)
merge_run: ƒ (graph, target, source)
apply_axiom: ƒ (axiom, solutions, parameters)

Discussion

Remove

[0.0, 0.0, 0.0],
[0.5, 1.0, 0.0],
xxx
[1.0, 1.0, 1.0]

If a component at an arbitrary index is removed, the following array elements need to shift up by one. This breaks all other arrays which reference this one.

The remove method addresses this.

RabbitEar.core.remove(graph, "vertices", [5, 9])

This will remove elements 5 and 9 from all arrays beginning with vertices_ ("vertices_coords"), and update all indices accordingly in every array that ends with _vertices ("edges_vertices").

Clean

graph.clean()

Clean will fix a graph in accordance with general graph theory. A graph cannot contain:

circular edges: an edge cannot connect the same vertex at both ends
duplicate edges: the same 2 vertices cannot have more than 1 edge between them

Populate

Consider this graph which models the square below.

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 four vertices are the four corners. The edges mark the boundaries except for the final edge, the diagonal, given the assignment "mountain fold".

If the above example is the variable g, this method will populate all the other arrays.

var graph = RabbitEar.graph(g)
graph.populate();

Resulting in:

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_length: [1, 1, 1, 1, 1.4142135623730951]
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]]

Planar Graphs

When the FOLD object is meant to represent a crease pattern, we can treat it like a planar graph.

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

Fragment

The fragment method converts a graph into a planar graph.

graph.fragment()

Fragment locates all overlapping edges and resolves them by adding a vertex at their intersection, and substitutes an overlapped edge with two edges.

This method removes all 3D information and triggers a re-build on all other component arrays.

Join

Join two graphs into one.

graph.join(graph2)

This example demonstrates the join method with a very permissive epsilon.

Notice how vertices will snap to other vertices. With a more appropriate epsilon this will still happen but with a more reasonable level of deformation.