coloring.hpp

Go to the documentation of this file.

#ifndef _COLORING_HPP
#define _COLORING_HPP

#include <assert.h>
#include <vector>
#include <list>
#include <iostream>
#include <CGAL/Triangulation_2.h>
#include <CGAL/Triangulation_face_base_with_info_2.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include "global.hpp"
#include "random.hpp"
#include "handle.hpp"
#include "store.hpp"
#include "properties.hpp"
#include "geometry.hpp"
#include "grid.hpp"

// One or the other of the following must be uncommented
#define GRID_EDGE_INDEX
// #define TRIANGULATION_EDGE_INDEX // This is much (4x) slower

#if defined(TRIANGULATION_EDGE_INDEX) && !defined(EXACT_GEOM_PRED)
#error "The triangulation index requires exact geometric predicates."
#endif

namespace CGAL {
  class Qt_widget;
}

namespace Arak {

  class QueryPointIndex;

  class Coloring {

  public:

    class Vertex;
    class InteriorEdge;
    class BoundaryEdge;

    typedef PointerHandle<Vertex> VertexHandle;

    typedef PointerHandle<InteriorEdge> IntEdgeHandle;

    typedef PointerHandle<BoundaryEdge> BdEdgeHandle;

  public:

    struct FaceColorInfo {
      Color color;
    };

    template <typename FaceInfoType = FaceColorInfo,
        typename VertexBaseType = CGAL::Triangulation_vertex_base_2<Geometry::Kernel> 
              >
    struct TriangulationTraits {
      typedef typename 
      CGAL::Triangulation_face_base_with_info_2<FaceInfoType,
            Geometry::Kernel> 
      FaceBaseWithInfo;

      typedef typename 
      CGAL::Constrained_triangulation_face_base_2<Geometry::Kernel, 
              FaceBaseWithInfo> 
      TFb;

      typedef typename 
      CGAL::Triangulation_data_structure_2<VertexBaseType, TFb> Tds;

      typedef CGAL::No_intersection_tag itag;

      typedef typename
      CGAL::Constrained_Delaunay_triangulation_2<Geometry::Kernel, Tds, itag> 
      Triangulation;
    };

#ifdef TRIANGULATION_EDGE_INDEX

  protected:

    template <class Vb = CGAL::Triangulation_vertex_base_2<Geometry::Kernel> >
    class TVb : public Vb {
      typedef Vb                              Base;
    public:
      typedef typename Vb::Vertex_handle      Vertex_handle;
      typedef typename Vb::Face_handle        Face_handle;
      typedef typename Vb::Point              Point;
      typedef std::pair<Face_handle,int>      Edge;
      
      template < typename TDS2 >
      struct Rebind_TDS {
  typedef typename Vb::template Rebind_TDS<TDS2>::Other    Vb2;
  typedef TVb<Vb2>                 Other;
      };
      
      VertexHandle vertex;
    
      TVb() : Base(), vertex(NULL) {}
      TVb(const Point & p) : Base(p), vertex(NULL) {}
      TVb(const Point & p, Face_handle f) : Base(f,p), vertex(NULL) {}
      TVb(Face_handle f) : Base(f), vertex(NULL) {}
    };

    typedef TriangulationTraits<FaceColorInfo, TVb<> >::Triangulation 
    TriangulationIndex;

    typedef TriangulationIndex::Face_handle TFaceHandle;
    
    typedef TriangulationIndex::Vertex_handle TVertexHandle;

    typedef TriangulationIndex::Edge TEdge;

    typedef TriangulationIndex::Line_face_circulator TFaceCirculator;

    class Tracer {

    protected:

      Geometry::Point source;

      Geometry::Point target;

      const Coloring::TriangulationIndex* tri;

      Coloring::TFaceCirculator circ;

      Coloring::TEdge edge;

      bool forwards;

      bool valid;

      bool isRay;

    public:

      Tracer(const Geometry::Point& source,
       const Geometry::Point& target,
       const Coloring::TriangulationIndex& tri,
       bool isRay = false,
       const Coloring::TFaceHandle hint = 
       Coloring::TFaceHandle());
      
