Graph connectivity

A = adjacencymatrix(mesh)

Get adjacency matrix.

loops, indices = boundaryloops(mesh)

Find boundary loops of mesh.

Returns pair (loops, indices):

• loops in a 2 × n Array{Int} of ranges into indices with start and stop in first and second row, respectively. n is the number of boundary loops.
• indices is a Vector{Int} with indices of all boundary vertices in order.

loops, b = boundaryloops(mesh, sort=true) provides the boundary loops in order of decreasing vertex count.

Example: The vertex indices of the first boundary loop are indices[loops[1,1]:loops[2,1]].

See also boundaryvertices, nboundaryloops, largestboundaryloop

i = boundaryvertices(mesh)

Find all boundary vertices as an unordered Vector{Int}.

See also boundaryloops

i = connectedcomponent(mesh, seed::Int[; A]) ::Vector{Int}

Find one connected component from seed vertex. If the adjacency matrix is available, it can be passed as A.

See also connectedcomponents

cc, seeds = connectedcomponents(mesh)

Find all connected components:

• cc is a Vector{Int} of length #V which contains the component index for each vertex: extrema(cc) == (1,ncc)
• seeds is a Vector{Int} of length ncc which contains seeds for connectedcomponent(mesh, seed).

where ncc == ncomponents(mesh) and #V is the number of vertices.

Note that each isolated vertex is one component.

See also connectedcomponent

part, ti, rti = disconnectvertices(f, mesh)

Generate a triangulation with all vertices !f(idx) disconnected.

The disconnected vertices become isolated vertices, i.e., the total number of vertices doesn't change in the output mesh. In fact, the output shares the vertex table with the input mesh!

Returns (part, ti, rti) with maps of triangle indices from part and from mesh.

for (i,j) in edges(mesh)
  ...
end

Generate all edges (i,j). Each edge, inner or boundary, is generated once.

fmesh, rvi, rti = filterisolatedvertices(mesh)

Generate fmesh with isolatedvertices removed from mesh. Calls filtervertices, which returns (fmesh, rvi, rti).

   fmesh, rvi, rti = filtervertices(f, mesh)

Generate mesh with all vertices !f(idx) removed.

• fmesh new mesh with filtered vertices
• rvi index array of length n with vertex indices in fmesh
• tvi index array of length m with triangle indices in fmesh

where n, m = size(mesh) are the size of the input mesh.

hasboundary(mesh) :: Bool

Does mesh have a boundary?

Note that isolatedvertices(mesh) are not boundary!

hasisolatedvertices(mesh) :: Bool

Does mesh have isolated vertices?

hasmultiplecomponents(mesh) :: Bool

Does the mesh consist of multiple connected components?

See also ncomponents, hassinglecomponent

hassinglecomponent(mesh) :: Bool

Does the mesh consist of a single connected component?

Note that en empty mesh does not have a (single) component.

See also ncomponents, hasmultiplecomponents

i = isolatedvertices(mesh)

Find all isolated vertices.

i = largestboundaryloop(mesh) :: Vector{Int}

Find the largest boundary loop, i.e., the one with the maximum number of vertices.

See also boundaryloops, longestboundaryloop

i = longestboundaryloop(mesh)

Find boundary loop with maximum length, returns indices, length.

See also boundaryloops, largestboundaryloop, shortestboundaryloop

mergedmesh, rvi, replace = mergevertices(mesh[; maxdist=0, reldist=true,
                                                isequal=alwaysequal, p = 2)

Generate mesh with (approximately) equal vertices being merged.

• maxdist maximum distance of vertices considered equal; use default if <=0
• reldist maximum distance is relative to std
• isequal additional binary predicate for testing equality (e.g. isapprox)
• p metric: measure distance in p-norm; p ∈ [1,2,Inf]

Returns mergedmesh, rvi, replace with vertex replacements rvi, replace: mergevertices calls replacevertices with replace as input and rvi as output.

• replace contains replacement index for every vertex (including "self-replacements"!)
• rvi contains indices in resulting

n = nboundaryloops(mesh)

Find the number of boundary loops.

See also boundaryloops

n = ncomponents(mesh)

Compute the number of connected components.

len = pathlength(mesh, idx[; loop=false)

Compute length of path specified by vertex indices idx.

Close the path if loop==true: add length of segment from last to first vertex.

lengths = pathlengths(mesh, loops, b[; loop=false])

Compute pathlength for multiple paths.

The paths are given in the representation (loops, b) that is returned by boundaryloops.

i = shortestboundaryloop(mesh)

Find boundary loop with minimum length, returns indices, length.

See also longestboundaryloop

loops, b, lengths = sortloopsbylength(mesh, loops, b[; loop=false])
loops, b, lengths = sortloopsbylength(mesh, boundaryloops(mesh)...; loop=true)

Sort loops returned by boundaryloops by pathlength.

parts = splitcomponents(mesh)

Split connected components into multiple meshes parts::Vector{TriMesh}.

The inverse operation is union: ∪(splitcomponents(mesh)) → mesh.

See also splitcomponentsmapped

mparts = splitcomponentsmapped(mesh)

Split connected components into multiple meshes.

The returned array mparts has entries (part, (i, ri), (ti, rti)) with

• part is a TriMesh as returned by splitcomponents
• vi, rvi map vertex indices from part (length(vi)==nv(part)) and to from mesh (length(rvi) ==nv(mesh)`)
• ti, tvi map triangle indices from part (length(ti)==mt(part)) and to from mesh (length(rti) ==mt(mesh)`)

See also splitcomponents

parts = splitcomponentsshared(mesh)

Partition mesh into components.

Similar top splitcomponentsbut parts *share* vertex table [positions(mesh)`]. Empty parts refer to isolated verrtices.

The difference to splitcomponents is calling disconnectvertices rather than filtervertices.

val = valence(mesh) :: Vector{Int}

Compute the valence (degree) for all vertices (handles boundary vertices).

mesh = union(part1, part2, ...)
mesh = part1 ∪ part2 ∪ ...

Merge disjoint components into mesh.

See also splitcomponents

fmesh = fliporientation(mesh)

Flip orientation of all triangles.