| 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 | #include <geogram/delaunay/delaunay_nn.h> | ||
| 41 | |||
| 42 | namespace GEO { | ||
| 43 | |||
| 44 | 65 | Delaunay_NearestNeighbors::Delaunay_NearestNeighbors( | |
| 45 | coord_index_t dimension | ||
| 46 | 65 | ) : | |
| 47 |
1/2✓ Branch 2 taken 65 times.
✗ Branch 3 not taken.
|
65 | Delaunay(dimension) { |
| 48 | set_thread_safe(true); | ||
| 49 | set_default_nb_neighbors(20); | ||
| 50 | set_stores_neighbors(true); | ||
| 51 |
1/2✓ Branch 1 taken 65 times.
✗ Branch 2 not taken.
|
65 | NN_ = NearestNeighborSearch::create(dimension); |
| 52 | 65 | } | |
| 53 | |||
| 54 |
1/2✓ Branch 0 taken 65 times.
✗ Branch 1 not taken.
|
260 | Delaunay_NearestNeighbors::~Delaunay_NearestNeighbors() { |
| 55 | 260 | } | |
| 56 | |||
| 57 |
1/2✓ Branch 0 taken 32980 times.
✗ Branch 1 not taken.
|
32980 | void Delaunay_NearestNeighbors::enlarge_neighborhood( |
| 58 | index_t v, index_t nb | ||
| 59 | ) { | ||
| 60 | neighbors_.lock_array(v); | ||
| 61 |
2/2✓ Branch 0 taken 32839 times.
✓ Branch 1 taken 141 times.
|
32980 | if(nb > neighbors_.array_size(v)) { |
| 62 | // Allocated on the stack (more thread-friendly and no need | ||
| 63 | // to deallocate) | ||
| 64 | 32839 | index_t* neighbors = (index_t*) alloca( | |
| 65 | sizeof(index_t) * nb | ||
| 66 | ); | ||
| 67 | 32839 | nb = get_neighbors_internal(v, nb, neighbors); | |
| 68 | 32839 | neighbors_.set_array(v, nb, neighbors, false); | |
| 69 | } | ||
| 70 | neighbors_.unlock_array(v); | ||
| 71 | 32980 | } | |
| 72 | |||
| 73 | 1254760 | void Delaunay_NearestNeighbors::store_neighbors_CB(index_t v) { | |
| 74 | // No need to lock/unlock array here, since we are | ||
| 75 | // sure that each array is accessed by a single thread. | ||
| 76 | index_t nb = neighbors_.array_size(v); | ||
| 77 | 1254760 | nb = std::min(nb, nb_vertices() - 1); | |
| 78 | // Allocated on the stack (more thread-friendly and no need | ||
| 79 | // to deallocate) | ||
| 80 | 1254760 | index_t* neighbors = (index_t*) alloca( | |
| 81 | sizeof(index_t) * nb | ||
| 82 | ); | ||
| 83 | 1254760 | nb = get_neighbors_internal(v, nb, neighbors); | |
| 84 | 1254760 | neighbors_.set_array(v, nb, neighbors, false); | |
| 85 | geo_debug_assert(neighbors_.array_size(v) == nb); | ||
| 86 | 1254760 | } | |
| 87 | |||
| 88 | ✗ | void Delaunay_NearestNeighbors::get_neighbors_internal( | |
| 89 | index_t v, vector<index_t>& neighbors | ||
| 90 | ) const { | ||
| 91 | ✗ | index_t nb = get_neighbors_internal( | |
| 92 | v, neighbors.size(), neighbors.data() | ||
| 93 | ); | ||
| 94 | ✗ | neighbors.resize(nb); | |
| 95 | ✗ | } | |
| 96 | |||
| 97 | 445 | void Delaunay_NearestNeighbors::set_vertices( | |
| 98 | index_t nb_vertices, const double* vertices | ||
| 99 | ) { | ||
| 100 | 445 | Delaunay::set_vertices(nb_vertices, vertices); | |
| 101 | 445 | NN_->set_points(nb_vertices, vertices); | |
| 102 | 445 | update_neighbors(); | |
| 103 | 445 | } | |
| 104 | |||
| 105 | 1287599 | index_t Delaunay_NearestNeighbors::get_neighbors_internal( | |
| 106 | index_t i, index_t nb_neigh, index_t* neighbors | ||
| 107 | ) const { | ||
| 108 | 1287599 | nb_neigh++; | |
| 109 | nb_neigh = std::min(nb_neigh, nb_vertices()); | ||
| 110 | |||
| 111 | // Allocated on the stack (more multithread-friendly | ||
| 112 | // and no need to free) | ||
| 113 | 1287599 | index_t* closest_pt_ix = (index_t*) alloca(sizeof(index_t) * nb_neigh); | |
| 114 | 1287599 | double* closest_pt_dist = (double*) alloca(sizeof(double) * nb_neigh); | |
| 115 | 1287599 | NN_->get_nearest_neighbors( | |
| 116 | nb_neigh, i, closest_pt_ix, closest_pt_dist | ||
| 117 | ); | ||
| 118 | |||
| 119 | index_t nb_neigh_result = 0; | ||
| 120 |
1/2✓ Branch 0 taken 28732570 times.
✗ Branch 1 not taken.
|
28732570 | for(index_t j = 0; j < nb_neigh; j++) { |
| 121 | geo_debug_assert(signed_index_t(closest_pt_ix[j]) >= 0); | ||
| 122 |
2/2✓ Branch 0 taken 27444971 times.
✓ Branch 1 taken 1287599 times.
|
28732570 | if(closest_pt_ix[j] != i) { |
| 123 | // Check for duplicated points | ||
| 124 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 27444971 times.
|
27444971 | if(closest_pt_dist[j] == 0.0) { |
| 125 | // If i is not the first one (in the | ||
| 126 | // duplicated points), then we 'disconnect' it | ||
| 127 | // (no neighbor !) | ||
| 128 | geo_debug_assert(signed_index_t(closest_pt_ix[j]) >= 0); | ||
| 129 | ✗ | if(closest_pt_ix[j] < i) { | |
| 130 | return 0; | ||
| 131 | } | ||
| 132 | // Else, i is the first one, and we simply | ||
| 133 | // skip (do not store) the connection with | ||
| 134 | // closest_pt_ix[j]. | ||
| 135 | } else { | ||
| 136 | 27444971 | neighbors[nb_neigh_result] = closest_pt_ix[j]; | |
| 137 | 27444971 | nb_neigh_result++; | |
| 138 |
2/2✓ Branch 0 taken 26157372 times.
✓ Branch 1 taken 1287599 times.
|
27444971 | if(nb_neigh_result == nb_neigh - 1) { |
| 139 | break; | ||
| 140 | } | ||
| 141 | } | ||
| 142 | } | ||
| 143 | } | ||
| 144 | return nb_neigh_result; | ||
| 145 | } | ||
| 146 | |||
| 147 | 1750 | index_t Delaunay_NearestNeighbors::nearest_vertex(const double* p) const { | |
| 148 | 1750 | return NN_->get_nearest_neighbor(p); | |
| 149 | } | ||
| 150 | |||
| 151 | /************************************************************************/ | ||
| 152 | } | ||
| 153 |