How to order a list of delaunay triangles to a ordered percolation list in Octave?

Question

Given a list of all triangles

v2_T = delaunay(v2_p)

from a list of all points "v2_p" and given a list of all triangle neighbors

v2_N = neighbors(v2_T)

how can I order "v2_T" such that starting from the first triangle going up, the next triangle you find in "v2_T" will always have at least one triangle neighbor I have listed previously. The closet function I can think of that performs a similar task might be a binary tree search or something involving a recursive algorithm.

Could someone provide sample Octave code? Thanks.

Answer 1

Here is my uncommitted solution to the above question. This is a dynamically linked function for Octave written in c++ with file name "dlf_percolate.cc". To compile this function use the command system('mkoctfile filedirectory/dlf_percolate.cc') or the alternative command mkoctfile "filedirectory/dlf_percolate.cc" in the octave terminal, where one must designate the file directory "filedirectory" of where the file "dlf_percolate.cc" is saved. To test the function v1_I = dlf_percolate(v2_N), one needs a generated list of neighbors v2_N = neighbors(v2_T), where v2_T is the generated list of delaunay triangles and neighbors() is a function that does not exist in Octave yet. Neighbors v2_N can be calculated from using functions used in the package "msh" http://octave.sourceforge.net/msh/. Once one has v2_N, one can compute the order of numerical labeled triangles in percolated order as v1_I = dlf_percolate(v2_N,v_first_neigh), where "v_first_neigh" is the first triangle to start calculating the percolated order of listed triangles "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 ;
    }

I believe any calculated percolation path must involve a recursive algorithm. If not, at minimum, recursion makes easier code implementation to solve these types of problems. The first build I designed for this function in Octave script called an Octave function recursively which ran progressively slower at each step of the recursive algorithm. I believe recursion in Octave functions is not very efficient, because of the functional over headed of the interpretive language. Writing native functions in c++ for Octave is a better way to implement recursive algorithms efficiently. The c++ function func_perc() is the recursive algorithm used in dlf_percolate().