---

delaunay.h

//$Header: /home/ben/Mapper/include/RCS/delaunay.h,v 6.15 2002/07/07 11:38:02 ben Exp $
#ifndef DELAUNAY_H
#define DELAUNAY_H
// Copyright Benedict Adamson 2002.
// This file is part of Mapper.

// Mapper is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.

// Mapper 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 General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with Mapper; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

#include <vector>

#include "vector2.h"

namespace delaunay {

   class edge{
      public: //Construction and destruction
         
         inline edge(
            const vector2 &v0,
            const vector2 &v1
            );

         inline ~edge(void);

      public: //Attributes
         
         inline const vector2 &vertex(
            const unsigned i
            ) const;

         inline friend bool operator==(
            const edge &a,
            const edge &b
            );

      private:
         vector2 vertex_[2];
         
   };



   class triangle{
      public: //Construction and destruction
         
         triangle(
            const vector2 &v0,
            const vector2 &v1,
            const vector2 &v2
            );

         triangle(
            const triangle &t
            );

         inline ~triangle(void);

      public: //Attributes

         inline const vector2 &vertex(
            const unsigned i
            ) const;

         inline const vector2 &circumcentre(void) const;

         const double circumradius(void) const;

         bool circumcircle_contains(
            const vector2 &p
            ) const;

      public: //messages
         //None

      public:

         inline friend bool operator==(
            const triangle &a,
            const triangle &b
            );

      private:
         vector2 vertex_[3];
         vector2 circumcentre_;
         double circumradius2;

         void calculate_circumcircle(void);

   };



   class triangulation{
      public://Construction and destruction

         triangulation(
            const double l,
            const double r,
            const double t,
            const double b
            );

         virtual ~triangulation(void);

      public: //attributes

         const double left;

         const double right;

         const double top;

         const double bottom;

         const vector2 tl;

         const vector2 tr;

         const vector2 br;

         const vector2 bl;

         inline bool corner_point(
            const vector2 &p
            ) const;

         inline bool border_triangle(
            const triangle &t
            ) const;

         bool contains(
            const vector2 &p
            ) const;

      public: //associations

         const vector< triangle > &triangles(void) const {
            return this->triangles_;
         }

      public: //messages

         void add_point(
            const vector2 &p
            );

      private:

         vector< triangle > triangles_;
         
   };

};
   


inline delaunay::edge::edge(
   const vector2 &v0,
   const vector2 &v1
   )
{
   this->vertex_[0] = v0;
   this->vertex_[1] = v1;
   {//Postconditions:
      //assert( this->vertex(0) == v0 );
      //assert( this->vertex(1) == v1 );
   };
}



inline delaunay::edge::~edge(void)
{
   //Do nothing
}


   
inline const vector2 &delaunay::edge::vertex(
   const unsigned i
   ) const
{
   {//Preconditions:
      //assert( i == 0 || i == 1 );
   };
   return this->vertex_[i];
}


inline bool delaunay::operator==(
   const edge &a,
   const edge &b
   )
{
   return
   (a.vertex_[0] == b.vertex_[0] && a.vertex_[1] == b.vertex_[1]) ||
   (a.vertex_[0] == b.vertex_[1] && a.vertex_[1] == b.vertex_[0]);
}



inline delaunay::triangle::~triangle(void)
{
   //Do nothing
}



inline const vector2 &delaunay::triangle::vertex(
   const unsigned i
   ) const
{
   {//Preconditions:
      //assert( 0 <= i && i <= 2 );
   };
   return this->vertex_[i];
}


inline const vector2 &delaunay::triangle::circumcentre(void) const
{
   return this->circumcentre_;
}


inline bool delaunay::operator==(
   const triangle &a,
   const triangle &b
   )
{
   return
   (a.vertex_[0] == b.vertex_[0] &&
    a.vertex_[1] == b.vertex_[1] &&
    a.vertex_[2] == b.vertex_[2]) ||
   (a.vertex_[0] == b.vertex_[1] &&
    a.vertex_[1] == b.vertex_[2] &&
    a.vertex_[2] == b.vertex_[0]) ||
   (a.vertex_[0] == b.vertex_[2] &&
    a.vertex_[1] == b.vertex_[0] &&
    a.vertex_[2] == b.vertex_[1]);
   //assert( triangle(a, b, c) == triangle(a, b, c) );
   //assert( triangle(a, b, c) == triangle(b, c, a) );
   //assert( triangle(a, b, c) == triangle(c, a, b) );
}

inline bool delaunay::triangulation::corner_point(
   const vector2 &p
   ) const
{
   return
      p == this->tl ||
      p == this->tr ||
      p == this->br ||
      p == this->bl;
   //assert( this->corner_point( &(this->tl) ) );
   //assert( this->corner_point( &(this->tr) ) );
   //assert( this->corner_point( &(this->br) ) );
   //assert( this->corner_point( &(this->bl) ) );
}



inline bool delaunay::triangulation::border_triangle(
   const triangle &t
   ) const
{
   //Returns true iff a vertex of the triangle is a corner point.
   return
      this->corner_point( t.vertex(0) ) ||
      this->corner_point( t.vertex(1) ) ||
      this->corner_point( t.vertex(2) );
}

#endif

---