00001
00002
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
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
00200
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
00222
00223
00224 M_triangles[0] = static_cast< Triangle * >( 0 );
00225 }
00226 if ( M_triangles[1] == tri )
00227 {
00228
00229
00230
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
00252
00253
00254 M_triangles[0] = tri;
00255 }
00256 else if ( ! M_triangles[1] )
00257 {
00258
00259
00260
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
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
00533 DelaunayTriangulation & operator=( const DelaunayTriangulation & );
00534
00535 public:
00536
00540 DelaunayTriangulation()
00541 { }
00542
00549 explicit
00550 DelaunayTriangulation( const Rect2D & region )
00551 {
00552
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
00750
00751
00752
00753
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
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