      Tracer()
  : source(CGAL::ORIGIN), 
    target(CGAL::ORIGIN), 
    tri(NULL), circ(),
    edge(Coloring::TFaceHandle(), 0), 
    forwards(true), valid(false), isRay(false) { }
      
      inline bool operator==(const Tracer& other) const
      { return ((valid == other.valid) &&
    (!valid || (valid && (circ == other.circ)))); }
      inline bool operator!=(const Tracer& other) const 
      { return !(*this == other); }
      
      Tracer operator++(int) {
  Tracer tmp(*this);
  ++(*this);
  return tmp;
      }
      Tracer& operator++();

      const TEdge* operator->() const {return &edge;}
      const TEdge& operator*() const { return edge;}

    }; // End of class: Coloring::Tracer

#endif // #ifdef TRIANGULATION_EDGE_INDEX

  public:

    class Vertex : public Geometry::Point {

      friend class InteriorEdge;
      friend class BoundaryEdge;
      friend class Coloring;
    
    public:

      enum Type {
  INTERIOR, 
  BOUNDARY, 
  CORNER,   
  INVALID,  
      };

    protected:

#ifdef TRIANGULATION_EDGE_INDEX

      TVertexHandle tvh;
#endif

      Type t;

      IntEdgeHandle prevIntEdge;

      IntEdgeHandle nextIntEdge;

      BdEdgeHandle prevBdEdge;

      BdEdgeHandle nextBdEdge;

      int index;

    public:

      Vertex() {
  t = INVALID;
  index = -1;
      }
    
      inline Type type() const { return t; }

      const Geometry::Point& point() const { return *this; }

      inline bool hasPrevIntEdge() const { 
  assert(type() != CORNER);
  return (prevIntEdge.valid()); 
      }

      inline IntEdgeHandle getPrevIntEdge() { 
  assert(type() != CORNER);
  return prevIntEdge; 
      }
      inline const IntEdgeHandle getPrevIntEdge() const { 
  assert(type() != CORNER);
  return prevIntEdge; 
      }

      inline bool hasNextIntEdge() const {
  assert(type() != CORNER);
  return (nextIntEdge.valid()); 
      }

      inline IntEdgeHandle getNextIntEdge() {
  assert(type() != CORNER);
  return nextIntEdge; 
      }
      inline const IntEdgeHandle getNextIntEdge() const {
  assert(type() != CORNER);
  return nextIntEdge; 
      }

      inline BdEdgeHandle getPrevBdEdge() {
  assert((type() == CORNER) || (type() == BOUNDARY)); 
  return prevBdEdge; 
      }
      inline const BdEdgeHandle getPrevBdEdge() const {
  assert((type() == CORNER) || (type() == BOUNDARY)); 
  return prevBdEdge; 
      }

      inline BdEdgeHandle getNextBdEdge() { 
  assert((type() == CORNER) || (type() == BOUNDARY)); 
  return nextBdEdge; 
      }
      inline const BdEdgeHandle getNextBdEdge() const { 
  assert((type() == CORNER) || (type() == BOUNDARY)); 
  return nextBdEdge; 
      }

      inline VertexHandle getPrevVertex() {
  return getPrevIntEdge()->getPrevVertex();
      }
      inline const VertexHandle getPrevVertex() const {
  return getPrevIntEdge()->getPrevVertex();
      }

      inline VertexHandle getNextVertex() {
  return getNextIntEdge()->getNextVertex();
      }
      inline const VertexHandle getNextVertex() const {
  return getNextIntEdge()->getNextVertex();
      }

      inline VertexHandle getPrevCornerVertex() {
  return getPrevBdEdge()->getPrevCornerVertex();
      }
      inline const VertexHandle getPrevCornerVertex() const {
  return getPrevBdEdge()->getPrevCornerVertex();
      }

      inline VertexHandle getNextCornerVertex() {
  return getNextBdEdge()->getNextCornerVertex();
      }
      inline const VertexHandle getNextCornerVertex() const {
  return getNextBdEdge()->getNextCornerVertex();
      }

