hetriang.h 11.9 KB
Newer Older
Maciej Suminski's avatar
Maciej Suminski committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
/*
 * 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>
Maciej Suminski's avatar
Maciej Suminski committed
54
#include <boost/weak_ptr.hpp>
Maciej Suminski's avatar
Maciej Suminski committed
55

56 57 58
namespace ttl
{
    class TRIANGULATION_HELPER;
59 60
};

61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
/**
 * 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
{
Maciej Suminski's avatar
Maciej Suminski committed
86 87 88
protected:
#ifdef TTL_USE_NODE_FLAG
    /// TTL_USE_NODE_FLAG must be defined
89
    bool m_flag;
Maciej Suminski's avatar
Maciej Suminski committed
90 91 92 93 94 95 96
#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)
97
    int m_id;
Maciej Suminski's avatar
Maciej Suminski committed
98 99
#endif

100 101
    /// Node coordinates
    int m_x, m_y;
Maciej Suminski's avatar
Maciej Suminski committed
102

103 104
    /// Reference count
    unsigned int m_refCount;
Maciej Suminski's avatar
Maciej Suminski committed
105 106 107

public:
    /// Constructor
108
    NODE( int aX = 0, int aY = 0 ) :
Maciej Suminski's avatar
Maciej Suminski committed
109
#ifdef TTL_USE_NODE_FLAG
110
        m_flag( false ),
Maciej Suminski's avatar
Maciej Suminski committed
111 112
#endif
#ifdef TTL_USE_NODE_ID
113
        m_id( id_count++ ),
Maciej Suminski's avatar
Maciej Suminski committed
114
#endif
115 116 117
        m_x( aX ), m_y( aY ), m_refCount( 0 )
    {
    }
Maciej Suminski's avatar
Maciej Suminski committed
118 119

    /// Destructor
120
    ~NODE() {}
Maciej Suminski's avatar
Maciej Suminski committed
121 122

    /// Returns the x-coordinate
123 124 125 126
    int GetX() const
    {
        return m_x;
    }
Maciej Suminski's avatar
Maciej Suminski committed
127 128

    /// Returns the y-coordinate
129 130 131 132
    int GetY() const
    {
        return m_y;
    }
Maciej Suminski's avatar
Maciej Suminski committed
133 134 135

#ifdef TTL_USE_NODE_ID
    /// Returns the id (TTL_USE_NODE_ID must be defined)
136 137 138 139
    int Id() const
    {
        return m_id;
    }
Maciej Suminski's avatar
Maciej Suminski committed
140 141 142 143
#endif

#ifdef TTL_USE_NODE_FLAG
    /// Sets the flag (TTL_USE_NODE_FLAG must be defined)
144 145 146 147
    void SetFlag( bool aFlag )
    {
        m_flag = aFlag;
    }
Maciej Suminski's avatar
Maciej Suminski committed
148 149

    /// Returns the flag (TTL_USE_NODE_FLAG must be defined)
150 151 152 153
    const bool& GetFlag() const
    {
        return m_flag;
    }
Maciej Suminski's avatar
Maciej Suminski committed
154 155
#endif

156 157 158 159
    void IncRefCount()
    {
        m_refCount++;
    }
Maciej Suminski's avatar
Maciej Suminski committed
160

161 162 163 164
    void DecRefCount()
    {
        m_refCount--;
    }
Maciej Suminski's avatar
Maciej Suminski committed
165

166 167 168 169 170
    unsigned int GetRefCount() const
    {
        return m_refCount;
    }
};
Maciej Suminski's avatar
Maciej Suminski committed
171

172 173 174 175 176 177 178 179
  
/**
 * \class EDGE
 * \brief \b %Edge class in the in the half-edge data structure.
 */
class EDGE
{
public:
Maciej Suminski's avatar
Maciej Suminski committed
180
    /// Constructor
181 182 183
    EDGE() : m_weight( 0 ), m_isLeadingEdge( false )
    {
    }
Maciej Suminski's avatar
Maciej Suminski committed
184 185

    /// Destructor
186 187 188
    virtual ~EDGE()
    {
    }
Maciej Suminski's avatar
Maciej Suminski committed
189 190

    /// Sets the source node
191 192 193 194
    void SetSourceNode( const NODE_PTR& aNode )
    {
        m_sourceNode = aNode;
    }
Maciej Suminski's avatar
Maciej Suminski committed
195 196

    /// Sets the next edge in face
197 198 199 200
    void SetNextEdgeInFace( const EDGE_PTR& aEdge )
    {
        m_nextEdgeInFace = aEdge;
    }
Maciej Suminski's avatar
Maciej Suminski committed
201 202

    /// Sets the twin edge
203 204 205 206
    void SetTwinEdge( const EDGE_PTR& aEdge )
    {
        m_twinEdge = aEdge;
    }
Maciej Suminski's avatar
Maciej Suminski committed
207 208

