delaunay.h

Go to the documentation of this file.

/*
 *  Copyright (c) 2000-2022 Inria
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions are met:
 *
 *  * Redistributions of source code must retain the above copyright notice,
 *  this list of conditions and the following disclaimer.
 *  * Redistributions in binary form must reproduce the above copyright notice,
 *  this list of conditions and the following disclaimer in the documentation
 *  and/or other materials provided with the distribution.
 *  * Neither the name of the ALICE Project-Team nor the names of its
 *  contributors may be used to endorse or promote products derived from this
 *  software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 *  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 *  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 *  ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 *  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 *  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 *  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 *  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 *  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 *  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 *  POSSIBILITY OF SUCH DAMAGE.
 *
 *  Contact: Bruno Levy
 *
 *     https://www.inria.fr/fr/bruno-levy
 *
 *     Inria,
 *     Domaine de Voluceau,
 *     78150 Le Chesnay - Rocquencourt
 *     FRANCE
 *
 */
 
#ifndef GEOGRAM_DELAUNAY_DELAUNAY
#define GEOGRAM_DELAUNAY_DELAUNAY
 
#include <geogram/basic/common.h>
#include <geogram/basic/counted.h>
#include <geogram/basic/smart_pointer.h>
#include <geogram/basic/packed_arrays.h>
#include <geogram/basic/factory.h>
#include <stdexcept>
 
namespace GEO {
 
    class Mesh;
 
    /************************************************************************/
 
    class GEOGRAM_API Delaunay : public Counted {
    public:
        struct InvalidDimension : std::logic_error {
            InvalidDimension(
                coord_index_t dimension,
                const char* name,
                const char* expected
            );
 
            const char* what() const GEO_NOEXCEPT override;
        };
 
 
        struct InvalidInput : std::logic_error {
 
            InvalidInput(int error_code_in);
 
            InvalidInput(const InvalidInput& rhs);
 
            ~InvalidInput() GEO_NOEXCEPT override;
 
            const char* what() const GEO_NOEXCEPT override;
 
            int error_code;
 
            vector<index_t> invalid_facets;
        };
 
        static Delaunay* create(
            coord_index_t dim, const std::string& name = "default"
        );
 
 
        static void initialize();
 
        coord_index_t dimension() const {
            return dimension_;
        }
 
        index_t cell_size() const {
            return cell_size_;
        }
 
        virtual void set_vertices(index_t nb_vertices, const double* vertices);
 
        void set_reorder(bool x) {
            do_reorder_ = x;
        }
 
        virtual void set_BRIO_levels(const vector<index_t>& levels);
 
        const double* vertices_ptr() const {
            return vertices_;
        }
 
        const double* vertex_ptr(index_t i) const {
            geo_debug_assert(i < nb_vertices());
            return vertices_ + vertex_stride_ * i;
        }
 
        index_t nb_vertices() const {
            return nb_vertices_;
        }
 
        virtual bool supports_constraints() const;
 
        virtual void set_constraints(const Mesh* mesh) {
            geo_assert(supports_constraints());
            constraints_ = mesh;
        }
 
        void set_refine(bool x) {
            refine_ = x;
        }
 
        bool get_refine() const {
            return refine_;
        }
 
        void set_quality(double qual) {
            quality_ = qual;
        }
 
        const Mesh* constraints() const {
            return constraints_;
        }
 
        index_t nb_cells() const {
            return nb_cells_;
        }
 
        index_t nb_finite_cells() const {
            geo_debug_assert(keeps_infinite());
            return nb_finite_cells_;
        }
 
        const index_t* cell_to_v() const {
            return cell_to_v_;
        }
 
        const index_t* cell_to_cell() const {
            return cell_to_cell_;
        }
 
        virtual index_t nearest_vertex(const double* p) const;
 
        index_t cell_vertex(index_t c, index_t lv) const {
            geo_debug_assert(c < nb_cells());
            geo_debug_assert(lv < cell_size());
            return cell_to_v_[c * cell_v_stride_ + lv];
        }
 
        index_t cell_adjacent(index_t c, index_t lf) const {
            geo_debug_assert(c < nb_cells());
            geo_debug_assert(lf < cell_size());
            return cell_to_cell_[c * cell_neigh_stride_ + lf];
        }
 
        bool cell_is_infinite(index_t c) const;
 
        bool cell_is_finite(index_t c) const {
            return !cell_is_infinite(c);
        }
 
        index_t index(index_t c, index_t v) const {
            geo_debug_assert(c < nb_cells());
            geo_debug_assert(v == NO_INDEX || v < nb_vertices());
            for(index_t iv = 0; iv < cell_size(); iv++) {
                if(cell_vertex(c, iv) == v) {
                    return iv;
                }
            }
            geo_assert_not_reached;
        }
 
