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