      double logSine();

    }; // End of class: Coloring::Vertex

    class Edge : public Geometry::Segment {

      friend class Vertex;
      friend class Coloring;

    protected:

      VertexHandle prevVertex;

      VertexHandle nextVertex;

      int index;

    public:

      Edge() {
  index = -1;
      }

      const Geometry::Segment& segment() const { return *this; }

      inline VertexHandle getPrevVertex() { return prevVertex; }
      inline const VertexHandle getPrevVertex() const { return prevVertex; }

      inline VertexHandle getNextVertex() { return nextVertex; }
      inline const VertexHandle getNextVertex() const { return nextVertex; }

      Geometry::Point 
      randomPoint(Arak::Util::Random& random = Arak::Util::default_random) const;

      double length() const { 
  using namespace Arak::Geometry;
  return sqrt(CGAL::to_double(squared_length())); 
      }

      bool operator==(const Edge& other) const {
  return (this == &other);
      }

      bool operator!=(const Edge& other) const {
  return !this->operator!=(other);
      }

    }; // End of class: Coloring::Edge

    typedef Grid<IntEdgeHandle> InteriorEdgeIndex;

    class InteriorEdge : public Edge {

      friend class Vertex;
      friend class Coloring;

    public:

      typedef InteriorEdgeIndex::Cell::Entry CellEntry;

      typedef std::list<CellEntry> CellEntryList;

    protected:

      CellEntryList entries;

      CellEntryList unused;

    public:

      InteriorEdge() : Edge(), entries() { }

      ~InteriorEdge() { }

      bool crosses(const Geometry::Point& a, 
       const Geometry::Point& b) const;

      const CellEntryList& cellEntries() const { return entries; }

    }; // End of class: Coloring::InteriorEdge

    class BoundaryEdge : public Edge {

      friend class Vertex;
      friend class Coloring;

    protected:

      VertexHandle prevCorner;

      VertexHandle nextCorner;

    public:

      BoundaryEdge() : Edge(), prevCorner(NULL), nextCorner(NULL) { }

      inline VertexHandle getPrevCornerVertex() { return prevCorner; }
      inline const VertexHandle getPrevCornerVertex() const { return prevCorner; }
      inline VertexHandle getNextCornerVertex() { return nextCorner; }
      inline const VertexHandle getNextCornerVertex() const { return nextCorner; }

      Geometry::Point 
      randomPoint(Arak::Util::Random& random = Arak::Util::default_random) const;

    }; // End of class: Coloring::BoundaryEdge

  public:

    class Listener {

    public:

      virtual void vertexHasBeenAdded(Coloring::VertexHandle vh) {};

      virtual void vertexWillBeRemoved(Coloring::VertexHandle vh) {};

      virtual void edgeHasBeenAdded(Coloring::IntEdgeHandle eh) {};

      virtual void edgeWillBeRemoved(Coloring::IntEdgeHandle eh) {};

      virtual void recolored(const Geometry::Point& a,
           const Geometry::Point& b,
           const Geometry::Point& c) {};
      
      virtual void recolored(const Geometry::Point& a,
           const Geometry::Point& b,
           const Geometry::Point& c,
           const Geometry::Point& d) {};

    }; // End of class: Coloring::Listener

  protected:

    Geometry::Rectangle bd;

    InteriorEdgeIndex* intEdgeIndex;

#ifdef TRIANGULATION_EDGE_INDEX

    TriangulationIndex tri;
#endif
    
    mutable QueryPointIndex* queryPoints;

    Store<Vertex> vertexStore;
  
    std::vector<VertexHandle> interiorVertices;
  
    std::vector<VertexHandle> boundaryVertices;
  
    std::vector<VertexHandle> cornerVertices;
  
    Store<InteriorEdge> intEdgeStore;
  
    std::vector<IntEdgeHandle> interiorEdges;
  
    Store<BoundaryEdge> bdEdgeStore;
  
    std::vector<BdEdgeHandle> boundaryEdges;

    mutable std::list<Listener*> listeners;

    double minEdgeLengthSq;

    VertexHandle newVertex(Vertex::Type type, const Geometry::Point& p);

