Branch data Line data Source code
1 : : //-------------------------------------------------------------------------
2 : : // Filename : OctTreeCell.cpp
3 : : //
4 : : // Purpose : Oct-tree node used by OctTree
5 : : //
6 : : // Special Notes : OctTree handles all memory allocation for this
7 : : // class.
8 : : //
9 : : // Creator : Jason Kraftcheck
10 : : //
11 : : // Creation Date : 01/30/02
12 : : //-------------------------------------------------------------------------
13 : :
14 : : #include "OctTreeCell.hpp"
15 : : #include "CubitVector.hpp"
16 : :
17 : : template <class X, class E>
18 : 0 : OctTreeCell<X,E>::OctTreeCell( OctTreeEntry<X,E> array[], int size )
19 : 0 : : node_count_(size)
20 : : {
21 : 0 : children_ = 0;
22 : 0 : OctTreeEntry<X,E>** prev_ptr_ptr = &head_;
23 [ # # ]: 0 : for( int i = 0; i < node_count_; i++ )
24 : : {
25 : 0 : OctTreeEntry<X,E>* entry = array + i;
26 : 0 : *prev_ptr_ptr = entry;
27 : 0 : prev_ptr_ptr = &(entry->next);
28 : : }
29 : 0 : *prev_ptr_ptr = 0;
30 : 0 : }
31 : :
32 : : template <class X, class E>
33 : 0 : void OctTreeCell<X,E>::append_nodes( DLIList<X*>& list )
34 : : {
35 [ # # ]: 0 : OctTreeEntry<X,E>* entry = node_count_ ? head_ : 0;
36 [ # # ]: 0 : for( ; entry; entry = entry->next )
37 : 0 : list.append( entry->node );
38 : 0 : }
39 : :
40 : : template <class X, class E>
41 : : void OctTreeCell<X,E>::append_all_nodes( DLIList<X*>& list )
42 : : {
43 : : if( node_count_ )
44 : : {
45 : : append_nodes( list );
46 : : }
47 : : else if( children_ )
48 : : {
49 : : for( int i = 0; i < 8; i++ )
50 : : children_[i].append_all_nodes( list );
51 : : }
52 : : }
53 : :
54 : : template <class X, class E>
55 : 0 : void OctTreeCell<X,E>::add_nodes( OctTreeEntry<X,E>* node )
56 : : {
57 [ # # ]: 0 : assert( leaf() );
58 : :
59 : 0 : OctTreeEntry<X,E>* last = node;
60 : 0 : int count = 1;
61 [ # # ]: 0 : while( last->next )
62 : : {
63 : 0 : count++;
64 : 0 : last = last->next;
65 : : }
66 : :
67 : 0 : last->next = head_;
68 : 0 : head_ = node;
69 : 0 : node_count_ += count;
70 : 0 : }
71 : :
72 : : template <class X, class E>
73 : 0 : OctTreeCell<X,E>* OctTreeCell<X,E>::child( int quadrant )
74 : : {
75 [ # # ][ # # ]: 0 : assert( quadrant >= 0 && quadrant < 8 && !node_count_ );
[ # # ]
76 [ # # ]: 0 : if( children_ )
77 : 0 : return children_ + quadrant;
78 : : else
79 : 0 : return 0;
80 : : }
81 : :
82 : : template <class X, class E>
83 : 0 : bool OctTreeCell<X,E>::split( const CubitVector& my_center,
84 : : OctTreeCell<X,E>* storage )
85 : : {
86 [ # # ]: 0 : assert( leaf() );
87 : 0 : bool result = false;
88 : :
89 [ # # ]: 0 : if( node_count_ > 3 )
90 : : {
91 : : // Data is a union. Make sure you never change
92 : : // the order of the following two lines!
93 : 0 : OctTreeEntry<X,E>* node = head_;
94 : 0 : children_ = storage;
95 : :
96 [ # # ]: 0 : while( node )
97 : : {
98 [ # # ]: 0 : CubitVector coords = E::coordinates(node->node);
99 [ # # ][ # # ]: 0 : int x = coords.x() < my_center.x() ? X_MIN : X_MAX;
100 [ # # ][ # # ]: 0 : int y = coords.y() < my_center.y() ? Y_MIN : Y_MAX;
[ # # ]
101 [ # # ][ # # ]: 0 : int z = coords.z() < my_center.z() ? Z_MIN : Z_MAX;
[ # # ]
102 : 0 : OctTreeEntry<X,E>* next = node->next;
103 : 0 : node->next = 0;
104 [ # # ]: 0 : children_[x|y|z].add_nodes( node );
105 : 0 : node = next;
106 : : }
107 : 0 : result = true;
108 : 0 : node_count_ = 0;
109 : : }
110 : :
111 : 0 : return result;
112 : : }
113 : :
114 : : template <class X, class E>
115 : 0 : void OctTreeCell<X,E>::node_locations( CubitVector& box_min,
116 : : CubitVector& box_max,
117 : : CubitVector& average,
118 : : CubitVector* std_dev )
119 : : {
120 [ # # ]: 0 : if( !node_count_ )
121 : 0 : return;
122 : :
123 : :
124 : : double x_min, y_min, z_min;
125 : : double x_max, y_max, z_max;
126 : : double x_avg, y_avg, z_avg;
127 [ # # ]: 0 : CubitVector coords = E::coordinates( head_->node );
128 [ # # ]: 0 : x_min = x_max = x_avg = coords.x();
129 [ # # ]: 0 : y_min = y_max = y_avg = coords.y();
130 [ # # ]: 0 : z_min = z_max = z_avg = coords.z();
131 : :
132 [ # # ]: 0 : for( OctTreeEntry<X,E>* entry = head_->next; entry; entry = entry->next )
133 : : {
134 : 0 : X* node = entry->node;
135 [ # # ][ # # ]: 0 : coords = E::coordinates( node );
136 : :
137 [ # # ]: 0 : double x = coords.x();
138 [ # # ]: 0 : if( x < x_min ) x_min = x;
139 [ # # ]: 0 : else if ( x > x_max ) x_max = x;
140 : 0 : x_avg += x;
141 : :
142 [ # # ]: 0 : double y = coords.y();
143 [ # # ]: 0 : if( y < y_min ) y_min = y;
144 [ # # ]: 0 : else if ( y > y_max ) y_max = y;
145 : 0 : y_avg += y;
146 : :
147 [ # # ]: 0 : double z = coords.z();
148 [ # # ]: 0 : if( z < z_min ) z_min = z;
149 [ # # ]: 0 : else if ( z > z_max ) z_max = z;
150 : 0 : z_avg += z;
151 : : }
152 : :
153 [ # # ]: 0 : box_min.set( x_min, y_min, z_min );
154 [ # # ]: 0 : box_max.set( x_max, y_max, z_max );
155 : :
156 : 0 : double inv = 1.0 / node_count_;
157 : 0 : x_avg *= inv;
158 : 0 : y_avg *= inv;
159 : 0 : z_avg *= inv;
160 [ # # ]: 0 : average.set( x_avg, y_avg, z_avg );
161 : :
162 [ # # ]: 0 : if( std_dev )
163 : : {
164 : 0 : X* hn = head_->node;
165 [ # # ][ # # ]: 0 : coords = E::coordinates(hn);
166 [ # # ][ # # ]: 0 : double x_dev = (coords.x() - x_avg) * (coords.x() - x_avg);
167 [ # # ][ # # ]: 0 : double y_dev = (coords.y() - y_avg) * (coords.y() - y_avg);
168 [ # # ][ # # ]: 0 : double z_dev = (coords.z() - z_avg) * (coords.z() - z_avg);
169 : :
170 [ # # ]: 0 : for( OctTreeEntry<X,E>* entry = head_->next; entry; entry = entry->next )
171 : : {
172 : 0 : X* node = entry->node;
173 [ # # ][ # # ]: 0 : coords = E::coordinates(node);
174 : :
175 [ # # ]: 0 : double x = coords.x();
176 : 0 : double dx = x - x_avg;
177 : 0 : x_dev += dx * dx;
178 : :
179 [ # # ]: 0 : double y = coords.y();
180 : 0 : double dy = y - y_avg;
181 : 0 : y_dev += dy * dy;
182 : :
183 [ # # ]: 0 : double z = coords.z();
184 : 0 : double dz = z - z_avg;
185 : 0 : z_dev += dz * dz;
186 : : }
187 : :
188 : 0 : inv = 1.0 / ( node_count_ - 1 );
189 : 0 : x_dev = sqrt(x_dev * inv);
190 : 0 : y_dev = sqrt(y_dev * inv);
191 : 0 : z_dev = sqrt(z_dev * inv);
192 : :
193 [ # # ]: 0 : std_dev->set( x_dev, y_dev, z_dev );
194 : : }
195 : : }
196 : :
|
