![]() |
Tulip
4.6.0
Better Visualization Through Research
|
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