Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/Delaunay.h
00001 /*
00002  *
00003  * This file is part of Tulip (www.tulip-software.org)
00004  *
00005  * Authors: David Auber and the Tulip development Team
00006  * from LaBRI, University of Bordeaux
00007  *
00008  * Tulip is free software; you can redistribute it and/or modify
00009  * it under the terms of the GNU Lesser General Public License
00010  * as published by the Free Software Foundation, either version 3
00011  * of the License, or (at your option) any later version.
00012  *
00013  * Tulip is distributed in the hope that it will be useful,
00014  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00015  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00016  * See the GNU General Public License for more details.
00017  *
00018  */
00019 ///@cond DOXYGEN_HIDDEN
00020 
00021 #ifndef DELAUNAY_H
00022 #define DELAUNAY_H
00023 #include <vector>
00024 #include <set>
00025 
00026 #include <tulip/Coord.h>
00027 
00028 namespace tlp {
00029 
00030 /**
00031  * @ingroup Graph
00032  * \brief functions for Delaunay Triangulations
00033  *
00034  * \author : David Auber/Daniel Archambault/Antoine Lambert : auber@tulip-software.org
00035  *
00036  * Computes the delaunay triangulation and returns the set of delaunay edges in the
00037  * vector edges and delaunay simplices (triangles in 2d, tetrahedra in 3d) of the triangulation in the vector simplices.
00038  * Edges and simplices are defined using a indexes into the original
00039  * set of points.
00040  */
00041 TLP_SCOPE bool delaunayTriangulation(std::vector<Coord> &points,
00042                                      std::vector<std::pair<unsigned int, unsigned int> > &edges,
00043                                      std::vector<std::vector<unsigned int> > &simplices,
00044                                      bool voronoiMode = false);
00045 
00046 /**
00047  * @ingroup Graph
00048  * @brief The VoronoiDiagram class
00049  */
00050 class TLP_SCOPE VoronoiDiagram {
00051 public:
00052 
00053   // A voronoi site.
00054   typedef Coord Site;
00055 
00056   // A voronoi vertex.
00057   typedef Coord Vertex;
00058 
00059   // A voronoi edge defined by the indexes of its extremities in the vertices vector
00060   typedef std::pair<unsigned int, unsigned int> Edge;
00061 
00062   // A voronoi Cell defined by the indexes of its vertices in the vertices vector
00063   typedef std::set<unsigned int> Cell;
00064 
00065   // Returns the number of voronoi sites
00066   unsigned int nbSites() const {
00067     return sites.size();
00068   }
00069 
00070   // Returns the number of voronoi vertices
00071   unsigned int nbVertices() const {
00072     return vertices.size();
00073   }
00074 
00075   // Returns the number of voronoi edges
00076   unsigned int nbEdges() const {
00077     return edges.size();
00078   }
00079 
00080   // Returns the ith site
00081   const Site &site(const unsigned int siteIdx) {
00082     return sites[siteIdx];
00083   }
00084 
00085   // Returns the ith voronoi vertex
00086   const Vertex &vertex(const unsigned int vertexIdx) {
00087     return vertices[vertexIdx];
00088   }
00089 
00090   // Returns the ith voronoi edge
00091   const Edge &edge(const unsigned int edgeIdx) {
00092     return edges[edgeIdx];
00093   }
00094 
00095   // Returns the ith voronoi cell
00096   const Cell &cell(const unsigned int cellIdx) {
00097     return cells[cellIdx];
00098   }
00099 
00100   // Returns the degree of the ith voronoi vertex
00101   unsigned int degreeOfVertex(const unsigned int vertexIdx) {
00102     return verticesDegree[vertexIdx];
00103   }
00104 
00105   // Returns the edges of the voronoi cell for the ith site
00106   std::vector<Edge> voronoiEdgesForSite(const unsigned int siteIdx) {
00107     std::vector<Edge> ret;
00108 
00109     for (size_t i = 0 ; i < siteToCellEdges[siteIdx].size() ; ++i) {
00110       ret.push_back(edges[siteToCellEdges[siteIdx][i]]);
00111     }
00112 
00113     return ret;
00114   }
00115 
00116   // Returns the cell for the ith site
00117   const Cell &voronoiCellForSite(const unsigned int siteIdx) {
00118     return cells[siteToCell[siteIdx]];
00119   }
00120 
00121   // Stores lists of each of these types defining the voronoi diagram
00122   std::vector<Site> sites;
00123   std::vector<Vertex> vertices;
00124   std::vector<Edge> edges;
00125   std::vector<Cell> cells;
00126   TLP_HASH_MAP<unsigned int, std::vector<unsigned int> > siteToCellEdges;
00127   TLP_HASH_MAP<unsigned int, unsigned int> siteToCell;
00128   TLP_HASH_MAP<unsigned int, unsigned int> verticesDegree;
00129 };
00130 
00131 /**
00132  * Computes the voronoi diagram of a set of points (for 2d and 3d layouts).
00133  * The set of input points are given in sites.  The resultant voronoi diagram is returned
00134  * in voronoiDiagram.  It automatically computes the set of all voronoi
00135  * vertices, edges and cells. In order to not have to deal with infinite
00136  * voronoi rays, the input layout is enclosed in its convex hull in 2d or
00137  * in its bounding box in 3d. It enables to have a connected voronoi cell
00138  * for each input site.
00139  */
00140 TLP_SCOPE bool voronoiDiagram(std::vector<Coord> &sites, VoronoiDiagram &voronoiDiagram);
00141 
00142 
00143 }
00144 #endif
00145 ///@endcond
 All Classes Files Functions Variables Enumerations Enumerator Properties