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

namespace Algo
{

Sylvain Thery's avatar
Sylvain Thery committed
7
8
9
namespace Surface
{

Basile Sauvage's avatar
Basile Sauvage committed
10
11
12
namespace Geometry
{

13
14
15
16
/***********************************************************
 * class VoronoiDiagram
 ***********************************************************/

Basile Sauvage's avatar
Basile Sauvage committed
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 ()
{
	regions.setAllValues(0);
	border.clear();
	front.clear();
	vmReached.unmarkAll();
}

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

template <typename PFP>
Basile Sauvage's avatar
Basile Sauvage committed
46
void VoronoiDiagram<PFP>::setSeeds_random (unsigned int nseeds)
Basile Sauvage's avatar
Basile Sauvage committed
47
{
Basile Sauvage's avatar
Basile Sauvage committed
48
	seeds.clear();
Basile Sauvage's avatar
Basile Sauvage committed
49
	srand ( time(NULL) );
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
	const unsigned int nbv = map.getNbCells(VERTEX);

	std::set<unsigned int> myVertices ;;
	while (myVertices.size() < nseeds)
	{
		myVertices.insert(rand() % nbv);
	}

	std::set<unsigned int>::iterator it = myVertices.begin();
	unsigned int n = 0;
	TraversorV<typename PFP::MAP> tv (map);
	Dart dit = tv.begin();

	while (it != myVertices.end())
	{
		while(n<*it)
Basile Sauvage's avatar
Basile Sauvage committed
66
		{
67
68
			dit = tv.next();
			++n;
Basile Sauvage's avatar
Basile Sauvage committed
69
		}
70
71
72
73
74
75
76
77
78
79
80
		seeds.push_back(dit);
		it++;
	}

	// random permutation = un-sort the seeds
	for (unsigned int i=0; i<nseeds; i++)
	{
		unsigned int j = i + rand() % (nseeds - i);
		Dart d = seeds[i];
		seeds[i] = seeds[j];
		seeds[j] = d;
Basile Sauvage's avatar
Basile Sauvage committed
81
82
83
84
85
86
	}
}

template <typename PFP>
void VoronoiDiagram<PFP>::initFrontWithSeeds ()
{
Basile Sauvage's avatar
Basile Sauvage committed
87
88
//	vmReached.unmarkAll();
	clear();
Basile Sauvage's avatar
Basile Sauvage committed
89
90
91
92
93
94
	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;
95
96
		regions[d] = i;
		vertexInfo[d].pathOrigin = d;
Basile Sauvage's avatar
Basile Sauvage committed
97
98
99
100
101
102
103
104
	}
}

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

105
106
107
template <typename PFP>
void VoronoiDiagram<PFP>::collectVertexFromFront(Dart e){
	regions[e] = regions[vertexInfo[e].pathOrigin];
108
109
	front.erase(vertexInfo[e].it);
	vertexInfo[e].valid=false;
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
}

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
132
133

template <typename PFP>
Basile Sauvage's avatar
Basile Sauvage committed
134
Dart VoronoiDiagram<PFP>::computeDiagram ()
Basile Sauvage's avatar
Basile Sauvage committed
135
136
137
{
	initFrontWithSeeds();

Basile Sauvage's avatar
Basile Sauvage committed
138
	Dart e;
Basile Sauvage's avatar
Basile Sauvage committed
139
140
	while ( !front.empty() )
	{
Basile Sauvage's avatar
Basile Sauvage committed
141
		e = front.begin()->second;
Basile Sauvage's avatar
Basile Sauvage committed
142
		float d = front.begin()->first;
143
144

		collectVertexFromFront(e);
Basile Sauvage's avatar
Basile Sauvage committed
145
146
147
148
149

		Traversor2VVaE<typename PFP::MAP> tv (map, e);
		for (Dart f = tv.begin(); f != tv.end(); f=tv.next())
		{
			if (vmReached.isMarked(f))
150
151
152
153
154
			{ // 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
155
156
			}
			else
157
158
			{ // f has not been reached : add it to the front
				addVertexToFront(f,d);
Basile Sauvage's avatar
Basile Sauvage committed
159
160
161
			}
		}
	}
Basile Sauvage's avatar
Basile Sauvage committed
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
	return e;
}

template <typename PFP>
void VoronoiDiagram<PFP>::computeDiagram_incremental (unsigned int nseeds)
{
	seeds.clear();

	// first seed
	srand ( time(NULL) );
	unsigned int s = rand() % map.getNbCells(VERTEX);
	unsigned int n = 0;
	TraversorV<typename PFP::MAP> tv (map);
	Dart dit = tv.begin();
	while(n<s)
	{
		dit = tv.next();
		++n;
	}
	seeds.push_back(dit);

	// add other seeds one by one
	Dart e = computeDiagram();

	for(unsigned int i = 1; i< nseeds ; i++)
	{
		seeds.push_back(e);
		e = computeDiagram();
	}
Basile Sauvage's avatar
Basile Sauvage committed
191
192
}

193
194
template <typename PFP>
void VoronoiDiagram<PFP>::computeDistancesWithinRegion (Dart seed)
Basile Sauvage's avatar
Basile Sauvage committed
195
{
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
	// init
	front.clear();
	vmReached.unmarkAll();

	vmReached.mark(seed);
	vertexInfo[seed].it = front.insert(std::pair<float,Dart>(0.0, seed));
	vertexInfo[seed].valid = true;
	vertexInfo[seed].pathOrigin = seed;

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

		collectVertexFromFront(e);

		Traversor2VVaE<typename PFP::MAP> tv (map, e);
		for (Dart f = tv.begin(); f != tv.end(); f=tv.next())
		{
			if (vmReached.isMarked(f))
			{ // f has been reached
				if (vertexInfo[f].valid) updateVertexInFront(f,d); // f is in the front : update
			}
			else
			{ // f has not been reached : add it to the front
				if ( regions[f] == regions[e] ) addVertexToFront(f,d);
			}
		}
	}
}

228
229
230
231
232
/***********************************************************
 * class CentroidalVoronoiDiagram
 ***********************************************************/

template <typename PFP>
Basile Sauvage's avatar
Basile Sauvage committed
233
234
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)
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
{
}

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){
252
	distances[e] = this->vertexInfo[e].it->first;
253
254
255
256
257
	pathOrigins[e] = this->vertexInfo[e].pathOrigin;

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

258

Basile Sauvage's avatar
Basile Sauvage committed
259
template <typename PFP>
Basile Sauvage's avatar
Basile Sauvage committed
260
261
262
263
264
265
266
267
void CentroidalVoronoiDiagram<PFP>::setSeeds_fromVector (const std::vector<Dart>& s)
{
	VoronoiDiagram<PFP>::setSeeds_fromVector (s);
	energyGrad.resize(this->seeds.size());
}

template <typename PFP>
void CentroidalVoronoiDiagram<PFP>::setSeeds_random (unsigned int nseeds)
Basile Sauvage's avatar
Basile Sauvage committed
268
{
Basile Sauvage's avatar
Basile Sauvage committed
269
	VoronoiDiagram<PFP>::setSeeds_random (nseeds);
Basile Sauvage's avatar
Basile Sauvage committed
270
271
	energyGrad.resize(this->seeds.size());
}
272

273
template <typename PFP>
Basile Sauvage's avatar
Basile Sauvage committed
274
void CentroidalVoronoiDiagram<PFP>::computeDiagram_incremental (unsigned int nseeds)
Basile Sauvage's avatar
Basile Sauvage committed
275
{
Basile Sauvage's avatar
Basile Sauvage committed
276
	VoronoiDiagram<PFP>::computeDiagram_incremental (nseeds);
Basile Sauvage's avatar
Basile Sauvage committed
277
278
279
280
281
282
	energyGrad.resize(this->seeds.size());
}


template <typename PFP>
void CentroidalVoronoiDiagram<PFP>::cumulateEnergy(){
Basile Sauvage's avatar
Basile Sauvage committed
283
	globalEnergy = 0.0;
284
285
	for (unsigned int i = 0; i < this->seeds.size(); i++)
	{
Basile Sauvage's avatar
Basile Sauvage committed
286
287
		cumulateEnergyFromRoot(this->seeds[i]);
		globalEnergy += distances[this->seeds[i]];
288
289
290
291
	}
}

template <typename PFP>
Basile Sauvage's avatar
Basile Sauvage committed
292
void CentroidalVoronoiDiagram<PFP>::cumulateEnergyAndGradients(){
Basile Sauvage's avatar
Basile Sauvage committed
293
	globalEnergy = 0.0;
Basile Sauvage's avatar
Basile Sauvage committed
294
	for (unsigned int i = 0; i < this->seeds.size(); i++)
Basile Sauvage's avatar
Basile Sauvage committed
295
296
297
298
299
300
301
302
303
304
	{
		cumulateEnergyAndGradientFromSeed(i);
		globalEnergy += distances[this->seeds[i]];
	}
}

template <typename PFP>
unsigned int CentroidalVoronoiDiagram<PFP>::moveSeedsOneEdgeNoCheck(){
	unsigned int m = 0;
	for (unsigned int i = 0; i < this->seeds.size(); i++)
Basile Sauvage's avatar
Basile Sauvage committed
305
	{
306
		Dart oldSeed = this->seeds[i];
Basile Sauvage's avatar
Basile Sauvage committed
307
308
309
310
311
312
313
314
		Dart newSeed = selectBestNeighborFromSeed(i);

		// move the seed
		if (newSeed != oldSeed)
		{
			this->seeds[i] = newSeed;
			m++;
		}
Basile Sauvage's avatar
Basile Sauvage committed
315
316
317
318
	}
	return m;
}

Basile Sauvage's avatar
Basile Sauvage committed
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
template <typename PFP>
unsigned int CentroidalVoronoiDiagram<PFP>::moveSeedsOneEdgeCheck(){
	unsigned int m = 0;
	for (unsigned int i = 0; i < this->seeds.size(); i++)
	{
		Dart oldSeed = this->seeds[i];
		Dart newSeed = selectBestNeighborFromSeed(i);

		// move the seed
		if (newSeed != oldSeed)
		{
			REAL regionEnergy = distances[oldSeed];
			this->seeds[i] = newSeed;
			this->computeDistancesWithinRegion(newSeed);
			cumulateEnergyAndGradientFromSeed(i);
			if (distances[newSeed] < regionEnergy)
				m++;
336
			else
Basile Sauvage's avatar
Basile Sauvage committed
337
				this->seeds[i] = oldSeed;
338
339
340
341
		}
	}
	return m;
}
Basile Sauvage's avatar
Basile Sauvage committed
342

Basile Sauvage's avatar
Basile Sauvage committed
343
344
345
template <typename PFP>
unsigned int CentroidalVoronoiDiagram<PFP>::moveSeedsToMedioid(){
	unsigned int m = 0;
Basile Sauvage's avatar
Basile Sauvage committed
346
	for (unsigned int i = 0; i < this->seeds.size(); i++)
Basile Sauvage's avatar
Basile Sauvage committed
347
	{
Basile Sauvage's avatar
Basile Sauvage committed
348
		Dart oldSeed, newSeed;
Basile Sauvage's avatar
Basile Sauvage committed
349
		unsigned int seedMoved = 0;
Basile Sauvage's avatar
Basile Sauvage committed
350
		REAL regionEnergy;
Basile Sauvage's avatar
Basile Sauvage committed
351

Basile Sauvage's avatar
Basile Sauvage committed
352
		do
Basile Sauvage's avatar
Basile Sauvage committed
353
		{
Basile Sauvage's avatar
Basile Sauvage committed
354
355
356
357
358
359
360
			oldSeed = this->seeds[i];
			regionEnergy = distances[oldSeed];

			newSeed = selectBestNeighborFromSeed(i);
			this->seeds[i] = newSeed;
			this->computeDistancesWithinRegion(newSeed);
			cumulateEnergyAndGradientFromSeed(i);
Basile Sauvage's avatar
Basile Sauvage committed
361
			if (distances[newSeed] < regionEnergy)
Basile Sauvage's avatar
Basile Sauvage committed
362
363
				seedMoved = 1;
			else
Basile Sauvage's avatar
Basile Sauvage committed
364
			{
Basile Sauvage's avatar
Basile Sauvage committed
365
366
				this->seeds[i] = oldSeed;
				newSeed = oldSeed;
Basile Sauvage's avatar
Basile Sauvage committed
367
			}
Basile Sauvage's avatar
Basile Sauvage committed
368
369
370
371
372

		} while (newSeed != oldSeed);

		m += seedMoved;
	}
Basile Sauvage's avatar
Basile Sauvage committed
373
374
	return m;
}
375

Basile Sauvage's avatar
Basile Sauvage committed
376
template <typename PFP>
Basile Sauvage's avatar
Basile Sauvage committed
377
378
379
typename PFP::REAL CentroidalVoronoiDiagram<PFP>::cumulateEnergyFromRoot(Dart e){
	REAL distArea = areaElts[e] * distances[e];
	distances[e] = areaElts[e] * distances[e] * distances[e];
Basile Sauvage's avatar
Basile Sauvage committed
380

381
382
383
384
385
	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
386
			distArea += cumulateEnergyFromRoot(f);
387
388
389
			distances[e] += distances[f];
		}
	}
