compute_homology_basis

Compute a basis for the homology group H_1(M,Z), based on the algorithm 6 in book [1].

  1. Gu, Xianfeng David, and Shing-Tung Yau, eds. Computational conformal geometry. Vol. 3. Somerville: International Press, 2008.

Contents

Syntax

hb = compute_homology_basis(face,vertex)

Description

face  : double array, nf x 3, connectivity of mesh
vertex: double array, nv x 3, vertex of mesh
hb: cell array, n x 1, a basis of homology group, each cell is a closed
    loop based. Return empty for genus zero surface. Two loops on each
    handle. If there is boundary on surface, each boundary will be an
    element of hb

Contribution

Author : Wen Cheng Feng
Created: 2014/03/13
Revised: 2014/03/24 by Wen, add doc
Copyright 2014 Computational Geometry Group
Department of Mathematics, CUHK
http://www.math.cuhk.edu.hk/~lmlui
function hb = compute_homology_basis(face,vertex)
ee = cut_graph(face,vertex);
nv = size(vertex,1);
G = sparse(ee(:,1),ee(:,2),ones(size(ee,1),1),nv,nv);
G = G+G';

if exist('graphminspantree')
    [tree,pred] = graphminspantree(G,'METHOD','Kruskal');
else
    [tree,pred] = minimum_spanning_tree(G);
end
v = find(pred==0);
[I,J,~] = find(tree+tree');
eh = setdiff(ee,[I,J],'rows');
hb = cell(size(eh,1),1);
for i = 1:size(eh,1)
    p1 = trace_path(pred,eh(i,1),v);
    p2 = trace_path(pred,eh(i,2),v);
    loop = [flipud(p1);eh(i,1);eh(i,2);p2];
    hb{i} = prune_path(loop);
end
if isempty(eh)
    hb = [];
end

function path = trace_path(pred,v,root)
path = [];
while true
    path = [path;pred(v)];
    v = pred(v);
    if v == root
        break;
    end
end

function path_new = prune_path(path)
ind = path ~= flipud(path);
i = find(ind,1)-1;
path_new = path(i:end-i+1);