Tulip  5.4.0
Large graphs analysis and drawing
Delaunay.h
1 /*
2  *
3  * This file is part of Tulip (http://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 #include <unordered_map>
26 
27 #include <tulip/Coord.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 
48 /**
49  * @ingroup Graph
50  * @brief The VoronoiDiagram class
51  */
52 class TLP_SCOPE VoronoiDiagram {
53 public:
54  // A voronoi site.
55  typedef Coord Site;
56 
57  // A voronoi vertex.
58  typedef Coord Vertex;
59 
60  // A voronoi edge defined by the indexes of its extremities in the vertices vector
61  typedef std::pair<unsigned int, unsigned int> Edge;
62 
63  // A voronoi Cell defined by the indexes of its vertices in the vertices vector
64  typedef std::set<unsigned int> Cell;
65 
66  // Returns the number of voronoi sites
67  unsigned int nbSites() const {
68  return sites.size();
69  }
70 
71  // Returns the number of voronoi vertices
72  unsigned int nbVertices() const {
73  return vertices.size();
74  }
75 
76  // Returns the number of voronoi edges
77  unsigned int nbEdges() const {
78  return edges.size();
79  }
80 
81  // Returns the ith site
82  const Site &site(const unsigned int siteIdx) {
83  return sites[siteIdx];
84  }
85 
86  // Returns the ith voronoi vertex
87  const Vertex &vertex(const unsigned int vertexIdx) {
88  return vertices[vertexIdx];
89  }
90 
91  // Returns the ith voronoi edge
92  const Edge &edge(const unsigned int edgeIdx) {
93  return edges[edgeIdx];
94  }
95 
96  // Returns the ith voronoi cell
97  const Cell &cell(const unsigned int cellIdx) {
98  return cells[cellIdx];
99  }
100 
101  // Returns the degree of the ith voronoi vertex
102  unsigned int degreeOfVertex(const unsigned int vertexIdx) {
103  return verticesDegree[vertexIdx];
104  }
105 
106  // Returns the edges of the voronoi cell for the ith site
107  std::vector<Edge> voronoiEdgesForSite(const unsigned int siteIdx) {
108  std::vector<Edge> ret;
109 
110  for (size_t i = 0; i < siteToCellEdges[siteIdx].size(); ++i) {
111  ret.push_back(edges[siteToCellEdges[siteIdx][i]]);
112  }
113 
114  return ret;
115  }
116 
117  // Returns the cell for the ith site
118  const Cell &voronoiCellForSite(const unsigned int siteIdx) {
119  return cells[siteToCell[siteIdx]];
120  }
121 
122  // Stores lists of each of these types defining the voronoi diagram
123  std::vector<Site> sites;
124  std::vector<Vertex> vertices;
125  std::vector<Edge> edges;
126  std::vector<Cell> cells;
127  std::unordered_map<unsigned int, std::vector<unsigned int>> siteToCellEdges;
128  std::unordered_map<unsigned int, unsigned int> siteToCell;
129  std::unordered_map<unsigned int, unsigned int> verticesDegree;
130 };
131 
132 /**
133  * Computes the voronoi diagram of a set of points (for 2d and 3d layouts).
134  * The set of input points are given in sites. The resultant voronoi diagram is returned
135  * in voronoiDiagram. It automatically computes the set of all voronoi
136  * vertices, edges and cells. In order to not have to deal with infinite
137  * voronoi rays, the input layout is enclosed in its convex hull in 2d or
138  * in its bounding box in 3d. It enables to have a connected voronoi cell
139  * for each input site.
140  */
141 TLP_SCOPE bool voronoiDiagram(std::vector<Coord> &sites, VoronoiDiagram &voronoiDiagram);
142 } // namespace tlp
143 #endif
144 ///@endcond