voronoiDiagrams.h 2.52 KB
Newer Older
Basile Sauvage's avatar
Basile Sauvage committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#ifndef __VORONOI_DIAGRAMS_H__
#define __VORONOI_DIAGRAMS_H__

#include <vector>
#include <map>

#include "Topology/generic/traversor2.h"

namespace CGoGN
{

namespace Algo
{

namespace Geometry
{

template <typename PFP>
class VoronoiDiagram {
20
protected :
Basile Sauvage's avatar
Basile Sauvage committed
21
22
23
24
25
26
	typedef typename PFP::REAL REAL;

	typedef struct
	{
		typename std::multimap<float,Dart>::iterator it ;
		bool valid ;
27
28
//		unsigned int region;
		Dart pathOrigin;
Basile Sauvage's avatar
Basile Sauvage committed
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
		static std::string CGoGNnameOfType() { return "VoronoiVertexInfo" ; }
	} VoronoiVertexInfo ;
	typedef NoMathIOAttribute<VoronoiVertexInfo> VertexInfo ;

	typename PFP::MAP& map;
	const EdgeAttribute<REAL>& edgeCost; // weights on the graph edges
	VertexAttribute<unsigned int>& regions; // region labels
	std::vector<Dart> border;
	std::vector<Dart> seeds;

	VertexAttribute<VertexInfo> vertexInfo;
	std::multimap<float,Dart> front ;
	CellMarkerStore<VERTEX> vmReached;

public :
	VoronoiDiagram (typename PFP::MAP& m, const EdgeAttribute<REAL>& c, VertexAttribute<unsigned int>& r);
	~VoronoiDiagram ();

	const std::vector<Dart>& getSeeds (){return seeds;}
	void setSeeds (const std::vector<Dart>&);
	void setRandomSeeds (unsigned int nbseeds);
	const std::vector<Dart>& getBorder (){return border;}
	void setCost (const EdgeAttribute<REAL>& c);

	void computeDiagram ();

55
protected :
56
	virtual void clear ();
Basile Sauvage's avatar
Basile Sauvage committed
57
	void initFrontWithSeeds();
58
	virtual void collectVertexFromFront(Dart e);
59
60
	void addVertexToFront(Dart f, float d);
	void updateVertexInFront(Dart f, float d);
Basile Sauvage's avatar
Basile Sauvage committed
61
62
};

63
64
65
66
67

template <typename PFP>
class CentroidalVoronoiDiagram : public VoronoiDiagram<PFP> {
private :
	typedef typename PFP::REAL REAL;
Basile Sauvage's avatar
Basile Sauvage committed
68
	typedef typename PFP::VEC3 VEC3;
69

Basile Sauvage's avatar
Basile Sauvage committed
70
71
	double globalEnergy;

72
73
	VertexAttribute<REAL>& distances; // distances from the seed
	VertexAttribute<Dart>& pathOrigins; // previous vertex on the shortest path from origin
Basile Sauvage's avatar
Basile Sauvage committed
74
	VertexAttribute<REAL>& areaElts; // area element attached to each vertex
75
76

public :
Basile Sauvage's avatar
Basile Sauvage committed
77
78
79
80
81
82
	CentroidalVoronoiDiagram (typename PFP::MAP& m,
			const EdgeAttribute<REAL>& c,
			VertexAttribute<unsigned int>& r,
			VertexAttribute<REAL>& d,
			VertexAttribute<Dart>& o,
			VertexAttribute<REAL>& a);
83
84
	~CentroidalVoronoiDiagram ();

Basile Sauvage's avatar
Basile Sauvage committed
85
	void cumulateEnergyOnPaths();
Basile Sauvage's avatar
Basile Sauvage committed
86
	unsigned int moveSeeds(); // returns the number of seeds that did move
Basile Sauvage's avatar
Basile Sauvage committed
87
	REAL getGlobalEnergy() {return globalEnergy;}
88

89
90
91
protected :
	void clear();
	void collectVertexFromFront(Dart e);
Basile Sauvage's avatar
Basile Sauvage committed
92
	REAL cumulateEnergyFromRoot(Dart e);
Basile Sauvage's avatar
Basile Sauvage committed
93
	unsigned int moveSeed(unsigned int numSeed);
94
95
96
};


Basile Sauvage's avatar
Basile Sauvage committed
97
98
99
100
101
102
103
}// end namespace Geometry
}// end namespace Algo
}// end namespace CGoGN

#include "voronoiDiagrams.hpp"

#endif