voronoiDiagrams.hpp 7 KB
Newer Older
Basile Sauvage's avatar
Basile Sauvage committed
1
2
3
4
5
6
7
8
9
namespace CGoGN
{

namespace Algo
{

namespace Geometry
{

10
11
12
13
/***********************************************************
 * class VoronoiDiagram
 ***********************************************************/

Basile Sauvage's avatar
Basile Sauvage committed
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
template <typename PFP>
VoronoiDiagram<PFP>::VoronoiDiagram (typename PFP::MAP& m, const EdgeAttribute<REAL>& p, VertexAttribute<unsigned int>& r) : map(m), edgeCost (p), regions (r), vmReached(m)
{
	vertexInfo = map.template addAttribute<VertexInfo, VERTEX>("vertexInfo");
}

template <typename PFP>
VoronoiDiagram<PFP>::~VoronoiDiagram ()
{
	map.removeAttribute(vertexInfo);
}

template <typename PFP>
void VoronoiDiagram<PFP>::clear ()
{
	border.clear();
	regions.setAllValues(0);
	border.clear();
	front.clear();
	vmReached.unmarkAll();
}

template <typename PFP>
void VoronoiDiagram<PFP>::setSeeds (const std::vector<Dart>& s)
{
Basile Sauvage's avatar
Basile Sauvage committed
39
40
	seeds.clear();
//	clear();
Basile Sauvage's avatar
Basile Sauvage committed
41
42
43
44
45
46
	seeds = s;
}

template <typename PFP>
void VoronoiDiagram<PFP>::setRandomSeeds (unsigned int nseeds)
{
Basile Sauvage's avatar
Basile Sauvage committed
47
48
49
	seeds.clear();
//	clear();
	vmReached.unmarkAll();
Basile Sauvage's avatar
Basile Sauvage committed
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

	srand ( time(NULL) );
	unsigned int n = nseeds;
	while (n > 0)
	{ // TODO : correct this random init which assumes contiguous Dart table
		Dart d = rand() % map.getNbDarts() ;
		if (! vmReached.isMarked(d))
		{
			vmReached.mark(d);
			seeds.push_back(d);
			n--;
		}
	}
}

template <typename PFP>
void VoronoiDiagram<PFP>::initFrontWithSeeds ()
{
Basile Sauvage's avatar
Basile Sauvage committed
68
69
//	vmReached.unmarkAll();
	clear();
Basile Sauvage's avatar
Basile Sauvage committed
70
71
72
73
74
75
	for (unsigned int i = 0; i < seeds.size(); i++)
	{
		Dart d = seeds[i];
		vmReached.mark(d);
		vertexInfo[d].it = front.insert(std::pair<float,Dart>(0.0, d));
		vertexInfo[d].valid = true;
76
77
		regions[d] = i;
		vertexInfo[d].pathOrigin = d;
Basile Sauvage's avatar
Basile Sauvage committed
78
79
80
81
82
83
84
85
	}
}

template <typename PFP>
void VoronoiDiagram<PFP>::setCost (const EdgeAttribute<typename PFP::REAL>& c){
	edgeCost = c;
}

86
87
88
template <typename PFP>
void VoronoiDiagram<PFP>::collectVertexFromFront(Dart e){
	regions[e] = regions[vertexInfo[e].pathOrigin];
89
90
	front.erase(vertexInfo[e].it);
	vertexInfo[e].valid=false;
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
}

template <typename PFP>
void VoronoiDiagram<PFP>::addVertexToFront(Dart f, float d){
	VertexInfo& vi (vertexInfo[f]);
	vi.it = front.insert(std::pair<float,Dart>(d + edgeCost[f], f));
	vi.valid=true;
	vi.pathOrigin = map.phi2(f);
	vmReached.mark(f);
}

template <typename PFP>
void VoronoiDiagram<PFP>::updateVertexInFront(Dart f, float d){
	VertexInfo& vi (vertexInfo[f]);
	float dist = d + edgeCost[f];
	if (dist < vi.it->first)
	{
		front.erase(vi.it);
		vi.it = front.insert(std::pair<float,Dart>(dist, f));
		vi.pathOrigin = map.phi2(f);
	}
}
Basile Sauvage's avatar
Basile Sauvage committed
113
114
115
116
117
118
119
120
121
122

template <typename PFP>
void VoronoiDiagram<PFP>::computeDiagram ()
{
	initFrontWithSeeds();

	while ( !front.empty() )
	{
		Dart e = front.begin()->second;
		float d = front.begin()->first;
123
124

		collectVertexFromFront(e);
Basile Sauvage's avatar
Basile Sauvage committed
125
126
127
128
129

		Traversor2VVaE<typename PFP::MAP> tv (map, e);
		for (Dart f = tv.begin(); f != tv.end(); f=tv.next())
		{
			if (vmReached.isMarked(f))
130
131
132
133
134
			{ // f has been reached
				if (vertexInfo[f].valid) // f is in the front : update
					updateVertexInFront(f,d);
				else // f is not in the front any more (already collected) : detect a border edge
					if ( regions[f] != regions[e] ) border.push_back(f);
Basile Sauvage's avatar
Basile Sauvage committed
135
136
			}
			else
137
138
			{ // f has not been reached : add it to the front
				addVertexToFront(f,d);
Basile Sauvage's avatar
Basile Sauvage committed
139
140
141
142
143
			}
		}
	}
}

144
145
146
147
148
/***********************************************************
 * class CentroidalVoronoiDiagram
 ***********************************************************/

template <typename PFP>
Basile Sauvage's avatar
Basile Sauvage committed
149
150
CentroidalVoronoiDiagram<PFP>::CentroidalVoronoiDiagram (typename PFP::MAP& m, const EdgeAttribute<REAL>& c, VertexAttribute<unsigned int>& r, VertexAttribute<REAL>& d, VertexAttribute<Dart>& o, VertexAttribute<REAL>& a) :
	VoronoiDiagram<PFP>(m,c,r), distances(d), pathOrigins(o), areaElts(a)
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
{
}

template <typename PFP>
CentroidalVoronoiDiagram<PFP>::~CentroidalVoronoiDiagram ()
{
}

template <typename PFP>
void CentroidalVoronoiDiagram<PFP>::clear ()
{
	VoronoiDiagram<PFP>::clear();
	distances.setAllValues(0.0);
}

template <typename PFP>
void CentroidalVoronoiDiagram<PFP>::collectVertexFromFront(Dart e){
168
	distances[e] = this->vertexInfo[e].it->first;
169
170
171
172
173
	pathOrigins[e] = this->vertexInfo[e].pathOrigin;

	VoronoiDiagram<PFP>::collectVertexFromFront(e);
}

174
175
176
177
template <typename PFP>
void CentroidalVoronoiDiagram<PFP>::cumulateDistancesOnPaths(){
	for (unsigned int i = 0; i < this->seeds.size(); i++)
	{
Basile Sauvage's avatar
Basile Sauvage committed
178
		cumulateDistancesFromRoot(this->seeds[i]);
179
180
181
182
	}
}

template <typename PFP>
Basile Sauvage's avatar
Basile Sauvage committed
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
unsigned int CentroidalVoronoiDiagram<PFP>::moveSeeds(){
	unsigned int m = 0;
	for (unsigned int i = 0; i < this->seeds.size(); i++)
	{
		m += moveSeed(i);
	}
	return m;
}


template <typename PFP>
typename PFP::REAL CentroidalVoronoiDiagram<PFP>::cumulateDistancesFromRoot(Dart e){
	REAL area = areaElts[e];
	distances[e] *= areaElts[e];

198
199
200
201
202
	Traversor2VVaE<typename PFP::MAP> tv (this->map, e);
	for (Dart f = tv.begin(); f != tv.end(); f=tv.next())
	{
		if ( pathOrigins[f] == this->map.phi2(f))
		{
Basile Sauvage's avatar
Basile Sauvage committed
203
			area += cumulateDistancesFromRoot(f);
204
205
206
			distances[e] += distances[f];
		}
	}
Basile Sauvage's avatar
Basile Sauvage committed
207
208
209
210
	return area;
}

template <typename PFP>
Basile Sauvage's avatar
Basile Sauvage committed
211
212
213
unsigned int CentroidalVoronoiDiagram<PFP>::moveSeed(unsigned int numSeed){
	Dart e = this->seeds[numSeed];
	unsigned int seedMoved = 0;
Basile Sauvage's avatar
Basile Sauvage committed
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236

	std::vector<Dart> v;
	v.reserve(8);

	std::vector<float> a;
	a.reserve(8);

	float regionArea = areaElts[e];
	distances[e] = 0.0;

	Traversor2VVaE<typename PFP::MAP> tv (this->map, e);
	for (Dart f = tv.begin(); f != tv.end(); f=tv.next())
	{
		if ( pathOrigins[f] == this->map.phi2(f))
		{
			float area = cumulateDistancesFromRoot(f);
			distances[e] += distances[f];
			v.push_back(f);
			a.push_back(area);
			regionArea += area;
		}
	}

Basile Sauvage's avatar
Basile Sauvage committed
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
	/* second attempt */
	VEC3 grad (0.0);
	const VertexAttribute<VEC3>& pos = this->map.template getAttribute<VEC3,VERTEX>("position");

	for (unsigned int j = 0; j<v.size(); ++j)
	{
		Dart f = v[j];
//		VEC3 edgeV = Algo::Geometry::vectorOutOfDart<PFP>(this->map,this->map.phi2(f),pos);
		VEC3 edgeV = pos[f] - pos[this->map.phi2(f)];
		edgeV.normalize();
		grad += distances[f] * edgeV;
	}

	float maxProj = 0.0;
	for (unsigned int j = 0; j<v.size(); ++j)
	{
		Dart f = v[j];
//		VEC3 edgeV = Algo::Geometry::vectorOutOfDart<PFP>(this->map,this->map.phi2(f),pos);
		VEC3 edgeV = pos[f] - pos[this->map.phi2(f)];
//		edgeV.normalize();
		float proj = edgeV * grad;
		proj -= areaElts[e] * this->edgeCost[f] * this->edgeCost[f];
		if (proj > maxProj)
		{
Basile Sauvage's avatar
Basile Sauvage committed
261
262
263
			if (numSeed==1 && j==0)
				CGoGNout << (edgeV * grad) / (areaElts[e] * this->edgeCost[f] * this->edgeCost[f]) * this->seeds.size() << CGoGNendl;
//				CGoGNout << edgeV * grad << "\t - \t" << areaElts[e] * this->edgeCost[f] * this->edgeCost[f] << CGoGNendl;
Basile Sauvage's avatar
Basile Sauvage committed
264
265
266
267
268
269
270
271
			maxProj = proj;
			seedMoved = 1;
			this->seeds[numSeed] = v[j];
		}
	}
	/* end second attempt */

/* first attempt by approximating the energy change
Basile Sauvage's avatar
Basile Sauvage committed
272
273
274
275
276
277
278
279
280
	float minDE = 0.0;
	for (unsigned int j = 0; j<v.size(); ++j)
	{
		float c = this->edgeCost[v[j]];
		float de = regionArea * c * c;
		de += 2 * c *( distances[e] - 2*distances[v[j]] );
		if (de < minDE)
		{
			minDE = de;
Basile Sauvage's avatar
Basile Sauvage committed
281
282
			seedMoved = 1;
			this->seeds[numSeed] = v[j];
Basile Sauvage's avatar
Basile Sauvage committed
283
284
		}
	}
Basile Sauvage's avatar
Basile Sauvage committed
285
286
*/
	return seedMoved;
287
}
288

Basile Sauvage's avatar
Basile Sauvage committed
289
290
291
}// end namespace Geometry
}// end namespace Algo
}// end namespace CGoGN