voronoiDiagrams.h 3.71 KB
Newer Older
Basile Sauvage's avatar
Basile Sauvage committed
1 2 3 4 5
#ifndef __VORONOI_DIAGRAMS_H__
#define __VORONOI_DIAGRAMS_H__

#include <vector>
#include <map>
6
#include <set>
Basile Sauvage's avatar
Basile Sauvage committed
7

8
//#include "Topology/map/map2.h"
9
#include "Topology/generic/traversor/traversor2.h"
Basile Sauvage's avatar
Basile Sauvage committed
10 11 12 13 14 15 16

namespace CGoGN
{

namespace Algo
{

Sylvain Thery's avatar
Sylvain Thery committed
17 18 19
namespace Surface
{

Basile Sauvage's avatar
Basile Sauvage committed
20 21 22 23
namespace Geometry
{

template <typename PFP>
Pierre Kraemer's avatar
Pierre Kraemer committed
24 25 26 27
class VoronoiDiagram
{
	typedef typename PFP::MAP MAP;
	typedef typename PFP::VEC3 VEC3;
Basile Sauvage's avatar
Basile Sauvage committed
28 29
	typedef typename PFP::REAL REAL;

Pierre Kraemer's avatar
Pierre Kraemer committed
30
protected :
Basile Sauvage's avatar
Basile Sauvage committed
31 32 33 34
	typedef struct
	{
		typename std::multimap<float,Dart>::iterator it ;
		bool valid ;
35 36
//		unsigned int region;
		Dart pathOrigin;
Basile Sauvage's avatar
Basile Sauvage committed
37 38
		static std::string CGoGNnameOfType() { return "VoronoiVertexInfo" ; }
	} VoronoiVertexInfo ;
Pierre Kraemer's avatar
Pierre Kraemer committed
39

40
	typedef NoTypeNameAttribute<VoronoiVertexInfo> VertexInfo ;
Basile Sauvage's avatar
Basile Sauvage committed
41

Pierre Kraemer's avatar
Pierre Kraemer committed
42
	MAP& map;
43 44
	const EdgeAttribute<REAL, MAP>& edgeCost; // weights on the graph edges
	VertexAttribute<unsigned int, MAP>& regions; // region labels
Basile Sauvage's avatar
Basile Sauvage committed
45 46 47
	std::vector<Dart> border;
	std::vector<Dart> seeds;

48
	VertexAttribute<VertexInfo, MAP> vertexInfo;
Basile Sauvage's avatar
Basile Sauvage committed
49
	std::multimap<float,Dart> front ;
Pierre Kraemer's avatar
Pierre Kraemer committed
50
	CellMarker<MAP, VERTEX> vmReached;
Basile Sauvage's avatar
Basile Sauvage committed
51 52

public :
53
	VoronoiDiagram (MAP& m, const EdgeAttribute<REAL, MAP>& c, VertexAttribute<unsigned int, MAP>& r);
Basile Sauvage's avatar
Basile Sauvage committed
54 55
	~VoronoiDiagram ();

Pierre Kraemer's avatar
Pierre Kraemer committed
56
	const std::vector<Dart>& getSeeds () { return seeds; }
Basile Sauvage's avatar
Basile Sauvage committed
57 58
	virtual void setSeeds_fromVector (const std::vector<Dart>&);
	virtual void setSeeds_random (unsigned int nbseeds);
Pierre Kraemer's avatar
Pierre Kraemer committed
59
	const std::vector<Dart>& getBorder () { return border; }
Sylvain Thery's avatar
Sylvain Thery committed
60 61

//	void setCost (const EdgeAttribute<REAL,MAP>& c); // impossible to reaffect a ref TODO pointer ?
Basile Sauvage's avatar
Basile Sauvage committed
62

Basile Sauvage's avatar
Basile Sauvage committed
63 64
	Dart computeDiagram ();
	virtual void computeDiagram_incremental (unsigned int nbseeds);
65
	void computeDistancesWithinRegion (Dart seed);
Basile Sauvage's avatar
Basile Sauvage committed
66

67
protected :
68
	virtual void clear ();
Basile Sauvage's avatar
Basile Sauvage committed
69
	void initFrontWithSeeds();
70
	virtual void collectVertexFromFront(Dart e);
71 72
	void addVertexToFront(Dart f, float d);
	void updateVertexInFront(Dart f, float d);
Basile Sauvage's avatar
Basile Sauvage committed
73 74
};

75
template <typename PFP>
Pierre Kraemer's avatar
Pierre Kraemer committed
76 77
class CentroidalVoronoiDiagram : public VoronoiDiagram<PFP>
{
78
	typedef typename PFP::MAP MAP;
Basile Sauvage's avatar
Basile Sauvage committed
79
	typedef typename PFP::VEC3 VEC3;
Pierre Kraemer's avatar
Pierre Kraemer committed
80
	typedef typename PFP::REAL REAL;
81

Pierre Kraemer's avatar
Pierre Kraemer committed
82
private :
Basile Sauvage's avatar
Basile Sauvage committed
83
	double globalEnergy;
Basile Sauvage's avatar
Basile Sauvage committed
84
	std::vector<VEC3> energyGrad; // gradient of the region energy at seed
Basile Sauvage's avatar
Basile Sauvage committed
85

86 87 88
	VertexAttribute<REAL, MAP>& distances; // distances from the seed
	VertexAttribute<Dart, MAP>& pathOrigins; // previous vertex on the shortest path from origin
	VertexAttribute<REAL, MAP>& areaElts; // area element attached to each vertex
89 90

public :
Pierre Kraemer's avatar
Pierre Kraemer committed
91 92
	CentroidalVoronoiDiagram (
			MAP& m,
93 94 95 96 97
			const EdgeAttribute<REAL, MAP>& c,
			VertexAttribute<unsigned int, MAP>& r,
			VertexAttribute<REAL, MAP>& d,
			VertexAttribute<Dart, MAP>& o,
			VertexAttribute<REAL, MAP>& a);
Pierre Kraemer's avatar
Pierre Kraemer committed
98

99 100
	~CentroidalVoronoiDiagram ();

Basile Sauvage's avatar
Basile Sauvage committed
101 102 103
	void setSeeds_fromVector (const std::vector<Dart>&);
	void setSeeds_random (unsigned int nbseeds);
	void computeDiagram_incremental (unsigned int nbseeds);
Basile Sauvage's avatar
Basile Sauvage committed
104 105 106 107 108 109 110 111
	void cumulateEnergy();
	void cumulateEnergyAndGradients();
	unsigned int moveSeedsOneEdgeNoCheck(); // returns the number of seeds that did move
	// move each seed along one edge according to the energy gradient
	unsigned int moveSeedsOneEdgeCheck(); // returns the number of seeds that did move
	// move each seed along one edge according to the energy gradient + check that the energy decreases
	unsigned int moveSeedsToMedioid(); // returns the number of seeds that did move
	// move each seed to the medioid of its region
Sylvain Thery's avatar
Sylvain Thery committed
112
	REAL getGlobalEnergy() { return REAL(globalEnergy); }
113

114 115 116
protected :
	void clear();
	void collectVertexFromFront(Dart e);
Basile Sauvage's avatar
Basile Sauvage committed
117
	REAL cumulateEnergyFromRoot(Dart e);
Basile Sauvage's avatar
Basile Sauvage committed
118 119 120
	void cumulateEnergyAndGradientFromSeed(unsigned int numSeed);
	Dart selectBestNeighborFromSeed(unsigned int numSeed);
//	unsigned int moveSeed(unsigned int numSeed);
121 122
};

Pierre Kraemer's avatar
Pierre Kraemer committed
123 124 125 126
} // namespace Geometry
} // namespace Surface
} // namespace Algo
} // namespace CGoGN
127

Pierre Kraemer's avatar
Pierre Kraemer committed
128
#include "Algo/Geometry/voronoiDiagrams.hpp"
Basile Sauvage's avatar
Basile Sauvage committed
129 130

#endif