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 multfunc *	MT_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_info *	MT_tree_info_new (struct multtree *root, struct multfunc *functions, double dmin, int kmax)
struct multtree *	MT_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)

Copyright

(C) 1993-1996 by Helena Mitasova and the GRASS Development Team

This program is free software under the GNU General Public License (>=v2). Read the file COPYING that comes with GRASS for details.

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)

Copyright

(C) 1993-1996 by Helena Mitasova and the GRASS Development Team

This program is free software under the GNU General Public License (>=v2). Read the file COPYING that comes with GRASS for details.

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

MAX	max 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().