GRASS Programmer's Manual  6.4.2(2012)
qtree.c
Go to the documentation of this file.
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 }
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines