delaunay_triangulation.h

説明を見る。
00001 // -*-c++-*-
00002 
00008 /*
00009  *Copyright:
00010 
00011  Copyright (C) Hidehisa AKIYAMA
00012 
00013  This code is free software; you can redistribute it and/or
00014  modify it under the terms of the GNU Lesser General Public
00015  License as published by the Free Software Foundation; either
00016  version 2.1 of the License, or (at your option) any later version.
00017 
00018  This library is distributed in the hope that it will be useful,
00019  but WITHOUT ANY WARRANTY; without even the implied warranty of
00020  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00021  Lesser General Public License for more details.
00022 
00023  You should have received a copy of the GNU Lesser General Public
00024  License along with this library; if not, write to the Free Software
00025  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00026 
00027  *EndCopyright:
00028  */
00029 
00031 
00032 #ifndef RCSC_GEOM_DELAUNAY_TRIANGULATION_H
00033 #define RCSC_GEOM_DELAUNAY_TRIANGULATION_H
00034 
00035 #include <rcsc/geom/rect_2d.h>
00036 #include <rcsc/geom/vector_2d.h>
00037 
00038 #include <boost/array.hpp>
00039 
00040 #include <algorithm>
00041 #include <map>
00042 #include <vector>
00043 
00044 namespace rcsc {
00045 
00050 class DelaunayTriangulation {
00051 public:
00052 
00053     static const double EPSILON;
00054 
00056     enum ContainedType {
00057         NOT_CONTAINED,
00058         CONTAINED,
00059         ONLINE,
00060         SAME_VERTEX,
00061     };
00062 
00064 
00068     class Vertex {
00069     private:
00070         int M_id; 
00071         Vector2D M_pos; 
00072 
00073     public:
00077         Vertex()
00078             : M_id( 0 )
00079           { }
00080 
00085         explicit
00086         Vertex( const int id )
00087             : M_id( id )
00088           { }
00089 
00093         virtual
00094         ~Vertex()
00095           { }
00096 
00102         Vertex( const int id,
00103                 const Vector2D & p )
00104             : M_id( id )
00105             , M_pos( p )
00106           { }
00107 
00114         Vertex( const int id,
00115                 const double & x,
00116                 const double & y )
00117             : M_id( id )
00118             , M_pos( x, y )
00119           { }
00120 
00126         Vertex & assign( const int id,
00127                          const Vector2D & p )
00128           {
00129               M_id = id;
00130               M_pos = p;
00131               return *this;
00132           }
00133 
00140         Vertex & assign( const int id,
00141                          const double & x,
00142                          const double & y )
00143           {
00144               M_id = id;
00145               M_pos.assign( x, y );
00146               return *this;
00147           }
00148 
00153         int id() const
00154           {
00155               return M_id;
00156           }
00157 
00162         const
00163         Vector2D & pos() const
00164           {
00165               return M_pos;
00166           }
00167     };
00168 
00170 
00171     class Edge;
00172     class Triangle;
00173 
00174     typedef Edge* EdgePtr;
00175     typedef Triangle* TrianglePtr;
00176 
00178 
00181     class Edge {
00182     private:
00183         const int M_id; 
00184         const Vertex * M_vertices[2]; 
00185         TrianglePtr M_triangles[2]; 
00186     public:
00187 
00194         Edge( const int id,
00195               const Vertex * v0,
00196               const Vertex * v1 )
00197             : M_id( id )
00198           {
00199               //std::cout << "Edge() id_" << id << " v0 " << v0 << " v1 " << v1
00200               //          << std::endl;
00201               M_vertices[0] = v0;
00202               M_vertices[1] = v1;
00203               std::fill_n( M_triangles, 2, static_cast< Triangle * >( 0 ) );
00204           }
00205 
00209         ~Edge()
00210           { }
00211 
00217         void removeTriangle( TrianglePtr tri )
00218           {
00219               if ( M_triangles[0] == tri )
00220               {
00221                   //std::cout << "Edge::removeTriangle() edge_id_" << M_id
00222                   //          << " remove tri_0 " << tri->id() << " "
00223                   //          << tri << std::endl;
00224                   M_triangles[0] = static_cast< Triangle * >( 0 );
00225               }
00226               if ( M_triangles[1] == tri )
00227               {
00228                   //std::cout << "Edge::removeTriangle() edge_id_" << M_id
00229                   //          << " remove tri_1 " << tri->id() << " "
00230                   //          << tri << std::endl;
00231                   M_triangles[1] = static_cast< Triangle * >( 0 );
00232               }
00233           }
00234 
00244         void setTriangle( TrianglePtr tri )
00245           {
00246               if ( M_triangles[0] == tri ) return;
00247               if ( M_triangles[1] == tri ) return;
00248 
00249               if ( ! M_triangles[0] )
00250               {
00251                   //std::cout << "Edge::setTriangle() edge_id_" << M_id
00252                   //          << " set tri_0 " << tri->id() << " "
00253                   //          << tri << std::endl;
00254                   M_triangles[0] = tri;
00255               }
00256               else if ( ! M_triangles[1] )
00257               {
00258                   //std::cout << "Edge::setTriangle() edge_id_" << M_id
00259                   //          << " set tri_1 " << tri->id() << " "
00260                   //          << tri << std::endl;
00261                   M_triangles[1] = tri;
00262               }
00263           }
00264 
00269         int id() const
00270           {
00271               return M_id;
00272           }
00273 
00279         const
00280         Vertex * vertex( const std::size_t i ) const
00281           {
00282               return M_vertices[i];
00283           }
00284 
00290         Triangle * triangle( const std::size_t i ) const
00291           {
00292               return M_triangles[i];
00293           }
00294 
00300         bool hasVertex( const Vertex * v ) const
00301           {
00302               return ( M_vertices[0] == v
00303                        || M_vertices[1] == v );
00304           }
00305 
00306     };
00307 
00309 
00312     class Triangle {
00313     private:
00314         int M_id; 
00315 
00317         boost::array< const Vertex *, 3 > M_vertices;
00319         boost::array< EdgePtr, 3 > M_edges;
00320 
00321         Vector2D M_circumcenter; 
00322         double M_circumradius; 
00323 
00324         // not used
00325         Triangle();
00326     public:
00327 
00337         Triangle( const int id,
00338                   EdgePtr e0,
00339                   EdgePtr e1,
00340                   EdgePtr e2 );
00341 
00345         ~Triangle()
00346           {
00347               M_edges[0]->removeTriangle( this );
00348               M_edges[1]->removeTriangle( this );
00349               M_edges[2]->removeTriangle( this );
00350           }
00351 
00356         int id() const
00357           {
00358               return M_id;
00359           }
00360 
00366         const
00367         Vertex * vertex( std::size_t i ) const
00368           {
00369               return M_vertices[i];
00370           }
00371 
00377         Edge * edge( std::size_t i ) const
00378           {
00379               return M_edges[i];
00380           }
00381 
00386         const
00387         Vector2D & circumcenter() const
00388           {
00389               return M_circumcenter;
00390           }
00391 
00396         const
00397         double & circumradius() const
00398           {
00399               return M_circumradius;
00400           }
00401 
00407         bool contains( const Vector2D & pos ) const
00408           {
00409               return pos.dist2( M_circumcenter ) < M_circumradius * M_circumradius;
00410           }
00411 
00417         bool hasVertex( const Vertex * v ) const
00418           {
00419               return ( v == M_vertices[0]
00420                        || v == M_vertices[1]
00421                        || v == M_vertices[2] );
00422           }
00423 
00429         bool hasEdge( const EdgePtr e ) const
00430           {
00431               return ( M_edges[0] == e
00432                        || M_edges[1] == e
00433                        || M_edges[2] == e );
00434           }
00435 
00442         const
00443         Vertex * getVertexExclude( const Vertex * v1,
00444                                    const Vertex * v2 ) const
00445           {
00446               for ( std::size_t i = 0; i < 3; ++i )
00447               {
00448                   if ( M_vertices[i] != v1
00449                        && M_vertices[i] != v2 )
00450                   {
00451                       return M_vertices[i];
00452                   }
00453               }
00454               return static_cast< const Vertex * >( 0 );
00455           }
00456 
00462         const
00463         Vertex * getVertexExclude( const Edge * edge ) const
00464           {
00465               return getVertexExclude( edge->vertex( 0 ),
00466                                        edge->vertex( 1 ) );
00467           }
00468 
00475         Edge * getEdgeInclude( const Vertex * v1,
00476                                const Vertex * v2 ) const
00477           {
00478               for ( std::size_t i = 0; i < 3; ++i )
00479               {
00480                   if ( M_edges[i]->hasVertex( v1 )
00481                        && M_edges[i]->hasVertex( v2 ) )
00482                   {
00483                       return M_edges[i];
00484                   }
00485               }
00486               return static_cast< Edge * >( 0 );
00487           }
00488 
00494         Edge * getEdgeExclude( const Vertex * v ) const
00495           {
00496               for ( std::size_t i = 0; i < 3; ++i )
00497               {
00498                   if ( ! M_edges[i]->hasVertex( v ) )
00499                   {
00500                       return M_edges[i];
00501                   }
00502               }
00503               return static_cast< Edge * >( 0 );
00504           }
00505 
00506     };
00507 
00509 
00510 private:
00511 
00513     int M_edge_count;
00515     int M_tri_count;
00516 
00518     Vertex M_initial_vertex[3];
00519 
00521     EdgePtr M_initial_edge[3];
00522 
00524     std::vector< Vertex > M_vertices;
00525 
00527     std::map< int, EdgePtr > M_edge_map;
00528 
00530     std::map< int, TrianglePtr > M_triangle_map;
00531 
00532     // not used
00533     DelaunayTriangulation & operator=( const DelaunayTriangulation & );
00534 
00535 public:
00536 
00540     DelaunayTriangulation()
00541       { }
00542 
00549     explicit
00550     DelaunayTriangulation( const Rect2D & region )
00551       {
00552           //std::cout << "create with rect" << std::endl;
00553           createInitialTriangle( region );
00554       }
00555 
00559     ~DelaunayTriangulation();
00560 
00565     const
00566     std::vector< Vertex > & vertices() const
00567       {
00568           return M_vertices;
00569       }
00570 
00575     const
00576     std::map< int, EdgePtr > & edgeMap() const
00577       {
00578           return M_edge_map;
00579       }
00580 
00585     const
00586     std::map< int, TrianglePtr > & triangleMap() const
00587       {
00588           return M_triangle_map;
00589       }
00590 
00596     void init( const Rect2D & region )
00597       {
00598           clear();
00599           createInitialTriangle( region );
00600       }
00601 
00605     void clear();
00606 
00613     int addVertex( const double & x,
00614                    const double & y )
00615       {
00616           int id = M_vertices.size();
00617           M_vertices.push_back( Vertex( id, x, y ) );
00618           return id;
00619       }
00620 
00626     int addVertex( const Vector2D & p )
00627       {
00628           return addVertex( p.x, p.y );
00629       }
00630 
00636     const
00637     Vertex * getVertex( const int id ) const;
00638 
00642     void compute();
00643 
00649     const
00650     TrianglePtr findTriangleContains( const Vector2D & pos ) const;
00651 
00657     const
00658     Vertex * findNearestVertex( const Vector2D & pos ) const;
00659 
00660 private:
00661 
00666     void createInitialTriangle( const Rect2D & region );
00667 
00671     void createInitialTriangle();
00672 
00676     void removeInitialVertices();
00677 
00683     void updateContainedVertex( const Vertex * vertex,
00684                                 TrianglePtr tri );
00685 
00691     void updateOnlineVertex( const Vertex * vertex,
00692                              TrianglePtr tri );
00693 
00701     void legalizeEdge( TrianglePtr new_tri,
00702                        const Vertex * new_vertex,
00703                        EdgePtr old_edge );
00704 
00711     ContainedType findTriangleContains( const Vector2D & pos,
00712                                         TrianglePtr * sol ) const;
00713 
00718     void removeEdge( int id )
00719       {
00720           std::map< int, EdgePtr >::iterator it = M_edge_map.find( id );
00721           if ( it != M_edge_map.end() )
00722           {
00723               delete it->second;
00724               M_edge_map.erase( it );
00725           }
00726       }
00727 
00732     void removeEdge( Edge * edge )
00733       {
00734           if ( edge )
00735           {
00736               removeEdge( edge->id() );
00737           }
00738       }
00739 
00744     void removeTriangle( int id )
00745       {
00746           std::map< int, TrianglePtr >::iterator it = M_triangle_map.find( id );
00747           if ( it != M_triangle_map.end() )
00748           {
00749               //std::cout << "remove triangle " << id
00750               //          << it->second->vertex( 0 )->pos()
00751               //          << it->second->vertex( 1 )->pos()
00752               //          << it->second->vertex( 2 )->pos()
00753               //          << std::endl;
00754               delete it->second;
00755               M_triangle_map.erase( it );
00756           }
00757       }
00758 
00763     void removeTriangle( TrianglePtr tri )
00764       {
00765           if ( tri )
00766           {
00767               removeTriangle( tri->id() );
00768           }
00769       }
00770 
00777     EdgePtr createEdge( const Vertex * v0,
00778                         const Vertex * v1 )
00779       {
00780           EdgePtr ptr = new Edge( M_edge_count++, v0, v1 );
00781           M_edge_map.insert( std::pair< int, EdgePtr >( ptr->id(), ptr ) );
00782           return ptr;
00783       }
00784 
00792     TrianglePtr createTriangle( Edge * e0,
00793                                 Edge * e1,
00794                                 Edge * e2 )
00795       {
00796           // triangle is set to edges in the constructor of Triangle
00797           TrianglePtr ptr = new Triangle( M_tri_count++, e0, e1, e2 );
00798           M_triangle_map.insert( std::pair< int, TrianglePtr >( ptr->id(), ptr ) );
00799           return ptr;
00800       }
00801 
00802 };
00803 
00804 }
00805 
00806 #endif

librcscに対してThu May 1 15:41:20 2008に生成されました。  doxygen 1.5.0