voronoiDiagrams.h 3.5 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"
Basile Sauvage's avatar
Basile Sauvage committed
9 10 11 12 13 14 15 16
#include "Topology/generic/traversor2.h"

namespace CGoGN
{

namespace Algo
{

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


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

template <typename PFP>
class VoronoiDiagram {
26
protected :
Basile Sauvage's avatar
Basile Sauvage committed
27 28 29 30 31 32
	typedef typename PFP::REAL REAL;

	typedef struct
	{
		typename std::multimap<float,Dart>::iterator it ;
		bool valid ;
33 34
//		unsigned int region;
		Dart pathOrigin;
Basile Sauvage's avatar
Basile Sauvage committed
35 36
		static std::string CGoGNnameOfType() { return "VoronoiVertexInfo" ; }
	} VoronoiVertexInfo ;
37
	typedef NoTypeNameAttribute<VoronoiVertexInfo> VertexInfo ;
Basile Sauvage's avatar
Basile Sauvage committed
38 39 40 41 42 43 44 45 46

	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 ;
Basile Sauvage's avatar
Basile Sauvage committed
47
	CellMarker<VERTEX> vmReached;
Basile Sauvage's avatar
Basile Sauvage committed
48 49 50 51 52 53

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

	const std::vector<Dart>& getSeeds (){return seeds;}
Basile Sauvage's avatar
Basile Sauvage committed
54 55
	virtual void setSeeds_fromVector (const std::vector<Dart>&);
	virtual void setSeeds_random (unsigned int nbseeds);
Basile Sauvage's avatar
Basile Sauvage committed
56 57 58
	const std::vector<Dart>& getBorder (){return border;}
	void setCost (const EdgeAttribute<REAL>& c);

Basile Sauvage's avatar
Basile Sauvage committed
59 60
	Dart computeDiagram ();
	virtual void computeDiagram_incremental (unsigned int nbseeds);
61
	void computeDistancesWithinRegion (Dart seed);
Basile Sauvage's avatar
Basile Sauvage committed
62

63
protected :
64
	virtual void clear ();
Basile Sauvage's avatar
Basile Sauvage committed
65
	void initFrontWithSeeds();
66
	virtual void collectVertexFromFront(Dart e);
67 68
	void addVertexToFront(Dart f, float d);
	void updateVertexInFront(Dart f, float d);
Basile Sauvage's avatar
Basile Sauvage committed
69 70
};

71 72 73 74 75

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

Basile Sauvage's avatar
Basile Sauvage committed
78
	double globalEnergy;
Basile Sauvage's avatar
Basile Sauvage committed
79
	std::vector<VEC3> energyGrad; // gradient of the region energy at seed
Basile Sauvage's avatar
Basile Sauvage committed
80

81 82
	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
83
	VertexAttribute<REAL>& areaElts; // area element attached to each vertex
84 85

public :
Basile Sauvage's avatar
Basile Sauvage committed
86 87 88 89 90 91
	CentroidalVoronoiDiagram (typename PFP::MAP& m,
			const EdgeAttribute<REAL>& c,
			VertexAttribute<unsigned int>& r,
			VertexAttribute<REAL>& d,
			VertexAttribute<Dart>& o,
			VertexAttribute<REAL>& a);
92 93
	~CentroidalVoronoiDiagram ();

Basile Sauvage's avatar
Basile Sauvage committed
94 95 96
	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
97 98 99 100 101 102 103 104
	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
Basile Sauvage's avatar
Basile Sauvage committed
105
	REAL getGlobalEnergy() {return globalEnergy;}
106

107 108 109
protected :
	void clear();
	void collectVertexFromFront(Dart e);
Basile Sauvage's avatar
Basile Sauvage committed
110
	REAL cumulateEnergyFromRoot(Dart e);
Basile Sauvage's avatar
Basile Sauvage committed
111 112 113
	void cumulateEnergyAndGradientFromSeed(unsigned int numSeed);
	Dart selectBestNeighborFromSeed(unsigned int numSeed);
//	unsigned int moveSeed(unsigned int numSeed);
114 115 116
};


Basile Sauvage's avatar
Basile Sauvage committed
117
}// end namespace Geometry
Sylvain Thery's avatar
Sylvain Thery committed
118
}// end namespace Surface
Basile Sauvage's avatar
Basile Sauvage committed
119 120 121 122 123 124
}// end namespace Algo
}// end namespace CGoGN

#include "voronoiDiagrams.hpp"

#endif