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