delaunay.h

/********************************************************************
 * Copyright (C) 2015-2021 by Liangliang Nan <liangliang.nan@gmail.com>
 * Copyright (C) 2000-2005 INRIA - Project ALICE
 *
 * The code in this file is partly from OGF/Graphite (2.0 alpha-4) with
 * modifications and enhancement:
 *      https://gforge.inria.fr/forum/forum.php?forum_id=11459
 * The original code was distributed under the GNU GPL license.
 ********************************************************************/
 
#ifndef EASY3D_ALGO_DELAUNAY_H
#define EASY3D_ALGO_DELAUNAY_H
 
#include <cassert>
 
#include <easy3d/core/types.h>
 
 
namespace easy3d {

    class Delaunay {
    public:
        explicit Delaunay(unsigned int dimension);

        virtual ~Delaunay();

        unsigned int dimension() const { return dimension_; }

        unsigned int cell_size() const { return cell_size_; }

        virtual void set_vertices(unsigned int nb_vertices, const float *vertices);

        const float *vertices_ptr() const { return vertices_; }

        const float *vertex_ptr(unsigned int i) const {
            assert(i < nb_vertices());
            return vertices_ + dimension() * i;
        }

        unsigned int nb_vertices() const { return nb_vertices_; }

        unsigned int nb_cells() const { return nb_cells_; }

        const int *cell_to_v() const { return cell_to_v_; }

        const int *cell_to_cell() const { return cell_to_cell_; }

        virtual unsigned int nearest_vertex(const float *p) const;

        int cell_vertex(unsigned int c, unsigned int lv) const {
            assert(c < nb_cells());
            assert(lv < cell_size());
            return cell_to_v_[c * cell_v_stride_ + lv];
        }

        int cell_adjacent(unsigned int c, unsigned int lf) const {
            assert(c < nb_cells());
            assert(lf < cell_size());
            return cell_to_cell_[c * cell_neigh_stride_ + lf];
        }

        int vertex_cell(unsigned int v) const {
            assert(v < nb_vertices());
            assert(v < v_to_cell_.size());
            return v_to_cell_[v];
        }

        unsigned int index(unsigned int c, int v) const {
            assert(c < nb_cells());
            assert(v < (int) nb_vertices());
            for (unsigned int iv = 0; iv < cell_size(); iv++) {
                if (cell_vertex(c, iv) == v) { return iv; }
            }
            DCHECK(false) << "should not have reached here";
            return cell_size();
        }

        unsigned int adjacent_index(unsigned int c1, unsigned int c2) const {
            assert(c1 < nb_cells());
            assert(c2 < nb_cells());
            for (unsigned int f = 0; f < cell_size(); f++) {
                if (cell_adjacent(c1, f) == c2) { return f; }
            }
            DCHECK(false) << "should not have reached here";
            return cell_size();
        }

        unsigned int next_around_vertex(unsigned int c, unsigned int lv) const {
            assert(c < nb_cells());
            assert(lv < cell_size());
            return cicl_[cell_size() * c + lv];
        }

        virtual void get_neighbors(unsigned int v, std::vector<unsigned int> &neighbors) const;
 

        bool check_duplicate_vertices();
 
    protected:
 
        void get_neighbors_internal(unsigned int v, std::vector<unsigned int> &neighbors) const;
 
        virtual void set_arrays(unsigned int nb_cells, const int *cell_to_v, const int *cell_to_cell);
 
        void update_v_to_cell();
 
        void update_cicl();
 
        void update_neighbors();
 
        void set_next_around_vertex(unsigned int c1, unsigned int lv, unsigned int c2) {
            assert(c1 < nb_cells());
            assert(c2 < nb_cells());
            assert(lv < cell_size());
            cicl_[cell_size() * c1 + lv] = static_cast<int>(c2);
        }
 
    protected:
        unsigned int dimension_;        
        unsigned int cell_size_;        
        unsigned int cell_v_stride_;    
        unsigned int cell_neigh_stride_;
        const float *vertices_;         
        unsigned int nb_vertices_;      
        unsigned int nb_cells_;         
        const int *cell_to_v_;          
        const int *cell_to_cell_;       
        std::vector<int> v_to_cell_;    
        std::vector<int> cicl_;         
        std::vector<std::vector<unsigned int>> neighbors_; 
        bool is_locked_;                
    };
 
}   // namespace easy3d
 
 
#endif  // EASY3D_ALGO_DELAUNAY_H