Geografic-Information-System/lib/rst/qtree/DESCRIPTION.TREE

/* updated by Mitasova Nov. 96, no changes necessary */

DATa STRUCTURES:
----------------

#define VOID_T char

struct multfunc { 
    int (*compare) ();
    VOID_T **(*divide_data) ();
    int (*add_data) ();
    int (*intersect) ();
    int (*division_check) ();
    int (*get_points) ();
};

struct tree_info {
  struct multfunc *functions;
  double dmin;
  int kmax;
  struct multtree *root;
};

struct multtree {
  VOID_T *data;
  struct multtree **leafs;
  struct multtree *parent;
  int    multant;
};




FUNCTIONS:
----------

struct multfunc * MT_functions_new(compare,divide_data,add_data,
                          intersect,division_check,get_points)  
    int (*compare) ();
    VOID_T **(*divide_data) ();
    int (*add_data) ();
    int (*intersect) ();
    int (*division_check) ();
    int (*get_points) ();
/* Initializes FUNCTIONS structure with given arguments*/




struct tree_info * MT_tree_info_new (root,functions,dmin,kmax)
    struct multtree *root;
    struct multfunc *functions; 
    double dmin;
    int    kmax;
/*Initializes TREE_INFO using given arguments*/





struct multtree * MT_tree_new (data, leafs, parent, multant)
    VOID_T *data;
    struct multtree **leafs;
    struct multtree *parent;
    int             multant;
/*Initializes TREE using given arguments*/






int 
MT_insert (point,info,tree,n_leafs)
    VOID_T  *point;
    struct tree_info *info;
    struct multtree *tree;
    int    n_leafs;
/*First checks for dividing cond. (if n_points>=KMAX) and TREE is a leaf
  by calling one of tree's functions (division_check()).
  If TREE is not a leaf (is a node) uses function compare to determine
   into which "son" we need to insert the point and calls MT_insert()
   with this son as a n argument.
  If TREE is a leaf but we don't need to divide it (n_points<KMAX) then
   calls function add_data(POINT) to add POINT to the data of TREE and
   returns the result of add_data() (which returns 1 if the point is
   inserted and 0 if its ignored (when its too dense)).
  If Division_check returns true, calls MT_divide(TREE) and then calls
   insert_quad() to insert the POINT into divided TREE and returns the
   result of MT_divide(). */







int 
MT_divide (info,tree,n_leafs)
    struct tree_info *info;
    struct multtree *tree;
    int      n_leafs;
/* Divides the tree by calling one of tree's functions (divide_data())
   and returns the result of divide_data() */







int 
MT_region_data (info, tree, data, MAX, n_leafs)
    struct tree_info *info;
    struct multtree *tree;
    VOID_T   *data;
    int             MAX;	/* max number of points we can add (KMAX2) */
    int             n_leafs;
 /* Gets points inside the region defined by DATA from TREE and
adds them to DATA. If the number of eligible
point is more than MAX returns MAX+1 othervise returns number of points added
to DATA.
  Uses tree's functions intersect() to find leafs that intersect given region
and get_points() to get points from such leafs. */