GRASS Programmer's Manual
6.4.2(2012)
|
00001 00002 /*- 00003 * Written by H. Mitasova, I. Kosinovsky, D. Gerdes Fall 1993 00004 * University of Illinois 00005 * US Army Construction Engineering Research Lab 00006 * Copyright 1993, H. Mitasova (University of Illinois), 00007 * I. Kosinovsky, (USA-CERL), and D.Gerdes (USA-CERL) 00008 * 00009 * updated by Mitasova Nov. 96, no changes necessary 00010 */ 00011 00012 #include <stdio.h> 00013 #include <stdlib.h> 00014 #include <math.h> 00015 00016 #include <grass/dataquad.h> 00017 #include <grass/qtree.h> 00018 00019 struct multfunc 00020 *MT_functions_new(int (*compare) (struct triple *, struct quaddata *), 00021 struct quaddata **(*divide_data) (struct quaddata *, 00022 int, double), 00023 int (*add_data) (struct triple *, struct quaddata *, 00024 double), 00025 int (*intersect) (struct quaddata *, struct quaddata *), 00026 int (*division_check) (struct quaddata *, int), 00027 int (*get_points) (struct quaddata *, struct quaddata *, 00028 int)) 00029 /* Initializes FUNCTIONS structure with given arguments */ 00030 { 00031 struct multfunc *functions; 00032 if (!(functions = (struct multfunc *)malloc(sizeof(struct multfunc)))) { 00033 return NULL; 00034 } 00035 functions->compare = compare; 00036 functions->divide_data = divide_data; 00037 functions->add_data = add_data; 00038 functions->intersect = intersect; 00039 functions->division_check = division_check; 00040 functions->get_points = get_points; 00041 return functions; 00042 } 00043 00044 struct tree_info *MT_tree_info_new(struct multtree *root, 00045 struct multfunc *functions, double dmin, 00046 int kmax) 00047 /*Initializes TREE_INFO using given arguments */ 00048 { 00049 struct tree_info *info; 00050 if (!(info = (struct tree_info *)malloc(sizeof(struct tree_info)))) { 00051 return NULL; 00052 } 00053 info->root = root; 00054 info->functions = functions; 00055 info->dmin = dmin; 00056 info->kmax = kmax; 00057 return info; 00058 } 00059 00060 struct multtree *MT_tree_new(struct quaddata *data, 00061 struct multtree **leafs, struct multtree *parent, 00062 int multant) 00063 /*Initializes TREE using given arguments */ 00064 { 00065 struct multtree *tree; 00066 if (!(tree = (struct multtree *)malloc(sizeof(struct multtree)))) { 00067 return NULL; 00068 } 00069 tree->data = data; 00070 tree->leafs = leafs; 00071 tree->parent = parent; 00072 tree->multant = multant; 00073 return tree; 00074 } 00075 00076 00077 00078 int MT_insert(struct triple *point, 00079 struct tree_info *info, struct multtree *tree, int n_leafs) 00080 /*First checks for dividing cond. (if n_points>=KMAX) and TREE is a leaf 00081 by calling one of tree's functions (division_check()). 00082 If TREE is not a leaf (is a node) uses function compare to determine 00083 into which "son" we need to insert the point and calls MT_insert() 00084 with this son as a n argument. 00085 If TREE is a leaf but we don't need to divide it (n_points<KMAX) then 00086 calls function add_data(POINT) to add POINT to the data of TREE and 00087 returns the result of add_data() (which returns 1 if the point is 00088 inserted and 0 if its ignored (when its too dense)). 00089 If Division_check returns true, calls MT_divide(TREE) and then calls 00090 insert_quad() to insert the POINT into divided TREE and returns the 00091 result of MT_divide(). */ 00092 { 00093 int j = 0, i, k, comp; 00094 00095 if (tree == NULL) { 00096 fprintf(stderr, "insert: tree is NULL\n"); 00097 return -5; 00098 } 00099 if (tree->data == NULL) { 00100 fprintf(stderr, "insert: tree->data is NULL\n"); 00101 return -5; 00102 } 00103 i = info->functions->division_check(tree->data, info->kmax); 00104 if (i <= 0) { 00105 if (i == -1) { 00106 comp = info->functions->compare(point, tree->data); 00107 if ((comp < 1) || (comp > n_leafs)) 00108 return -3; 00109 j = MT_insert(point, info, tree->leafs[comp - 1], n_leafs); 00110 } 00111 else { 00112 if (i == 0) { 00113 j = info->functions->add_data(point, tree->data, info->dmin); 00114 } 00115 } 00116 } 00117 else { 00118 k = MT_divide(info, tree, n_leafs); 00119 if (k == 1) 00120 j = MT_insert(point, info, tree, n_leafs); 00121 if (k == -3) { 00122 static int once = 0; 00123 00124 if (!once) { 00125 fprintf(stderr, "Point out of range!\n"); 00126 once = 1; 00127 } 00128 } 00129 if (k < 0) 00130 return k; 00131 00132 } 00133 return j; 00134 } 00135 00136 00137 int MT_divide(struct tree_info *info, struct multtree *tree, int n_leafs) 00138 /* Divides the tree by calling one of tree's functions (divide_data()) 00139 and returns the result of divide_data() */ 00140 { 00141 int i; 00142 struct quaddata **datas; 00143 struct multtree *par; 00144 struct multtree **leafs; 00145 00146 datas = info->functions->divide_data(tree->data, info->kmax, info->dmin); 00147 if (datas == NULL) { 00148 fprintf(stderr, "datas is NULL\n"); 00149 return -7; 00150 } 00151 par = tree; 00152 leafs = (struct multtree **)malloc(sizeof(struct multtree *) * n_leafs); 00153 for (i = 1; i <= n_leafs; i++) { 00154 leafs[i - 1] = MT_tree_new(datas[i], NULL, par, i); 00155 } 00156 tree->leafs = leafs; 00157 return 1; 00158 } 00159 00160 00161 00162 00163 00164 00165 int MT_region_data(struct tree_info *info, struct multtree *tree, struct quaddata *data, int MAX, /* max number of points we can add (KMAX2) */ 00166 int n_leafs) 00167 /* Gets points inside the region defined by DATA from TREE and 00168 adds them to DATA. If the number of eligible 00169 point is more than MAX returns MAX+1 othervise returns number of points added 00170 to DATA. 00171 Uses tree's functions intersect() to find leafs that intersect given region 00172 and get_points() to get points from such leafs. */ 00173 { 00174 int n = 0, j; 00175 00176 if (tree == NULL) { 00177 fprintf(stderr, "MT_region_data: tree is NULL\n"); 00178 return n; 00179 } 00180 if (tree->data == NULL) { 00181 fprintf(stderr, "MT_region_data: data is NULL\n"); 00182 return n; 00183 } 00184 if (info->functions->intersect(data, tree->data)) { 00185 if (tree->leafs != NULL) { 00186 for (j = 0; j < n_leafs; j++) { 00187 if ((n = 00188 n + MT_region_data(info, tree->leafs[j], data, MAX - n, 00189 n_leafs)) > MAX) 00190 return n; 00191 } 00192 } 00193 else { 00194 n = info->functions->get_points(data, tree->data, MAX); 00195 } 00196 return n; 00197 } 00198 return 0; 00199 }