#include "kd_tree.h"#include "bd_tree.h"#include <cstring>#include <cstdlib>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 |
| enum ANNtreeType |
Definition at line 48 of file kd_dump.cpp.
| 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 255 of file kd_dump.cpp.
References ANNabort, annAllocPt(), annAllocPts(), annError(), annReadTree(), ANNwarn, and STRING_LEN.
{
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 370 of file kd_dump.cpp.
References ANNabort, annError(), BD_TREE, KD_TRIVIAL, 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
}
}
| const double EPSILON = 1E-5 |
Definition at line 46 of file kd_dump.cpp.
| const int STRING_LEN = 500 |
Definition at line 45 of file kd_dump.cpp.
Referenced by annReadDump(), and annReadTree().
1.7.2