| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Copyright (c) 2000-2022 Inria | ||
| 3 | * All rights reserved. | ||
| 4 | * | ||
| 5 | * Redistribution and use in source and binary forms, with or without | ||
| 6 | * modification, are permitted provided that the following conditions are met: | ||
| 7 | * | ||
| 8 | * * Redistributions of source code must retain the above copyright notice, | ||
| 9 | * this list of conditions and the following disclaimer. | ||
| 10 | * * Redistributions in binary form must reproduce the above copyright notice, | ||
| 11 | * this list of conditions and the following disclaimer in the documentation | ||
| 12 | * and/or other materials provided with the distribution. | ||
| 13 | * * Neither the name of the ALICE Project-Team nor the names of its | ||
| 14 | * contributors may be used to endorse or promote products derived from this | ||
| 15 | * software without specific prior written permission. | ||
| 16 | * | ||
| 17 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | ||
| 18 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
| 19 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
| 20 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | ||
| 21 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | ||
| 22 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | ||
| 23 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | ||
| 24 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | ||
| 25 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | ||
| 26 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | ||
| 27 | * POSSIBILITY OF SUCH DAMAGE. | ||
| 28 | * | ||
| 29 | * Contact: Bruno Levy | ||
| 30 | * | ||
| 31 | * https://www.inria.fr/fr/bruno-levy | ||
| 32 | * | ||
| 33 | * Inria, | ||
| 34 | * Domaine de Voluceau, | ||
| 35 | * 78150 Le Chesnay - Rocquencourt | ||
| 36 | * FRANCE | ||
| 37 | * | ||
| 38 | */ | ||
| 39 | |||
| 40 | #ifndef GEOGRAM_POINTS_KD_TREE | ||
| 41 | #define GEOGRAM_POINTS_KD_TREE | ||
| 42 | |||
| 43 | #include <geogram/basic/common.h> | ||
| 44 | #include <geogram/points/nn_search.h> | ||
| 45 | #include <algorithm> | ||
| 46 | |||
| 47 | /** | ||
| 48 | * \file geogram/points/kd_tree.h | ||
| 49 | * \brief An implementation of NearestNeighborSearch with a kd-tree | ||
| 50 | */ | ||
| 51 | |||
| 52 | namespace GEO { | ||
| 53 | |||
| 54 | /** | ||
| 55 | * \brief Base class for all Kd-tree implementations. | ||
| 56 | */ | ||
| 57 | class GEOGRAM_API KdTree : public NearestNeighborSearch { | ||
| 58 | public: | ||
| 59 | /** | ||
| 60 | * \brief KdTree constructor. | ||
| 61 | * \param[in] dim dimension of the points. | ||
| 62 | */ | ||
| 63 | KdTree(coord_index_t dim); | ||
| 64 | |||
| 65 | /** \copydoc NearestNeighborSearch::set_points() */ | ||
| 66 | void set_points(index_t nb_points, const double* points) override; | ||
| 67 | |||
| 68 | /** \copydoc NearestNeighborSearch::stride_supported() */ | ||
| 69 | bool stride_supported() const override; | ||
| 70 | |||
| 71 | /** \copydoc NearestNeighborSearch::set_points() */ | ||
| 72 | void set_points( | ||
| 73 | index_t nb_points, const double* points, index_t stride | ||
| 74 | ) override; | ||
| 75 | |||
| 76 | /** \copydoc NearestNeighborSearch::get_nearest_neighbors() */ | ||
| 77 | void get_nearest_neighbors( | ||
| 78 | index_t nb_neighbors, | ||
| 79 | const double* query_point, | ||
| 80 | index_t* neighbors, | ||
| 81 | double* neighbors_sq_dist | ||
| 82 | ) const override; | ||
| 83 | |||
| 84 | /** \copydoc NearestNeighborSearch::get_nearest_neighbors() */ | ||
| 85 | void get_nearest_neighbors( | ||
| 86 | index_t nb_neighbors, | ||
| 87 | const double* query_point, | ||
| 88 | index_t* neighbors, | ||
| 89 | double* neighbors_sq_dist, | ||
| 90 | KeepInitialValues | ||
| 91 | ) const override; | ||
| 92 | |||
| 93 | /** \copydoc NearestNeighborSearch::get_nearest_neighbors() */ | ||
| 94 | void get_nearest_neighbors( | ||
| 95 | index_t nb_neighbors, | ||
| 96 | index_t query_point, | ||
| 97 | index_t* neighbors, | ||
| 98 | double* neighbors_sq_dist | ||
| 99 | ) const override; | ||
| 100 | |||
| 101 | /**********************************************************************/ | ||
| 102 | |||
| 103 | /** | ||
| 104 | * \brief The context for traversing a KdTree. | ||
| 105 | * \details Stores a sorted sequence of (point,distance) | ||
| 106 | * couples. | ||
| 107 | */ | ||
| 108 | struct NearestNeighbors { | ||
| 109 | |||
| 110 | /** | ||
| 111 | * \brief Creates a new NearestNeighbors | ||
| 112 | * \details Storage is provided and managed by the caller. | ||
| 113 | * Initializes neighbors_sq_dist[0..nb_neigh-1] | ||
| 114 | * to Numeric::max_float64() and neighbors[0..nb_neigh-1] | ||
| 115 | * to NO_INDEX. | ||
| 116 | * \param[in] nb_neighbors_in number of neighbors to retrieve | ||
| 117 | * \param[in] user_neighbors_in storage for the neighbors, allocated | ||
| 118 | * and managed by caller, with space for nb_neighbors_in integers | ||
| 119 | * \param[in] user_neighbors_sq_dist_in storage for neighbors | ||
| 120 | * squared distance, allocated and managed by caller, | ||
| 121 | * with space for nb_neighbors_in doubles | ||
| 122 | * \param[in] work_neighbors_in storage for the neighbors, allocated | ||
| 123 | * and managed by caller, with space | ||
| 124 | * for nb_neighbors_in + 1 integers | ||
| 125 | * \param[in] work_neighbors_sq_dist_in storage | ||
| 126 | * for neighbors squared distance, allocated and managed | ||
| 127 | * by caller, with space for nb_neighbors_in + 1 doubles | ||
| 128 | */ | ||
| 129 | NearestNeighbors( | ||
| 130 | index_t nb_neighbors_in, | ||
| 131 | index_t* user_neighbors_in, | ||
| 132 | double* user_neighbors_sq_dist_in, | ||
| 133 | index_t* work_neighbors_in, | ||
| 134 | double* work_neighbors_sq_dist_in | ||
| 135 | 1546041 | ) : | |
| 136 | 1546041 | nb_neighbors(0), | |
| 137 | 1546041 | nb_neighbors_max(nb_neighbors_in), | |
| 138 | 1546041 | neighbors(work_neighbors_in), | |
| 139 | 1546041 | neighbors_sq_dist(work_neighbors_sq_dist_in), | |
| 140 | 1546041 | user_neighbors(user_neighbors_in), | |
| 141 | 1546041 | user_neighbors_sq_dist(user_neighbors_sq_dist_in), | |
| 142 | 1546041 | nb_visited(0) | |
| 143 | { | ||
| 144 | // Yes, '<=' because we got space for n+1 neigbors | ||
| 145 | // in the work arrays. | ||
| 146 | for(index_t i = 0; i <= nb_neighbors; ++i) { | ||
| 147 | 1546041 | neighbors[i] = NO_INDEX; | |
| 148 | 1546041 | neighbors_sq_dist[i] = Numeric::max_float64(); | |
| 149 | } | ||
| 150 | } | ||
| 151 | |||
| 152 | /** | ||
| 153 | * \brief Gets the squared distance to the furthest | ||
| 154 | * neighbor. | ||
| 155 | */ | ||
| 156 | double furthest_neighbor_sq_dist() const { | ||
| 157 | return | ||
| 158 |
8/8✓ Branch 0 taken 10361018 times.
✓ Branch 1 taken 4777099 times.
✓ Branch 2 taken 31606364 times.
✓ Branch 3 taken 38770741 times.
✓ Branch 4 taken 15332383 times.
✓ Branch 5 taken 1665728 times.
✓ Branch 6 taken 15250638 times.
✓ Branch 7 taken 1565330 times.
|
119329301 | nb_neighbors == nb_neighbors_max ? |
| 159 | 72550403 | neighbors_sq_dist[nb_neighbors - 1] : | |
| 160 | 72550403 | Numeric::max_float64() | |
| 161 | ; | ||
| 162 | } | ||
| 163 | |||
| 164 | /** | ||
| 165 | * \brief Inserts a new neighbor. | ||
| 166 | * \details Only the nb_neighbor nearest points are kept. | ||
| 167 | * \param[in] neighbor the index of the point | ||
| 168 | * \param[in] sq_dist the squared distance between the point | ||
| 169 | * and the query point. | ||
| 170 | * \pre sq_dist <= furthest_neighbor_sq_dist() (needs to be tested | ||
| 171 | * by client code before insertion). | ||
| 172 | */ | ||
| 173 | 70377105 | void insert( | |
| 174 | index_t neighbor, double sq_dist | ||
| 175 | ) { | ||
| 176 | geo_debug_assert( | ||
| 177 | sq_dist <= furthest_neighbor_sq_dist() | ||
| 178 | ); | ||
| 179 | |||
| 180 | int i; | ||
| 181 |
2/2✓ Branch 0 taken 1143998442 times.
✓ Branch 1 taken 5053627 times.
|
1149052069 | for(i=int(nb_neighbors); i>0; --i) { |
| 182 |
2/2✓ Branch 0 taken 1078674964 times.
✓ Branch 1 taken 65323478 times.
|
1143998442 | if(neighbors_sq_dist[i - 1] < sq_dist) { |
| 183 | break; | ||
| 184 | } | ||
| 185 | 1078674964 | neighbors[i] = neighbors[i - 1]; | |
| 186 | 1078674964 | neighbors_sq_dist[i] = neighbors_sq_dist[i - 1]; | |
| 187 | } | ||
| 188 | |||
| 189 | 70377105 | neighbors[i] = neighbor; | |
| 190 | 70377105 | neighbors_sq_dist[i] = sq_dist; | |
| 191 | |||
| 192 |
2/2✓ Branch 0 taken 40316782 times.
✓ Branch 1 taken 30060323 times.
|
70377105 | if(nb_neighbors < nb_neighbors_max) { |
| 193 | 40316782 | ++nb_neighbors; | |
| 194 | } | ||
| 195 | 70377105 | } | |
| 196 | |||
| 197 | /** | ||
| 198 | * \brief Copies the user neighbors and distances into | ||
| 199 | * the work zone and initializes nb_neighbors to max_nb_neighbors. | ||
| 200 | * \details This function is called by nearest neighbors search when | ||
| 201 | * KeepInitialValues is specified, to initialize search | ||
| 202 | * from user-provided initial guess. | ||
| 203 | */ | ||
| 204 | ✗ | void copy_from_user() { | |
| 205 | ✗ | for(index_t i=0; i<nb_neighbors_max; ++i) { | |
| 206 | ✗ | neighbors[i] = user_neighbors[i]; | |
| 207 | ✗ | neighbors_sq_dist[i] = user_neighbors_sq_dist[i]; | |
| 208 | } | ||
| 209 | ✗ | neighbors[nb_neighbors_max] = NO_INDEX; | |
| 210 | ✗ | neighbors_sq_dist[nb_neighbors_max] = Numeric::max_float64(); | |
| 211 | ✗ | nb_neighbors = nb_neighbors_max; | |
| 212 | ✗ | } | |
| 213 | |||
| 214 | /** | ||
| 215 | * \brief Copies the found nearest neighbors from the work zone | ||
| 216 | * to the user neighbors and squared distance arrays. | ||
| 217 | * \details This function is called by find_nearest_neighbors() | ||
| 218 | * after traversal of the tree. | ||
| 219 | */ | ||
| 220 | void copy_to_user() { | ||
| 221 |
2/4✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 40316782 times.
✓ Branch 3 taken 1546041 times.
|
41862823 | for(index_t i=0; i<nb_neighbors_max; ++i) { |
| 222 | 40316782 | user_neighbors[i] = neighbors[i]; | |
| 223 | 40316782 | user_neighbors_sq_dist[i] = neighbors_sq_dist[i]; | |
| 224 | } | ||
| 225 | } | ||
| 226 | |||
| 227 | /** \brief Current number of neighbors. */ | ||
| 228 | index_t nb_neighbors; | ||
| 229 | |||
| 230 | /** \brief Maximum number of neighbors. */ | ||
| 231 | index_t nb_neighbors_max; | ||
| 232 | |||
| 233 | /** | ||
| 234 | * \brief Internal array of neighbors. | ||
| 235 | * \details size = nb_neigbors_max + 1 | ||
| 236 | */ | ||
| 237 | index_t* neighbors; | ||
| 238 | |||
| 239 | /** | ||
| 240 | * \brief Internal squared distance to neigbors. | ||
| 241 | * \details size = nb_neigbors_max + 1 | ||
| 242 | */ | ||
| 243 | double* neighbors_sq_dist; | ||
| 244 | |||
| 245 | /** | ||
| 246 | * \brief User-provided array of neighbors. | ||
| 247 | * \details size = nb_neighbors_max | ||
| 248 | */ | ||
| 249 | index_t* user_neighbors; | ||
| 250 | |||
| 251 | /** | ||
| 252 | * \brief User-provided array of neighbors | ||
| 253 | * squared distances. | ||
| 254 | * \details size = nb_neighbors_max | ||
| 255 | */ | ||
| 256 | double* user_neighbors_sq_dist; | ||
| 257 | |||
| 258 | /** | ||
| 259 | * \brief Number of points visited during | ||
| 260 | * traversal. | ||
| 261 | */ | ||
| 262 | size_t nb_visited; | ||
| 263 | }; | ||
| 264 | |||
| 265 | /** | ||
| 266 | * \brief The recursive function to implement KdTree traversal and | ||
| 267 | * nearest neighbors computation. | ||
| 268 | * \note This is a lower-level function, most users will not use it. | ||
| 269 | * \details Traverses the subtree under the | ||
| 270 | * node_index node that corresponds to the | ||
| 271 | * [b,e) point sequence. Nearest neighbors | ||
| 272 | * are inserted into neighbors during | ||
| 273 | * traversal. | ||
| 274 | * \param[in] node_index index of the current node in the Kd tree | ||
| 275 | * \param[in] b index of the first point in the subtree under | ||
| 276 | * node \p node_index | ||
| 277 | * \param[in] e one position past the index of the last point in the | ||
| 278 | * subtree under node \p node_index | ||
| 279 | * \param[in,out] bbox_min coordinates of the lower | ||
| 280 | * corner of the bounding box. | ||
| 281 | * Allocated and managed by caller. | ||
| 282 | * Modified by the function and restored on exit. | ||
| 283 | * \param[in,out] bbox_max coordinates of the | ||
| 284 | * upper corner of the bounding box. | ||
| 285 | * Allocated and managed by caller. | ||
| 286 | * Modified by the function and restored on exit. | ||
| 287 | * \param[in] bbox_dist squared distance between | ||
| 288 | * the query point and a bounding box of the | ||
| 289 | * [b,e) point sequence. It is used to early | ||
| 290 | * prune traversals that do not generate nearest | ||
| 291 | * neighbors. | ||
| 292 | * \param[in] query_point the query point | ||
| 293 | * \param[in,out] neighbors the computed nearest neighbors | ||
| 294 | */ | ||
| 295 | virtual void get_nearest_neighbors_recursive( | ||
| 296 | index_t node_index, index_t b, index_t e, | ||
| 297 | double* bbox_min, double* bbox_max, | ||
| 298 | double bbox_dist, const double* query_point, | ||
| 299 | NearestNeighbors& neighbors | ||
| 300 | ) const; | ||
| 301 | |||
| 302 | /** | ||
| 303 | * \brief Initializes bounding box and box distance for | ||
| 304 | * Kd-Tree traversal. | ||
| 305 | * \note This is a lower-level function, most users will not use it. | ||
| 306 | * \details This functions needs to be called before | ||
| 307 | * get_nearest_neighbors_recursive() | ||
| 308 | * \param[out] bbox_min a pointer to an array of dimension() doubles, | ||
| 309 | * managed by client code (typically on the stack). | ||
| 310 | * \param[out] bbox_max a pointer to an array of dimension() doubles, | ||
| 311 | * managed by client code (typically on the stack). | ||
| 312 | * \param[out] box_dist the squared distance between the query point and | ||
| 313 | * the box. | ||
| 314 | * \param[in] query_point a const pointer to the coordinates of | ||
| 315 | * the query point. | ||
| 316 | */ | ||
| 317 | void init_bbox_and_bbox_dist_for_traversal( | ||
| 318 | double* bbox_min, double* bbox_max, | ||
| 319 | double& box_dist, const double* query_point | ||
| 320 | ) const; | ||
| 321 | |||
| 322 | /** | ||
| 323 | * \brief Gets the root node. | ||
| 324 | * \return the index of the root node. | ||
| 325 | */ | ||
| 326 | index_t root() const { | ||
| 327 | return root_; | ||
| 328 | } | ||
| 329 | |||
| 330 | protected: | ||
| 331 | /** | ||
| 332 | * \brief Number of points stored in the leafs of the tree. | ||
| 333 | */ | ||
| 334 | static constexpr index_t MAX_LEAF_SIZE = 16; | ||
| 335 | |||
| 336 | /** | ||
| 337 | * \brief Builds the tree. | ||
| 338 | * \return the index of the root node. | ||
| 339 | */ | ||
| 340 | virtual index_t build_tree() = 0 ; | ||
| 341 | |||
| 342 | /** | ||
| 343 | * \brief Gets all the attributes of a node. | ||
| 344 | * \details This function is virtual, because indices can | ||
| 345 | * be either computed on the fly (as in BalancedKdTree) or | ||
| 346 | * stored (as in AdaptiveKdTree). | ||
| 347 | * \param[in] n a node index | ||
| 348 | * \param[in] b the first point in the node | ||
| 349 | * \param[in] e one position past the last point in the node | ||
| 350 | * \param[out] left_child the node index of the | ||
| 351 | * left child of node \p n. | ||
| 352 | * \param[out] right_child the node index of the | ||
| 353 | * right child of node \p n. | ||
| 354 | * \param[out] splitting_coord The coordinate along which \p n is split. | ||
| 355 | * \param[out] m the point m such that [b,m-1] corresponds | ||
| 356 | * to the points in the left child of \p n and [m,e-1] | ||
| 357 | * corresponds to the points in the right child of \p n. | ||
| 358 | * \param[out] splitting_val The coordinate value that separates points | ||
| 359 | * in the left and right children. | ||
| 360 | */ | ||
| 361 | virtual void get_node( | ||
| 362 | index_t n, index_t b, index_t e, | ||
| 363 | index_t& left_child, index_t& right_child, | ||
| 364 | coord_index_t& splitting_coord, | ||
| 365 | index_t& m, | ||
| 366 | double& splitting_val | ||
| 367 | ) const = 0; | ||
| 368 | |||
| 369 | |||
| 370 | |||
| 371 | /** | ||
| 372 | * \brief The recursive function to implement KdTree traversal and | ||
| 373 | * nearest neighbors computation in a leaf. | ||
| 374 | * \details Traverses the node_index leaf that corresponds to the | ||
| 375 | * [b,e) point sequence. Nearest neighbors | ||
| 376 | * are inserted into neighbors during traversal. | ||
| 377 | * \param[in] node_index index of the leaf to be traversed. | ||
| 378 | * \param[in] b index of the first point in the leaf. | ||
| 379 | * \param[in] e one position past the index of the last point in the | ||
| 380 | * leaf. | ||
| 381 | * \param[in] query_point the query point | ||
| 382 | * \param[in,out] neighbors the computed nearest neighbors | ||
| 383 | */ | ||
| 384 | virtual void get_nearest_neighbors_leaf( | ||
| 385 | index_t node_index, index_t b, index_t e, | ||
| 386 | const double* query_point, | ||
| 387 | NearestNeighbors& neighbors | ||
| 388 | ) const; | ||
| 389 | |||
| 390 | /** | ||
| 391 | * \brief Computes the minimum and maximum point coordinates | ||
| 392 | * along a coordinate. | ||
| 393 | * \param[in] b first index of the point sequence | ||
| 394 | * \param[in] e one position past the last index of the point sequence | ||
| 395 | * \param[in] coord coordinate along which the extent is measured | ||
| 396 | * \param[out] minval , maxval minimum and maximum | ||
| 397 | */ | ||
| 398 | 679261 | void get_minmax( | |
| 399 | index_t b, index_t e, coord_index_t coord, | ||
| 400 | double& minval, double& maxval | ||
| 401 | ) const { | ||
| 402 | 679261 | minval = Numeric::max_float64(); | |
| 403 | 679261 | maxval = Numeric::min_float64(); | |
| 404 |
2/2✓ Branch 0 taken 61531927 times.
✓ Branch 1 taken 679261 times.
|
62211188 | for(index_t i = b; i < e; ++i) { |
| 405 |
2/2✓ Branch 0 taken 2538940 times.
✓ Branch 1 taken 58992987 times.
|
61531927 | double val = point_ptr(point_index_[i])[coord]; |
| 406 |
2/2✓ Branch 0 taken 3570998 times.
✓ Branch 1 taken 57960929 times.
|
61531927 | minval = std::min(minval, val); |
| 407 | 61531927 | maxval = std::max(maxval, val); | |
| 408 | } | ||
| 409 | 679261 | } | |
| 410 | |||
| 411 | /** | ||
| 412 | * \brief Computes the extent of a point sequence | ||
| 413 | * along a given coordinate. | ||
| 414 | * \param[in] b first index of the point sequence | ||
| 415 | * \param[in] e one position past the last index of the point sequence | ||
| 416 | * \param[in] coord coordinate along which the extent is measured | ||
| 417 | * \return the extent of the sequence along the coordinate | ||
| 418 | */ | ||
| 419 | double spread(index_t b, index_t e, coord_index_t coord) const { | ||
| 420 | double minval,maxval; | ||
| 421 | 677401 | get_minmax(b,e,coord,minval,maxval); | |
| 422 |
4/4✓ Branch 0 taken 339 times.
✓ Branch 1 taken 1989 times.
✓ Branch 2 taken 121239 times.
✓ Branch 3 taken 412101 times.
|
677401 | return maxval - minval; |
| 423 | } | ||
| 424 | |||
| 425 | /** | ||
| 426 | * \brief KdTree destructor. | ||
| 427 | */ | ||
| 428 | ~KdTree() override; | ||
| 429 | |||
| 430 | protected: | ||
| 431 | vector<index_t> point_index_; | ||
| 432 | vector<double> bbox_min_; | ||
| 433 | vector<double> bbox_max_; | ||
| 434 | index_t root_; | ||
| 435 | }; | ||
| 436 | |||
| 437 | /*********************************************************************/ | ||
| 438 | |||
| 439 | /** | ||
| 440 | * \brief Implements NearestNeighborSearch using a balanced | ||
| 441 | * Kd-tree. | ||
| 442 | * \details The tree is perfectly balanced, thus no combinatorics | ||
| 443 | * is stored: the two children of node n are 2n+1 and 2n+2. For | ||
| 444 | * regular to moderately irregular pointsets it works well. For | ||
| 445 | * highly irregular pointsets, AdaptiveKdTree is more efficient. | ||
| 446 | */ | ||
| 447 | class GEOGRAM_API BalancedKdTree : public KdTree { | ||
| 448 | public: | ||
| 449 | /** | ||
| 450 | * \brief Creates a new BalancedKdTree. | ||
| 451 | * \param[in] dim dimension of the points | ||
| 452 | */ | ||
| 453 | BalancedKdTree(coord_index_t dim); | ||
| 454 | |||
| 455 | protected: | ||
| 456 | /** | ||
| 457 | * \brief BalancedKdTree destructor | ||
| 458 | */ | ||
| 459 | ~BalancedKdTree() override; | ||
| 460 | |||
| 461 | /** | ||
| 462 | * \brief Returns the maximum node index in subtree. | ||
| 463 | * \param[in] node_id node index of the subtree | ||
| 464 | * \param[in] b first index of the points sequence in the subtree | ||
| 465 | * \param[in] e one position past the last index of the point | ||
| 466 | * sequence in the subtree | ||
| 467 | */ | ||
| 468 | 283975 | static index_t max_node_index( | |
| 469 | index_t node_id, index_t b, index_t e | ||
| 470 | ) { | ||
| 471 |
2/2✓ Branch 0 taken 141733 times.
✓ Branch 1 taken 142242 times.
|
283975 | if(e - b <= MAX_LEAF_SIZE) { |
| 472 | return node_id; | ||
| 473 | } | ||
| 474 | 141733 | index_t m = b + (e - b) / 2; | |
| 475 | return std::max( | ||
| 476 | 141733 | max_node_index(2 * node_id, b, m), | |
| 477 | 141733 | max_node_index(2 * node_id + 1, m, e) | |
| 478 | ); | ||
| 479 | } | ||
| 480 | |||
| 481 | /** | ||
| 482 | * \brief Computes the coordinate along which a point | ||
| 483 | * sequence will be split. | ||
| 484 | * \param[in] b first index of the point sequence | ||
| 485 | * \param[in] e one position past the last index of the point sequence | ||
| 486 | */ | ||
| 487 | coord_index_t best_splitting_coord(index_t b, index_t e); | ||
| 488 | |||
| 489 | /** | ||
| 490 | * \brief Creates the subtree under a node. | ||
| 491 | * \param[in] node_index index of the node that represents | ||
| 492 | * the subtree to create | ||
| 493 | * \param[in] b first index of the point sequence in the subtree | ||
| 494 | * \param[in] e one position past the last index of the point | ||
| 495 | * index in the subtree | ||
| 496 | */ | ||
| 497 | 142242 | void create_kd_tree_recursive( | |
| 498 | index_t node_index, index_t b, index_t e | ||
| 499 | ) { | ||
| 500 |
2/2✓ Branch 0 taken 142242 times.
✓ Branch 1 taken 138660 times.
|
280902 | if(e - b <= MAX_LEAF_SIZE) { |
| 501 | return; | ||
| 502 | } | ||
| 503 | 138660 | index_t m = split_kd_node(node_index, b, e); | |
| 504 | 138660 | create_kd_tree_recursive(2 * node_index, b, m); | |
| 505 | 138660 | create_kd_tree_recursive(2 * node_index + 1, m, e); | |
| 506 | } | ||
| 507 | |||
| 508 | /** | ||
| 509 | * \brief Computes and stores the splitting coordinate | ||
| 510 | * and splitting value of the node node_index, that | ||
| 511 | * corresponds to the [b,e) points sequence. | ||
| 512 | * | ||
| 513 | * \return a node index m. The point sequences | ||
| 514 | * [b,m) and [m,e) correspond to the left | ||
| 515 | * child (2*node_index) and right child (2*node_index+1) | ||
| 516 | * of node_index. | ||
| 517 | */ | ||
| 518 | index_t split_kd_node( | ||
| 519 | index_t node_index, index_t b, index_t e | ||
| 520 | ); | ||
| 521 | |||
| 522 | /** \copydoc KdTree::build_tree() */ | ||
| 523 | index_t build_tree() override; | ||
| 524 | |||
| 525 | /** \copydoc KdTree::get_node() */ | ||
| 526 | void get_node( | ||
| 527 | index_t n, index_t b, index_t e, | ||
| 528 | index_t& left_child, index_t& right_child, | ||
| 529 | coord_index_t& splitting_coord, | ||
| 530 | index_t& m, | ||
| 531 | double& splitting_val | ||
| 532 | ) const override; | ||
| 533 | |||
| 534 | protected: | ||
| 535 | |||
| 536 | /** | ||
| 537 | * \brief One per node, splitting coordinate. | ||
| 538 | */ | ||
| 539 | vector<coord_index_t> splitting_coord_; | ||
| 540 | |||
| 541 | /** | ||
| 542 | * \brief One per node, splitting coordinate value. | ||
| 543 | */ | ||
| 544 | vector<double> splitting_val_; | ||
| 545 | |||
| 546 | /** | ||
| 547 | * \brief Indices for multithreaded tree construction. | ||
| 548 | */ | ||
| 549 | index_t m0_, m1_, m2_, m3_, m4_, m5_, m6_, m7_, m8_; | ||
| 550 | }; | ||
| 551 | |||
| 552 | /*********************************************************************/ | ||
| 553 | |||
| 554 | /** | ||
| 555 | * \brief Implements NearestNeighborSearch using an Adaptive | ||
| 556 | * Kd-tree. | ||
| 557 | * \details This corresponds to the same algorithm as in the | ||
| 558 | * ANN library (by David Mount), but stored in flat arrays | ||
| 559 | * (rather than dynamically allocated tree structure). The | ||
| 560 | * data structure is more compact, and slightly faster. | ||
| 561 | * As compared with BalancedKdTree, when the distribution of | ||
| 562 | * points is heterogeneous, it will be faster, at the expensen of | ||
| 563 | * a slightly more requires storage (uses an additional 8 bytes | ||
| 564 | * per node), and construction is not parallel, because size of | ||
| 565 | * left subtree needs to be known before starting constructing | ||
| 566 | * the right subtree. This does not make a big difference since | ||
| 567 | * in general Kd-tree query time dominates construction time in | ||
| 568 | * most of the algorithms that use a Kd-tree. | ||
| 569 | */ | ||
| 570 | class GEOGRAM_API AdaptiveKdTree : public KdTree { | ||
| 571 | public: | ||
| 572 | /** | ||
| 573 | * \brief Creates a new BalancedKdTree. | ||
| 574 | * \param[in] dim dimension of the points | ||
| 575 | */ | ||
| 576 | AdaptiveKdTree(coord_index_t dim); | ||
| 577 | |||
| 578 | protected: | ||
| 579 | /** \copydoc KdTree::build_tree() */ | ||
| 580 | index_t build_tree() override; | ||
| 581 | |||
| 582 | /** \copydoc KdTree::get_node() */ | ||
| 583 | void get_node( | ||
| 584 | index_t n, index_t b, index_t e, | ||
| 585 | index_t& left_child, index_t& right_child, | ||
| 586 | coord_index_t& splitting_coord, | ||
| 587 | index_t& m, | ||
| 588 | double& splitting_val | ||
| 589 | ) const override; | ||
| 590 | |||
| 591 | /** | ||
| 592 | * \brief Creates the subtree under a node. | ||
| 593 | * \param[in] b first index of the point sequence in the subtree | ||
| 594 | * \param[in] e one position past the last index of the point | ||
| 595 | * index in the subtree | ||
| 596 | * \param[in,out] bbox_min coordinates of the lower | ||
| 597 | * corner of the bounding box. | ||
| 598 | * Allocated and managed by caller. | ||
| 599 | * Modified by the function and restored on exit. | ||
| 600 | * \return the node index of the root of the created tree. | ||
| 601 | */ | ||
| 602 | virtual index_t create_kd_tree_recursive( | ||
| 603 | index_t b, index_t e, | ||
| 604 | double* bbox_min, double* bbox_max | ||
| 605 | ); | ||
| 606 | |||
| 607 | /** | ||
| 608 | * \brief Computes and stores the splitting coordinate | ||
| 609 | * and splitting value of the node node_index, that | ||
| 610 | * corresponds to the [b,e) points sequence. | ||
| 611 | * The point sequences [b,m) and [m,e) correspond to the left | ||
| 612 | * child (2*node_index) and right child (2*node_index+1) | ||
| 613 | * of node_index. | ||
| 614 | * \param[in,out] bbox_min coordinates of the lower | ||
| 615 | * corner of the bounding box. | ||
| 616 | * Allocated and managed by caller. | ||
| 617 | * Modified by the function and restored on exit. | ||
| 618 | * \param[out] m the point index. | ||
| 619 | * \param[out] cut_dim the coordinate along which the node is split. | ||
| 620 | * \param[out] cut_val the splitting value. | ||
| 621 | */ | ||
| 622 | virtual void split_kd_node( | ||
| 623 | index_t b, index_t e, | ||
| 624 | double* bbox_min, double* bbox_max, | ||
| 625 | index_t& m, coord_index_t& cut_dim, double& cut_val | ||
| 626 | ); | ||
| 627 | |||
| 628 | /** | ||
| 629 | * \brief Reorders the points in a sequence in such a way that | ||
| 630 | * the specified coordinate in the beginning of the sequence is | ||
| 631 | * smaller than the specified cutting value. | ||
| 632 | * \param[in] b first index of the point sequence | ||
| 633 | * \param[in] e one position past the last index of the point sequence | ||
| 634 | * \param[in] coord coordinate along which the extent is measured | ||
| 635 | * \param[in] val the cutting value | ||
| 636 | * \param[out] br1 , br2 on exit, point indices are reordered in such | ||
| 637 | * a way that: | ||
| 638 | * - the sequence b .. br1-1 has points with coord smaller than val | ||
| 639 | * - the sequence br1 .. br2-1 has points with coord equal to val | ||
| 640 | * - the sequence br2 .. e-1 has points with coord larger than val | ||
| 641 | */ | ||
| 642 | virtual void plane_split( | ||
| 643 | index_t b, index_t e, coord_index_t coord, double val, | ||
| 644 | index_t& br1, index_t& br2 | ||
| 645 | ); | ||
| 646 | |||
| 647 | /** | ||
| 648 | * \brief Gets a point coordinate by index and coordinate. | ||
| 649 | * \param[in] index index of the point. | ||
| 650 | * \param[in] coord coordinate, in 0..dimension()-1 | ||
| 651 | * \return the coordinate of the point, after re-numerotation. | ||
| 652 | */ | ||
| 653 | double point_coord(int index, coord_index_t coord) { | ||
| 654 | geo_debug_assert(index >= 0); | ||
| 655 | geo_debug_assert(index_t(index) < nb_points()); | ||
| 656 | geo_debug_assert(coord < dimension()); | ||
| 657 |
6/6✓ Branch 0 taken 36928 times.
✓ Branch 1 taken 44298 times.
✓ Branch 2 taken 4589 times.
✓ Branch 3 taken 1624 times.
✓ Branch 4 taken 3579 times.
✓ Branch 5 taken 76874 times.
|
167892 | index_t direct_index = point_index_[index_t(index)]; |
| 658 | geo_debug_assert(direct_index < nb_points()); | ||
| 659 |
8/8✓ Branch 0 taken 36928 times.
✓ Branch 1 taken 44298 times.
✓ Branch 2 taken 36919 times.
✓ Branch 3 taken 52647 times.
✓ Branch 4 taken 4589 times.
✓ Branch 5 taken 1624 times.
✓ Branch 6 taken 3579 times.
✓ Branch 7 taken 76874 times.
|
257458 | return (points_ + direct_index * stride_)[coord]; |
| 660 | } | ||
| 661 | |||
| 662 | |||
| 663 | /** | ||
| 664 | * \brief Gets the number of nodes. | ||
| 665 | * \return the number of nodes. | ||
| 666 | */ | ||
| 667 | index_t nb_nodes() const { | ||
| 668 | return splitting_coord_.size(); | ||
| 669 | } | ||
| 670 | |||
| 671 | /** | ||
| 672 | * \brief Creates a new node. | ||
| 673 | * \return the index of the newly created node. | ||
| 674 | */ | ||
| 675 | virtual index_t new_node(); | ||
| 676 | |||
| 677 | protected: | ||
| 678 | /** | ||
| 679 | * \brief One per node, splitting coordinate. | ||
| 680 | */ | ||
| 681 | vector<coord_index_t> splitting_coord_; | ||
| 682 | |||
| 683 | /** | ||
| 684 | * \brief One per node, splitting coordinate value. | ||
| 685 | */ | ||
| 686 | vector<double> splitting_val_; | ||
| 687 | |||
| 688 | /** | ||
| 689 | * \brief One per node, node splitting index. | ||
| 690 | * \details Children points sequences: | ||
| 691 | * - left child points: b .. node_m_[node_index]-1 | ||
| 692 | * - right child points: node_m_[node_index] .. e-1 | ||
| 693 | */ | ||
| 694 | vector<index_t> node_m_; | ||
| 695 | |||
| 696 | /** | ||
| 697 | * \brief One per node, right child index. | ||
| 698 | * \details left child is implicit (left_child(n) = n+1). | ||
| 699 | */ | ||
| 700 | vector<index_t> node_right_child_; | ||
| 701 | }; | ||
| 702 | |||
| 703 | /*********************************************************************/ | ||
| 704 | } | ||
| 705 | |||
| 706 | #endif | ||
| 707 |