    void freeVertex(VertexHandle& v);
  
    void disconnectFromBd(VertexHandle v);
  
    IntEdgeHandle newInteriorEdge(VertexHandle prev, VertexHandle next);

    BdEdgeHandle newBoundaryEdge(VertexHandle prev, 
         VertexHandle next,
         VertexHandle prevCorner, 
         VertexHandle nextCorner);

    void freeEdge(IntEdgeHandle& e);

    void freeEdge(BdEdgeHandle& e);

    void recolored(const Geometry::Point& a,
       const Geometry::Point& b,
       const Geometry::Point& c);
    
    void recolored(const Geometry::Point& a,
       const Geometry::Point& b,
       const Geometry::Point& c,
       const Geometry::Point& d);

    inline void notifyVertexWillBeRemoved(VertexHandle vh) {
      for (std::list<Listener*>::iterator it = listeners.begin(); 
     it != listeners.end(); it++) 
  (*it)->vertexWillBeRemoved(vh);
    }
    
    inline void notifyVertexHasBeenAdded(VertexHandle vh) {
      for (std::list<Listener*>::iterator it = listeners.begin(); 
     it != listeners.end(); it++) 
  (*it)->vertexHasBeenAdded(vh);
    }

    inline void notifyEdgeWillBeRemoved(IntEdgeHandle eh) {
      for (std::list<Listener*>::iterator it = listeners.begin(); 
     it != listeners.end(); it++) 
  (*it)->edgeWillBeRemoved(eh);
    }
    
    inline void notifyEdgeHasBeenAdded(IntEdgeHandle eh) {
      for (std::list<Listener*>::iterator it = listeners.begin(); 
     it != listeners.end(); it++) 
  (*it)->edgeHasBeenAdded(eh);
    }

    void initialize(Geometry::Rectangle &boundary, 
        int gridRows = 10,
        int gridCols = 10,
        double minEdgeLength = 0.0);

    void clear();

  public:
  
    Coloring();

    Coloring(Geometry::Rectangle &boundary, 
       int gridRows = 10,
       int gridCols = 10,
       double minEdgeLength = 0.0);
  
    Coloring(const Util::PropertyMap& props);

    ~Coloring();

    void test() const;

    const Geometry::Rectangle& boundary() const { return bd; }

    const InteriorEdgeIndex& getInteriorEdgeIndex() const {
      return *intEdgeIndex;
    }

    inline int numVertices(Vertex::Type type) const {
      switch (type) {
      case Vertex::INTERIOR:
  return interiorVertices.size();
      case Vertex::BOUNDARY:
  return boundaryVertices.size();
      case Vertex::CORNER:
  return cornerVertices.size();
      default:
  assert(false);
      }
    }

    inline const VertexHandle getVertex(Vertex::Type type, int index) const {
      switch (type) {
      case Vertex::INTERIOR:
  return interiorVertices[index];
      case Vertex::BOUNDARY:
  return boundaryVertices[index];
      case Vertex::CORNER:
  return cornerVertices[index];
      default:
  assert(false);
      }
    }

    inline VertexHandle getVertex(Vertex::Type type, int index) {
      switch (type) {
      case Vertex::INTERIOR:
  return interiorVertices[index];
      case Vertex::BOUNDARY:
  return boundaryVertices[index];
      case Vertex::CORNER:
  return cornerVertices[index];
      default:
  assert(false);
      }
    }

    inline int numInteriorEdges() const {
      return interiorEdges.size();
    }

    inline int numBoundaryEdges() const {
      return boundaryEdges.size();
    }

    inline const IntEdgeHandle getInteriorEdge(int index) const {
      return interiorEdges[index];
    }
    inline IntEdgeHandle getInteriorEdge(int index) {
      return interiorEdges[index];
    }

    inline const BdEdgeHandle getBoundaryEdge(int index) const {
      return boundaryEdges[index];
    }
    inline BdEdgeHandle getBoundaryEdge(int index) {
      return boundaryEdges[index];
    }

    struct TEST_IF_VALID_TAG {};

    struct DO_IF_VALID_TAG {};

