| 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_DELAUNAY_DELAUNAY | ||
| 41 | #define GEOGRAM_DELAUNAY_DELAUNAY | ||
| 42 | |||
| 43 | #include <geogram/basic/common.h> | ||
| 44 | #include <geogram/basic/counted.h> | ||
| 45 | #include <geogram/basic/smart_pointer.h> | ||
| 46 | #include <geogram/basic/packed_arrays.h> | ||
| 47 | #include <geogram/basic/factory.h> | ||
| 48 | #include <stdexcept> | ||
| 49 | |||
| 50 | /** | ||
| 51 | * \file geogram/delaunay/delaunay.h | ||
| 52 | * \brief Abstract interface for Delaunay | ||
| 53 | */ | ||
| 54 | |||
| 55 | namespace GEO { | ||
| 56 | |||
| 57 | class Mesh; | ||
| 58 | |||
| 59 | /************************************************************************/ | ||
| 60 | |||
| 61 | /** | ||
| 62 | * \brief Abstract interface for Delaunay triangulation in Nd. | ||
| 63 | * \details | ||
| 64 | * Delaunay objects are created using method create() which | ||
| 65 | * uses the Factory service. New Delaunay triangulations can be | ||
| 66 | * implemented and registered to the factory using | ||
| 67 | * geo_register_Delaunay_creator(). | ||
| 68 | * \see DelaunayFactory | ||
| 69 | * \see geo_register_Delaunay_creator | ||
| 70 | */ | ||
| 71 | class GEOGRAM_API Delaunay : public Counted { | ||
| 72 | public: | ||
| 73 | /** | ||
| 74 | * \brief Invalid dimension exception | ||
| 75 | * \details This exception is thrown by the Delaunay derived | ||
| 76 | * constructors if the dimension in the constructor is not supported | ||
| 77 | * by the implementation | ||
| 78 | */ | ||
| 79 | struct InvalidDimension : std::logic_error { | ||
| 80 | /** | ||
| 81 | * \brief Creates a invalid dimension exception | ||
| 82 | * \param[in] dimension the specified dimension | ||
| 83 | * \param[in] name the name of the Delaunay implementation | ||
| 84 | * \param[in] expected the expected dimension | ||
| 85 | */ | ||
| 86 | InvalidDimension( | ||
| 87 | coord_index_t dimension, | ||
| 88 | const char* name, | ||
| 89 | const char* expected | ||
| 90 | ); | ||
| 91 | |||
| 92 | /** | ||
| 93 | * \brief Gets the string identifying the exception | ||
| 94 | */ | ||
| 95 | const char* what() const GEO_NOEXCEPT override; | ||
| 96 | }; | ||
| 97 | |||
| 98 | |||
| 99 | /** | ||
| 100 | * \brief Invalid input exception | ||
| 101 | * \details This exception is thrown by Delaunay implementations | ||
| 102 | * in constrained mode, when constraints self-intersect. | ||
| 103 | */ | ||
| 104 | struct InvalidInput : std::logic_error { | ||
| 105 | |||
| 106 | /** | ||
| 107 | * \brief InvalidInput constructor. | ||
| 108 | * \param[in] error_code_in an implementation-dependent error code | ||
| 109 | */ | ||
| 110 | InvalidInput(int error_code_in); | ||
| 111 | |||
| 112 | /** | ||
| 113 | * \brief InvalidInput copy constructor. | ||
| 114 | * \param[in] rhs a const reference to the InvalidInput to be copied | ||
| 115 | */ | ||
| 116 | InvalidInput(const InvalidInput& rhs); | ||
| 117 | |||
| 118 | ~InvalidInput() GEO_NOEXCEPT override; | ||
| 119 | |||
| 120 | /** | ||
| 121 | * \brief Gets the string identifying the exception | ||
| 122 | */ | ||
| 123 | const char* what() const GEO_NOEXCEPT override; | ||
| 124 | |||
| 125 | /** | ||
| 126 | * \brief An implementation-dependent error code. | ||
| 127 | */ | ||
| 128 | int error_code; | ||
| 129 | |||
| 130 | /** | ||
| 131 | * \brief The indices of the constrained facets that | ||
| 132 | * have an intersection (or that are duplicated). | ||
| 133 | */ | ||
| 134 | vector<index_t> invalid_facets; | ||
| 135 | }; | ||
| 136 | |||
| 137 | /** | ||
| 138 | * \brief Creates a Delaunay triangulation of the | ||
| 139 | * specified dimension. | ||
| 140 | * \param[in] dim dimension of the triangulation | ||
| 141 | * \param[in] name name of the implementation to use: | ||
| 142 | * - "tetgen" - Delaunay with the Tetgen library (dimension 3 only) | ||
| 143 | * - "BDEL" - Delaunay in 3D (dimension 3 only) | ||
| 144 | * - "BPOW" - Weighted regular 3D triangulation (dimension 4 only) | ||
| 145 | * - "NN" - Delaunay with NearestNeighborSearch (any dimension) | ||
| 146 | * - "default" - uses the command line argument "algo:delaunay" | ||
| 147 | * \retval nullptr if \p format is not a valid Delaunay algorithm name. | ||
| 148 | * \retval otherwise, a pointer to a Delaunay algorithm object. The | ||
| 149 | * returned pointer must be stored in an Delaunay_var that does | ||
| 150 | * automatic destruction: | ||
| 151 | * \code | ||
| 152 | * Delaunay_var handler = Delaunay::create(3, "default"); | ||
| 153 | * \endcode | ||
| 154 | */ | ||
| 155 | static Delaunay* create( | ||
| 156 |
4/6✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✓ Branch 5 taken 7 times.
✓ Branch 6 taken 36 times.
✗ Branch 7 not taken.
|
192 | coord_index_t dim, const std::string& name = "default" |
| 157 | ); | ||
| 158 | |||
| 159 | |||
| 160 | /** | ||
| 161 | * \brief This function needs to be called once before | ||
| 162 | * using the Delaunay class. | ||
| 163 | * \details registers the factories. | ||
| 164 | */ | ||
| 165 | static void initialize(); | ||
| 166 | |||
| 167 | /** | ||
| 168 | * \brief Gets the dimension of this Delaunay. | ||
| 169 | * \return the dimension of this Delauna | ||
| 170 | */ | ||
| 171 | 2950 | coord_index_t dimension() const { | |
| 172 | 2950 | return dimension_; | |
| 173 | } | ||
| 174 | |||
| 175 | /** | ||
| 176 | * \brief Gets the number of vertices in each cell | ||
| 177 | * \details Cell_size = dimension + 1 | ||
| 178 | * \return the number of vertices in each cell | ||
| 179 | */ | ||
| 180 | 23268 | index_t cell_size() const { | |
| 181 | 23268 | return cell_size_; | |
| 182 | } | ||
| 183 | |||
| 184 | /** | ||
| 185 | * \brief Sets the vertices of this Delaunay, and recomputes the cells. | ||
| 186 | * \param[in] nb_vertices number of vertices | ||
| 187 | * \param[in] vertices a pointer to the coordinates of the vertices, as | ||
| 188 | * a contiguous array of doubles | ||
| 189 | */ | ||
| 190 | virtual void set_vertices(index_t nb_vertices, const double* vertices); | ||
| 191 | |||
| 192 | /** | ||
| 193 | * \brief Specifies whether vertices should be reordered. | ||
| 194 | * \details Reordering is activated by default. Some special | ||
| 195 | * usages of Delaunay3d may require to deactivate it (for | ||
| 196 | * instance if vertices are already known to be ordered). | ||
| 197 | * \param[in] x if true, then vertices are reordered using | ||
| 198 | * BRIO-Hilbert ordering. This improves speed significantly | ||
| 199 | * (enabled by default). | ||
| 200 | */ | ||
| 201 | void set_reorder(bool x) { | ||
| 202 | do_reorder_ = x; | ||
| 203 | } | ||
| 204 | |||
| 205 | /** | ||
| 206 | * \brief Specifies the bounds of each level to be used | ||
| 207 | * when hierarchic ordering is specified from outside. | ||
| 208 | * \details This function is used by some implementation | ||
| 209 | * when set_reorder(false) was called. | ||
| 210 | * \param[in] levels specifies the bounds of each level | ||
| 211 | * used by the hierarchical index. First level has | ||
| 212 | * indices between levels[0] ... levels[1]. | ||
| 213 | */ | ||
| 214 | virtual void set_BRIO_levels(const vector<index_t>& levels); | ||
| 215 | |||
| 216 | /** | ||
| 217 | * \brief Gets a pointer to the array of vertices. | ||
| 218 | * \return A const pointer to the array of vertices. | ||
| 219 | */ | ||
| 220 | const double* vertices_ptr() const { | ||
| 221 | return vertices_; | ||
| 222 | } | ||
| 223 | |||
| 224 | /** | ||
| 225 | * \brief Gets a pointer to a vertex by its global index. | ||
| 226 | * \param[in] i global index of the vertex | ||
| 227 | * \return a pointer to vertex \p i | ||
| 228 | */ | ||
| 229 | 505995284 | const double* vertex_ptr(index_t i) const { | |
| 230 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 505995284 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
505995284 | geo_debug_assert(i < nb_vertices()); |
| 231 | 505995284 | return vertices_ + vertex_stride_ * i; | |
| 232 | } | ||
| 233 | |||
| 234 | /** | ||
| 235 | * \brief Gets the number of vertices. | ||
| 236 | * \return the number of vertices in this Delaunay | ||
| 237 | */ | ||
| 238 | 517026641 | index_t nb_vertices() const { | |
| 239 | 517026641 | return nb_vertices_; | |
| 240 | } | ||
| 241 | |||
| 242 | /** | ||
| 243 | * \brief Tests whether constraints are supported | ||
| 244 | * by this Delaunay. | ||
| 245 | * \retval true if constraints are supported | ||
| 246 | * \retval false otherwise | ||
| 247 | */ | ||
| 248 | virtual bool supports_constraints() const; | ||
| 249 | |||
| 250 | /** | ||
| 251 | * \brief Defines the constraints. | ||
| 252 | * \details The triangulation will be constrained | ||
| 253 | * to pass through the vertices and triangles of | ||
| 254 | * the mesh. This function should be called | ||
| 255 | * before set_vertices(). | ||
| 256 | * \param[in] mesh the definition of the constraints | ||
| 257 | * \pre constraints_supported() | ||
| 258 | */ | ||
| 259 | ✗ | virtual void set_constraints(const Mesh* mesh) { | |
| 260 | ✗ | geo_assert(supports_constraints()); | |
| 261 | ✗ | constraints_ = mesh; | |
| 262 | ✗ | } | |
| 263 | |||
| 264 | /** | ||
| 265 | * \brief Specifies whether the mesh should be refined. | ||
| 266 | * \details If set, then the mesh elements are improved | ||
| 267 | * by inserting additional vertices in the mesh. | ||
| 268 | * It is not taken into account by all implementations. | ||
| 269 | * This function should be called before set_vertices(). | ||
| 270 | * \param[in] x true if the mesh should be refined, false | ||
| 271 | * otherwise. | ||
| 272 | */ | ||
| 273 | ✗ | void set_refine(bool x) { | |
| 274 | ✗ | refine_ = x; | |
| 275 | ✗ | } | |
| 276 | |||
| 277 | /** | ||
| 278 | * \brief Tests whether mesh refinement is selected. | ||
| 279 | * \retval true if mesh refinement is selected | ||
| 280 | * \retval false otherwise | ||
| 281 | * \see set_refine() | ||
| 282 | */ | ||
| 283 | bool get_refine() const { | ||
| 284 | return refine_; | ||
| 285 | } | ||
| 286 | |||
| 287 | /** | ||
| 288 | * \brief Specifies the desired quality for mesh elements | ||
| 289 | * when refinement is enabled (\see set_refine). | ||
| 290 | * \details | ||
| 291 | * Only taken into account after set_refine(true) is called. | ||
| 292 | * It is not taken into account by all implementations. | ||
| 293 | * This function should be called before set_vertices(). | ||
| 294 | * \param[in] qual typically in [1.0, 2.0], specifies | ||
| 295 | * the desired quality of mesh elements (1.0 means maximum | ||
| 296 | * quality, and generates a higher number of elements). | ||
| 297 | */ | ||
| 298 | ✗ | void set_quality(double qual) { | |
| 299 | ✗ | quality_ = qual; | |
| 300 | ✗ | } | |
| 301 | |||
| 302 | /** | ||
| 303 | * \brief Gets the constraints. | ||
| 304 | * \return the constraints or nullptr if no constraints | ||
| 305 | * were definied. | ||
| 306 | */ | ||
| 307 | const Mesh* constraints() const { | ||
| 308 | return constraints_; | ||
| 309 | } | ||
| 310 | |||
| 311 | /** | ||
| 312 | * \brief Gets the number of cells. | ||
| 313 | * \return the number of cells in this Delaunay | ||
| 314 | */ | ||
| 315 | 23918 | index_t nb_cells() const { | |
| 316 | 23918 | return nb_cells_; | |
| 317 | } | ||
| 318 | |||
| 319 | /** | ||
| 320 | * \brief Gets the number of finite cells. | ||
| 321 | * \pre this function can only be called if | ||
| 322 | * keep_finite is set | ||
| 323 | * \details Finite cells have indices 0..nb_finite_cells()-1 | ||
| 324 | * and infinite cells have indices nb_finite_cells()..nb_cells()-1 | ||
| 325 | * \see set_keeps_infinite(), keeps_infinite() | ||
| 326 | */ | ||
| 327 | 786 | index_t nb_finite_cells() const { | |
| 328 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 786 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
786 | geo_debug_assert(keeps_infinite()); |
| 329 | 786 | return nb_finite_cells_; | |
| 330 | } | ||
| 331 | |||
| 332 | /** | ||
| 333 | * \brief Gets a pointer to the cell-to-vertex incidence array. | ||
| 334 | * \return a const pointer to the cell-to-vertex incidence array | ||
| 335 | */ | ||
| 336 | const index_t* cell_to_v() const { | ||
| 337 | return cell_to_v_; | ||
| 338 | } | ||
| 339 | |||
| 340 | /** | ||
| 341 | * \brief Gets a pointer to the cell-to-cell adjacency array. | ||
| 342 | * \return a const pointer to the cell-to-cell adjacency array | ||
| 343 | */ | ||
| 344 | const index_t* cell_to_cell() const { | ||
| 345 | return cell_to_cell_; | ||
| 346 | } | ||
| 347 | |||
| 348 | /** | ||
| 349 | * \brief Computes the nearest vertex from a query point. | ||
| 350 | * \param[in] p query point | ||
| 351 | * \return the index of the nearest vertex | ||
| 352 | */ | ||
| 353 | virtual index_t nearest_vertex(const double* p) const; | ||
| 354 | |||
| 355 | /** | ||
| 356 | * \brief Gets a vertex index by cell index and local vertex index. | ||
| 357 | * \param[in] c cell index | ||
| 358 | * \param[in] lv local vertex index in cell \p c | ||
| 359 | * \return the index of the lv-th vertex of cell c. | ||
| 360 | */ | ||
| 361 | 18290 | index_t cell_vertex(index_t c, index_t lv) const { | |
| 362 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 18290 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
18290 | geo_debug_assert(c < nb_cells()); |
| 363 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 18290 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
18290 | geo_debug_assert(lv < cell_size()); |
| 364 | 18290 | return cell_to_v_[c * cell_v_stride_ + lv]; | |
| 365 | } | ||
| 366 | |||
| 367 | /** | ||
| 368 | * \brief Gets an adjacent cell index by cell index and | ||
| 369 | * local facet index. | ||
| 370 | * \param[in] c cell index | ||
| 371 | * \param[in] lf local facet index | ||
| 372 | * \return the index of the cell adjacent to \p c accros | ||
| 373 | * facet \p lf if it exists, or NO_INDEX if on border | ||
| 374 | */ | ||
| 375 | ✗ | index_t cell_adjacent(index_t c, index_t lf) const { | |
| 376 | ✗ | geo_debug_assert(c < nb_cells()); | |
| 377 | ✗ | geo_debug_assert(lf < cell_size()); | |
| 378 | ✗ | return cell_to_cell_[c * cell_neigh_stride_ + lf]; | |
| 379 | } | ||
| 380 | |||
| 381 | /** | ||
| 382 | * \brief Tests whether a cell is infinite. | ||
| 383 | * \retval true if cell \p c is infinite | ||
| 384 | * \retval false otherwise | ||
| 385 | * \see keeps_infinite(), set_keeps_infinite() | ||
| 386 | */ | ||
| 387 | bool cell_is_infinite(index_t c) const; | ||
| 388 | |||
| 389 | /** | ||
| 390 | * \brief Tests whether a cell is finite. | ||
| 391 | * \retval true if cell \p c is finite | ||
| 392 | * \retval false otherwise | ||
| 393 | * \see keeps_infinite(), set_keeps_infinite() | ||
| 394 | */ | ||
| 395 | 779 | bool cell_is_finite(index_t c) const { | |
| 396 | 779 | return !cell_is_infinite(c); | |
| 397 | } | ||
| 398 | |||
| 399 | /** | ||
| 400 | * \brief Retrieves a local vertex index from cell index | ||
| 401 | * and global vertex index. | ||
| 402 | * \param[in] c cell index | ||
| 403 | * \param[in] v global vertex index | ||
| 404 | * \return the local index of vertex \p v in cell \p c | ||
| 405 | * \pre cell \p c is incident to vertex \p v | ||
| 406 | */ | ||
| 407 | ✗ | index_t index(index_t c, index_t v) const { | |
| 408 | ✗ | geo_debug_assert(c < nb_cells()); | |
| 409 | ✗ | geo_debug_assert(v == NO_INDEX || v < nb_vertices()); | |
| 410 | ✗ | for(index_t iv = 0; iv < cell_size(); iv++) { | |
| 411 | ✗ | if(cell_vertex(c, iv) == v) { | |
| 412 | ✗ | return iv; | |
| 413 | } | ||
| 414 | } | ||
| 415 | ✗ | geo_assert_not_reached; | |
| 416 | } | ||
| 417 | |||
| 418 | /** | ||
| 419 | * \brief Retrieves a local facet index from two adacent | ||
| 420 | * cell global indices. | ||
| 421 | * \param[in] c1 global index of first cell | ||
| 422 | * \param[in] c2 global index of second cell | ||
| 423 | * \return the local index of the face accros which | ||
| 424 | * \p c2 is adjacent to \p c1 | ||
| 425 | * \pre cell \p c1 and cell \p c2 are adjacent | ||
| 426 | */ | ||
| 427 | index_t adjacent_index(index_t c1, index_t c2) const { | ||
| 428 | geo_debug_assert(c1 < nb_cells()); | ||
| 429 | geo_debug_assert(c2 < nb_cells()); | ||
| 430 | for(index_t f = 0; f < cell_size(); f++) { | ||
| 431 | if(cell_adjacent(c1, f) == c2) { | ||
| 432 | return f; | ||
| 433 | } | ||
| 434 | } | ||
| 435 | geo_assert_not_reached; | ||
| 436 | } | ||
| 437 | |||
| 438 | /** | ||
| 439 | * \brief Gets an incident cell index by a vertex index. | ||
| 440 | * \details Can only be used if set_stores_cicl(true) was called. | ||
| 441 | * \param[in] v a vertex index | ||
| 442 | * \return the index of a cell incident to vertex \p v | ||
| 443 | * \see stores_cicl(), set_store_cicl() | ||
| 444 | */ | ||
| 445 | ✗ | index_t vertex_cell(index_t v) const { | |
| 446 | ✗ | geo_debug_assert(v < nb_vertices()); | |
| 447 | ✗ | geo_debug_assert(v < v_to_cell_.size()); | |
| 448 | ✗ | return v_to_cell_[v]; | |
| 449 | } | ||
| 450 | |||
| 451 | |||
| 452 | /** | ||
| 453 | * \brief Traverses the list of cells incident to a vertex. | ||
| 454 | * \details Can only be used if set_stores_cicl(true) was called. | ||
| 455 | * \param[in] c cell index | ||
| 456 | * \param[in] lv local vertex index | ||
| 457 | * \return the index of the next cell around vertex \p c or NO_INDEX if | ||
| 458 | * \p c was the last one in the list | ||
| 459 | * \see stores_cicl(), set_store_cicl() | ||
| 460 | */ | ||
| 461 | ✗ | index_t next_around_vertex(index_t c, index_t lv) const { | |
| 462 | ✗ | geo_debug_assert(c < nb_cells()); | |
| 463 | ✗ | geo_debug_assert(lv < cell_size()); | |
| 464 | ✗ | return cicl_[cell_size() * c + lv]; | |
| 465 | } | ||
| 466 | |||
| 467 | /** | ||
| 468 | * \brief Gets the one-ring neighbors of vertex v. | ||
| 469 | * \details Depending on store_neighbors_ internal flag, the | ||
| 470 | * neighbors are computed or copied from the previously computed | ||
| 471 | * list. | ||
| 472 | * \param[in] v vertex index | ||
| 473 | * \param[out] neighbors indices of the one-ring neighbors of | ||
| 474 | * vertex \p v | ||
| 475 | * \see stores_neighbors(), set_stores_neighbors() | ||
| 476 | */ | ||
| 477 | 4137273 | void get_neighbors(index_t v, vector<index_t>& neighbors) const { | |
| 478 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 4137273 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
4137273 | geo_debug_assert(v < nb_vertices()); |
| 479 |
1/2✓ Branch 0 taken 4137273 times.
✗ Branch 1 not taken.
|
4137273 | if(store_neighbors_) { |
| 480 | 4137273 | neighbors_.get_array(v, neighbors); | |
| 481 | } else { | ||
| 482 | ✗ | get_neighbors_internal(v, neighbors); | |
| 483 | } | ||
| 484 | 4137273 | } | |
| 485 | |||
| 486 | /** | ||
| 487 | * \brief Saves the histogram of vertex degree (can be | ||
| 488 | * visualized with gnuplot). | ||
| 489 | * \param[out] out an ASCII stream where to output the histogram. | ||
| 490 | */ | ||
| 491 | void save_histogram(std::ostream& out) const; | ||
| 492 | |||
| 493 | /** | ||
| 494 | * \brief Tests whether neighbors are stored. | ||
| 495 | * \details Vertices neighbors (i.e. Delaunay 1-skeleton) can be | ||
| 496 | * stored for faster access (used for instance by | ||
| 497 | * RestrictedVoronoiDiagram). | ||
| 498 | * \retval true if neighbors are stored. | ||
| 499 | * \retval false otherwise. | ||
| 500 | */ | ||
| 501 | bool stores_neighbors() const { | ||
| 502 | return store_neighbors_; | ||
| 503 | } | ||
| 504 | |||
| 505 | /** | ||
| 506 | * \brief Specifies whether neighbors should be stored. | ||
| 507 | * \details Vertices neighbors (i.e. Delaunay 1-skeleton) can be | ||
| 508 | * stored for faster access (used for instance by | ||
| 509 | * RestrictedVoronoiDiagram). | ||
| 510 | * \param[in] x if true neighbors will be stored, else they will not | ||
| 511 | */ | ||
| 512 | 112 | void set_stores_neighbors(bool x) { | |
| 513 | 112 | store_neighbors_ = x; | |
| 514 |
1/2✓ Branch 0 taken 112 times.
✗ Branch 1 not taken.
|
112 | if(store_neighbors_) { |
| 515 | 112 | set_stores_cicl(true); | |
| 516 | } | ||
| 517 | 112 | } | |
| 518 | |||
| 519 | /** | ||
| 520 | * \brief Tests whether incident tetrahedra lists | ||
| 521 | * are stored. | ||
| 522 | * \retval true if incident tetrahedra lists are stored. | ||
| 523 | * \retval false otherwise. | ||
| 524 | */ | ||
| 525 | ✗ | bool stores_cicl() const { | |
| 526 | ✗ | return store_cicl_; | |
| 527 | } | ||
| 528 | |||
| 529 | /** | ||
| 530 | * \brief Specifies whether incident tetrahedra lists | ||
| 531 | * should be stored. | ||
| 532 | * \param[in] x if true, incident trahedra lists are stored, | ||
| 533 | * else they are not. | ||
| 534 | */ | ||
| 535 | 112 | void set_stores_cicl(bool x) { | |
| 536 | 112 | store_cicl_ = x; | |
| 537 | 112 | } | |
| 538 | |||
| 539 | |||
| 540 | /** | ||
| 541 | * \brief Tests whether infinite elements are kept. | ||
| 542 | * \retval true if infinite elements are kept | ||
| 543 | * \retval false otherwise | ||
| 544 | */ | ||
| 545 | 788 | bool keeps_infinite() const { | |
| 546 | 788 | return keep_infinite_; | |
| 547 | } | ||
| 548 | |||
| 549 | /** | ||
| 550 | * \brief Sets whether infinite elements should be kept. | ||
| 551 | * \details Internally, Delaunay implementation uses an | ||
| 552 | * infinite vertex and infinite simplices indicent to it. | ||
| 553 | * By default they are discarded at the end of set_vertices(). | ||
| 554 | * \param[in] x true if infinite elements should be kept, | ||
| 555 | * false otherwise | ||
| 556 | */ | ||
| 557 | 3 | void set_keeps_infinite(bool x) { | |
| 558 | 3 | keep_infinite_ = x; | |
| 559 | 3 | } | |
| 560 | |||
| 561 | /** | ||
| 562 | * \brief Tests whether thread-safe mode is active. | ||
| 563 | * \return true if thread-safe mode is active, false otherwise. | ||
| 564 | */ | ||
| 565 | ✗ | bool thread_safe() const { | |
| 566 | ✗ | return neighbors_.thread_safe(); | |
| 567 | } | ||
| 568 | |||
| 569 | /** | ||
| 570 | * \brief Specifies whether thread-safe mode should be used. | ||
| 571 | * \param[in] x if true then thread-safe mode will be used, else | ||
| 572 | * it will not. | ||
| 573 | */ | ||
| 574 | 66 | void set_thread_safe(bool x) { | |
| 575 | 66 | neighbors_.set_thread_safe(x); | |
| 576 | 66 | } | |
| 577 | |||
| 578 | /** | ||
| 579 | * \brief Sets the default number of stored neighbors. | ||
| 580 | * \details Storage of neighbors is optimized for a default | ||
| 581 | * neighborhood size. | ||
| 582 | * \see store_neighbors() | ||
| 583 | * \param[in] x default number of stored neighbors | ||
| 584 | */ | ||
| 585 | 66 | void set_default_nb_neighbors(index_t x) { | |
| 586 | 66 | default_nb_neighbors_ = x; | |
| 587 | 66 | } | |
| 588 | |||
| 589 | /** | ||
| 590 | * \brief Gets the default number of stored neighbors. | ||
| 591 | * \details Storage of neighbors is optimized for a default | ||
| 592 | * neighborhood size. | ||
| 593 | * \see store_neighbors() | ||
| 594 | * \return The default number of stored neighbors. | ||
| 595 | */ | ||
| 596 | index_t default_nb_neighbors() const { | ||
| 597 | return default_nb_neighbors_; | ||
| 598 | } | ||
| 599 | |||
| 600 | /** | ||
| 601 | * \brief Frees all memory used for neighbors storage. | ||
| 602 | */ | ||
| 603 | void clear_neighbors() { | ||
| 604 | neighbors_.clear(); | ||
| 605 | } | ||
| 606 | |||
| 607 | /** | ||
| 608 | * \brief Specifies whether all internal regions should be kept. | ||
| 609 | * \details Only relevant in constrained mode. | ||
| 610 | * \param[in] x if true, all internal regions are kept, else only | ||
| 611 | * the outer most region is kept (default). | ||
| 612 | */ | ||
| 613 | ✗ | void set_keep_regions(bool x) { | |
| 614 | ✗ | keep_regions_ = x; | |
| 615 | ✗ | } | |
| 616 | |||
| 617 | /** | ||
| 618 | * \brief Gets the region id associated with a tetrahedron. | ||
| 619 | * \details Only callable if set_keep_region(true) was called before | ||
| 620 | * set_vertices() in constrained mode. | ||
| 621 | * \param[in] t a tetrahedron index. | ||
| 622 | * \return the region associated with \p t. | ||
| 623 | */ | ||
| 624 | virtual index_t region(index_t t) const; | ||
| 625 | |||
| 626 | |||
| 627 | protected: | ||
| 628 | /** | ||
| 629 | * \brief Creates a new Delaunay triangulation | ||
| 630 | * \details This creates a new Delaunay triangulation for the | ||
| 631 | * specified \p dimension. Specific implementations of the Delaunay | ||
| 632 | * triangulation may not support the specified \p dimension and will | ||
| 633 | * throw a InvalidDimension exception. | ||
| 634 | * \param[in] dimension dimension of the triangulation | ||
| 635 | * \throw InvalidDimension This exception is thrown if the specified | ||
| 636 | * \p dimension is not supported by the Delaunay implementation. | ||
| 637 | * \note This function is never called directly, use create() | ||
| 638 | */ | ||
| 639 | Delaunay(coord_index_t dimension); | ||
| 640 | |||
| 641 | /** | ||
| 642 | * \brief Delaunay destructor. | ||
| 643 | */ | ||
| 644 | ~Delaunay() override; | ||
| 645 | |||
| 646 | /** | ||
| 647 | * \brief Internal implementation for get_neighbors (with vector). | ||
| 648 | * \param[in] v index of the Delaunay vertex | ||
| 649 | * \param[in,out] neighbors the computed neighbors of vertex \p v. | ||
| 650 | * Its size is used to determine the number of queried neighbors. | ||
| 651 | */ | ||
| 652 | virtual void get_neighbors_internal( | ||
| 653 | index_t v, vector<index_t>& neighbors | ||
| 654 | ) const; | ||
| 655 | |||
| 656 | /** | ||
| 657 | * \brief Sets the arrays that represent the combinatorics | ||
| 658 | * of this Delaunay. | ||
| 659 | * \param[in] nb_cells number of cells | ||
| 660 | * \param[in] cell_to_v the cell-to-vertex incidence array | ||
| 661 | * \param[in] cell_to_cell the cell-to-cell adjacency array | ||
| 662 | */ | ||
| 663 | virtual void set_arrays( | ||
| 664 | index_t nb_cells, | ||
| 665 | const index_t* cell_to_v, const index_t* cell_to_cell | ||
| 666 | ); | ||
| 667 | |||
| 668 | /** | ||
| 669 | * \brief Stores for each vertex v a cell incident to v. | ||
| 670 | */ | ||
| 671 | virtual void update_v_to_cell(); | ||
| 672 | |||
| 673 | /** | ||
| 674 | * \brief Updates the circular incident cell lists. | ||
| 675 | * \details Used by next_around_vertex(). | ||
| 676 | */ | ||
| 677 | virtual void update_cicl(); | ||
| 678 | |||
| 679 | /** | ||
| 680 | * \brief Computes the stored neighbor lists. | ||
| 681 | */ | ||
| 682 | virtual void update_neighbors(); | ||
| 683 | |||
| 684 | /** | ||
| 685 | * \brief Sets the circular incident edge list. | ||
| 686 | * \param[in] c1 index of a cell | ||
| 687 | * \param[in] lv local index of a vertex of \p c1 | ||
| 688 | * \param[in] c2 index of the next cell around \p c1%'s vertex \p lv | ||
| 689 | */ | ||
| 690 | ✗ | void set_next_around_vertex( | |
| 691 | index_t c1, index_t lv, index_t c2 | ||
| 692 | ) { | ||
| 693 | ✗ | geo_debug_assert(c1 < nb_cells()); | |
| 694 | ✗ | geo_debug_assert(c2 < nb_cells()); | |
| 695 | ✗ | geo_debug_assert(lv < cell_size()); | |
| 696 | ✗ | cicl_[cell_size() * c1 + lv] = c2; | |
| 697 | ✗ | } | |
| 698 | |||
| 699 | public: | ||
| 700 | /** | ||
| 701 | * \brief Stores the neighbors of a vertex. | ||
| 702 | * \details Used internally for parallel | ||
| 703 | * computation of the neighborhoods. | ||
| 704 | * \param[in] i index of the vertex for which the | ||
| 705 | * neighbors should be stored. | ||
| 706 | */ | ||
| 707 | virtual void store_neighbors_CB(index_t i); | ||
| 708 | |||
| 709 | protected: | ||
| 710 | /** | ||
| 711 | * \brief Sets the dimension of this Delaunay. | ||
| 712 | * \details Updates all the parameters related with | ||
| 713 | * the dimension. This includes vertex_stride (number | ||
| 714 | * of doubles between two consecutive vertices), | ||
| 715 | * cell size (number of vertices in a cell), | ||
| 716 | * cell_v_stride (number of integers between two | ||
| 717 | * consecutive cell vertex arrays), | ||
| 718 | * cell_neigh_stride (number of integers | ||
| 719 | * between two consecutive cell adjacency arrays). | ||
| 720 | * \param[in] dim the dimension | ||
| 721 | */ | ||
| 722 | 75 | void set_dimension(coord_index_t dim) { | |
| 723 | 75 | dimension_ = dim; | |
| 724 | 75 | vertex_stride_ = dim; | |
| 725 | 75 | cell_size_ = index_t(dim) + 1; | |
| 726 | 75 | cell_v_stride_ = cell_size_; | |
| 727 | 75 | cell_neigh_stride_ = cell_size_; | |
| 728 | 75 | } | |
| 729 | |||
| 730 | coord_index_t dimension_; | ||
| 731 | index_t vertex_stride_; | ||
| 732 | index_t cell_size_; | ||
| 733 | index_t cell_v_stride_; | ||
| 734 | index_t cell_neigh_stride_; | ||
| 735 | |||
| 736 | const double* vertices_; | ||
| 737 | index_t nb_vertices_; | ||
| 738 | index_t nb_cells_; | ||
| 739 | const index_t* cell_to_v_; | ||
| 740 | const index_t* cell_to_cell_; | ||
| 741 | vector<index_t> v_to_cell_; | ||
| 742 | vector<index_t> cicl_; | ||
| 743 | bool is_locked_; | ||
| 744 | PackedArrays neighbors_; | ||
| 745 | bool store_neighbors_; | ||
| 746 | index_t default_nb_neighbors_; | ||
| 747 | |||
| 748 | /** | ||
| 749 | * \brief If true, uses BRIO reordering | ||
| 750 | * (in some implementations) | ||
| 751 | */ | ||
| 752 | bool do_reorder_; | ||
| 753 | |||
| 754 | const Mesh* constraints_; | ||
| 755 | |||
| 756 | bool refine_; | ||
| 757 | double quality_; | ||
| 758 | |||
| 759 | /** | ||
| 760 | * \brief It true, circular incident tet | ||
| 761 | * lists are stored. | ||
| 762 | */ | ||
| 763 | bool store_cicl_; | ||
| 764 | |||
| 765 | /** | ||
| 766 | * \brief If true, infinite vertex and | ||
| 767 | * infinite simplices are kept. | ||
| 768 | */ | ||
| 769 | bool keep_infinite_; | ||
| 770 | |||
| 771 | /** | ||
| 772 | * \brief If keep_infinite_ is true, then | ||
| 773 | * finite cells are 0..nb_finite_cells_-1 | ||
| 774 | * and infinite cells are | ||
| 775 | * nb_finite_cells_ ... nb_cells_ | ||
| 776 | */ | ||
| 777 | index_t nb_finite_cells_; | ||
| 778 | |||
| 779 | bool keep_regions_; | ||
| 780 | }; | ||
| 781 | |||
| 782 | /** | ||
| 783 | * \brief Smart pointer that refers to a Delaunay object | ||
| 784 | * \relates Delaunay | ||
| 785 | */ | ||
| 786 | typedef SmartPointer<Delaunay> Delaunay_var; | ||
| 787 | |||
| 788 | /** | ||
| 789 | * \brief Delaunay Factory | ||
| 790 | * \details | ||
| 791 | * This Factory is used to create Delaunay objects. | ||
| 792 | * It can also be used to register new Delaunay | ||
| 793 | * implementations. | ||
| 794 | * \see geo_register_Delaunay_creator | ||
| 795 | * \see Factory | ||
| 796 | * \relates Delaunay | ||
| 797 | */ | ||
| 798 | typedef Factory1<Delaunay, coord_index_t> DelaunayFactory; | ||
| 799 | |||
| 800 | /** | ||
| 801 | * \brief Helper macro to register a Delaunay implementation | ||
| 802 | * \see DelaunayFactory | ||
| 803 | * \relates Delaunay | ||
| 804 | */ | ||
| 805 | #define geo_register_Delaunay_creator(type, name) \ | ||
| 806 | geo_register_creator(GEO::DelaunayFactory, type, name) | ||
| 807 | } | ||
| 808 | |||
| 809 | #endif | ||
| 810 |