GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
qtree.c
Go to the documentation of this file.
1 /*!
2  * \file qtree.c
3  *
4  * \author
5  * H. Mitasova, I. Kosinovsky, D. Gerdes, Fall 1993,
6  * University of Illinois and
7  * US Army Construction Engineering Research Lab
8  *
9  * \author H. Mitasova (University of Illinois),
10  * \author I. Kosinovsky, (USA-CERL)
11  * \author D.Gerdes (USA-CERL)
12  *
13  * \author updated/checked by Mitasova Nov. 96 (no changes necessary)
14  *
15  * \copyright
16  * (C) 1993-1996 by Helena Mitasova and the GRASS Development Team
17  *
18  * \copyright
19  * This program is free software under the
20  * GNU General Public License (>=v2).
21  * Read the file COPYING that comes with GRASS for details.
22  */
23 
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <math.h>
27 
28 #include <grass/dataquad.h>
29 #include <grass/qtree.h>
30 
31 /*! Initializes multfunc structure with given arguments */
32 struct multfunc
33  *MT_functions_new(int (*compare) (struct triple *, struct quaddata *),
34  struct quaddata **(*divide_data) (struct quaddata *,
35  int, double),
36  int (*add_data) (struct triple *, struct quaddata *,
37  double),
38  int (*intersect) (struct quaddata *, struct quaddata *),
39  int (*division_check) (struct quaddata *, int),
40  int (*get_points) (struct quaddata *, struct quaddata *,
41  int))
42 {
43  struct multfunc *functions;
44  if (!(functions = (struct multfunc *)malloc(sizeof(struct multfunc)))) {
45  return NULL;
46  }
47  functions->compare = compare;
48  functions->divide_data = divide_data;
49  functions->add_data = add_data;
50  functions->intersect = intersect;
51  functions->division_check = division_check;
52  functions->get_points = get_points;
53  return functions;
54 }
55 
56 /*! Initializes tree_info using given arguments */
58  struct multfunc *functions, double dmin,
59  int kmax)
60 {
61  struct tree_info *info;
62  if (!(info = (struct tree_info *)malloc(sizeof(struct tree_info)))) {
63  return NULL;
64  }
65  info->root = root;
66  info->functions = functions;
67  info->dmin = dmin;
68  info->kmax = kmax;
69  return info;
70 }
71 
72 /** Initializes multtree using given arguments */
74  struct multtree **leafs, struct multtree *parent,
75  int multant)
76 {
77  struct multtree *tree;
78  if (!(tree = (struct multtree *)malloc(sizeof(struct multtree)))) {
79  return NULL;
80  }
81  tree->data = data;
82  tree->leafs = leafs;
83  tree->parent = parent;
84  tree->multant = multant;
85  return tree;
86 }
87 
88 
89 /*!
90  * First checks for dividing cond. (if n_points>=KMAX) and tree
91  * is a leaf by calling one of tree's functions (`division_check()`).
92  * If tree is not a leaf (is a node) uses function compare to determine
93  * into which "son" we need to insert the point and calls MT_insert()
94  * with this son as a n argument.
95  *
96  * If TREE is a leaf but we don't need to divide it (n_points<KMAX) then
97  * calls function `add_data(point, ...)` to add point to the data of tree
98  * and returns the result of `add_data()` (which returns 1 if the point is
99  * inserted and 0 if its ignored (when its too dense)).
100  *
101  * If `division_check()` returns true, calls MT_divide() and then calls
102  * MT_insert() to insert the point into divided tree and returns the
103  * result of MT_divide().
104  */
105 int MT_insert(struct triple *point,
106  struct tree_info *info, struct multtree *tree, int n_leafs)
107 {
108  int j = 0, i, k, comp;
109 
110  if (tree == NULL) {
111  fprintf(stderr, "insert: tree is NULL\n");
112  return -5;
113  }
114  if (tree->data == NULL) {
115  fprintf(stderr, "insert: tree->data is NULL\n");
116  return -5;
117  }
118  i = info->functions->division_check(tree->data, info->kmax);
119  if (i <= 0) {
120  if (i == -1) {
121  comp = info->functions->compare(point, tree->data);
122  if ((comp < 1) || (comp > n_leafs))
123  return -3;
124  j = MT_insert(point, info, tree->leafs[comp - 1], n_leafs);
125  }
126  else {
127  if (i == 0) {
128  j = info->functions->add_data(point, tree->data, info->dmin);
129  }
130  }
131  }
132  else {
133  k = MT_divide(info, tree, n_leafs);
134  if (k == 1)
135  j = MT_insert(point, info, tree, n_leafs);
136  if (k == -3) {
137  static int once = 0;
138 
139  if (!once) {
140  fprintf(stderr, "Point out of range!\n");
141  once = 1;
142  }
143  }
144  if (k < 0)
145  return k;
146 
147  }
148  return j;
149 }
150 
151 
152 /*!
153  * Divide a tree
154  *
155  * Divides the tree by calling one of tree's functions (divide_data())
156  * and returns the result of divide_data()
157  */
158 int MT_divide(struct tree_info *info, struct multtree *tree, int n_leafs)
159 {
160  int i;
161  struct quaddata **datas;
162  struct multtree *par;
163  struct multtree **leafs;
164 
165  datas = info->functions->divide_data(tree->data, info->kmax, info->dmin);
166  if (datas == NULL) {
167  fprintf(stderr, "datas is NULL\n");
168  return -7;
169  }
170  par = tree;
171  leafs = (struct multtree **)malloc(sizeof(struct multtree *) * n_leafs);
172  for (i = 1; i <= n_leafs; i++) {
173  leafs[i - 1] = MT_tree_new(datas[i], NULL, par, i);
174  }
175  tree->leafs = leafs;
176  return 1;
177 }
178 
179 
180 
181 
182 
183 /*!
184  * Get points inside a region from a tree
185  *
186  * Gets points inside the region defined by DATA from TREE and
187  * adds them to DATA. If the number of eligible
188  * point is more than MAX returns MAX+1 otherwise returns number of points added
189  * to DATA.
190  *
191  * Uses tree's functions intersect() to find leafs that intersect given region
192  * and get_points() to get points from such leafs.
193  */
194 int MT_region_data(struct tree_info *info, struct multtree *tree,
195  struct quaddata *data,
196  int MAX, /*!< max number of points we can add (KMAX2) */
197  int n_leafs
198  )
199 {
200  int n = 0, j;
201 
202  if (tree == NULL) {
203  fprintf(stderr, "MT_region_data: tree is NULL\n");
204  return n;
205  }
206  if (tree->data == NULL) {
207  fprintf(stderr, "MT_region_data: data is NULL\n");
208  return n;
209  }
210  if (info->functions->intersect(data, tree->data)) {
211  if (tree->leafs != NULL) {
212  for (j = 0; j < n_leafs; j++) {
213  if ((n =
214  n + MT_region_data(info, tree->leafs[j], data, MAX - n,
215  n_leafs)) > MAX)
216  return n;
217  }
218  }
219  else {
220  n = info->functions->get_points(data, tree->data, MAX);
221  }
222  return n;
223  }
224  return 0;
225 }
int(* intersect)()
Definition: qtree.h:43
int(* compare)()
Definition: qtree.h:40
#define MAX(a, b)
Definition: kdtree.c:26
struct tree_info * MT_tree_info_new(struct multtree *root, struct multfunc *functions, double dmin, int kmax)
Definition: qtree.c:57
int(* division_check)()
Definition: qtree.h:44
#define NULL
Definition: ccmath.h:32
struct quaddata * data
Definition: qtree.h:58
double dmin
Definition: qtree.h:51
void * malloc(YYSIZE_T)
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))
Definition: qtree.c:33
struct multtree * MT_tree_new(struct quaddata *data, struct multtree **leafs, struct multtree *parent, int multant)
Definition: qtree.c:73
struct multfunc * functions
Definition: qtree.h:50
Definition: qtree.h:38
int(* get_points)()
Definition: qtree.h:45
int kmax
Definition: qtree.h:52
int MT_region_data(struct tree_info *info, struct multtree *tree, struct quaddata *data, int MAX, int n_leafs)
Definition: qtree.c:194
int compare(const void *a, const void *b)
Definition: dgraph.c:177
struct quaddata **(* divide_data)()
Definition: qtree.h:41
int MT_insert(struct triple *point, struct tree_info *info, struct multtree *tree, int n_leafs)
Definition: qtree.c:105
Definition: qtree.h:56
struct multtree * parent
Definition: qtree.h:60
struct multtree * root
Definition: qtree.h:53
int MT_divide(struct tree_info *info, struct multtree *tree, int n_leafs)
Definition: qtree.c:158
struct multtree ** leafs
Definition: qtree.h:59
int multant
Definition: qtree.h:61
int(* add_data)()
Definition: qtree.h:42