    struct DO_WITHOUT_TEST_TAG {};

    bool deleteVertex(VertexHandle v, TEST_IF_VALID_TAG) const;
    bool deleteVertex(VertexHandle& v, DO_IF_VALID_TAG);
    bool deleteVertex(VertexHandle& v, DO_WITHOUT_TEST_TAG);


    bool splitEdge(IntEdgeHandle e, 
       const Geometry::Point& p, 
       TEST_IF_VALID_TAG) const;
    bool splitEdge(IntEdgeHandle& e, 
       const Geometry::Point& p, 
       DO_IF_VALID_TAG);
    bool splitEdge(IntEdgeHandle& e, 
       const Geometry::Point& p, 
       DO_WITHOUT_TEST_TAG);


    bool newInteriorTriangle(const Geometry::Point& x, 
           const Geometry::Point& y, 
           const Geometry::Point& z, 
           TEST_IF_VALID_TAG) const;
    VertexHandle newInteriorTriangle(const Geometry::Point& x, 
             const Geometry::Point& y, 
             const Geometry::Point& z, 
             DO_IF_VALID_TAG);
    VertexHandle newInteriorTriangle(const Geometry::Point& x, 
             const Geometry::Point& y, 
             const Geometry::Point& z, 
             DO_WITHOUT_TEST_TAG);


    bool newBoundaryTriangle(BdEdgeHandle e, 
           const Geometry::Point& u, 
           const Geometry::Point& v, 
           const Geometry::Point& w,
           TEST_IF_VALID_TAG) const;
    VertexHandle newBoundaryTriangle(BdEdgeHandle e, 
             const Geometry::Point& u, 
             const Geometry::Point& v, 
             const Geometry::Point& w,
             DO_IF_VALID_TAG);
    VertexHandle newBoundaryTriangle(BdEdgeHandle e, 
             const Geometry::Point& u, 
             const Geometry::Point& v, 
             const Geometry::Point& w,
             DO_WITHOUT_TEST_TAG);


    bool newCornerTriangle(VertexHandle corner, 
         const Geometry::Point& u, 
         const Geometry::Point& v, 
         TEST_IF_VALID_TAG) const;
    VertexHandle newCornerTriangle(VertexHandle corner, 
           const Geometry::Point& u, 
           const Geometry::Point& v, 
           DO_IF_VALID_TAG);
    VertexHandle newCornerTriangle(VertexHandle corner, 
           const Geometry::Point& u, 
           const Geometry::Point& v, 
           DO_WITHOUT_TEST_TAG);


    bool deleteIntTriangle(VertexHandle vh, TEST_IF_VALID_TAG) const;
    bool deleteIntTriangle(VertexHandle& vh, DO_IF_VALID_TAG);
    bool deleteIntTriangle(VertexHandle& vh, DO_WITHOUT_TEST_TAG);


    bool deleteBdTriangle(VertexHandle vh, TEST_IF_VALID_TAG) const;
    bool deleteBdTriangle(VertexHandle& vh, DO_IF_VALID_TAG);
    bool deleteBdTriangle(VertexHandle& vh, DO_WITHOUT_TEST_TAG);


    bool deleteCornerTriangle(VertexHandle vh, TEST_IF_VALID_TAG) const;
    bool deleteCornerTriangle(VertexHandle& vh, DO_IF_VALID_TAG);
    bool deleteCornerTriangle(VertexHandle& vh, DO_WITHOUT_TEST_TAG);


    bool moveIntVertex(VertexHandle v, 
           const Geometry::Point& p, 
           TEST_IF_VALID_TAG) const;
    bool moveIntVertex(VertexHandle& v, 
           const Geometry::Point& p, 
           DO_IF_VALID_TAG);
    bool moveIntVertex(VertexHandle& v, 
           const Geometry::Point& p, 
           DO_WITHOUT_TEST_TAG);


    bool moveVertexAlongBd(VertexHandle v, 
         const Geometry::Point& p, 
         TEST_IF_VALID_TAG) const;
    bool moveVertexAlongBd(VertexHandle& v, 
         const Geometry::Point& p, 
         DO_IF_VALID_TAG);
    bool moveVertexAlongBd(VertexHandle& v, 
         const Geometry::Point& p, 
         DO_WITHOUT_TEST_TAG);


