HeTriang.h

Go to the documentation of this file.

//==================================================================================================
//
// File: HeTriang.h
//
// Created: March 1 2001
//
// Author: Øyvind Hjelle <oyvind.hjelle@math.sintef.no>
//
// Revision: $Id: HeTriang.h,v 1.2 2006/07/26 12:08:44 oyvindhj Exp $
//
// Description:
//
//==================================================================================================
// Copyright (C) 2000-2003 SINTEF Applied Mathematics.  All rights reserved.
//
// This file may be distributed under the terms of the Q Public License
// as defined by Trolltech AS of Norway and appearing in the file
// LICENSE.QPL included in the packaging of this file.
// 
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
//==================================================================================================


#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.h>
#include <ttl/ttl_util.h>
#include <ttl/utils/HandleId.h>
#include <ttl/utils/Handle.h>


using namespace std;

//--------------------------------------------------------------------------------------------------
// The half-edge data structure
//--------------------------------------------------------------------------------------------------

namespace hed {

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

  class Node : public virtual HandleId {

#ifdef TTL_USE_NODE_ID
    static int id_count;
#endif

    double x_, y_, z_;

#ifdef TTL_USE_NODE_ID
    int id_;
#endif

#ifdef TTL_USE_NODE_FLAG
    bool flag_;
#endif

public:
    Node() { init(0, 0, 0); }

    Node(double x, double y, double z = 0.0) { init(x, y, z); }

    ~Node() {}

    void init(double x, double y, double z) { 

#ifdef TTL_USE_NODE_ID
      id_ = id_count++;
#endif

      x_ = x; y_ = y; z_ = z; 
    }

    const double& x() const { return x_; }

    const double& y() const { return y_; }

    const double& z() const { return z_; }

#ifdef TTL_USE_NODE_ID
    const int& id() const { return id_; }
#endif

#ifdef TTL_USE_NODE_FLAG
    void setFlag(bool flag) { flag_ = flag; }

    const bool& getFlag() const { return flag_; }
#endif

  }; // End og class Node

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

  class Edge {
    
    Handle<Node> sourceNode_;
    Edge*        twinEdge_;
    Edge*        nextEdgeInFace_;

    struct {
      unsigned char isLeadingEdge_ : 1;
      unsigned char isConstrained_ : 1;
    } flags_;

  public:
    Edge() { sourceNode_ = NULL; twinEdge_ = NULL; nextEdgeInFace_ = NULL; 
      flags_.isLeadingEdge_ = 0; flags_.isConstrained_ = 0; }

    ~Edge() { if(twinEdge_) twinEdge_->setTwinEdge(NULL); }

    void setSourceNode(Node* node) { sourceNode_ = node; }

    void setNextEdgeInFace(Edge* edge) { nextEdgeInFace_ = edge; }

    void setTwinEdge(Edge* edge) { twinEdge_ = edge; }

    void setAsLeadingEdge(bool val=true) { flags_.isLeadingEdge_ = (val == true ? 1 : 0); }

    bool isLeadingEdge() const { return flags_.isLeadingEdge_ == 1 ? true : false; }

   void setConstrained(bool val=true) { unsigned char cstr = (val == true ? 1 : 0); 
      flags_.isConstrained_ = cstr; if (twinEdge_) twinEdge_->flags_.isConstrained_ = cstr; }

    bool isConstrained() const { return flags_.isConstrained_ == 1 ? true : false; }

    Edge* getTwinEdge() const { return twinEdge_; };

    Edge* getNextEdgeInFace() const { return nextEdgeInFace_; }

    Node* getSourceNode() { return sourceNode_.getPtr(); }

    Node* getTargetNode() { return getNextEdgeInFace()->getSourceNode(); }

  }; // End of class Edge


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


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

  class Triangulation {

  protected:
    list<Edge*> leadingEdges_; // one half-edge for each arc
    void addLeadingEdge(Edge* edge) { edge->setAsLeadingEdge(); leadingEdges_.push_front(edge); }
    bool removeLeadingEdgeFromList(Edge* leadingEdge);
    void cleanAll();
    
  public:
    Triangulation() {}
    
    Triangulation(const Triangulation& tr) { 
      cout << "Triangulation: Copy constructor not present - EXIT."; 
      exit(-1);
    }

    ~Triangulation() { cleanAll(); }
    
    void createDelaunay(vector<Node*>::iterator first,
                        vector<Node*>::iterator last);

    //  When using rectangular boundary - loop through all points and expand.
    //  (Called from createDelaunay(...) when starting)
    Edge* initTwoEnclosingTriangles(vector<Node*>::iterator first,
                                    vector<Node*>::iterator last);


    // These two functions are required by TTL for Delaunay triangulation
    
    void swapEdge(Edge& diagonal);

    Edge* splitTriangle(Edge& edge, Node& point);


    // Functions required by TTL for removing nodes in a Delaunay triangulation
    
    void removeTriangle(Edge& edge); // boundary triangle required    

    void reverse_splitTriangle(Edge& edge);


    Dart createDart();

    const list<Edge*>& getLeadingEdges() const { return leadingEdges_; }

    int noTriangles() const { return leadingEdges_.size(); }
    
    list<Edge*>* getEdges(bool skip_boundary_edges = false) const;

#ifdef TTL_USE_NODE_FLAG
    void flagNodes(bool flag) const;

    list<Node*>* getNodes() const;
#endif

    void optimizeDelaunay();

    bool checkDelaunay() const;    

    Edge* getInteriorNode() const;

    Edge* getBoundaryEdge() const;

    void printEdges(ofstream& os) const;

  }; // End of class Triangulation


}; // End of hed namespace

#endif