GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-36359e2344
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 */
33  int (*compare)(struct triple *, struct quaddata *),
34  struct quaddata **(*divide_data)(struct quaddata *, int, double),
35  int (*add_data)(struct triple *, struct quaddata *, double),
36  int (*intersect)(struct quaddata *, struct quaddata *),
37  int (*division_check)(struct quaddata *, int),
38  int (*get_points)(struct quaddata *, struct quaddata *, int))
39 {
40  struct multfunc *functions;
41 
42  if (!(functions = (struct multfunc *)malloc(sizeof(struct multfunc)))) {
43  return NULL;
44  }
45  functions->compare = compare;
46  functions->divide_data = divide_data;
47  functions->add_data = add_data;
48  functions->intersect = intersect;
49  functions->division_check = division_check;
50  functions->get_points = get_points;
51  return functions;
52 }
53 
54 /*! Initializes tree_info using given arguments */
56  struct multfunc *functions, double dmin,
57  int kmax)
58 {
59  struct tree_info *info;
60 
61  if (!(info = (struct tree_info *)malloc(sizeof(struct tree_info)))) {
62  return NULL;
63  }
64  info->root = root;
65  info->functions = functions;
66  info->dmin = dmin;
67  info->kmax = kmax;
68  return info;
69 }
70 
71 /** Initializes multtree using given arguments */
72 struct multtree *MT_tree_new(struct quaddata *data, struct multtree **leafs,
73  struct multtree *parent, int multant)
74 {
75  struct multtree *tree;
76 
77  if (!(tree = (struct multtree *)malloc(sizeof(struct multtree)))) {
78  return NULL;
79  }
80  tree->data = data;
81  tree->leafs = leafs;
82  tree->parent = parent;
83  tree->multant = multant;
84  return tree;
85 }
86 
87 /*!
88  * First checks for dividing cond. (if n_points>=KMAX) and tree
89  * is a leaf by calling one of tree's functions (`division_check()`).
90  * If tree is not a leaf (is a node) uses function compare to determine
91  * into which "son" we need to insert the point and calls MT_insert()
92  * with this son as a n argument.
93  *
94  * If TREE is a leaf but we don't need to divide it (n_points<KMAX) then
95  * calls function `add_data(point, ...)` to add point to the data of tree
96  * and returns the result of `add_data()` (which returns 1 if the point is
97  * inserted and 0 if its ignored (when its too dense)).
98  *
99  * If `division_check()` returns true, calls MT_divide() and then calls
100  * MT_insert() to insert the point into divided tree and returns the
101  * result of MT_divide().
102  */
103 int MT_insert(struct triple *point, struct tree_info *info,
104  struct multtree *tree, int n_leafs)
105 {
106  int j = 0, i, k, comp;
107 
108  if (tree == NULL) {
109  fprintf(stderr, "insert: tree is NULL\n");
110  return -5;
111  }
112  if (tree->data == NULL) {
113  fprintf(stderr, "insert: tree->data is NULL\n");
114  return -5;
115  }
116  i = info->functions->division_check(tree->data, info->kmax);
117  if (i <= 0) {
118  if (i == -1) {
119  comp = info->functions->compare(point, tree->data);
120  if ((comp < 1) || (comp > n_leafs))
121  return -3;
122  j = MT_insert(point, info, tree->leafs[comp - 1], n_leafs);
123  }
124  else {
125  if (i == 0) {
126  j = info->functions->add_data(point, tree->data, info->dmin);
127  }
128  }
129  }
130  else {
131  k = MT_divide(info, tree, n_leafs);
132  if (k == 1)
133  j = MT_insert(point, info, tree, n_leafs);
134  if (k == -3) {
135  static int once = 0;
136 
137  if (!once) {
138  fprintf(stderr, "Point out of range!\n");
139  once = 1;
140  }
141  }
142  if (k < 0)
143  return k;
144  }
145  return j;
146 }
147 
148 /*!
149  * Divide a tree
150  *
151  * Divides the tree by calling one of tree's functions (divide_data())
152  * and returns the result of divide_data()
153  */
154 int MT_divide(struct tree_info *info, struct multtree *tree, int n_leafs)
155 {
156  int i;
157  struct quaddata **datas;
158  struct multtree *par;
159  struct multtree **leafs;
160 
161  datas = info->functions->divide_data(tree->data, info->kmax, info->dmin);
162  if (datas == NULL) {
163  fprintf(stderr, "datas is NULL\n");
164  return -7;
165  }
166  par = tree;
167  leafs = (struct multtree **)malloc(sizeof(struct multtree *) * n_leafs);
168  for (i = 1; i <= n_leafs; i++) {
169  leafs[i - 1] = MT_tree_new(datas[i], NULL, par, i);
170  }
171  tree->leafs = leafs;
172  return 1;
173 }
174 
175 /*!
176  * Get points inside a region from a tree
177  *
178  * Gets points inside the region defined by DATA from TREE and
179  * adds them to DATA. If the number of eligible
180  * point is more than MAX returns MAX+1 otherwise returns number of points added
181  * to DATA.
182  *
183  * Uses tree's functions intersect() to find leafs that intersect given region
184  * and get_points() to get points from such leafs.
185  */
186 int MT_region_data(struct tree_info *info, struct multtree *tree,
187  struct quaddata *data,
188  int MAX, /*!< max number of points we can add (KMAX2) */
189  int n_leafs)
190 {
191  int n = 0, j;
192 
193  if (tree == NULL) {
194  fprintf(stderr, "MT_region_data: tree is NULL\n");
195  return n;
196  }
197  if (tree->data == NULL) {
198  fprintf(stderr, "MT_region_data: data is NULL\n");
199  return n;
200  }
201  if (info->functions->intersect(data, tree->data)) {
202  if (tree->leafs != NULL) {
203  for (j = 0; j < n_leafs; j++) {
204  if ((n = n + MT_region_data(info, tree->leafs[j], data, MAX - n,
205  n_leafs)) > MAX)
206  return n;
207  }
208  }
209  else {
210  n = info->functions->get_points(data, tree->data, MAX);
211  }
212  return n;
213  }
214  return 0;
215 }
#define NULL
Definition: ccmath.h:32
int compare(const void *a, const void *b)
Definition: dgraph.c:168
#define MAX(a, b)
Definition: gis.h:149
int MT_region_data(struct tree_info *info, struct multtree *tree, struct quaddata *data, int MAX, int n_leafs)
Definition: qtree.c:186
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:32
struct tree_info * MT_tree_info_new(struct multtree *root, struct multfunc *functions, double dmin, int kmax)
Definition: qtree.c:55
struct multtree * MT_tree_new(struct quaddata *data, struct multtree **leafs, struct multtree *parent, int multant)
Definition: qtree.c:72
int MT_divide(struct tree_info *info, struct multtree *tree, int n_leafs)
Definition: qtree.c:154
int MT_insert(struct triple *point, struct tree_info *info, struct multtree *tree, int n_leafs)
Definition: qtree.c:103
void * malloc(YYSIZE_T)
Definition: qtree.h:36
int(* compare)(struct triple *, struct quaddata *)
Definition: qtree.h:37
int(* division_check)(struct quaddata *, int)
Definition: qtree.h:41
int(* get_points)(struct quaddata *, struct quaddata *, int)
Definition: qtree.h:42
int(* add_data)(struct triple *, struct quaddata *, double)
Definition: qtree.h:39
int(* intersect)(struct quaddata *, struct quaddata *)
Definition: qtree.h:40
struct quaddata **(* divide_data)(struct quaddata *, int, double)
Definition: qtree.h:38
Definition: qtree.h:52
struct multtree ** leafs
Definition: qtree.h:54
struct quaddata * data
Definition: qtree.h:53
struct multtree * parent
Definition: qtree.h:55
int multant
Definition: qtree.h:56
struct multtree * root
Definition: qtree.h:49
int kmax
Definition: qtree.h:48
struct multfunc * functions
Definition: qtree.h:46
double dmin
Definition: qtree.h:47