1 2 /**************************************************************************** 3 * 4 * MODULE: r.viewshed 5 * 6 * AUTHOR(S): Laura Toma, Bowdoin College - ltoma@bowdoin.edu 7 * Yi Zhuang - yzhuang@bowdoin.edu 8 9 * Ported to GRASS by William Richard - 10 * wkrichar@bowdoin.edu or willster3021@gmail.com 11 * Markus Metz: surface interpolation 12 * 13 * Date: april 2011 14 * 15 * PURPOSE: To calculate the viewshed (the visible cells in the 16 * raster) for the given viewpoint (observer) location. The 17 * visibility model is the following: Two points in the raster are 18 * considered visible to each other if the cells where they belong are 19 * visible to each other. Two cells are visible to each other if the 20 * line-of-sight that connects their centers does not intersect the 21 * terrain. The terrain is NOT viewed as a tesselation of flat cells, 22 * i.e. if the line-of-sight does not pass through the cell center, 23 * elevation is determined using bilinear interpolation. 24 * The viewshed algorithm is efficient both in 25 * terms of CPU operations and I/O operations. It has worst-case 26 * complexity O(n lg n) in the RAM model and O(sort(n)) in the 27 * I/O-model. For the algorithm and all the other details see the 28 * paper: "Computing Visibility on * Terrains in External Memory" by 29 * Herman Haverkort, Laura Toma and Yi Zhuang. 30 * 31 * COPYRIGHT: (C) 2008 by the GRASS Development Team 32 * 33 * This program is free software under the GNU General Public License 34 * (>=v2). Read the file COPYING that comes with GRASS for details. 35 * 36 *****************************************************************************/ 37 38 #ifndef __RB_BINARY_SEARCH_TREE__ 39 #define __RB_BINARY_SEARCH_TREE__ 40 41 #define SMALLEST_GRADIENT (- 9999999999999999999999.0) 42 /*this value is returned by findMaxValueWithinDist() is there is no 43 key within that distance. The largest double value is 1.7 E 308 */ 44 45 46 47 #define RB_RED (0) 48 #define RB_BLACK (1) 49 50 /*<===========================================> 51 //public: 52 //The value that's stored in the tree 53 //Change this structure to avoid type casting at run time */ 54 typedef struct tree_value_ 55 { 56 /*this field is mandatory and cannot be removed. 57 //the tree is indexed by this "key". */ 58 double key; 59 60 /*anything else below this line is optional */ 61 double gradient[3]; 62 double angle[3]; 63 double maxGradient; 64 } TreeValue; 65 66 67 /*The node of a tree */ 68 typedef struct tree_node_ 69 { 70 TreeValue value; 71 72 char color; 73 74 struct tree_node_ *left; 75 struct tree_node_ *right; 76 struct tree_node_ *parent; 77 78 } TreeNode; 79 80 typedef struct rbtree_ 81 { 82 TreeNode *root; 83 } RBTree; 84 85 86 87 RBTree *create_tree(TreeValue tv); 88 void delete_tree(RBTree * t); 89 void destroy_sub_tree(TreeNode * node); 90 void insert_into(RBTree * rbt, TreeValue value); 91 void delete_from(RBTree * rbt, double key); 92 TreeNode *search_for_node_with_key(RBTree * rbt, double key); 93 94 95 /*------------The following is designed for kreveld's algorithm-------*/ 96 double find_max_gradient_within_key(RBTree * rbt, double key, double angle, double gradient); 97 98 /*LT: not sure if this is correct */ 99 int is_empty(RBTree * t); 100 101 102 103 104 105 /*<================================================> 106 //private: 107 //The below are private functions you should not 108 //call directly when using the Tree 109 110 //<---------------------------------> 111 //for RB tree only 112 113 //in RB TREE, used to replace NULL */ 114 void init_nil_node(); 115 116 117 /*Left and Right Rotation 118 //the root of the tree may be modified during the rotations 119 //so TreeNode** is passed into the functions */ 120 void left_rotate(TreeNode ** root, TreeNode * x); 121 void right_rotate(TreeNode ** root, TreeNode * y); 122 void rb_insert_fixup(TreeNode ** root, TreeNode * z); 123 void rb_delete_fixup(TreeNode ** root, TreeNode * x); 124 125 /*<------------------------------------> */ 126 127 128 /*compare function used by findMaxValue 129 //-1: v1 < v2 130 //0: v1 = v2 131 //2: v1 > v2 */ 132 char compare_values(TreeValue * v1, TreeValue * v2); 133 134 /*a function used to compare two doubles */ 135 char compare_double(double a, double b); 136 137 /*create a tree node */ 138 TreeNode *create_tree_node(TreeValue value); 139 140 /*create node with its value set to the value given 141 //and insert the node into the tree */ 142 void insert_into_tree(TreeNode ** root, TreeValue value); 143 144 /*delete the node out of the tree */ 145 void delete_from_tree(TreeNode ** root, double key); 146 147 /*search for a node with the given key */ 148 TreeNode *search_for_node(TreeNode * root, double key); 149 150 /*find the min value in the given tree value */ 151 double find_value_min_value(TreeValue * v); 152 153 /*find the max value in the given tree 154 //you need to provide a compare function to compare the nodes */ 155 double find_max_value(TreeNode * root); 156 157 /*find max within the max key */ 158 double find_max_value_within_key(TreeNode * root, double maxKey, double angle, double gradient); 159 160 #endif 161