    /// Sets the edge as a leading edge
209 210 211 212
    void SetAsLeadingEdge( bool aLeading = true )
    {
        m_isLeadingEdge = aLeading;
    }
Maciej Suminski's avatar
Maciej Suminski committed
213 214

    /// Checks if an edge is a leading edge
215 216 217 218
    bool IsLeadingEdge() const
    {
        return m_isLeadingEdge;
    }
Maciej Suminski's avatar
Maciej Suminski committed
219 220

    /// Returns the twin edge
221 222 223 224
    EDGE_PTR GetTwinEdge() const
    {
        return m_twinEdge.lock();
    }
Maciej Suminski's avatar
Maciej Suminski committed
225

226 227 228 229
    void ClearTwinEdge()
    {
        m_twinEdge.reset();
    }
Maciej Suminski's avatar
Maciej Suminski committed
230 231

    /// Returns the next edge in face
232 233 234 235
    const EDGE_PTR& GetNextEdgeInFace() const
    {
        return m_nextEdgeInFace;
    }
Maciej Suminski's avatar
Maciej Suminski committed
236 237

    /// Retuns the source node
238 239 240 241
    const NODE_PTR& GetSourceNode() const
    {
        return m_sourceNode;
    }
Maciej Suminski's avatar
Maciej Suminski committed
242 243

    /// Returns the target node
244 245 246 247
    virtual const NODE_PTR& GetTargetNode() const
    {
        return m_nextEdgeInFace->GetSourceNode();
    }
Maciej Suminski's avatar
Maciej Suminski committed
248

249 250 251 252
    void SetWeight( unsigned int weight )
    {
        m_weight = weight;
    }
Maciej Suminski's avatar
Maciej Suminski committed
253

254 255 256 257
    unsigned int GetWeight() const
    {
        return m_weight;
    }
Maciej Suminski's avatar
Maciej Suminski committed
258

259
    void Clear()
Maciej Suminski's avatar
Maciej Suminski committed
260
    {
261 262
        m_sourceNode.reset();
        m_nextEdgeInFace.reset();
Maciej Suminski's avatar
Maciej Suminski committed
263

264
        if( !m_twinEdge.expired() )
Maciej Suminski's avatar
Maciej Suminski committed
265
        {
266 267
            m_twinEdge.lock()->ClearTwinEdge();
            m_twinEdge.reset();
Maciej Suminski's avatar
Maciej Suminski committed
268 269 270
        }
    }

271 272 273 274 275 276 277
protected:
    NODE_PTR        m_sourceNode;
    EDGE_WEAK_PTR   m_twinEdge;
    EDGE_PTR        m_nextEdgeInFace;
    unsigned int    m_weight;
    bool            m_isLeadingEdge;
};
Maciej Suminski's avatar
Maciej Suminski committed
278 279


280 281 282
 /**
  * \class EDGE_MST
  * \brief \b Specialization of %EDGE class to be used for Minimum Spanning Tree algorithm.
Maciej Suminski's avatar
Maciej Suminski committed
283
  */
284 285 286 287
class EDGE_MST : public EDGE
{
private:
    NODE_PTR m_target;
Maciej Suminski's avatar
Maciej Suminski committed
288

289 290 291 292 293 294 295
public:
    EDGE_MST( const NODE_PTR& aSource, const NODE_PTR& aTarget, unsigned int aWeight = 0 ) :
        m_target( aTarget )
    {
        m_sourceNode = aSource;
        m_weight = aWeight;
    }
Maciej Suminski's avatar
Maciej Suminski committed
296

297
    EDGE_MST( const EDGE& edge )
Maciej Suminski's avatar
Maciej Suminski committed
298
    {
299 300 301
        m_sourceNode = edge.GetSourceNode();
        m_target = edge.GetTargetNode();
        m_weight = edge.GetWeight();
Maciej Suminski's avatar
Maciej Suminski committed
302 303
    }

304 305 306
    ~EDGE_MST()
    {
    }
Maciej Suminski's avatar
Maciej Suminski committed
307 308

    /// @copydoc Edge::setSourceNode()
309 310 311 312 313
    virtual const NODE_PTR& GetTargetNode() const
    {
        return m_target;
    }
};
Maciej Suminski's avatar
Maciej Suminski committed
314

315
class DART; // Forward declaration (class in this namespace)
Maciej Suminski's avatar
Maciej Suminski committed
316