    bool moveBdVertexPastCorner(BdEdgeHandle e, 
        const Geometry::Point& p,
        TEST_IF_VALID_TAG) const;
    bool moveBdVertexPastCorner(BdEdgeHandle& e, 
        const Geometry::Point& p,
        DO_IF_VALID_TAG);
    bool moveBdVertexPastCorner(BdEdgeHandle& e, 
        const Geometry::Point& p,
        DO_WITHOUT_TEST_TAG);


    bool recolorQuadrilateral(IntEdgeHandle ab, 
            IntEdgeHandle cd, 
            bool ac, 
            TEST_IF_VALID_TAG) const;
    bool recolorQuadrilateral(IntEdgeHandle& ab, 
            IntEdgeHandle& cd, 
            bool ac, 
            DO_IF_VALID_TAG);
    bool recolorQuadrilateral(IntEdgeHandle& ab, 
            IntEdgeHandle& cd, 
            bool ac, 
            DO_WITHOUT_TEST_TAG);
  
#ifdef GRID_EDGE_INDEX

    bool compatible(const Geometry::Point &xp, 
        const Geometry::Point &yp) const;
#endif // #ifdef GRID_EDGE_INDEX

#ifdef TRIANGULATION_EDGE_INDEX

    bool compatible(const Geometry::Point &xp, 
        const Geometry::Point &yp,
        TFaceHandle fh = TFaceHandle()) const;
#endif // #ifdef TRIANGULATION_EDGE_INDEX

    bool trace(const Geometry::Point &xp, 
         const Geometry::Point &yp,
         IntEdgeHandle& edge,
         Geometry::Point &ipt,
         Geometry::Kernel::FT& sd) const;

    bool interior(const Geometry::Point& xp) const {
      return bd.has_on_bounded_side(xp);
    }

    bool boundary(const Geometry::Point& xp) const {
      return bd.has_on_boundary(xp);
    }

    bool outside(const Geometry::Point& xp) const {
      return bd.has_on_unbounded_side(xp);
    }

    Geometry::Point 
    randomPoint(Arak::Util::Random& random = Arak::Util::default_random) const;

    double area() const { 
      using namespace Arak::Geometry;
      return CGAL::to_double(bd.area()); 
    }
    
    inline VertexHandle randomVertex(Vertex::Type type, 
             Arak::Util::Random& random = Arak::Util::default_random) const {
      assert(numVertices(type) > 0);
      return getVertex(type, random.uniform(numVertices(type)));
    }

    void getPointWithColor(Geometry::Point& p, Color& c) const;

    Color color(const Geometry::Point& point) const;
    
    bool solid(const Geometry::Polygon& poly, Arak::Color color) const;

    void addListener(Listener& listener) const;

    void addQueryPoints(const QueryPointIndex& index) const;

    const QueryPointIndex& getQueryPoints() const { return *queryPoints; }

    QueryPointIndex& getQueryPoints() { return *queryPoints; }

    void write(std::ostream& out) const;

    void writeBinary(std::ostream& out) const;

    void writeXfig(std::ostream& out) const;

    bool read(std::istream& in);

    bool readBinary(std::istream& in);

    template <typename FaceInfoType>
    void toTriangulation(CGAL::Constrained_Delaunay_triangulation_2<Geometry::Kernel, 
   CGAL::Tds2<CGAL::Tvb<Arak::Geometry::Kernel, CGAL::Tdsvb<void> >, 
   CGAL::Ctfb<Geometry::Kernel, 
   CGAL::Triangulation_face_base_with_info_2<FaceInfoType, 
   Geometry::Kernel, CGAL::Tfb<Arak::Geometry::Kernel, 
   CGAL::Tdsfb<void> > > > >, CGAL::No_intersection_tag>& tri) const;

    void visualize(CGAL::Qt_widget& widget,
       bool drawEdges = true,
       bool drawVertices = true,
       bool drawRegions = false,
       bool drawQueries = false) const;

