voronoiDiagrams.h 2.46 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
70
71

	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
72
	VertexAttribute<REAL>& areaElts; // area element attached to each vertex
73
74

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

83
	void cumulateDistancesOnPaths();
Basile Sauvage's avatar
Basile Sauvage committed
84
	unsigned int moveSeeds(); // returns the number of seeds that did move
85

86
87
88
protected :
	void clear();
	void collectVertexFromFront(Dart e);
Basile Sauvage's avatar
Basile Sauvage committed
89
	REAL cumulateDistancesFromRoot(Dart e);
Basile Sauvage's avatar
Basile Sauvage committed
90
	unsigned int moveSeed(unsigned int numSeed);
91
92
93
};


Basile Sauvage's avatar
Basile Sauvage committed
94
95
96
97
98
99
100
}// end namespace Geometry
}// end namespace Algo
}// end namespace CGoGN

#include "voronoiDiagrams.hpp"

#endif