317 318 319 320 321 322 323 324 325
/**
 * \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;
326

327
    ttl::TRIANGULATION_HELPER* m_helper;
328

329 330 331 332
    void addLeadingEdge( EDGE_PTR& aEdge )
    {
        aEdge->SetAsLeadingEdge();
        m_leadingEdges.push_front( aEdge );
Maciej Suminski's avatar
Maciej Suminski committed
333
    }
334

335
    bool removeLeadingEdgeFromList( EDGE_PTR& aLeadingEdge );
336

Maciej Suminski's avatar
Maciej Suminski committed
337
    void cleanAll();
338

339
    /** Swaps the edge associated with \e dart in the actual data structure.
340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389
     *
     *   <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:
Maciej Suminski's avatar
Maciej Suminski committed
390
    /// Default constructor
391 392
    TRIANGULATION();

Maciej Suminski's avatar
Maciej Suminski committed
393
    /// Copy constructor
394
    TRIANGULATION( const TRIANGULATION& aTriangulation );
Maciej Suminski's avatar
Maciej Suminski committed
395 396

    /// Destructor
397 398
    ~TRIANGULATION();

Maciej Suminski's avatar
Maciej Suminski committed
399
    /// Creates a Delaunay triangulation from a set of points
400
    void CreateDelaunay( NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast );
Maciej Suminski's avatar
Maciej Suminski committed
401 402 403 404

    /// Creates an initial Delaunay triangulation from two enclosing triangles
    //  When using rectangular boundary - loop through all points and expand.
    //  (Called from createDelaunay(...) when starting)
405 406
    EDGE_PTR InitTwoEnclosingTriangles( NODES_CONTAINER::iterator aFirst,
                                        NODES_CONTAINER::iterator aLast );
Maciej Suminski's avatar
Maciej Suminski committed
407 408

    // These two functions are required by TTL for Delaunay triangulation
409

Maciej Suminski's avatar
Maciej Suminski committed
410
    /// Swaps the edge associated with diagonal
411
    void SwapEdge( EDGE_PTR& aDiagonal );
Maciej Suminski's avatar
Maciej Suminski committed
412 413

    /// Splits the triangle associated with edge into three new triangles joining at point 
414
    EDGE_PTR SplitTriangle( EDGE_PTR& aEdge, const NODE_PTR& aPoint );
Maciej Suminski's avatar
Maciej Suminski committed
415 416

    // Functions required by TTL for removing nodes in a Delaunay triangulation
417

Maciej Suminski's avatar
Maciej Suminski committed
418
    /// Removes the boundary triangle associated with edge
419
    void RemoveTriangle( EDGE_PTR& aEdge ); // boundary triangle required
Maciej Suminski's avatar
Maciej Suminski committed
420 421

    /// The reverse operation of removeTriangle
422
    void ReverseSplitTriangle( EDGE_PTR& aEdge );
Maciej Suminski's avatar
Maciej Suminski committed
423 424

    /// Creates an arbitrary CCW dart
425
    DART CreateDart();
Maciej Suminski's avatar
Maciej Suminski committed
426 427

    /// Returns a list of "triangles" (one leading half-edge for each triangle)
428 429 430 431
    const std::list<EDGE_PTR>& GetLeadingEdges() const
    {
        return m_leadingEdges;
    }
Maciej Suminski's avatar
Maciej Suminski committed
432 433

    /// Returns the number of triangles
434 435 436 437 438
    int NoTriangles() const
    {
        return (int) m_leadingEdges.size();
    }

Maciej Suminski's avatar
Maciej Suminski committed
439
    /// Returns a list of half-edges (one half-edge for each arc)
440
    std::list<EDGE_PTR>* GetEdges( bool aSkipBoundaryEdges = false ) const;
Maciej Suminski's avatar
Maciej Suminski committed
441 442 443

#ifdef TTL_USE_NODE_FLAG
    /// Sets flag in all the nodes  
444
    void FlagNodes( bool aFlag ) const;
Maciej Suminski's avatar
Maciej Suminski committed
445 446

    /// Returns a list of nodes. This function requires TTL_USE_NODE_FLAG to be defined. \see Node.
447
    std::list<NODE_PTR>* GetNodes() const;
Maciej Suminski's avatar
Maciej Suminski committed
448 449 450
#endif

    /// Swaps edges until the triangulation is Delaunay (constrained edges are not swapped)
451
    void OptimizeDelaunay();
Maciej Suminski's avatar
Maciej Suminski committed
452 453

    /// Checks if the triangulation is Delaunay
454
    bool CheckDelaunay() const;
Maciej Suminski's avatar
Maciej Suminski committed
455 456

    /// Returns an arbitrary interior node (as the source node of the returned edge)
457
    EDGE_PTR GetInteriorNode() const;
Maciej Suminski's avatar
Maciej Suminski committed
458

459
    EDGE_PTR GetBoundaryEdgeInTriangle( const EDGE_PTR& aEdge ) const;
460

Maciej Suminski's avatar
Maciej Suminski committed
461
    /// Returns an arbitrary boundary edge
462
    EDGE_PTR GetBoundaryEdge() const;
Maciej Suminski's avatar
Maciej Suminski committed
463 464

    /// Print edges for plotting with, e.g., gnuplot
465
    void PrintEdges( std::ofstream& aOutput ) const;
Maciej Suminski's avatar
Maciej Suminski committed
466

467 468
    friend class ttl::TRIANGULATION_HELPER;
};
Maciej Suminski's avatar
Maciej Suminski committed
469 470 471
}; // End of hed namespace

#endif