Triangulation Class Reference

Triangulating a convex polygon by ear-removal. More...

#include <Triangulation.h>

Collaboration diagram for Triangulation:

Classes
class	Node

Public Types
typedef CGAL::PointS2< Real >	PointS2
typedef CGAL::Simple_cartesian < Real >::Segment_2	SegmentS2
typedef Three_tuple< int >	Triangle
	Connectivity for a triangle. More...
typedef std::vector< Triangle >	Connectivity
	Element connectivity table. More...

Public Member Functions
	Triangulation ()
	A constructor. More...
void	triangulate (const Point_2 *ps, int n, Connectivity *tri)
	Main entry for triangulation. More...

Private Types
typedef std::list< Node >	Node_list
typedef Node_list::iterator	Node_iterator
typedef Node_list::const_iterator	Node_const_iterator

Private Member Functions
const PointS2 &	get_point (const Node &v) const
Node_iterator	get_next (Node_iterator i)
Node_iterator	get_prev (Node_iterator i)
Node_const_iterator	get_next (Node_const_iterator i) const
Node_const_iterator	get_prev (Node_const_iterator i) const
bool	is_diagonal (Node_const_iterator u, Node_const_iterator v) const
bool	in_cone (Node_const_iterator u, Node_const_iterator v) const
bool	is_diagonalie (Node_const_iterator u, Node_const_iterator v) const

Private Attributes
const Point_2 *	_pnts
Node_list	_nodes

Detailed Description

Triangulating a convex polygon by ear-removal.

This class implements the ear-removal algorithm described in the book "Computational Geometry in C" for triangulating a convex polygon. It triangulates a polygon by cutting off ears incrementally until only one triangle is left. This method may generate triangles with poor quality, but quality is not a concern because we will compute integration instead of differentiation.

Definition at line 50 of file Triangulation.h.

Member Typedef Documentation

typedef std::vector< Triangle> Connectivity

Element connectivity table.

Definition at line 75 of file Triangulation.h.

typedef Node_list::const_iterator Node_const_iterator

private

Definition at line 71 of file Triangulation.h.

typedef Node_list::iterator Node_iterator

private

Definition at line 70 of file Triangulation.h.

typedef std::list< Node> Node_list

private

Definition at line 69 of file Triangulation.h.

typedef CGAL::PointS2<Real> PointS2

Definition at line 52 of file Triangulation.h.

typedef CGAL::Simple_cartesian<Real>::Segment_2 SegmentS2

Definition at line 53 of file Triangulation.h.

typedef Three_tuple< int> Triangle

Connectivity for a triangle.

Definition at line 73 of file Triangulation.h.

Constructor & Destructor Documentation

Triangulation ( )

inline

A constructor.

Definition at line 79 of file Triangulation.h.

{}

Member Function Documentation

Node_iterator get_next ( Node_iterator  i )

inlineprivate

Definition at line 130 of file Triangulation.h.

References _nodes, and i.

Referenced by in_cone(), is_diagonalie(), and triangulate().

                                           {
    return ( ++i==_nodes.end()) ? _nodes.begin() : i;
  }

Here is the caller graph for this function:

Node_const_iterator get_next ( Node_const_iterator  i ) const

inlineprivate

Definition at line 138 of file Triangulation.h.

References _nodes, and i.

                                                             {
    return ( ++i==_nodes.end()) ? _nodes.begin() : i;
  }

const PointS2& get_point ( const Node &  v ) const

inlineprivate

Definition at line 128 of file Triangulation.h.

References _pnts, and Triangulation::Node::id().

Referenced by in_cone(), and is_diagonalie().

{ return (PointS2&)_pnts[v.id()]; }

Here is the call graph for this function:

Here is the caller graph for this function:

Node_iterator get_prev ( Node_iterator  i )

inlineprivate

Definition at line 133 of file Triangulation.h.

References _nodes, and i.

Referenced by in_cone(), and triangulate().

                                            {
    if ( i==_nodes.begin()) i=_nodes.end();
    return --i;
  }

Here is the caller graph for this function:

Node_const_iterator get_prev ( Node_const_iterator  i ) const

inlineprivate

Definition at line 141 of file Triangulation.h.

