Merge pull request #4 from FOSSEE/develop

merging dev into master

3 files changed, 894 insertions, 0 deletions

diff --git a/include/ttl/halfedge/hedart.h b/include/ttl/halfedge/hedart.h
new file mode 100644
index 0000000..2749c50
--- /dev/null
+++ b/include/ttl/halfedge/hedart.h
@@ -0,0 +1,191 @@
+/*
+ * Copyright (C) 1998, 2000-2007, 2010, 2011, 2012, 2013 SINTEF ICT,
+ * Applied Mathematics, Norway.
+ *
+ * Contact information: E-mail: tor.dokken@sintef.no                      
+ * SINTEF ICT, Department of Applied Mathematics,                         
+ * P.O. Box 124 Blindern,                                                 
+ * 0314 Oslo, Norway.                                                     
+ *
+ * This file is part of TTL.
+ *
+ * TTL is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version. 
+ *
+ * TTL 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 Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public
+ * License along with TTL. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * In accordance with Section 7(b) of the GNU Affero General Public
+ * License, a covered work must retain the producer line in every data
+ * file that is created or manipulated using TTL.
+ *
+ * Other Usage
+ * You can be released from the requirements of the license by purchasing
+ * a commercial license. Buying such a license is mandatory as soon as you
+ * develop commercial activities involving the TTL library without
+ * disclosing the source code of your own applications.
+ *
+ * This file may be used in accordance with the terms contained in a
+ * written agreement between you and SINTEF ICT. 
+ */
+
+#ifndef _HALF_EDGE_DART_
+#define _HALF_EDGE_DART_
+
+#include <ttl/halfedge/hetriang.h>
+
+namespace hed
+{
+/**
+ * \class Dart
+ * \brief \b %Dart class for the half-edge data structure.
+ *
+ * See \ref api for a detailed description of how the member functions
+ * should be implemented.
+ */
+class DART
+{
+    EDGE_PTR m_edge;
+
+    /// Dart direction: true if dart is counterclockwise in face
+    bool m_dir;
+
+public:
+    /// Default constructor
+    DART()
+    {
+        m_dir = true;
+    }
+
+    /// Constructor
+    DART( const EDGE_PTR& aEdge, bool aDir = true )
+    {
+        m_edge = aEdge;
+        m_dir = aDir;
+    }
+
+    /// Copy constructor
+    DART( const DART& aDart )
+    {
+        m_edge = aDart.m_edge;
+        m_dir  = aDart.m_dir;
+    }
+
+    /// Destructor
+    ~DART()
+    {
+    }
+
+    /// Assignment operator
+    DART& operator=( const DART& aDart )
+    {
+        if( this == &aDart )
+            return *this;
+
+        m_edge = aDart.m_edge;
+        m_dir = aDart.m_dir;
+
+        return *this;
+    }
+
+    /// Comparing dart objects
+    bool operator==( const DART& aDart ) const
+    {
+        return ( aDart.m_edge == m_edge && aDart.m_dir == m_dir );
+    }
+
+    /// Comparing dart objects
+    bool operator!=( const DART& aDart ) const
+    {
+        return !( aDart == *this );
+    }
+
+    /// Maps the dart to a different node
+    DART& Alpha0()
+    {
+        m_dir = !m_dir;
+        return *this;
+    }
+
+    /// Maps the dart to a different edge
+    DART& Alpha1()
+    {
+        if( m_dir )
+        {
+            m_edge = m_edge->GetNextEdgeInFace()->GetNextEdgeInFace();
+            m_dir = false;
+        }
+        else
+        {
+            m_edge = m_edge->GetNextEdgeInFace();
+            m_dir = true;
+        }
+
+        return *this;
+    }
+
+    /// Maps the dart to a different triangle. \b Note: the dart is not changed if it is at the boundary!
+    DART& Alpha2()
+    {
+        if( m_edge->GetTwinEdge() )
+        {
+            m_edge = m_edge->GetTwinEdge();
+            m_dir = !m_dir;
+        }
+
+        // else, the dart is at the boundary and should not be changed
+        return *this;
+    }
+
+    /** @name Utilities not required by TTL */
+    //@{
+    void Init( const EDGE_PTR& aEdge, bool aDir = true )
+    {
+        m_edge = aEdge;
+        m_dir = aDir;
+    }
+
+    double X() const
+    {
+        return GetNode()->GetX();
+    }
+
+    double Y() const
+    {
+        return GetNode()->GetY();
+    }
+
+    bool IsCCW() const
+    {
+        return m_dir;
+    }
+
+    const NODE_PTR& GetNode() const
+    {
+        return m_dir ? m_edge->GetSourceNode() : m_edge->GetTargetNode();
+    }
+
+    const NODE_PTR& GetOppositeNode() const
+    {
+        return m_dir ? m_edge->GetTargetNode() : m_edge->GetSourceNode();
+    }
+
+    EDGE_PTR& GetEdge()
+    {
+        return m_edge;
+    }
+
+    //@} // End of Utilities not required by TTL
+};
+
+} // End of hed namespace
+
+#endif
diff --git a/include/ttl/halfedge/hetraits.h b/include/ttl/halfedge/hetraits.h
new file mode 100644
index 0000000..04288a0
--- /dev/null
+++ b/include/ttl/halfedge/hetraits.h
@@ -0,0 +1,189 @@
+/*
+ * Copyright (C) 1998, 2000-2007, 2010, 2011, 2012, 2013 SINTEF ICT,
+ * Applied Mathematics, Norway.
+ *
+ * Contact information: E-mail: tor.dokken@sintef.no                      
+ * SINTEF ICT, Department of Applied Mathematics,                         
+ * P.O. Box 124 Blindern,                                                 
+ * 0314 Oslo, Norway.                                                     
+ *
+ * This file is part of TTL.
+ *
+ * TTL is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version. 
+ *
+ * TTL 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 Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public
+ * License along with TTL. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * In accordance with Section 7(b) of the GNU Affero General Public
+ * License, a covered work must retain the producer line in every data
+ * file that is created or manipulated using TTL.
+ *
+ * Other Usage
+ * You can be released from the requirements of the license by purchasing
+ * a commercial license. Buying such a license is mandatory as soon as you
+ * develop commercial activities involving the TTL library without
+ * disclosing the source code of your own applications.
+ *
+ * This file may be used in accordance with the terms contained in a
+ * written agreement between you and SINTEF ICT. 
+ */
+
+#ifndef _HALF_EDGE_TRAITS_
+#define _HALF_EDGE_TRAITS_
+
+#include <ttl/halfedge/hetriang.h>
+#include <ttl/halfedge/hedart.h>
+
+namespace hed
+{
+/**
+ * \struct TTLtraits
+ * \brief \b Traits class (static struct) for the half-edge data structure.
+ *
+ * The member functions are those required by different function templates
+ * in the TTL. Documentation is given here to explain what actions
+ * should be carried out on the actual data structure as required by the functions
+ * in the \ref ttl namespace.
+ *
+ * The source code of \c %HeTraits.h shows how the traits class is implemented for the
+ * half-edge data structure.
+ *
+ * \see \ref api
+ */
+struct TTLtraits
+{
+    /**
+     * The floating point type used in calculations involving scalar products and cross products.
+     */
+    typedef double REAL_TYPE;
+    
+    /** @name Geometric Predicates */
+    //@{
+    /**
+     * Scalar product between two 2D vectors represented as darts.\n
+     *
+     * ttl_util::scalarProduct2d can be used.
+     */
+    static REAL_TYPE ScalarProduct2D( const DART& aV1, const DART& aV2 )
+    {
+        DART v10 = aV1;
+        v10.Alpha0();
+
+        DART v20 = aV2;
+        v20.Alpha0();
+
+        return ttl_util::ScalarProduct2D( v10.X() - aV1.X(),  v10.Y() - aV1.Y(),
+                                          v20.X() - aV2.X(),  v20.Y() - aV2.Y() );
+    }
+
+    /**
+     * Scalar product between two 2D vectors.
+     * The first vector is represented by a dart \e v, and the second
+     * vector has direction from the source node of \e v to the point \e p.\n
+     *
+     * ttl_util::ScalarProduct2D can be used.
+     */
+    static REAL_TYPE ScalarProduct2D( const DART& aV, const NODE_PTR& aP )
+    {
+        DART d0 = aV;
+        d0.Alpha0();
+
+        return ttl_util::ScalarProduct2D( d0.X() - aV.X(),     d0.Y() - aV.Y(),
+                                          aP->GetX() - aV.X(), aP->GetY() - aV.Y() );
+    }
+
+    /**
+     * Cross product between two vectors in the plane represented as darts.
+     * The z-component of the cross product is returned.\n
+     *
+     * ttl_util::CrossProduct2D can be used.
+     */
+    static REAL_TYPE CrossProduct2D( const DART& aV1, const DART& aV2 )
+    {
+        DART v10 = aV1;
+        v10.Alpha0();
+
+        DART v20 = aV2;
+        v20.Alpha0();
+
+        return ttl_util::CrossProduct2D( v10.X() - aV1.X(), v10.Y() - aV1.Y(),
+                                         v20.X() - aV2.X(), v20.Y() - aV2.Y() );
+    }
+
+    /**
+     * Cross product between two vectors in the plane.
+     * The first vector is represented by a dart \e v, and the second
+     * vector has direction from the source node of \e v to the point \e p.
+     * The z-component of the cross product is returned.\n
+     *
+     * ttl_util::CrossProduct2d can be used.
+     */
+    static REAL_TYPE CrossProduct2D( const DART& aV, const NODE_PTR& aP )
+    {
+        DART d0 = aV;
+        d0.Alpha0();
+
+        return ttl_util::CrossProduct2D( d0.X() - aV.X(),     d0.Y() - aV.Y(),
+                                         aP->GetX() - aV.X(), aP->GetY() - aV.Y() );
+    }
+
+    /**
+     * Let \e n1 and \e n2 be the nodes associated with two darts, and let \e p
+     * be a point in the plane. Return a positive value if \e n1, \e n2,
+     * and \e p occur in counterclockwise order; a negative value if they occur
+     * in clockwise order; and zero if they are collinear.
+     */
+    static REAL_TYPE Orient2D( const DART& aN1, const DART& aN2, const NODE_PTR& aP )
+    {
+        REAL_TYPE pa[2];
+        REAL_TYPE pb[2];
+        REAL_TYPE pc[2];
+
+        pa[0] = aN1.X();
+        pa[1] = aN1.Y();
+        pb[0] = aN2.X();
+        pb[1] = aN2.Y();
+        pc[0] = aP->GetX();
+        pc[1] = aP->GetY();
+
+        return ttl_util::Orient2DFast( pa, pb, pc );
+    }
+
+    /**
+     * This is the same predicate as represented with the function above,
+     * but with a slighty different interface:
+     * The last parameter is given as a dart where the source node of the dart
+     * represents a point in the plane.
+     * This function is required for constrained triangulation.
+     */
+    static REAL_TYPE Orient2D( const DART& aN1, const DART& aN2, const DART& aP )
+    {
+        REAL_TYPE pa[2];
+        REAL_TYPE pb[2];
+        REAL_TYPE pc[2];
+
+        pa[0] = aN1.X();
+        pa[1] = aN1.Y();
+        pb[0] = aN2.X();
+        pb[1] = aN2.Y();
+        pc[0] = aP.X();
+        pc[1] = aP.Y();
+
+        return ttl_util::Orient2DFast( pa, pb, pc );
+    }
+
+    //@} // End of Geometric Predicates Group
+};
+
+}; // End of hed namespace
+
+#endif
diff --git a/include/ttl/halfedge/hetriang.h b/include/ttl/halfedge/hetriang.h
new file mode 100644
index 0000000..1642e92
--- /dev/null
+++ b/include/ttl/halfedge/hetriang.h
@@ -0,0 +1,514 @@
+/*
+ * Copyright (C) 1998, 2000-2007, 2010, 2011, 2012, 2013 SINTEF ICT,
+ * Applied Mathematics, Norway.
+ * Copyright (C) 2013 CERN
+ * @author Maciej Suminski <maciej.suminski@cern.ch>
+ *
+ * Contact information: E-mail: tor.dokken@sintef.no
+ * SINTEF ICT, Department of Applied Mathematics,
+ * P.O. Box 124 Blindern,
+ * 0314 Oslo, Norway.
+ *
+ * This file is part of TTL.
+ *
+ * TTL is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * TTL 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 Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public
+ * License along with TTL. If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * In accordance with Section 7(b) of the GNU Affero General Public
+ * License, a covered work must retain the producer line in every data
+ * file that is created or manipulated using TTL.
+ *
+ * Other Usage
+ * You can be released from the requirements of the license by purchasing
+ * a commercial license. Buying such a license is mandatory as soon as you
+ * develop commercial activities involving the TTL library without
+ * disclosing the source code of your own applications.
+ *
+ * This file may be used in accordance with the terms contained in a
+ * written agreement between you and SINTEF ICT.
+ */
+
+#ifndef _HE_TRIANG_H_
+#define _HE_TRIANG_H_
+
+//#define TTL_USE_NODE_ID   // Each node gets it's own unique id
+#define TTL_USE_NODE_FLAG // Each node gets a flag (can be set to true or false)
+
+#include <list>
+#include <vector>
+#include <iostream>
+#include <fstream>
+#include <ttl/ttl_util.h>
+#include <boost/shared_ptr.hpp>
+#include <boost/weak_ptr.hpp>
+#include <layers_id_colors_and_visibility.h>
+
+class BOARD_CONNECTED_ITEM;
+
+namespace ttl
+{
+    class TRIANGULATION_HELPER;
+};
+
+/**
+ * The half-edge data structure
+ */
+namespace hed
+{
+// Helper typedefs
+class NODE;
+class EDGE;
+typedef boost::shared_ptr<NODE> NODE_PTR;
+typedef boost::shared_ptr<EDGE> EDGE_PTR;
+typedef boost::weak_ptr<EDGE> EDGE_WEAK_PTR;
+typedef std::vector<NODE_PTR> NODES_CONTAINER;
+
+/**
+ * \class NODE
+ * \brief \b Node class for data structures (Inherits from HandleId)
+ *
+ * \note
+ * - To enable node IDs, TTL_USE_NODE_ID must be defined.
+ * - To enable node flags, TTL_USE_NODE_FLAG must be defined.
+ * - TTL_USE_NODE_ID and TTL_USE_NODE_FLAG should only be enabled if this functionality is
+ *   required by the application, because they increase the memory usage for each Node object.
+ */
+class NODE
+{
+protected:
+#ifdef TTL_USE_NODE_FLAG
+    /// TTL_USE_NODE_FLAG must be defined
+    bool m_flag;
+#endif
+
+#ifdef TTL_USE_NODE_ID
+    /// TTL_USE_NODE_ID must be defined
+    static int id_count;
+
+    /// A unique id for each node (TTL_USE_NODE_ID must be defined)
+    int m_id;
+#endif
+
+    /// Node coordinates
+    int m_x, m_y;
+
+    /// Tag for quick connection resolution
+    int m_tag;
+
+    /// List of board items that share this node
+    std::list<const BOARD_CONNECTED_ITEM*> m_parents;
+
+    /// Layers that are occupied by this node
+    LSET m_layers;
+
+    /// Recomputes the layers used by this node
+    void updateLayers();
+
+public:
+    /// Constructor
+    NODE( int aX = 0, int aY = 0 ) :
+#ifdef TTL_USE_NODE_FLAG
+        m_flag( false ),
+#endif
+#ifdef TTL_USE_NODE_ID
+        m_id( id_count++ ),
+#endif
+        m_x( aX ), m_y( aY ), m_tag( -1 )
+    {
+        m_layers.reset();
+    }
+
+    /// Destructor
+    ~NODE() {}
+
+    /// Returns the x-coordinate
+    inline int GetX() const
+    {
+        return m_x;
+    }
+
+    /// Returns the y-coordinate
+    inline int GetY() const
+    {
+        return m_y;
+    }
+
+    /// Returns tag, common identifier for connected nodes
+    inline int GetTag() const
+    {
+        return m_tag;
+    }
+
+    /// Sets tag, common identifier for connected nodes
+    inline void SetTag( int aTag )
+    {
+        m_tag = aTag;
+    }
+
+#ifdef TTL_USE_NODE_ID
+    /// Returns the id (TTL_USE_NODE_ID must be defined)
+    inline int Id() const
+    {
+        return m_id;
+    }
+#endif
+
+#ifdef TTL_USE_NODE_FLAG
+    /// Sets the flag (TTL_USE_NODE_FLAG must be defined)
+    inline void SetFlag( bool aFlag )
+    {
+        m_flag = aFlag;
+    }
+
+    /// Returns the flag (TTL_USE_NODE_FLAG must be defined)
+    inline const bool& GetFlag() const
+    {
+        return m_flag;
+    }
+#endif
+
+    inline unsigned int GetRefCount() const
+    {
+        return m_parents.size();
+    }
+
+    inline void AddParent( const BOARD_CONNECTED_ITEM* aParent )
+    {
+        m_parents.push_back( aParent );
+        m_layers.reset();   // mark as needs updating
+    }
+
+    inline void RemoveParent( const BOARD_CONNECTED_ITEM* aParent )
+    {
+        m_parents.remove( aParent );
+        m_layers.reset();   // mark as needs updating
+    }
+
+    const LSET& GetLayers()
+    {
+        if( m_layers.none() )
+            updateLayers();
+
+        return m_layers;
+    }
+
+    // Tag used for unconnected items.
+    static const int TAG_UNCONNECTED = -1;
+};
+
+
+/**
+ * \class EDGE
+ * \brief \b %Edge class in the in the half-edge data structure.
+ */
+class EDGE
+{
+public:
+    /// Constructor
+    EDGE() : m_weight( 0 ), m_isLeadingEdge( false )
+    {
+    }
+
+    /// Destructor
+    virtual ~EDGE()
+    {
+    }
+
+    /// Returns tag, common identifier for connected nodes
+    inline int GetTag() const
+    {
+        int tag = GetSourceNode()->GetTag();
+        if( tag >= 0 )
+            return tag;
+
+        return GetTargetNode()->GetTag();
+    }
+
+    /// Sets the source node
+    inline void SetSourceNode( const NODE_PTR& aNode )
+    {
+        m_sourceNode = aNode;
+    }
+
+    /// Sets the next edge in face
+    inline void SetNextEdgeInFace( const EDGE_PTR& aEdge )
+    {
+        m_nextEdgeInFace = aEdge;
+    }
+
+    /// Sets the twin edge
+    inline void SetTwinEdge( const EDGE_PTR& aEdge )
+    {
+        m_twinEdge = aEdge;
+    }
+
+    /// Sets the edge as a leading edge
+    inline void SetAsLeadingEdge( bool aLeading = true )
+    {
+        m_isLeadingEdge = aLeading;
+    }
+
+    /// Checks if an edge is a leading edge
+    inline bool IsLeadingEdge() const
+    {
+        return m_isLeadingEdge;
+    }
+
+    /// Returns the twin edge
+    inline EDGE_PTR GetTwinEdge() const
+    {
+        return m_twinEdge.lock();
+    }
+
+    inline void ClearTwinEdge()
+    {
+        m_twinEdge.reset();
+    }
+
+    /// Returns the next edge in face
+    inline const EDGE_PTR& GetNextEdgeInFace() const
+    {
+        return m_nextEdgeInFace;
+    }
+
+    /// Retuns the source node
+    inline const NODE_PTR& GetSourceNode() const
+    {
+        return m_sourceNode;
+    }
+
+    /// Returns the target node
+    virtual const NODE_PTR& GetTargetNode() const
+    {
+        return m_nextEdgeInFace->GetSourceNode();
+    }
+
+    inline void SetWeight( unsigned int weight )
+    {
+        m_weight = weight;
+    }
+
+    inline unsigned int GetWeight() const
+    {
+        return m_weight;
+    }
+
+    void Clear()
+    {
+        m_sourceNode.reset();
+        m_nextEdgeInFace.reset();
+
+        if( !m_twinEdge.expired() )
+        {
+            m_twinEdge.lock()->ClearTwinEdge();
+            m_twinEdge.reset();
+        }
+    }
+
+protected:
+    NODE_PTR        m_sourceNode;
+    EDGE_WEAK_PTR   m_twinEdge;
+    EDGE_PTR        m_nextEdgeInFace;
+    unsigned int    m_weight;
+    bool            m_isLeadingEdge;
+};
+
+
+ /**
+  * \class EDGE_MST
+  * \brief \b Specialization of %EDGE class to be used for Minimum Spanning Tree algorithm.
+  */
+class EDGE_MST : public EDGE
+{
+private:
+    NODE_PTR m_target;
+
+public:
+    EDGE_MST( const NODE_PTR& aSource, const NODE_PTR& aTarget, unsigned int aWeight = 0 ) :
+        m_target( aTarget )
+    {
+        m_sourceNode = aSource;
+        m_weight = aWeight;
+    }
+
+    /// @copydoc Edge::setSourceNode()
+    virtual const NODE_PTR& GetTargetNode() const
+    {
+        return m_target;
+    }
+
+private:
+    EDGE_MST( const EDGE& aEdge )
+    {
+        assert( false );
+    }
+};
+
+class DART; // Forward declaration (class in this namespace)
+
+/**
+ * \class TRIANGULATION
+ * \brief \b %Triangulation class for the half-edge data structure with adaption to TTL.
+ */
+class TRIANGULATION
+{
+protected:
+    /// One half-edge for each arc
+    std::list<EDGE_PTR> m_leadingEdges;
+
+    ttl::TRIANGULATION_HELPER* m_helper;
+
+    void addLeadingEdge( EDGE_PTR& aEdge )
+    {
+        aEdge->SetAsLeadingEdge();
+        m_leadingEdges.push_front( aEdge );
+    }
+
+    bool removeLeadingEdgeFromList( EDGE_PTR& aLeadingEdge );
+
+    void cleanAll();
+
+    /** Swaps the edge associated with \e dart in the actual data structure.
+     *
+     *   <center>
+     *   \image html swapEdge.gif
+     *   </center>
+     *
+     *   \param aDart
+     *   Some of the functions require a dart as output.
+     *   If this is required by the actual function, the dart should be delivered
+     *   back in a position as seen if it was glued to the edge when swapping (rotating)
+     *   the edge CCW; see the figure.
+     *
+     *   \note
+     *   - If the edge is \e constrained, or if it should not be swapped for
+     *     some other reason, this function need not do the actual swap of the edge.
+     *   - Some functions in TTL require that \c swapEdge is implemented such that
+     *     darts outside the quadrilateral are not affected by the swap.
+     */
+    void swapEdge( DART& aDart );
+
+    /**
+     * Splits the triangle associated with \e dart in the actual data structure into
+     * three new triangles joining at \e point.
+     *
+     * <center>
+     * \image html splitTriangle.gif
+     * </center>
+     *
+     * \param aDart
+     * Output: A CCW dart incident with the new node; see the figure.
+     */
+    void splitTriangle( DART& aDart, const NODE_PTR& aPoint );
+
+    /**
+     * The reverse operation of TTLtraits::splitTriangle.
+     * This function is only required for functions that involve
+     * removal of interior nodes; see for example TrinagulationHelper::RemoveInteriorNode.
+     *
+     * <center>
+     * \image html reverse_splitTriangle.gif
+     * </center>
+     */
+    void reverseSplitTriangle( DART& aDart );
+
+    /**
+     * Removes a triangle with an edge at the boundary of the triangulation
+     * in the actual data structure
+     */
+    void removeBoundaryTriangle( DART& aDart );
+
+public:
+    /// Default constructor
+    TRIANGULATION();
+
+    /// Copy constructor
+    TRIANGULATION( const TRIANGULATION& aTriangulation );
+
+    /// Destructor
+    ~TRIANGULATION();
+
+    /// Creates a Delaunay triangulation from a set of points
+    void CreateDelaunay( NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast );
+
+    /// Creates an initial Delaunay triangulation from two enclosing triangles
+    //  When using rectangular boundary - loop through all points and expand.
+    //  (Called from createDelaunay(...) when starting)
+    EDGE_PTR InitTwoEnclosingTriangles( NODES_CONTAINER::iterator aFirst,
+                                        NODES_CONTAINER::iterator aLast );
+
+    // These two functions are required by TTL for Delaunay triangulation
+
+    /// Swaps the edge associated with diagonal
+    void SwapEdge( EDGE_PTR& aDiagonal );
+
+    /// Splits the triangle associated with edge into three new triangles joining at point
+    EDGE_PTR SplitTriangle( EDGE_PTR& aEdge, const NODE_PTR& aPoint );
+
+    // Functions required by TTL for removing nodes in a Delaunay triangulation
+
+    /// Removes the boundary triangle associated with edge
+    void RemoveTriangle( EDGE_PTR& aEdge ); // boundary triangle required
+
+    /// The reverse operation of removeTriangle
+    void ReverseSplitTriangle( EDGE_PTR& aEdge );
+
+    /// Creates an arbitrary CCW dart
+    DART CreateDart();
+
+    /// Returns a list of "triangles" (one leading half-edge for each triangle)
+    const std::list<EDGE_PTR>& GetLeadingEdges() const
+    {
+        return m_leadingEdges;
+    }
+
+    /// Returns the number of triangles
+    int NoTriangles() const
+    {
+        return (int) m_leadingEdges.size();
+    }
+
+    /// Returns a list of half-edges (one half-edge for each arc)
+    std::list<EDGE_PTR>* GetEdges( bool aSkipBoundaryEdges = false ) const;
+
+#ifdef TTL_USE_NODE_FLAG
+    /// Sets flag in all the nodes
+    void FlagNodes( bool aFlag ) const;
+
+    /// Returns a list of nodes. This function requires TTL_USE_NODE_FLAG to be defined. \see Node.
+    std::list<NODE_PTR>* GetNodes() const;
+#endif
+
+    /// Swaps edges until the triangulation is Delaunay (constrained edges are not swapped)
+    void OptimizeDelaunay();
+
+    /// Checks if the triangulation is Delaunay
+    bool CheckDelaunay() const;
+
+    /// Returns an arbitrary interior node (as the source node of the returned edge)
+    EDGE_PTR GetInteriorNode() const;
+
+    EDGE_PTR GetBoundaryEdgeInTriangle( const EDGE_PTR& aEdge ) const;
+
+    /// Returns an arbitrary boundary edge
+    EDGE_PTR GetBoundaryEdge() const;
+
+    /// Print edges for plotting with, e.g., gnuplot
+    void PrintEdges( std::ofstream& aOutput ) const;
+
+    friend class ttl::TRIANGULATION_HELPER;
+};
+}; // End of hed namespace
+
+#endif