/*! * \file qtree.c * * \author * H. Mitasova, I. Kosinovsky, D. Gerdes, Fall 1993, * University of Illinois and * US Army Construction Engineering Research Lab * * \author H. Mitasova (University of Illinois), * \author I. Kosinovsky, (USA-CERL) * \author D.Gerdes (USA-CERL) * * \author updated/checked by Mitasova Nov. 96 (no changes necessary) * * \copyright * (C) 1993-1996 by Helena Mitasova and the GRASS Development Team * * \copyright * This program is free software under the * GNU General Public License (>=v2). * Read the file COPYING that comes with GRASS for details. */ #include #include #include #include #include /*! Initializes multfunc structure with given arguments */ 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)) { struct multfunc *functions; if (!(functions = (struct multfunc *)malloc(sizeof(struct multfunc)))) { return NULL; } functions->compare = compare; functions->divide_data = divide_data; functions->add_data = add_data; functions->intersect = intersect; functions->division_check = division_check; functions->get_points = get_points; return functions; } /*! Initializes tree_info using given arguments */ struct tree_info *MT_tree_info_new(struct multtree *root, struct multfunc *functions, double dmin, int kmax) { struct tree_info *info; if (!(info = (struct tree_info *)malloc(sizeof(struct tree_info)))) { return NULL; } info->root = root; info->functions = functions; info->dmin = dmin; info->kmax = kmax; return info; } /** Initializes multtree using given arguments */ struct multtree *MT_tree_new(struct quaddata *data, struct multtree **leafs, struct multtree *parent, int multant) { struct multtree *tree; if (!(tree = (struct multtree *)malloc(sizeof(struct multtree)))) { return NULL; } tree->data = data; tree->leafs = leafs; tree->parent = parent; tree->multant = multant; return tree; } /*! * First checks for dividing cond. (if n_points>=KMAX) and tree * is a leaf by calling one of tree's functions (`division_check()`). * If tree is not a leaf (is a node) uses function compare to determine * into which "son" we need to insert the point and calls MT_insert() * with this son as a n argument. * * If TREE is a leaf but we don't need to divide it (n_pointsdata == NULL) { fprintf(stderr, "insert: tree->data is NULL\n"); return -5; } i = info->functions->division_check(tree->data, info->kmax); if (i <= 0) { if (i == -1) { comp = info->functions->compare(point, tree->data); if ((comp < 1) || (comp > n_leafs)) return -3; j = MT_insert(point, info, tree->leafs[comp - 1], n_leafs); } else { if (i == 0) { j = info->functions->add_data(point, tree->data, info->dmin); } } } else { k = MT_divide(info, tree, n_leafs); if (k == 1) j = MT_insert(point, info, tree, n_leafs); if (k == -3) { static int once = 0; if (!once) { fprintf(stderr, "Point out of range!\n"); once = 1; } } if (k < 0) return k; } return j; } /*! * Divide a tree * * Divides the tree by calling one of tree's functions (divide_data()) * and returns the result of divide_data() */ int MT_divide(struct tree_info *info, struct multtree *tree, int n_leafs) { int i; struct quaddata **datas; struct multtree *par; struct multtree **leafs; datas = info->functions->divide_data(tree->data, info->kmax, info->dmin); if (datas == NULL) { fprintf(stderr, "datas is NULL\n"); return -7; } par = tree; leafs = (struct multtree **)malloc(sizeof(struct multtree *) * n_leafs); for (i = 1; i <= n_leafs; i++) { leafs[i - 1] = MT_tree_new(datas[i], NULL, par, i); } tree->leafs = leafs; return 1; } /*! * Get points inside a region from a tree * * Gets points inside the region defined by DATA from TREE and * adds them to DATA. If the number of eligible * point is more than MAX returns MAX+1 otherwise returns number of points added * to DATA. * * Uses tree's functions intersect() to find leafs that intersect given region * and get_points() to get points from such leafs. */ int MT_region_data(struct tree_info *info, struct multtree *tree, struct quaddata *data, int MAX, /*!< max number of points we can add (KMAX2) */ int n_leafs ) { int n = 0, j; if (tree == NULL) { fprintf(stderr, "MT_region_data: tree is NULL\n"); return n; } if (tree->data == NULL) { fprintf(stderr, "MT_region_data: data is NULL\n"); return n; } if (info->functions->intersect(data, tree->data)) { if (tree->leafs != NULL) { for (j = 0; j < n_leafs; j++) { if ((n = n + MT_region_data(info, tree->leafs[j], data, MAX - n, n_leafs)) > MAX) return n; } } else { n = info->functions->get_points(data, tree->data, MAX); } return n; } return 0; }