kd_dump.cpp File Reference

#include "kd_tree.h"
#include "bd_tree.h"

Include dependency graph for kd_dump.cpp:

Go to the source code of this file.

Enumerations
enum	ANNtreeType { KD_TREE, BD_TREE }

Functions
static ANNkd_ptr	annReadDump (istream &in, ANNtreeType tree_type, ANNpointArray &the_pts, ANNidxArray &the_pidx, int &the_dim, int &the_n_pts, int &the_bkt_size, ANNpoint &the_bnd_box_lo, ANNpoint &the_bnd_box_hi)
static ANNkd_ptr	annReadTree (istream &in, ANNtreeType tree_type, ANNidxArray the_pidx, int &next_idx)

Variables
const int	STRING_LEN = 500
const double	EPSILON = 1E-5

Enumeration Type Documentation

enum ANNtreeType

Enumerator
KD_TREE
BD_TREE

Definition at line 46 of file kd_dump.cpp.

{KD_TREE, BD_TREE};     // tree types (used in loading)

Function Documentation

static ANNkd_ptr annReadDump ( istream &  in, ANNtreeType  tree_type, ANNpointArray &  the_pts, ANNidxArray &  the_pidx, int &  the_dim, int &  the_n_pts, int &  the_bkt_size, ANNpoint &  the_bnd_box_lo, ANNpoint &  the_bnd_box_hi  )

static

Definition at line 253 of file kd_dump.cpp.

References ANNabort, annAllocPt(), annAllocPts(), annError(), annReadTree(), ANNwarn, STRING_LEN, and version.

{
        int j;
        char str[STRING_LEN];                                           // storage for string
        char version[STRING_LEN];                                       // ANN version number
        ANNkd_ptr the_root = NULL;

        //------------------------------------------------------------------
        //      Input file header
        //------------------------------------------------------------------
        in >> str;                                                                      // input header
        if (strcmp(str, "#ANN") != 0) {                         // incorrect header
                annError("Incorrect header for dump file", ANNabort);
        }
        in.getline(version, STRING_LEN);                        // get version (ignore)

        //------------------------------------------------------------------
        //      Input the points
        //                      An array the_pts is allocated and points are read from
        //                      the dump file.
        //------------------------------------------------------------------
        in >> str;                                                                      // get major heading
        if (strcmp(str, "points") == 0) {                       // points section
                in >> the_dim;                                                  // input dimension
                in >> the_n_pts;                                                // number of points
                                                                                                // allocate point storage
                the_pts = annAllocPts(the_n_pts, the_dim);
                for (int i = 0; i < the_n_pts; i++) {   // input point coordinates
                        ANNidx idx;                                                     // point index
                        in >> idx;                                                      // input point index
                        if (idx < 0 || idx >= the_n_pts) {
                                annError("Point index is out of range", ANNabort);
                        }
                        for (j = 0; j < the_dim; j++) {
                                in >> the_pts[idx][j];                  // read point coordinates
                        }
                }
                in >> str;                                                              // get next major heading
        }
        else {                                                                          // no points were input
                annError("Points must be supplied in the dump file", ANNabort);
        }

        //------------------------------------------------------------------
        //      Input the tree
        //                      After the basic header information, we invoke annReadTree
        //                      to do all the heavy work.  We create our own array of
        //                      point indices (so we can pass them to annReadTree())
        //                      but we do not deallocate them.  They will be deallocated
        //                      when the tree is destroyed.
        //------------------------------------------------------------------
        if (strcmp(str, "tree") == 0) {                         // tree section
                in >> the_dim;                                                  // read dimension
                in >> the_n_pts;                                                // number of points
                in >> the_bkt_size;                                             // bucket size
                the_bnd_box_lo = annAllocPt(the_dim);   // allocate bounding box pts
                the_bnd_box_hi = annAllocPt(the_dim);

                for (j = 0; j < the_dim; j++) {                 // read bounding box low
                        in >> the_bnd_box_lo[j];
                }
                for (j = 0; j < the_dim; j++) {                 // read bounding box low
                        in >> the_bnd_box_hi[j];
                }
                the_pidx = new ANNidx[the_n_pts];               // allocate point index array
                int next_idx = 0;                                               // number of indices filled
                                                                                                // read the tree and indices
                the_root = annReadTree(in, tree_type, the_pidx, next_idx);
                if (next_idx != the_n_pts) {                    // didn't see all the points?
                        annError("Didn't see as many points as expected", ANNwarn);
                }
        }
        else {
                annError("Illegal dump format.  Expecting section heading", ANNabort);
        }
        return the_root;
}

static ANNkd_ptr annReadTree ( istream &  in, ANNtreeType  tree_type, ANNidxArray  the_pidx, int &  next_idx  )

static

Definition at line 368 of file kd_dump.cpp.

References ANNabort, annError(), BD_TREE, KD_TRIVIAL, n_pts, and STRING_LEN.

Referenced by annReadDump().

{
        char tag[STRING_LEN];                                           // tag (leaf, split, shrink)
        int n_pts;                                                                      // number of points in leaf
        int cd;                                                                         // cut dimension
        ANNcoord cv;                                                            // cut value
        ANNcoord lb;                                                            // low bound
        ANNcoord hb;                                                            // high bound
        int n_bnds;                                                                     // number of bounding sides
        int sd;                                                                         // which side

        in >> tag;                                                                      // input node tag

        if (strcmp(tag, "null") == 0) {                         // null tree
                return NULL;
        }
        //------------------------------------------------------------------
        //      Read a leaf
        //------------------------------------------------------------------
        if (strcmp(tag, "leaf") == 0) {                         // leaf node

                in >> n_pts;                                                    // input number of points
                int old_idx = next_idx;                                 // save next_idx
                if (n_pts == 0) {                                               // trivial leaf
                        return KD_TRIVIAL;
                }
                else {
                        for (int i = 0; i < n_pts; i++) {       // input point indices
                                in >> the_pidx[next_idx++];             // store in array of indices
                        }
                }
                return new ANNkd_leaf(n_pts, &the_pidx[old_idx]);
        }
        //------------------------------------------------------------------
        //      Read a splitting node
        //------------------------------------------------------------------
        else if (strcmp(tag, "split") == 0) {           // splitting node

                in >> cd >> cv >> lb >> hb;

                                                                                                // read low and high subtrees
                ANNkd_ptr lc = annReadTree(in, tree_type, the_pidx, next_idx);
                ANNkd_ptr hc = annReadTree(in, tree_type, the_pidx, next_idx);
                                                                                                // create new node and return
                return new ANNkd_split(cd, cv, lb, hb, lc, hc);
        }
        //------------------------------------------------------------------
        //      Read a shrinking node (bd-tree only)
        //------------------------------------------------------------------
        else if (strcmp(tag, "shrink") == 0) {          // shrinking node
                if (tree_type != BD_TREE) {
                        annError("Shrinking node not allowed in kd-tree", ANNabort);
                }

                in >> n_bnds;                                                   // number of bounding sides
                                                                                                // allocate bounds array
                ANNorthHSArray bds = new ANNorthHalfSpace[n_bnds];
                for (int i = 0; i < n_bnds; i++) {
                        in >> cd >> cv >> sd;                           // input bounding halfspace
                                                                                                // copy to array
                        bds[i] = ANNorthHalfSpace(cd, cv, sd);
                }
                                                                                                // read inner and outer subtrees
                ANNkd_ptr ic = annReadTree(in, tree_type, the_pidx, next_idx);
                ANNkd_ptr oc = annReadTree(in, tree_type, the_pidx, next_idx);
                                                                                                // create new node and return
                return new ANNbd_shrink(n_bnds, bds, ic, oc);
        }
        else {
                annError("Illegal node type in dump file", ANNabort);
                exit(0);                                                                // to keep the compiler happy
        }
}

Variable Documentation

const double EPSILON = 1E-5

Definition at line 44 of file kd_dump.cpp.

const int STRING_LEN = 500

Definition at line 43 of file kd_dump.cpp.