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