Basile Sauvage's avatar
Basile Sauvage committed
390
	return distArea;
Basile Sauvage's avatar
Basile Sauvage committed
391
392
}

Basile Sauvage's avatar
Basile Sauvage committed
393
394
template <typename PFP>
void CentroidalVoronoiDiagram<PFP>::cumulateEnergyAndGradientFromSeed(unsigned int numSeed){
Basile Sauvage's avatar
Basile Sauvage committed
395
	// precondition : energyGrad.size() > numSeed
Basile Sauvage's avatar
Basile Sauvage committed
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
	Dart e = this->seeds[numSeed];

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

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

	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 distArea = cumulateEnergyFromRoot(f);
			da.push_back(distArea);
			distances[e] += distances[f];
			v.push_back(f);
		}
	}

	// compute the gradient
	// TODO : check if the computation of grad and proj is still valid for other edgeCost than geodesic distances
	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 = pos[f] - pos[this->map.phi2(f)];
		edgeV.normalize();
		grad += da[j] * edgeV;
	}
	grad /= 2.0;
	energyGrad[numSeed] = grad;
}


template <typename PFP>
Dart CentroidalVoronoiDiagram<PFP>::selectBestNeighborFromSeed(unsigned int numSeed)
{
	Dart e = this->seeds[numSeed];
	Dart newSeed = e;
	const VertexAttribute<VEC3>& pos = this->map.template getAttribute<VEC3,VERTEX>("position");

	// TODO : check if the computation of grad and proj is still valid for other edgeCost than geodesic distances
	float maxProj = 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))
		{
			VEC3 edgeV = pos[f] - pos[this->map.phi2(f)];
	//		edgeV.normalize();
			float proj = edgeV * energyGrad[numSeed];
			if (proj > maxProj)
			{
				maxProj = proj;
				newSeed = f;
			}
		}
	}
	return newSeed;
}

