BICPL: point_bintree.c Source File

00001 /* ---------------------------------------------------------------------------- 00002 @COPYRIGHT : 00003 Copyright 1993,1994,1995 David MacDonald, 00004 McConnell Brain Imaging Centre, 00005 Montreal Neurological Institute, McGill University. 00006 Permission to use, copy, modify, and distribute this 00007 software and its documentation for any purpose and without 00008 fee is hereby granted, provided that the above copyright 00009 notice appear in all copies. The author and McGill University 00010 make no representations about the suitability of this 00011 software for any purpose. It is provided "as is" without 00012 express or implied warranty. 00013 ---------------------------------------------------------------------------- */ 00014 00015 #include <volume_io/internal_volume_io.h> 00016 #include <bicpl/data_structures.h> 00017 #include <bicpl/geom.h> 00018 00019 #ifndef lint 00020 static char rcsid[] = "$Header: /software/source//libraries/bicpl/Data_structures/point_bintree.c,v 1.9 2000/02/06 15:30:11 stever Exp $"; 00021 #endif 00022 00023 private void recursive_find_closest_point( 00024 Point *point, 00025 bintree_node_struct *node, 00026 range_struct *range, 00027 object_struct *object, 00028 int *obj_index, 00029 Real *closest_dist, 00030 Point *closest_point ); 00031 private Real get_point_range_dist( 00032 Point *point, 00033 range_struct *range ); 00034 00035 /* ----------------------------- MNI Header ----------------------------------- 00036 @NAME : find_closest_point_in_bintree 00037 @INPUT : point 00038 bintree 00039 @OUTPUT : object 00040 obj_index 00041 point_on_object 00042 @RETURNS : distance 00043 @DESCRIPTION: Finds the closest point in a set of objects with an 00044 associated bintree to a given point. 00045 @METHOD : 00046 @GLOBALS : 00047 @CALLS : 00048 @CREATED : Jun 21, 1995 David MacDonald 00049 @MODIFIED : 00050 ---------------------------------------------------------------------------- */ 00051 00052 public Real find_closest_point_in_bintree( 00053 Point *point, 00054 bintree_struct_ptr bintree, 00055 object_struct *object, 00056 int *obj_index, 00057 Point *point_on_object ) 00058 { 00059 Real dist; 00060 00061 dist = 1.0e60; 00062 00063 if( obj_index != (int *) NULL ) 00064 *obj_index = -1; 00065 00066 recursive_find_closest_point( point, bintree->root, &bintree->range, 00067 object, obj_index, &dist, point_on_object ); 00068 00069 return( sqrt( dist ) ); 00070 } 00071 00072 /* ----------------------------- MNI Header ----------------------------------- 00073 @NAME : recursive_find_closest_point 00074 @INPUT : point 00075 node 00076 range 00077 @OUTPUT : object 00078 obj_index 00079 closest_dist 00080 closest_point 00081 @RETURNS : 00082 @DESCRIPTION: Traverses the bintree looking for the closest point. 00083 @METHOD : 00084 @GLOBALS : 00085 @CALLS : 00086 @CREATED : Jun 21, 1995 David MacDonald 00087 @MODIFIED : 00088 ---------------------------------------------------------------------------- */ 00089 00090 private void recursive_find_closest_point( 00091 Point *point, 00092 bintree_node_struct *node, 00093 range_struct *range, 00094 object_struct *object, 00095 int *obj_index, 00096 Real *closest_dist, 00097 Point *closest_point ) 00098 { 00099 int i, n_objects, *object_list, axis_index; 00100 int n_to_search; 00101 bintree_node_struct *children[2], *tmp_node; 00102 range_struct children_ranges[2], tmp_range; 00103 Real children_distances[2]; 00104 Real dist; 00105 Point object_point; 00106 Real left_limit, right_limit; 00107 00108 if( bintree_node_is_leaf( node ) ) 00109 { 00110 n_objects = get_bintree_leaf_objects( node, &object_list ); 00111 00112 for_less( i, 0, n_objects ) 00113 { 00114 dist = get_point_object_distance_sq( point, object, object_list[i], 00115 &object_point ); 00116 00117 if( dist < *closest_dist ) 00118 { 00119 *closest_dist = dist; 00120 *closest_point = object_point; 00121 *obj_index = object_list[i]; 00122 } 00123 } 00124 } 00125 else 00126 { 00127 axis_index = get_node_split_axis( node ); 00128 00129 n_to_search = 0; 00130 00131 if( get_bintree_left_child( node, &children[n_to_search] ) ) 00132 { 00133 left_limit = get_node_split_position( children[n_to_search] ); 00134 children_ranges[n_to_search] = *range; 00135 children_ranges[n_to_search].limits[axis_index][1] = 00136 (float) left_limit; 00137 children_distances[n_to_search] = get_point_range_dist( point, 00138 &children_ranges[n_to_search] ); 00139 00140 if( children_distances[n_to_search] <= *closest_dist ) 00141 ++n_to_search; 00142 } 00143 00144 if( get_bintree_right_child( node, &children[n_to_search] ) ) 00145 { 00146 right_limit = get_node_split_position( children[n_to_search] ); 00147 children_ranges[n_to_search] = *range; 00148 children_ranges[n_to_search].limits[axis_index][0] = 00149 (float) right_limit; 00150 children_distances[n_to_search] = get_point_range_dist( point, 00151 &children_ranges[n_to_search] ); 00152 00153 if( children_distances[n_to_search] <= *closest_dist ) 00154 ++n_to_search; 00155 } 00156 00157 if( n_to_search == 2 && children_distances[1] < children_distances[0] ) 00158 { 00159 tmp_range = children_ranges[0]; 00160 children_ranges[0] = children_ranges[1]; 00161 children_ranges[1] = tmp_range; 00162 tmp_node = children[0]; 00163 children[0] = children[1]; 00164 children[1] = tmp_node; 00165 } 00166 00167 for_less( i, 0, n_to_search ) 00168 { 00169 recursive_find_closest_point( point, children[i], 00170 &children_ranges[i], 00171 object, obj_index, 00172 closest_dist, closest_point ); 00173 } 00174 } 00175 } 00176 00177 /* ----------------------------- MNI Header ----------------------------------- 00178 @NAME : get_point_range_dist 00179 @INPUT : point 00180 range 00181 @OUTPUT : 00182 @RETURNS : 00183 @DESCRIPTION: Gets the distance to a box. 00184 @METHOD : 00185 @GLOBALS : 00186 @CALLS : 00187 @CREATED : Jun 21, 1995 David MacDonald 00188 @MODIFIED : 00189 ---------------------------------------------------------------------------- */ 00190 00191 private Real get_point_range_dist( 00192 Point *point, 00193 range_struct *range ) 00194 { 00195 int c; 00196 Real min_plane, max_plane, point_pos, dist, sum; 00197 00198 sum = 0.0; 00199 00200 for_less( c, 0, N_DIMENSIONS ) 00201 { 00202 min_plane = (Real) range->limits[c][0]; 00203 max_plane = (Real) range->limits[c][1]; 00204 point_pos = (Real) Point_coord(*point,c); 00205 00206 if( point_pos < min_plane ) 00207 dist = min_plane - point_pos; 00208 else if( point_pos > max_plane ) 00209 dist = point_pos - max_plane; 00210 else 00211 dist = 0.0; 00212 00213 sum += dist * dist; 00214 } 00215 00216 return( sum ); 00217 } 00218 00219 private void recursive_find_closest_vertex( 00220 Point *point, 00221 bintree_node_struct *node, 00222 range_struct *range, 00223 object_struct *object, 00224 Real *closest_dist, 00225 int *closest_vertex ); 00226 00227 /* ----------------------------- MNI Header ----------------------------------- 00228 @NAME : find_closest_vertex_in_bintree 00229 @INPUT : point 00230 bintree 00231 @OUTPUT : object 00232 vertex_on_object 00233 @RETURNS : distance 00234 @DESCRIPTION: Finds the closest vertex in a set of objects with an 00235 associated bintree to a given point. 00236 @METHOD : 00237 @GLOBALS : 00238 @CALLS : 00239 @CREATED : Jun 21, 1995 David MacDonald 00240 @MODIFIED : 00241 ---------------------------------------------------------------------------- */ 00242 00243 public Real find_closest_vertex_in_bintree( 00244 Point *point, 00245 bintree_struct_ptr bintree, 00246 object_struct *object, 00247 int *vertex_on_object ) 00248 { 00249 Real dist; 00250 00251 dist = 1.0e30; 00252 00253 recursive_find_closest_vertex( point, bintree->root, &bintree->range, 00254 object, &dist, vertex_on_object ); 00255 00256 return( dist ); 00257 } 00258 00259 /* ----------------------------- MNI Header ----------------------------------- 00260 @NAME : recursive_find_closest_vertex 00261 @INPUT : point 00262 node 00263 range 00264 @OUTPUT : object 00265 closest_dist 00266 closest_vertex 00267 @RETURNS : 00268 @DESCRIPTION: Traverses the bintree looking for the closest point. 00269 @METHOD : 00270 @GLOBALS : 00271 @CALLS : 00272 @CREATED : Jun 21, 1995 David MacDonald 00273 @MODIFIED : 00274 ---------------------------------------------------------------------------- */ 00275 00276 private void recursive_find_closest_vertex( 00277 Point *point, 00278 bintree_node_struct *node, 00279 range_struct *range, 00280 object_struct *object, 00281 Real *closest_dist, 00282 int *closest_vertex ) 00283 { 00284 int i, n_objects, *object_list, axis_index; 00285 int n_to_search; 00286 bintree_node_struct *children[2], *tmp_node; 00287 range_struct children_ranges[2], tmp_range; 00288 Real children_distances[2]; 00289 Real dist; 00290 int object_vertex; 00291 Real left_limit, right_limit; 00292 00293 if( bintree_node_is_leaf( node ) ) 00294 { 00295 n_objects = get_bintree_leaf_objects( node, &object_list ); 00296 00297 for_less( i, 0, n_objects ) 00298 { 00299 dist = get_point_object_vertex_distance( point, object, 00300 object_list[i], &object_vertex ); 00301 00302 if( dist < *closest_dist ) 00303 { 00304 *closest_dist = dist; 00305 *closest_vertex = object_vertex; 00306 } 00307 } 00308 } 00309 else 00310 { 00311 axis_index = get_node_split_axis( node ); 00312 00313 n_to_search = 0; 00314 00315 if( get_bintree_left_child( node, &children[n_to_search] ) ) 00316 { 00317 left_limit = get_node_split_position( children[n_to_search] ); 00318 children_ranges[n_to_search] = *range; 00319 children_ranges[n_to_search].limits[axis_index][1] = 00320 (float) left_limit; 00321 children_distances[n_to_search] = get_point_range_dist( point, 00322 &children_ranges[n_to_search] ); 00323 00324 if( children_distances[n_to_search] <= 00325 *closest_dist * *closest_dist ) 00326 ++n_to_search; 00327 } 00328 00329 if( get_bintree_right_child( node, &children[n_to_search] ) ) 00330 { 00331 right_limit = get_node_split_position( children[n_to_search] ); 00332 children_ranges[n_to_search] = *range; 00333 children_ranges[n_to_search].limits[axis_index][0] = 00334 (float) right_limit; 00335 children_distances[n_to_search] = get_point_range_dist( point, 00336 &children_ranges[n_to_search] ); 00337 00338 if( children_distances[n_to_search] <= 00339 *closest_dist * *closest_dist ) 00340 ++n_to_search; 00341 } 00342 00343 if( n_to_search == 2 && children_distances[1] < children_distances[0] ) 00344 { 00345 tmp_range = children_ranges[0]; 00346 children_ranges[0] = children_ranges[1]; 00347 children_ranges[1] = tmp_range; 00348 tmp_node = children[0]; 00349 children[0] = children[1]; 00350 children[1] = tmp_node; 00351 } 00352 00353 for_less( i, 0, n_to_search ) 00354 { 00355 recursive_find_closest_vertex( point, children[i], 00356 &children_ranges[i], 00357 object, 00358 closest_dist, closest_vertex ); 00359 } 00360 } 00361 }