        index_t adjacent_index(index_t c1, index_t c2) const {
            geo_debug_assert(c1 < nb_cells());
            geo_debug_assert(c2 < nb_cells());
            for(index_t f = 0; f < cell_size(); f++) {
                if(cell_adjacent(c1, f) == c2) {
                    return f;
                }
            }
            geo_assert_not_reached;
        }
 
        index_t vertex_cell(index_t v) const {
            geo_debug_assert(v < nb_vertices());
            geo_debug_assert(v < v_to_cell_.size());
            return v_to_cell_[v];
        }
 
 
        index_t next_around_vertex(index_t c, index_t lv) const {
            geo_debug_assert(c < nb_cells());
            geo_debug_assert(lv < cell_size());
            return cicl_[cell_size() * c + lv];
        }
 
        void get_neighbors(index_t v, vector<index_t>& neighbors) const {
            geo_debug_assert(v < nb_vertices());
            if(store_neighbors_) {
                neighbors_.get_array(v, neighbors);
            } else {
                get_neighbors_internal(v, neighbors);
            }
        }
 
        void save_histogram(std::ostream& out) const;
 
        bool stores_neighbors() const {
            return store_neighbors_;
        }
 
        void set_stores_neighbors(bool x) {
            store_neighbors_ = x;
            if(store_neighbors_) {
                set_stores_cicl(true);
            }
        }
 
        bool stores_cicl() const {
            return store_cicl_;
        }
 
        void set_stores_cicl(bool x) {
            store_cicl_ = x;
        }
 
 
        bool keeps_infinite() const {
            return keep_infinite_;
        }
 
        void set_keeps_infinite(bool x) {
            keep_infinite_ = x;
        }
 
        bool thread_safe() const {
            return neighbors_.thread_safe();
        }
 
        void set_thread_safe(bool x) {
            neighbors_.set_thread_safe(x);
        }
 
        void set_default_nb_neighbors(index_t x) {
            default_nb_neighbors_ = x;
        }
 
        index_t default_nb_neighbors() const {
            return default_nb_neighbors_;
        }
 
        void clear_neighbors() {
            neighbors_.clear();
        }
 
        void set_keep_regions(bool x) {
            keep_regions_ = x;
        }
 
        virtual index_t region(index_t t) const;
 
 
    protected:
        Delaunay(coord_index_t dimension);
 
        ~Delaunay() override;
 
        virtual void get_neighbors_internal(
            index_t v, vector<index_t>& neighbors
        ) const;
 
        virtual void set_arrays(
            index_t nb_cells,
            const index_t* cell_to_v, const index_t* cell_to_cell
        );
 
        virtual void update_v_to_cell();
 
        virtual void update_cicl();
 
        virtual void update_neighbors();
 
        void set_next_around_vertex(
            index_t c1, index_t lv, index_t c2
        ) {
            geo_debug_assert(c1 < nb_cells());
            geo_debug_assert(c2 < nb_cells());
            geo_debug_assert(lv < cell_size());
            cicl_[cell_size() * c1 + lv] = c2;
        }
 
    public:
        virtual void store_neighbors_CB(index_t i);
 
    protected:
        void set_dimension(coord_index_t dim) {
            dimension_ = dim;
            vertex_stride_ = dim;
            cell_size_ = index_t(dim) + 1;
            cell_v_stride_ = cell_size_;
            cell_neigh_stride_ = cell_size_;
        }
 
        coord_index_t dimension_;
        index_t vertex_stride_;
        index_t cell_size_;
        index_t cell_v_stride_;
        index_t cell_neigh_stride_;
 
        const double* vertices_;
        index_t nb_vertices_;
        index_t nb_cells_;
        const index_t* cell_to_v_;
        const index_t* cell_to_cell_;
        vector<index_t> v_to_cell_;
        vector<index_t> cicl_;
        bool is_locked_;
        PackedArrays neighbors_;
        bool store_neighbors_;
        index_t default_nb_neighbors_;
 
        bool do_reorder_;
 
        const Mesh* constraints_;
 
        bool refine_;
        double quality_;
 
        bool store_cicl_;
 
        bool keep_infinite_;
 
        index_t nb_finite_cells_;
 
        bool keep_regions_;
    };
 
    typedef SmartPointer<Delaunay> Delaunay_var;
 
    typedef Factory1<Delaunay, coord_index_t> DelaunayFactory;
 
#define geo_register_Delaunay_creator(type, name)               \
    geo_register_creator(GEO::DelaunayFactory, type, name)
}
 
#endif