/*
template <typename PFP>
unsigned int CentroidalVoronoiDiagram<PFP>::moveSeed(unsigned int numSeed){

	// collect energy and compute the gradient
//	cumulateEnergyAndGradientFromSeed(numSeed);

	// select the new seed
	Dart newSeed = selectBestNeighborFromSeed(numSeed);

	// move the seed
	Dart oldSeed = this->seeds[numSeed];
	unsigned int seedMoved = 0;
	if (newSeed != oldSeed)
	{
		this->seeds[numSeed] = newSeed;
		seedMoved = 1;
	}

	return seedMoved;
}
*/

/*
Basile Sauvage's avatar
Basile Sauvage committed
486
template <typename PFP>
Basile Sauvage's avatar
Basile Sauvage committed
487
488
489
unsigned int CentroidalVoronoiDiagram<PFP>::moveSeed(unsigned int numSeed){
	Dart e = this->seeds[numSeed];
	unsigned int seedMoved = 0;
Basile Sauvage's avatar
Basile Sauvage committed
490
491
492
493

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

Basile Sauvage's avatar
Basile Sauvage committed
494
495
	std::vector<float> da;
	da.reserve(8);
Basile Sauvage's avatar
Basile Sauvage committed
496
497
498
499
500
501
502
503

	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))
		{
Basile Sauvage's avatar
Basile Sauvage committed
504
505
			float distArea = cumulateEnergyFromRoot(f);
			da.push_back(distArea);
Basile Sauvage's avatar
Basile Sauvage committed
506
507
508
509
510
			distances[e] += distances[f];
			v.push_back(f);
		}
	}

Basile Sauvage's avatar
Basile Sauvage committed
511
	// TODO : check if the computation of grad and proj is still valid for other edgeCost than geodesic distances
Basile Sauvage's avatar
Basile Sauvage committed
512
513
514
	VEC3 grad (0.0);
	const VertexAttribute<VEC3>& pos = this->map.template getAttribute<VEC3,VERTEX>("position");

Basile Sauvage's avatar
Basile Sauvage committed
515
	// compute the gradient
Basile Sauvage's avatar
Basile Sauvage committed
516
517
518
519
520
	for (unsigned int j = 0; j<v.size(); ++j)
	{
		Dart f = v[j];
		VEC3 edgeV = pos[f] - pos[this->map.phi2(f)];
		edgeV.normalize();
Basile Sauvage's avatar
Basile Sauvage committed
521
		grad += da[j] * edgeV;
Basile Sauvage's avatar
Basile Sauvage committed
522
	}
Basile Sauvage's avatar
Basile Sauvage committed
523
	grad /= 2.0;
Basile Sauvage's avatar
Basile Sauvage committed
524
525

	float maxProj = 0.0;
Basile Sauvage's avatar
Basile Sauvage committed
526
//	float memoForTest = 0.0;
Basile Sauvage's avatar
Basile Sauvage committed
527
528
529
530
531
532
	for (unsigned int j = 0; j<v.size(); ++j)
	{
		Dart f = v[j];
		VEC3 edgeV = pos[f] - pos[this->map.phi2(f)];
//		edgeV.normalize();
		float proj = edgeV * grad;
Basile Sauvage's avatar
Basile Sauvage committed
533
//		proj -= areaElts[e] * this->edgeCost[f] * this->edgeCost[f];
Basile Sauvage's avatar
Basile Sauvage committed
534
535
		if (proj > maxProj)
		{
Basile Sauvage's avatar
Basile Sauvage committed
536
537
//			if (numSeed==1) memoForTest = (edgeV * grad) / (areaElts[e] * this->edgeCost[f] * this->edgeCost[f]);
//				CGoGNout << (edgeV * grad) / (areaElts[e] * this->edgeCost[f] * this->edgeCost[f]) * this->seeds.size() << CGoGNendl;
Basile Sauvage's avatar
Basile Sauvage committed
538
//				CGoGNout << edgeV * grad << "\t - \t" << areaElts[e] * this->edgeCost[f] * this->edgeCost[f] << CGoGNendl;
Basile Sauvage's avatar
Basile Sauvage committed
539
540
541
542
543
			maxProj = proj;
			seedMoved = 1;
			this->seeds[numSeed] = v[j];
		}
	}
Basile Sauvage's avatar
Basile Sauvage committed
544

Basile Sauvage's avatar
Basile Sauvage committed
545
	return seedMoved;
546
}
Basile Sauvage's avatar
Basile Sauvage committed
547
*/
Basile Sauvage's avatar
Basile Sauvage committed
548
}// end namespace Geometry
Sylvain Thery's avatar
Sylvain Thery committed
549
} // Surface
Basile Sauvage's avatar
Basile Sauvage committed
550
551
}// end namespace Algo
}// end namespace CGoGN