Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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#include <unordered_map>
26
27#include <tulip/Coord.h>
28
29namespace 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 */
43TLP_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 */
52class TLP_SCOPE VoronoiDiagram {
53public:
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 */
141TLP_SCOPE bool voronoiDiagram(std::vector<Coord> &sites, VoronoiDiagram &voronoiDiagram);
142} // namespace tlp
143#endif
144///@endcond