delaunay_triangulation.h

Go to the documentation of this file.

// -*-c++-*-
 
/*
 *Copyright:
 
 Copyright (C) Hidehisa AKIYAMA
 
 This code is free software; you can redistribute it and/or
 modify it under the terms of the GNU Lesser General Public
 License as published by the Free Software Foundation; either
 version 3 of the License, or (at your option) any later version.
 
 This library is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 Lesser General Public License for more details.
 
 You should have received a copy of the GNU Lesser General Public
 License along with this library; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
 *EndCopyright:
 */
 
 
#ifndef RCSC_GEOM_DELAUNAY_TRIANGULATION_H
#define RCSC_GEOM_DELAUNAY_TRIANGULATION_H
 
#include <rcsc/geom/rect_2d.h>
#include <rcsc/geom/vector_2d.h>
 
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <array>
 
namespace rcsc {
 
class DelaunayTriangulation {
public:
 
    static const double EPSILON; 
 
 
    enum ContainedType {
        NOT_CONTAINED,
        CONTAINED,
        ONLINE,
        SAME_VERTEX,
    };
 
 
    class Vertex {
    private:
        int M_id; 
        Vector2D M_pos; 
 
    public:
        Vertex()
            : M_id( 0 )
          { }
 
        explicit
        Vertex( const int id )
            : M_id( id )
          { }
 
        virtual
        ~Vertex()
          { }
 
        Vertex( const int id,
                const Vector2D & p )
            : M_id( id )
            , M_pos( p )
          { }
 
        Vertex( const int id,
                const double x,
                const double y )
            : M_id( id )
            , M_pos( x, y )
          { }
 
        Vertex & assign( const int id,
                         const Vector2D & p )
          {
              M_id = id;
              M_pos = p;
              return *this;
          }
 
        Vertex & assign( const int id,
                         const double x,
                         const double y )
          {
              M_id = id;
              M_pos.assign( x, y );
              return *this;
          }
 
        int id() const
          {
              return M_id;
          }
 
        const
        Vector2D & pos() const
          {
              return M_pos;
          }
    };
 
 
    class Edge;
    class Triangle;
 
    typedef Edge* EdgePtr; 
    typedef Triangle* TrianglePtr; 
 
 
    class Edge {
    private:
        const int M_id; 
        const Vertex * M_vertices[2]; 
        TrianglePtr M_triangles[2]; 
    public:
 
        Edge( const int id,
              const Vertex * v0,
              const Vertex * v1 )
            : M_id( id )
          {
              //std::cout << "Edge() id_" << id << " v0 " << v0 << " v1 " << v1
              //          << std::endl;
              M_vertices[0] = v0;
              M_vertices[1] = v1;
              std::fill_n( M_triangles, 2, nullptr );
          }
 
        ~Edge()
          { }
 
        void removeTriangle( TrianglePtr tri )
          {
              if ( M_triangles[0] == tri )
              {
                  //std::cout << "Edge::removeTriangle() edge_id_" << M_id
                  //          << " remove tri_0 " << tri->id() << " "
                  //          << tri << std::endl;
                  M_triangles[0] = nullptr;
              }
              if ( M_triangles[1] == tri )
              {
                  //std::cout << "Edge::removeTriangle() edge_id_" << M_id
                  //          << " remove tri_1 " << tri->id() << " "
                  //          << tri << std::endl;
                  M_triangles[1] = nullptr;
              }
          }
 
        void setTriangle( TrianglePtr tri )
          {
              if ( M_triangles[0] == tri ) return;
              if ( M_triangles[1] == tri ) return;
 
              if ( ! M_triangles[0] )
              {
                  //std::cout << "Edge::setTriangle() edge_id_" << M_id
                  //          << " set tri_0 " << tri->id() << " "
                  //          << tri << std::endl;
                  M_triangles[0] = tri;
              }
              else if ( ! M_triangles[1] )
              {
                  //std::cout << "Edge::setTriangle() edge_id_" << M_id
                  //          << " set tri_1 " << tri->id() << " "
                  //          << tri << std::endl;
                  M_triangles[1] = tri;
              }
          }
 
        int id() const
          {
              return M_id;
          }
 
        const
        Vertex * vertex( const std::size_t i ) const
          {
              return M_vertices[i];
          }
 
        Triangle * triangle( const std::size_t i ) const
          {
              return M_triangles[i];
          }
 
        bool hasVertex( const Vertex * v ) const
          {
              return ( M_vertices[0] == v
                       || M_vertices[1] == v );
          }
 
    };
 
 
    class Triangle {
    private:
        int M_id; 
 
        std::array< const Vertex *, 3 > M_vertices;
        std::array< EdgePtr, 3 > M_edges;
 
        Vector2D M_circumcenter; 
        double M_circumradius; 
 
        Vector2D M_voronoi_vertex; 
 
        // not used
        Triangle() = delete;
    public:
 
        Triangle( const int id,
                  EdgePtr e0,
                  EdgePtr e1,
                  EdgePtr e2 );
 
        ~Triangle()
          {
              M_edges[0]->removeTriangle( this );
              M_edges[1]->removeTriangle( this );
              M_edges[2]->removeTriangle( this );
          }
 
        void updateVoronoiVertex();
 
        int id() const
          {
              return M_id;
          }
 
        const
        Vertex * vertex( std::size_t i ) const
          {
              return M_vertices[i];
          }
 
        Edge * edge( std::size_t i ) const
          {
              return M_edges[i];
          }
 
        const
        Vector2D & circumcenter() const
          {
              return M_circumcenter;
          }
 
        double circumradius() const
          {
              return M_circumradius;
          }
 
        const Vector2D & voronoiVertex() const
          {
              return M_voronoi_vertex;
          }
 
