Tulip  6.0.0
Large graphs analysis and drawing
Delaunay.h
1 /*
2  *
3  * This file is part of Tulip (https://tulip.labri.fr)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 ///@cond DOXYGEN_HIDDEN
20 
21 #ifndef DELAUNAY_H
22 #define DELAUNAY_H
23 #include <vector>
24 #include <set>
25 
26 #include <tulip/Coord.h>
27 #include <tulip/tuliphash.h>
28 
29 namespace tlp {
30 
31 /**
32  * @ingroup Graph
33  * \brief functions for Delaunay Triangulations
34  *
35  * \author : David Auber/Daniel Archambault/Antoine Lambert : auber@labri.fr
36  *
37  * Computes the delaunay triangulation and returns the set of delaunay edges in the
38  * vector edges and delaunay simplices (triangles in 2d, tetrahedra in 3d) of the triangulation in
39  * the vector simplices.
40  * Edges and simplices are defined using a indexes into the original
41  * set of points.
42  */
43 TLP_SCOPE bool delaunayTriangulation(std::vector<Coord> &points,
44  std::vector<std::pair<unsigned int, unsigned int>> &edges,
45  std::vector<std::vector<unsigned int>> &simplices,
46  bool voronoiMode = false);
47 struct QhullFacade {
48  static std::string QhullVersion();
49 };
50 /**
51  * @ingroup Graph
52  * @brief The VoronoiDiagram class
53  */
54 class TLP_SCOPE VoronoiDiagram {
55 public:
56  // A voronoi site.
57  typedef Coord Site;
58 
59  // A voronoi vertex.
60  typedef Coord Vertex;
61 
62  // A voronoi edge defined by the indexes of its extremities in the vertices vector
63  typedef std::pair<unsigned int, unsigned int> Edge;
64 
65  // A voronoi Cell defined by the indexes of its vertices in the vertices vector
66  typedef std::set<unsigned int> Cell;
67 
68  // Returns the number of voronoi sites
69  inline unsigned int nbSites() const {
70  return sites.size();
71  }
72 
73  // Returns the number of voronoi vertices
74  inline unsigned int nbVertices() const {
75  return vertices.size();
76  }
77 
78  // Returns the number of voronoi edges
79  inline unsigned int nbEdges() const {
80  return edges.size();
81  }
82 
83  // Returns the ith site
84  inline const Site &site(const unsigned int siteIdx) {
85  return sites[siteIdx];
86  }
87 
88  // Returns the ith voronoi vertex
89  inline const Vertex &vertex(const unsigned int vertexIdx) {
90  return vertices[vertexIdx];
91  }
92 
93  // Returns the ith voronoi edge
94  inline const Edge &edge(const unsigned int edgeIdx) {
95  return edges[edgeIdx];
96  }
97 
98  // Returns the ith voronoi cell
99  inline const Cell &cell(const unsigned int cellIdx) {
100  return cells[cellIdx];
101  }
102 
103  // Returns the degree of the ith voronoi vertex
104  inline unsigned int degreeOfVertex(const unsigned int vertexIdx) {
105  return verticesDegree[vertexIdx];
106  }
107 
108  // Returns the edges of the voronoi cell for the ith site
109  std::vector<Edge> voronoiEdgesForSite(const unsigned int siteIdx) {
110  auto &site = siteToCellEdges[siteIdx];
111  std::vector<Edge> ret(site.size());
112 
113  for (size_t i = 0; i < siteToCellEdges[siteIdx].size(); ++i) {
114  ret.push_back(edges[siteToCellEdges[siteIdx][i]]);
115  }
116 
117  return ret;
118  }
119 
120  // Returns the cell for the ith site
121  inline const Cell &voronoiCellForSite(const unsigned int siteIdx) {
122  return cells[siteToCell[siteIdx]];
123  }
124 
125  // Stores lists of each of these types defining the voronoi diagram
126  std::vector<Site> sites;
127  std::vector<Vertex> vertices;
128  std::vector<Edge> edges;
129  std::vector<Cell> cells;
130  tlp_hash_map<unsigned int, std::vector<unsigned int>> siteToCellEdges;
131  tlp_hash_map<unsigned int, unsigned int> siteToCell;
132  tlp_hash_map<unsigned int, unsigned int> verticesDegree;
133 };
134 
135 /**
136  * Computes the voronoi diagram of a set of points (for 2d and 3d layouts).
137  * The set of input points are given in sites. The resultant voronoi diagram is returned
138  * in voronoiDiagram. It automatically computes the set of all voronoi
139  * vertices, edges and cells. In order to not have to deal with infinite
140  * voronoi rays, the input layout is enclosed in its convex hull in 2d or
141  * in its bounding box in 3d. It enables to have a connected voronoi cell
142  * for each input site.
143  */
144 TLP_SCOPE bool voronoiDiagram(std::vector<Coord> &sites, VoronoiDiagram &voronoiDiagram);
145 } // namespace tlp
146 #endif
147 ///@endcond