如何將一個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（）中使用的遞歸算法。