GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
qtree.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <grass/dataquad.h>
#include <grass/qtree.h>
Include dependency graph for qtree.c:

Go to the source code of this file.

Functions

struct multfuncMT_functions_new (int(*compare)(struct triple *, struct quaddata *), struct quaddata **(*divide_data)(struct quaddata *, int, double), int(*add_data)(struct triple *, struct quaddata *, double), int(*intersect)(struct quaddata *, struct quaddata *), int(*division_check)(struct quaddata *, int), int(*get_points)(struct quaddata *, struct quaddata *, int))
 
struct tree_infoMT_tree_info_new (struct multtree *root, struct multfunc *functions, double dmin, int kmax)
 
struct multtreeMT_tree_new (struct quaddata *data, struct multtree **leafs, struct multtree *parent, int multant)
 
int MT_insert (struct triple *point, struct tree_info *info, struct multtree *tree, int n_leafs)
 
int MT_divide (struct tree_info *info, struct multtree *tree, int n_leafs)
 
int MT_region_data (struct tree_info *info, struct multtree *tree, struct quaddata *data, int MAX, int n_leafs)
 

Detailed Description

Author
H. Mitasova, I. Kosinovsky, D. Gerdes, Fall 1993, University of Illinois and US Army Construction Engineering Research Lab
H. Mitasova (University of Illinois),
I. Kosinovsky, (USA-CERL)
D.Gerdes (USA-CERL)
modified by H. Mitasova, November 1996 (include variable smoothing)
Author
H. Mitasova, I. Kosinovsky, D. Gerdes, Fall 1993, University of Illinois and US Army Construction Engineering Research Lab
H. Mitasova (University of Illinois),
I. Kosinovsky, (USA-CERL)
D.Gerdes (USA-CERL)
updated/checked by Mitasova Nov. 96 (no changes necessary)

Definition in file qtree.c.

Function Documentation

◆ MT_divide()

int MT_divide ( struct tree_info info,
struct multtree tree,
int  n_leafs 
)

Divide a tree

Divides the tree by calling one of tree's functions (divide_data()) and returns the result of divide_data()

Definition at line 158 of file qtree.c.

References multtree::data, multfunc::divide_data, tree_info::dmin, tree_info::functions, tree_info::kmax, multtree::leafs, malloc(), MT_tree_new(), and NULL.

Referenced by MT_insert().

◆ MT_functions_new()

struct multfunc* MT_functions_new ( int(*)(struct triple *, struct quaddata *)  compare,
struct quaddata **(*)(struct quaddata *, int, double)  divide_data,
int(*)(struct triple *, struct quaddata *, double)  add_data,
int(*)(struct quaddata *, struct quaddata *)  intersect,
int(*)(struct quaddata *, int)  division_check,
int(*)(struct quaddata *, struct quaddata *, int)  get_points 
)

Initializes multfunc structure with given arguments

Definition at line 33 of file qtree.c.

References multfunc::add_data, multfunc::compare, compare(), multfunc::divide_data, multfunc::division_check, multfunc::get_points, multfunc::intersect, malloc(), and NULL.

◆ MT_insert()

int MT_insert ( struct triple 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() and then calls MT_insert() to insert the point into divided tree and returns the result of MT_divide().

Definition at line 105 of file qtree.c.

References multfunc::add_data, multfunc::compare, multtree::data, multfunc::division_check, tree_info::dmin, tree_info::functions, tree_info::kmax, multtree::leafs, MT_divide(), MT_insert(), and NULL.

Referenced by MT_insert().

◆ MT_region_data()

int MT_region_data ( struct tree_info info,
struct multtree tree,
struct quaddata data,
int  MAX,
int  n_leafs 
)

Get points inside a region from a tree

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 otherwise 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.

Parameters
MAXmax number of points we can add (KMAX2)

Definition at line 194 of file qtree.c.

◆ MT_tree_info_new()

struct tree_info* MT_tree_info_new ( struct multtree root,
struct multfunc functions,
double  dmin,
int  kmax 
)

Initializes tree_info using given arguments

Definition at line 57 of file qtree.c.

References tree_info::dmin, tree_info::functions, tree_info::kmax, malloc(), NULL, and tree_info::root.

◆ MT_tree_new()

struct multtree* MT_tree_new ( struct quaddata data,
struct multtree **  leafs,
struct multtree parent,
int  multant 
)

Initializes multtree using given arguments

Definition at line 73 of file qtree.c.

Referenced by MT_divide().