    bool operator==(const Coloring& other) const {
      return (this == &other);
    }

    bool operator!=(const Coloring& other) const {
      return (this != &other);
    }
  };

  inline std::ostream& operator<<(std::ostream& out, const Coloring& c) {
    c.write(out);
    return out;
  }

  inline std::istream& operator>>(std::istream& in, Coloring& c) {
    if (!c.read(in))
      in.setstate(std::ios_base::failbit);
    return in;
  }

  template <typename FaceInfoType>
  void Coloring::toTriangulation(CGAL::Constrained_Delaunay_triangulation_2<Geometry::Kernel, 
   CGAL::Tds2<CGAL::Tvb<Arak::Geometry::Kernel, CGAL::Tdsvb<void> >, 
   CGAL::Ctfb<Geometry::Kernel, 
   CGAL::Triangulation_face_base_with_info_2<FaceInfoType, 
   Geometry::Kernel, CGAL::Tfb<Arak::Geometry::Kernel, 
   CGAL::Tdsfb<void> > > > >, CGAL::No_intersection_tag>& tri) const {
    typedef typename TriangulationTraits<FaceInfoType>::Triangulation 
      Triangulation;
    typedef typename Triangulation::Vertex_handle TVh;
    typedef typename Triangulation::Face_handle TFh;
    // Clear the current triangulation.
    tri.clear();
    // Build a map from vertex handles of the coloring to vertex
    // handles of the triangulation.
    std::map<VertexHandle, TVh> c2t;
    // Add the vertices of the coloring to the triangulation.
    for (int i = 0; i < numVertices(Coloring::Vertex::CORNER); i++) {
      Coloring::VertexHandle v = 
  getVertex(Coloring::Vertex::CORNER, i);
      c2t[v] = tri.insert(v->point());
    }
    for (int i = 0; i < numVertices(Coloring::Vertex::BOUNDARY); i++) {
      Coloring::VertexHandle v = 
  getVertex(Coloring::Vertex::BOUNDARY, i);
      c2t[v] = tri.insert(v->point());
    }
    for (int i = 0; i < numVertices(Coloring::Vertex::INTERIOR); i++) {
      Coloring::VertexHandle v = 
  getVertex(Coloring::Vertex::INTERIOR, i);
      c2t[v] = tri.insert(v->point());
    }
    // Add all interior edges as contraints.
    for (int i = 0; i < numInteriorEdges(); i++) {
      const Coloring::IntEdgeHandle e = getInteriorEdge(i);
      Coloring::VertexHandle u = e->getPrevVertex();
      Coloring::VertexHandle v = e->getNextVertex();
      tri.insert_constraint(c2t[u], c2t[v]);
    }
    // Now color the faces.  First invalidate all the colors.
    typedef typename Triangulation::Finite_faces_iterator FiniteFacesIterator;
    FiniteFacesIterator it = tri.finite_faces_begin();
    FiniteFacesIterator end = tri.finite_faces_end();
    while (it != end) {
      it->info().color = INVALID_COLOR;
      it++;
    }
    // Then color one of the faces.
    Geometry::Point p;
    Color c;
    getPointWithColor(p, c);
    TFh fh = tri.locate(p);
    assert(!tri.is_infinite(fh));
    fh->info().color = c;
    // Color neighbors via a depth-first search.
    std::stack<TFh> unvisited;
    unvisited.push(fh);
    while (!unvisited.empty()) {
      fh = unvisited.top(); unvisited.pop();
      assert(fh->info().color != INVALID_COLOR);
      // Visit any neighbors that are finite and not yet colored.
      for (int i = 0; i < 3; i++) {
  TFh nbr = fh->neighbor(i);
  if ((nbr->info().color == INVALID_COLOR) && 
      (!tri.is_infinite(nbr))) {
    if (fh->is_constrained(i))
      nbr->info().color = opposite(fh->info().color);
    else
      nbr->info().color = fh->info().color;
    unvisited.push(nbr);
  }
      }
    }
  }

} // End of namespace: Arak

#endif

---