GRASS GIS 7 Programmer's Manual  7.0.4(2016)-r00000
qtree.c
Go to the documentation of this file.
1 
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <math.h>
27 
28 #include <grass/dataquad.h>
29 #include <grass/qtree.h>
30 
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 
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 
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 
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 
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 
194 int MT_region_data(struct tree_info *info, struct multtree *tree,
195  struct quaddata *data,
196  int MAX,
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
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
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
#define MAX(a, b)
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
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