# [−][src]Module plexus::graph

Half-edge graph representation of meshes.

This module provides a flexible representation of meshes as a half-edge
graph. *Half-edges* and *edges* are referred to as *arcs* and *edges*,
respectively. Meshes can store arbitrary geometric data associated with any
topological structure (vertices, arcs, edges, and faces).

Geometry is vertex-based, meaning that geometric operations depend on
vertices exposing some notion of positional data. See the `geometry`

module
and `AsPosition`

trait. If geometry does not have this property, then
spatial operations will not be available.

See the user guide for more details and examples.

# Representation

A `MeshGraph`

is conceptually composed of *vertices*, *arcs*, *edges*, and
*faces*. The figure below summarizes the connectivity in a `MeshGraph`

.

Arcs are directed and connect vertices. An arc that is directed toward a
vertex $A$ is an *incoming arc* with respect to $A$. Similarly, an arc
directed away from such a vertex is an *outgoing arc*. Every vertex is
associated with exactly one *leading arc*, which is always an outgoing arc.
The vertex toward which an arc is directed is the arc's *destination vertex*
and the other is its *source vertex*.

Every arc is paired with an *opposite arc* with an opposing direction.
Given an arc from a vertex $A$ to a vertex $B$, that arc will have an
opposite arc from $B$ to $A$. Such arcs are notated $\overrightarrow{AB}$
and $\overrightarrow{BA}$. Together, these arcs form an *edge*, which is not
directed. An edge and its two arcs are together called a *composite edge*.

Arcs are connected to their neighbors, known as *next* and *previous arcs*.
A traversal along a series of arcs is a *path*. The path formed by
traversing from an arc to its next arc and so on is a *ring*. When a face is
present within an ring, the arcs will refer to that face and the face will
refer to exactly one of the arcs in the ring (this is the leading arc of the
face). An arc with no associated face is known as a *boundary arc*. If
either of an edge's arcs is a boundary arc, then that edge is a *boundary
edge*.

A path that terminates is *open* and a path that forms a loop is *closed*.
Rings are always closed. Paths may be notated using *sequence* or *set
notation* and both forms are used to describe rings and faces.

Sequence notation is formed from the ordered sequence of vertices that a path traverses, including the source vertex of the first arc and the destination vertex of the last arc. Set notation is similar, but is implicitly closed and only includes the ordered and unique set of vertices traversed by the path. An open path over vertices $A$, $B$, and $C$ is notated as a sequence $\overrightarrow{(A,B,C)}$. A closed path over vertices $A$, $B$, and $C$ includes the arc $\overrightarrow{CA}$ and is notated as a sequence $\overrightarrow{(A,B,C,A)}$ or a set $\overrightarrow{\{A,B,C\}}$.

Together with vertices and faces, the connectivity of arcs allows for effecient traversals of topology. For example, it becomes trivial to find neighboring topologies, such as the faces that share a given vertex or the neighboring faces of a given face.

`MeshGraph`

s store topological data using associative collections and mesh
data is accessed using keys into this storage. Keys are exposed as strongly
typed and opaque values, which can be used to refer to a topological
structure.

# Topological Views

`MeshGraph`

s expose *views* over their topological structures (vertices,
arcs, edges, and faces). Views are accessed via keys or iteration and behave
similarly to references. They provide the primary API for interacting with a
`MeshGraph`

's topology and geometry. There are three types summarized below:

Type | Traversal | Exclusive | Geometry | Topology |
---|---|---|---|---|

Immutable | Yes | No | Immutable | Immutable |

Mutable | Yes | Yes | Mutable | Mutable |

Orphan | No | No | Mutable | N/A |

*Immutable* and *mutable views* behave similarly to references: immutable
views cannot mutate a graph and are not exclusive while mutable views may
mutate both the geometry and topology of a graph but are exclusive.

*Orphan views* are similar to mutable views in that they may mutate the
geometry of a graph, but they do not have access to the topology of a graph.
Because they do not know about other vertices, arcs, etc., an orphan view
cannot traverse a graph in any way. These views are most useful for
modifying the geometry of a graph and, unlike mutable views, they are not
exclusive. Iterators over topological structures in a graph sometimes emit
orphan views.

# Examples

Generating a graph from a $uv$-sphere:

use decorum::N64; use nalgebra::Point3; use plexus::graph::MeshGraph; use plexus::prelude::*; use plexus::primitive::generate::Position; use plexus::primitive::sphere::UvSphere; let mut graph = UvSphere::default() .polygons::<Position<Point3<N64>>>() .collect::<MeshGraph<Point3<N64>>>();

Extruding a face in a graph:

use decorum::N64; use nalgebra::Point3; use plexus::graph::MeshGraph; use plexus::prelude::*; use plexus::primitive::generate::Position; use plexus::primitive::sphere::UvSphere; let mut graph = UvSphere::new(8, 8) .polygons::<Position<Point3<N64>>>() .collect::<MeshGraph<Point3<N64>>>(); let key = graph.faces().nth(0).unwrap().key(); // Get the key of the first face. let face = graph.face_mut(key).unwrap().extrude(1.0); // Extrude the face.

Traversing and circulating over a graph:

use nalgebra::Point2; use plexus::graph::MeshGraph; use plexus::prelude::*; use plexus::primitive::Tetragon; let mut graph = MeshGraph::<Point2<f64>>::from_raw_buffers( vec![Tetragon::new(0u32, 1, 2, 3)], vec![(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)], ) .unwrap(); graph.triangulate(); // Traverse an arc and use a circulator to get the faces of a nearby vertex. let key = graph.arcs().nth(0).unwrap().key(); let mut vertex = graph .arc_mut(key) .unwrap() .into_opposite_arc() .into_next_arc() .into_destination_vertex(); for mut face in vertex.neighboring_face_orphans() { // `face.geometry` is mutable here. }

## Re-exports

`pub use Selector::ByIndex;` |

`pub use Selector::ByKey;` |

## Structs

Arc | Graph arc. |

ArcKey | |

ArcOrphan | Orphan view of an arc. |

ArcView | View of an arc in a graph. |

Edge | Graph edge. |

EdgeKey | |

EdgeOrphan | Orphan view of an edge. |

EdgeView | View of an edge in a graph. |

Face | Graph face. |

FaceKey | |

FaceOrphan | Orphan view of a face. |

FaceView | View of a face in a graph. |

MeshGraph | Half-edge graph representation of a mesh. |

Path | View of a path in a graph. |

Ring | View of a ring in a graph. |

Vertex | Graph vertex. |

VertexKey | |

VertexOrphan | Orphan view of a vertex. |

VertexView | View of a vertex in a graph. |

## Enums

GraphError | |

Selector | Topology selector. |

## Traits

ArcNormal | |

EdgeMidpoint | |

Edgoid | Edge-like structure. Abstracts arcs and edges. |

FaceCentroid | |

FaceNormal | |

FacePlane | |

GraphGeometry | Graph geometry. |

Rebind | |

Ringoid | Ring-like structure. Abstracts faces and rings. |

VertexCentroid | |

VertexNormal |

## Type Definitions

VertexPosition |