GRASS GIS 8 Programmer's Manual 8.3.2(2024)-exported
Loading...
Searching...
No Matches
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 */
72struct 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 */
103int 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 */
154int 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 */
186int 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 MT_region_data(struct tree_info *info, struct multtree *tree, struct quaddata *data, int MAX, int n_leafs)
Definition qtree.c:186
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
struct tree_info * MT_tree_info_new(struct multtree *root, struct multfunc *functions, double dmin, int kmax)
Definition qtree.c:55
int MT_insert(struct triple *point, struct tree_info *info, struct multtree *tree, int n_leafs)
Definition qtree.c:103
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
#define MAX(a, b)
Definition shpopen.c:65
int(* compare)(struct triple *, struct quaddata *)
Definition qtree.h:37
struct quaddata **(* divide_data)(struct quaddata *, int, double)
Definition qtree.h:38
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 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