如何将一个delaunay三角形列表排序为Octave中的有序渗滤列表？

Question

鉴于

v2_T = delaunay(v2_p) 

所有三角形的列表从所有点“v2_p”列表，并给所有三角形的邻居

v2_N = neighbors(v2_T) 

我怎么可以为了“v2_T”的列表，使得从开始第一个三角形上升，在“v2_T”中找到的下一个三角形总是会有至少一个之前列出的三角形邻居。我能想到的执行类似任务的closet函数可能是二叉树搜索或涉及递归算法的东西。

有人可以提供示例Octave代码吗？谢谢。

Answer 1

这是我对上述问题的未提出的解决方案。这是一个用C++编写的Octave动态链接函数，文件名为“dlf_percolate.cc”。要编译此功能，请在八度音终端中使用命令系统（'mkoctfile filedirectory/dlf_percolate.cc'）或备用命令mkoctfile“filedirectory/dlf_percolate.cc”，其中必须指定文件目录“文件目录” dlf_percolate.cc“被保存。为了测试函数v1_I = dlf_percolate（v2_N），需要一个生成的邻居列表v2_N = neighbors（v2_T），其中v2_T是delaunay三角形的生成列表，邻居（）是一个在Octave中不存在的函数。可以使用包“msh”http://octave.sourceforge.net/msh/中使用的函数来计算邻居v2_N。一旦有v2_N，就可以计算过滤顺序中数值标记的三角形的顺序为v1_I = dlf_percolate（v2_N，v_first_neigh），其中“v_first_neigh”是开始计算列出的三角形“v1_I”的渗透顺序的第一个三角形。

#include <octave/oct.h> 
void func_perc 
    (
     Matrix & v2_neigh_list 
     , 
     ColumnVector & v1_perc_list 
     , 
     ColumnVector & b1_toggled_neigh 
     , 
     int & v0_perc_index 
     , 
     int v0_next_neigh 
    ) ; 
DEFUN_DLD (dlf_percolate, args, , 
"Returns a list of sorted indices of the neighbors in percolated order." 
) { 
    int v0_first_neigh = 1 ; 
    switch(args.length()) 
    { 
    case 1: 
     // v0_first_neigh = 1 default value 
     break; 
    case 2: 
     v0_first_neigh = args(1).scalar_value() ; 
     break; 
    default: 
     error("Only one or two inputs are needed!") ; 
     return args; 
     break; 
    } 
    octave_value_list o1_retval ; 
    Matrix v2_neigh_list = args(0).matrix_value() ; 
    int v0_cols = v2_neigh_list.cols(); 
    int v0_rows = v2_neigh_list.rows(); 
    if((v0_first_neigh <= 0) || (v0_rows < v0_first_neigh)) 
    { 
     error("v0_first_neigh must be a valid member of the list!") ; 
     return args; 
    } 
    ColumnVector v1_perc_list(v0_rows,0); 
    ColumnVector b1_toggled_neigh(v0_rows,false); 
    int v0_perc_index = 0 ; 
    func_perc 
     (
      v2_neigh_list 
      , 
      v1_perc_list 
      , 
      b1_toggled_neigh 
      , 
      v0_perc_index 
      , 
      v0_first_neigh 
     ) ; 
    o1_retval(0) = v1_perc_list ; 
    return o1_retval ; 
} 
void func_perc 
    (
     Matrix & v2_neigh_list 
     , 
     ColumnVector & v1_perc_list 
     , 
     ColumnVector & b1_toggled_neigh 
     , 
     int & v0_perc_index 
     , 
     int v0_next_neigh 
    ) 
    { 
     if 
      (
       (v0_next_neigh > 0) 
       && 
       ((v0_perc_index) < v1_perc_list.length()) 
       && 
       (b1_toggled_neigh(v0_next_neigh - 1) == false) 
      ) 
      { 
       v1_perc_list(v0_perc_index) = v0_next_neigh ; 
       v0_perc_index++; 
       b1_toggled_neigh(v0_next_neigh - 1) = true ; 
       for(int v0_i = 0 ; v0_i < v2_neigh_list.cols() ; v0_i++) 
        { 
         func_perc 
          (
           v2_neigh_list 
           , 
           v1_perc_list 
           , 
           b1_toggled_neigh 
           , 
           v0_perc_index 
           , 
           v2_neigh_list(v0_next_neigh - 1 , v0_i) 
          ) ; 
        } 
      } 
     return ; 
    } 

我相信任何计算的渗透路径必须涉及递归算法。如果没有，至少递归使代码实现更容易解决这些类型的问题。我在Octave脚本中为这个函数设计的第一个版本被递归地称为Octave函数，递归算法的每一步都会逐渐变慢。我认为Octave函数的递归不是很有效率，因为解释性语言的功能超过了它。使用C++编写Octave原生函数是更有效地实现递归算法的一种更好的方法。 C++函数func_perc（）是dlf_percolate（）中使用的递归算法。