hetriang.h 12.4 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 54 55
/*
 * 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
56
#include <boost/weak_ptr.hpp>
Maciej Suminski's avatar
Maciej Suminski committed
57

58 59 60 61
namespace ttl {
  class TriangulationHelper;
};

Maciej Suminski's avatar
Maciej Suminski committed
62 63 64 65 66 67 68 69 70 71
//--------------------------------------------------------------------------------------------------
// The half-edge data structure
//--------------------------------------------------------------------------------------------------

namespace hed {
  // Helper typedefs
  class Node;
  class Edge;
  typedef boost::shared_ptr<Node> NodePtr;
  typedef boost::shared_ptr<Edge> EdgePtr;
Maciej Suminski's avatar
Maciej Suminski committed
72
  typedef boost::weak_ptr<Edge> EdgeWeakPtr;
Maciej Suminski's avatar
Maciej Suminski committed
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158
  typedef std::vector<NodePtr> NodesContainer;

  //------------------------------------------------------------------------------------------------
  // Node class for data structures
  //------------------------------------------------------------------------------------------------

  /** \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 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 id_;
#endif

    int x_, y_;

    unsigned int refCount_;

public:
    /// Constructor
    Node( int x = 0, int y = 0 ) :
#ifdef TTL_USE_NODE_FLAG
    flag_( false ),
#endif
#ifdef TTL_USE_NODE_ID
    id_( id_count++ ),
#endif
    x_( x ), y_( y ), refCount_( 0 ) {}

    /// Destructor
    ~Node() {}

    /// Returns the x-coordinate
    int GetX() const { return x_; }

    /// Returns the y-coordinate
    int GetY() const { return y_; }

#ifdef TTL_USE_NODE_ID
    /// Returns the id (TTL_USE_NODE_ID must be defined)
    int Id() const { return id_; }
#endif

#ifdef TTL_USE_NODE_FLAG
    /// Sets the flag (TTL_USE_NODE_FLAG must be defined)
    void SetFlag(bool aFlag) { flag_ = aFlag; }

    /// Returns the flag (TTL_USE_NODE_FLAG must be defined)
    const bool& GetFlag() const { return flag_; }
#endif

    void IncRefCount() { refCount_++; }
    void DecRefCount() { refCount_--; }
    unsigned int GetRefCount() const { return refCount_; }
  }; // End of class Node

  
  //------------------------------------------------------------------------------------------------
  // Edge class in the half-edge data structure
  //------------------------------------------------------------------------------------------------

  /** \class Edge
  *   \brief \b %Edge class in the in the half-edge data structure.
  */

  class Edge {
  public:
    /// Constructor
Maciej Suminski's avatar
Maciej Suminski committed
159
    Edge() : weight_(0), isLeadingEdge_(false) {}
Maciej Suminski's avatar
Maciej Suminski committed
160 161 162 163 164 165 166 167 168 169 170 171 172 173

    /// Destructor
    virtual ~Edge() {}

    /// Sets the source node
    void setSourceNode(const NodePtr& node) { sourceNode_ = node; }

    /// Sets the next edge in face
    void setNextEdgeInFace(const EdgePtr& edge) { nextEdgeInFace_ = edge; }

    /// Sets the twin edge
    void setTwinEdge(const EdgePtr& edge) { twinEdge_ = edge; }

    /// Sets the edge as a leading edge
Maciej Suminski's avatar
Maciej Suminski committed
174
    void setAsLeadingEdge(bool val=true) { isLeadingEdge_ = val; }
Maciej Suminski's avatar
Maciej Suminski committed
175 176

    /// Checks if an edge is a leading edge
Maciej Suminski's avatar
Maciej Suminski committed
177
    bool isLeadingEdge() const { return isLeadingEdge_; }
Maciej Suminski's avatar
Maciej Suminski committed
178 179

    /// Returns the twin edge
Maciej Suminski's avatar
Maciej Suminski committed
180 181 182
    EdgePtr getTwinEdge() const { return twinEdge_.lock(); };

    void clearTwinEdge() { twinEdge_.reset(); }
Maciej Suminski's avatar
Maciej Suminski committed
183 184 185 186 187

    /// Returns the next edge in face
    const EdgePtr& getNextEdgeInFace() const { return nextEdgeInFace_; }

    /// Retuns the source node
Maciej Suminski's avatar
Maciej Suminski committed
188
    const NodePtr& getSourceNode() const { return sourceNode_; }
Maciej Suminski's avatar
Maciej Suminski committed
189 190

    /// Returns the target node
Maciej Suminski's avatar
Maciej Suminski committed
191
    virtual const NodePtr& getTargetNode() const { return nextEdgeInFace_->getSourceNode(); }
Maciej Suminski's avatar
Maciej Suminski committed
192 193 194 195 196

    void setWeight( unsigned int weight ) { weight_ = weight; }

    unsigned int getWeight() const { return weight_; }

Maciej Suminski's avatar
Maciej Suminski committed
197 198 199 200 201 202 203 204 205 206 207 208
    void clear()
    {
        sourceNode_.reset();
        nextEdgeInFace_.reset();

        if( !twinEdge_.expired() )
        {
            twinEdge_.lock()->clearTwinEdge();
            twinEdge_.reset();
        }
    }

Maciej Suminski's avatar
Maciej Suminski committed
209 210
  protected:
    NodePtr sourceNode_;
Maciej Suminski's avatar
Maciej Suminski committed
211
    EdgeWeakPtr twinEdge_;
Maciej Suminski's avatar
Maciej Suminski committed
212 213
    EdgePtr nextEdgeInFace_;
    unsigned int weight_;
Maciej Suminski's avatar
Maciej Suminski committed
214
    bool isLeadingEdge_;
Maciej Suminski's avatar
Maciej Suminski committed
215 216 217 218
  }; // End of class Edge


  /** \class EdgeMST
Maciej Suminski's avatar
Maciej Suminski committed
219
  *   \brief \b Specialization of %Edge class to be used for Minimum Spanning Tree algorithm.
Maciej Suminski's avatar
Maciej Suminski committed
220 221 222 223 224 225 226 227 228 229 230
  */
  class EdgeMST : public Edge
  {
  private:
    NodePtr target_;

  public:
    EdgeMST( const NodePtr& source, const NodePtr& target, unsigned int weight = 0 ) :
        target_(target)
        { sourceNode_ = source; weight_ = weight; }

Maciej Suminski's avatar
Maciej Suminski committed
231 232 233 234 235 236 237
    EdgeMST( const Edge& edge )
    {
        sourceNode_ = edge.getSourceNode();
        target_ = edge.getTargetNode();
        weight_ = edge.getWeight();
    }

Maciej Suminski's avatar
Maciej Suminski committed
238 239 240
    ~EdgeMST() {};

    /// @copydoc Edge::setSourceNode()
Maciej Suminski's avatar
Maciej Suminski committed
241
    virtual const NodePtr& getTargetNode() const { return target_; }
Maciej Suminski's avatar
Maciej Suminski committed
242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258
  };


  //------------------------------------------------------------------------------------------------
  class Dart; // Forward declaration (class in this namespace)

  //------------------------------------------------------------------------------------------------
  // Triangulation class in the half-edge data structure
  //------------------------------------------------------------------------------------------------

  /** \class Triangulation
  *   \brief \b %Triangulation class for the half-edge data structure with adaption to TTL.
  */

  class Triangulation {

  protected:
259 260 261 262
    std::list<EdgePtr> leadingEdges_; // one half-edge for each arc

    ttl::TriangulationHelper* helper;

Maciej Suminski's avatar
Maciej Suminski committed
263 264 265 266
    void addLeadingEdge(EdgePtr& edge) {
        edge->setAsLeadingEdge();
        leadingEdges_.push_front( edge );
    }
267

Maciej Suminski's avatar
Maciej Suminski committed
268
    bool removeLeadingEdgeFromList(EdgePtr& leadingEdge);
269

Maciej Suminski's avatar
Maciej Suminski committed
270 271
    void cleanAll();
    
272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301
    /** Swaps the edge associated with \e dart in the actual data structure.
    *
    *   <center>
    *   \image html swapEdge.gif
    *   </center>
    *
    *   \param dart
    *   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& dart);

    /** 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 dart
    *   Output: A CCW dart incident with the new node; see the figure.
    */
Maciej Suminski's avatar
Maciej Suminski committed
302
    void splitTriangle(Dart& dart, const NodePtr& point);
303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318

    /** 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 reverse_splitTriangle(Dart& dart);

    /** Removes a triangle with an edge at the boundary of the triangulation
    *   in the actual data structure
    */
    void removeBoundaryTriangle(Dart& d);

Maciej Suminski's avatar
Maciej Suminski committed
319 320
  public:
    /// Default constructor
321
    Triangulation();
Maciej Suminski's avatar
Maciej Suminski committed
322 323
    
    /// Copy constructor
324
    Triangulation(const Triangulation& tr);
Maciej Suminski's avatar
Maciej Suminski committed
325 326

    /// Destructor
327
    ~Triangulation();
Maciej Suminski's avatar
Maciej Suminski committed
328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345
    
    /// Creates a Delaunay triangulation from a set of points
    void createDelaunay(NodesContainer::iterator first,
                        NodesContainer::iterator last);

    /// Creates an initial Delaunay triangulation from two enclosing triangles
    //  When using rectangular boundary - loop through all points and expand.
    //  (Called from createDelaunay(...) when starting)
    EdgePtr initTwoEnclosingTriangles(NodesContainer::iterator first,
                                      NodesContainer::iterator last);


    // These two functions are required by TTL for Delaunay triangulation
    
    /// Swaps the edge associated with diagonal
    void swapEdge(EdgePtr& diagonal);

    /// Splits the triangle associated with edge into three new triangles joining at point 
Maciej Suminski's avatar
Maciej Suminski committed
346
    EdgePtr splitTriangle(EdgePtr& edge, const NodePtr& point);
Maciej Suminski's avatar
Maciej Suminski committed
347 348 349 350 351 352 353 354 355 356 357 358 359 360


    // Functions required by TTL for removing nodes in a Delaunay triangulation
    
    /// Removes the boundary triangle associated with edge
    void removeTriangle(EdgePtr& edge); // boundary triangle required

    /// The reverse operation of removeTriangle
    void reverse_splitTriangle(EdgePtr& edge);

    /// Creates an arbitrary CCW dart
    Dart createDart();

    /// Returns a list of "triangles" (one leading half-edge for each triangle)
361
    const std::list<EdgePtr>& getLeadingEdges() const { return leadingEdges_; }
Maciej Suminski's avatar
Maciej Suminski committed
362 363

    /// Returns the number of triangles
Maciej Suminski's avatar
Maciej Suminski committed
364
    int noTriangles() const { return (int)leadingEdges_.size(); }
Maciej Suminski's avatar
Maciej Suminski committed
365 366
    
    /// Returns a list of half-edges (one half-edge for each arc)
367
    std::list<EdgePtr>* getEdges(bool skip_boundary_edges = false) const;
Maciej Suminski's avatar
Maciej Suminski committed
368 369 370 371 372 373

#ifdef TTL_USE_NODE_FLAG
    /// Sets flag in all the nodes  
    void flagNodes(bool flag) const;

    /// Returns a list of nodes. This function requires TTL_USE_NODE_FLAG to be defined. \see Node.
374
    std::list<NodePtr>* getNodes() const;
Maciej Suminski's avatar
Maciej Suminski committed
375 376 377 378 379 380 381 382 383 384 385
#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)
    EdgePtr getInteriorNode() const;

386 387
    EdgePtr getBoundaryEdgeInTriangle(const EdgePtr& e) const;

Maciej Suminski's avatar
Maciej Suminski committed
388 389 390 391 392 393
    /// Returns an arbitrary boundary edge
    EdgePtr getBoundaryEdge() const;

    /// Print edges for plotting with, e.g., gnuplot
    void printEdges(std::ofstream& os) const;

394 395
    friend class ttl::TriangulationHelper;

Maciej Suminski's avatar
Maciej Suminski committed
396 397 398 399 400 401
  }; // End of class Triangulation


}; // End of hed namespace

#endif