References _nodes, and i.

                                                             {
    if ( i==_nodes.begin()) i=_nodes.end();
    return --i;
  }

bool in_cone ( Node_const_iterator  u, Node_const_iterator  v  ) const

inlineprivate

Definition at line 150 of file Triangulation.h.

References get_next(), get_point(), get_prev(), leftturn(), and rightturn().

Referenced by is_diagonal().

                                                                    {
    Node_const_iterator a0 = get_prev( u);
    Node_const_iterator a1 = get_next( u);
    
    if ( !CGAL::rightturn( get_point(*u), get_point(*a1), get_point(*a0))) {
      return ( CGAL::leftturn(get_point(*u), get_point(*v), get_point(*a0)) &&
               CGAL::leftturn(get_point(*v), get_point(*u), get_point(*a1)));
    }
    
    return ( ! CGAL::rightturn(get_point(*v), get_point(*u), get_point(*a1)) &&
             ! CGAL::rightturn(get_point(*a0), get_point(*u), get_point(*v)));
  }

Here is the call graph for this function:

Here is the caller graph for this function:

bool is_diagonal ( Node_const_iterator  u, Node_const_iterator  v  ) const

inlineprivate

Definition at line 146 of file Triangulation.h.

References in_cone(), and is_diagonalie().

Referenced by triangulate().

                                                                        {
    return in_cone( u, v) && in_cone( v, u) && is_diagonalie( u, v);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

bool is_diagonalie ( Node_const_iterator  u, Node_const_iterator  v  ) const

inlineprivate

Definition at line 163 of file Triangulation.h.

References _nodes, CGAL::do_intersect(), get_next(), get_point(), i, and j.

Referenced by is_diagonal().

                                                                          {
    for ( Node_const_iterator i=_nodes.begin(); i!=_nodes.end(); ++i) {
      Node_const_iterator j = get_next(i);

      if ( u!=i && u!=j && v!=i && v!=j &&
           CGAL::do_intersect( SegmentS2( get_point(*u), get_point(*v)),
                               SegmentS2( get_point(*i), get_point(*j))))
        return false;
    }
    return true;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

void triangulate ( const Point_2 *  ps, int  n, Connectivity *  tri  )

inline

Main entry for triangulation.

Parameters

ps	the coordinates of the nodes.
n	the number of nodes.
tri	the element connectivity for output.

Definition at line 87 of file Triangulation.h.

References _nodes, _pnts, get_next(), get_prev(), i, is_diagonal(), n, and RFC_assertion.

Referenced by Overlay::number_subfaces().

                                                                 {
    _pnts = ps;
    _nodes.clear();
    for ( int i=0; i<n; ++i) _nodes.push_back( Node(i));

    // Initialize ears
    for ( Node_iterator it=_nodes.begin(); it!=_nodes.end(); ++it) {
      it->set_ear( is_diagonal( get_prev(it), get_next(it)));
    }

    tri->resize(0); tri->reserve( n-2);
    // Loop through to remove ears.
    for ( ; n>3; --n) {
      // The inner loop searches for an ear
      for ( Node_iterator it=_nodes.begin(); it!=_nodes.end(); ++it) {
        if ( it->is_ear()) {
          Node_iterator v1=get_prev( it), v0=get_prev( v1);
          Node_iterator v3=get_next( it), v4=get_next( v3);

          // Output the ear
          tri->push_back( Triangle( v1->id(), it->id(), v3->id()));

          // update neighbor vertices
          v1->set_ear( is_diagonal( v0, v3));
          v3->set_ear( is_diagonal( v1, v4));

          // Cut off the ear
          _nodes.erase( it);
          break;
        }
      } 
    }
    RFC_assertion( n==3);

    tri->push_back( Triangle( _nodes.front().id(), (++_nodes.begin())->id(),
                              _nodes.back().id()));
    _nodes.clear();
  }

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

Node_list _nodes

private

Definition at line 177 of file Triangulation.h.

Referenced by get_next(), get_prev(), is_diagonalie(), and triangulate().

const Point_2* _pnts

private

Definition at line 176 of file Triangulation.h.

Referenced by get_point(), and triangulate().

---

The documentation for this class was generated from the following file:

• Triangulation.h