00001 #ifndef mmn_make_tri_tree_h_ 00002 #define mmn_make_tri_tree_h_ 00003 //: 00004 // \file 00005 // \brief Compute arcs defining a graph s.t. triangles form a tree. 00006 // \author Tim Cootes 00007 00008 #include <vnl/vnl_matrix.h> 00009 #include <mmn/mmn_arc.h> 00010 #include <mmn/mmn_triplet.h> 00011 #include <mmn/mmn_dependancy.h> 00012 #include <vcl_vector.h> 00013 00014 //: Compute arcs defining a graph s.t. triangles form a tree. 00015 // Compute arc of graph such that point belongs to at least one triangle, 00016 // and the graph of triangles is a tree (acyclic). 00017 // Two triangles are neighbours if they share an edge (arc). 00018 // 00019 // The approach is to select nodes one at a time, at each step 00020 // choosing the node closest to two nodes ending an existing arc. 00021 // This gives two new arcs. 00022 // 00023 // Complexity is approximately O(n^2) 00024 // 00025 // \param D: a symmetric matrix indicating proximity of two nodes 00026 // \param arcs: Output 2n-3 arcs defining the graph. 00027 // \param v0: If input as < D.rows() then defines one node of the first arc 00028 void mmn_make_tri_tree(const vnl_matrix<double>& D, 00029 vcl_vector<mmn_arc>& arcs, 00030 unsigned int v0 = (unsigned int)(-1)); 00031 00032 //: Compute arcs defining a graph s.t. triangles form a tree. 00033 // Compute arc of graph such that point belongs to at least one triangle, 00034 // and the graph of triangles is a tree (acyclic). 00035 // Two triangles are neighbours if they share an edge (arc). 00036 // 00037 // The approach is to select nodes one at a time, at each step 00038 // choosing the node closest to two nodes ending an existing arc. 00039 // This gives two new arcs. 00040 // 00041 // Complexity is approximately O(n^2) 00042 // 00043 // \param D: a symmetric matrix indicating proximity of two nodes 00044 // \param arcs: Output 2n-3 arcs defining the graph. 00045 // \param triplets: n-2 triplets defining triangles 00046 // \param deps: n-1 dependancies, defining a way to traverse graph 00047 // \param v0: If input as < D.rows() then defines one node of the first arc 00048 void mmn_make_tri_tree(const vnl_matrix<double>& D, 00049 vcl_vector<mmn_arc>& arcs, 00050 vcl_vector<mmn_triplet>& triplets, 00051 vcl_vector<mmn_dependancy>& deps, 00052 unsigned int v0 = (unsigned int)(-1)); 00053 00054 00055 #endif // mmn_make_tri_tree_h_ 00056
1.7.5.1