        bool contains( const Vector2D & pos ) const
          {
              return pos.dist2( M_circumcenter ) < M_circumradius * M_circumradius;
          }
 
        bool hasVertex( const Vertex * v ) const
          {
              return ( v == M_vertices[0]
                       || v == M_vertices[1]
                       || v == M_vertices[2] );
          }
 
        bool hasEdge( const EdgePtr e ) const
          {
              return ( M_edges[0] == e
                       || M_edges[1] == e
                       || M_edges[2] == e );
          }
 
        const
        Vertex * getVertexExclude( const Vertex * v1,
                                   const Vertex * v2 ) const
          {
              for ( std::size_t i = 0; i < 3; ++i )
              {
                  if ( M_vertices[i] != v1
                       && M_vertices[i] != v2 )
                  {
                      return M_vertices[i];
                  }
              }
              return nullptr;
          }
 
        const
        Vertex * getVertexExclude( const Edge * edge ) const
          {
              return getVertexExclude( edge->vertex( 0 ),
                                       edge->vertex( 1 ) );
          }
 
        Edge * getEdgeInclude( const Vertex * v1,
                               const Vertex * v2 ) const
          {
              for ( std::size_t i = 0; i < 3; ++i )
              {
                  if ( M_edges[i]->hasVertex( v1 )
                       && M_edges[i]->hasVertex( v2 ) )
                  {
                      return M_edges[i];
                  }
              }
              return nullptr;
          }
 
        Edge * getEdgeExclude( const Vertex * v ) const
          {
              for ( std::size_t i = 0; i < 3; ++i )
              {
                  if ( ! M_edges[i]->hasVertex( v ) )
                  {
                      return M_edges[i];
                  }
              }
              return nullptr;
          }
 
    };
 
 
    typedef std::vector< Vertex > VertexCont; 
    typedef std::unordered_map< int, EdgePtr > EdgeCont; 
    typedef std::unordered_map< int, TrianglePtr > TriangleCont; 
 
private:
 
    int M_edge_count;
    int M_tri_count;
 
    Vertex M_initial_vertex[3];
 
    EdgePtr M_initial_edge[3];
 
    VertexCont M_vertices;
 
    EdgeCont M_edges;
 
    TriangleCont M_triangles;
 
    // not used
    DelaunayTriangulation & operator=( const DelaunayTriangulation & ) = delete;
 
public:
 
    DelaunayTriangulation() = default;
 
    explicit
    DelaunayTriangulation( const Rect2D & region )
      {
          //std::cout << "create with rect" << std::endl;
          createInitialTriangle( region );
      }
 
    ~DelaunayTriangulation();
 
    void init( const Rect2D & region )
      {
          clear();
          createInitialTriangle( region );
      }
 
    void clear();
 
    void clearResults();
 
    const
    VertexCont & vertices() const
      {
          return M_vertices;
      }
 
    const
    EdgeCont & edges() const
      {
          return M_edges;
      }
 
    const
    TriangleCont & triangles() const
      {
          return M_triangles;
      }
 
    int addVertex( const double x,
                   const double y );
 
    int addVertex( const Vector2D & p )
      {
          return addVertex( p.x, p.y );
      }
 
    void addVertices( const std::vector< Vector2D > & v );
 
    const
    Vertex * getVertex( const int id ) const;
 
    void compute();
 
    void updateVoronoiVertex();
 
    const
    Triangle * findTriangleContains( const Vector2D & pos ) const;
 
    const
    Vertex * findNearestVertex( const Vector2D & pos ) const;
 
private:
 
    void createInitialTriangle( const Rect2D & region );
 
    void createInitialTriangle();
 
    void removeInitialVertices();
 
    bool updateContainedVertex( const Vertex * vertex,
                                const TrianglePtr tri );
 
    bool updateOnlineVertex( const Vertex * vertex,
                             const TrianglePtr tri );
 
    bool legalizeEdge( TrianglePtr new_tri,
                       const Vertex * new_vertex,
                       EdgePtr old_edge );
 
    ContainedType findTriangleContains( const Vector2D & pos,
                                        TrianglePtr * sol ) const;
 
    void removeEdge( int id )
      {
          EdgeCont::iterator it = M_edges.find( id );
          if ( it != M_edges.end() )
          {
              delete it->second;
              M_edges.erase( it );
          }
      }
 
    void removeEdge( Edge * edge )
      {
          if ( edge )
          {
              removeEdge( edge->id() );
          }
      }
 
    void removeTriangle( int id )
      {
          TriangleCont::iterator it = M_triangles.find( id );
          if ( it != M_triangles.end() )
          {
              //std::cout << "remove triangle " << id
              //          << it->second->vertex( 0 )->pos()
              //          << it->second->vertex( 1 )->pos()
              //          << it->second->vertex( 2 )->pos()
              //          << std::endl;
              delete it->second;
              M_triangles.erase( it );
          }
      }
 
    void removeTriangle( TrianglePtr tri )
      {
          if ( tri )
          {
              removeTriangle( tri->id() );
          }
      }
 
    EdgePtr createEdge( const Vertex * v0,
                        const Vertex * v1 )
      {
          EdgePtr ptr = new Edge( M_edge_count++, v0, v1 );
          M_edges.insert( EdgeCont::value_type( ptr->id(), ptr ) );
          return ptr;
      }
 
    TrianglePtr createTriangle( Edge * e0,
                                Edge * e1,
                                Edge * e2 )
      {
          // triangle is set to edges in the constructor of Triangle
          TrianglePtr ptr = new Triangle( M_tri_count++, e0, e1, e2 );
          M_triangles.insert( TriangleCont::value_type( ptr->id(), ptr ) );
          return ptr;
      }
 
};
 
}
 
#endif