Delaunay.h

Go to the documentation of this file.

/*

             *
            ***
           *****
   *********************       Mercenaries Engineering SARL
     *****************              Copyright (C) 2018
       *************
         *********        http://www.mercenaries-engineering.com
        ***********
       ****     ****
      **           **

*/
#pragma once

#include <vector>
#include <mutex>

#include <ImathVec.h>

#include <Maquina/Export.h>

namespace maquina
{

  class MAQUINA_EXPORT DelaunayTriangulation2D
  {
  public:
    DelaunayTriangulation2D();

    DelaunayTriangulation2D(const std::vector<Imath::V2d>& points);

    bool is_inside_super_triangle(const Imath::V2d& p);

    bool insert(const Imath::V2d& p);

    std::vector<Imath::V2d> points() const;

    const std::vector<int>& convex_hull() const;

    const std::vector<Imath::V3i>& triangulation() const;

    std::vector<std::pair<int, double>> nnc(const Imath::V2d& p) const;

    // TODO
    // Voronoi2D voronoi() const;

    static bool is_in_circumcircle(const Imath::V2d& p, const Imath::V2d& a, const Imath::V2d& b, const Imath::V2d& c);

  private:
    // actually performs the insertion of the i-th point.
    void perform_insertion(int i);
    // returns the list of indices of the triangles invalidated by the insertion of p.
    std::vector<size_t> _invalidated_triangles(const Imath::V2d& p) const;
    // returns the list of triangle-aware boundary edges of the Bowyer-Watson enveloppe around p.
    std::vector<Imath::V3i> _bowyer_watson_boundary_edges(const std::vector<size_t>& invalid_triangles) const;

    int _n_set_points;
    std::vector<Imath::V2d> _points; // contains the set of points + the additional building points (super-triangle points)
    std::vector<Imath::V3i> _triangles; // the full triangulation of the point set AND the super triangle

    mutable std::vector<int> _convex_hull; // the convex hull of the set of points
    mutable std::vector<Imath::V3i> _triangulation; // the result of the triangulation
    mutable bool _is_convex_hull_dirty = true; // True if a point has been inserted since the last convex hull request, false otherwise
    mutable bool _is_triangulation_dirty = true; // True if a point has been inserted since the last triangulation request, false otherwise

    mutable std::mutex _mutex; // to synchronize accesses
  };
}