1
2
3
4
5
6
7
8
9
10
11
12
13
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
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
191
192
193
194
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
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
|
#include "ff++.hpp"
// #ifndef WITH_NO_INIT
// #include "ff++.hpp"
// #include "AFunction_ext.hpp"
// #endif
// using namespace std;
#include <set>
#include <vector>
#include <map>
#include <algorithm>
//#include "msh3.hpp"
// #include <iostream>
using namespace Fem2D;
// FreeFem glue
class WATERSHED_P1_Op : public E_F0mps
{
public:
Expression eTh,eff,eret;
static const int n_name_param = 1;
static basicAC_F0::name_and_type name_param[n_name_param];
Expression nargs[n_name_param];
public:
WATERSHED_P1_Op(const basicAC_F0 & args,Expression tth, Expression fff,Expression rrr)
: eTh(tth),eff(fff),eret(rrr)
{
args.SetNameParam(n_name_param,name_param,nargs);
}
AnyType operator()(Stack stack) const;
private:
template<typename T>
T arg(int i, Stack stack, T a) const {
return nargs[i]
? GetAny< T >( (*nargs[i])(stack) )
: a;
}
};
basicAC_F0::name_and_type WATERSHED_P1_Op::name_param[]= {
{ "eps", &typeid(double)}
};
// algorithm
typedef int triangle_t;
typedef int vertex_t;
typedef int color_t;
struct fat_vertex_t {
vertex_t vertex;
triangle_t triangle;
int edge;
fat_vertex_t(vertex_t v, triangle_t t, int e)
: vertex(v), triangle(t), edge(e) {}
friend bool operator<(fat_vertex_t const& a, fat_vertex_t const& b)
{ return a.vertex < b.vertex; }
friend bool operator==(fat_vertex_t const& a, fat_vertex_t const& b)
{ return a.vertex == b.vertex; }
};
typedef std::vector<fat_vertex_t> vertices_t;
typedef std::pair<fat_vertex_t, double> ver_val_t;
struct cmp_t {
bool operator()(ver_val_t const& t1, ver_val_t const& t2) const {
return t1.second < t2.second;
}
};
typedef std::priority_queue<ver_val_t, std::vector<ver_val_t>, cmp_t> queue_t;
typedef KNM<long> ret_type;
template<typename Func>
void for_each_triangle(Mesh const& Th, triangle_t const triangle0, int const edge0, Func func) {
int const vertex = Th(triangle0, edge0);
if( !func( triangle0 ) )
return;
int edge = edge0;
int triangle = triangle0;
for(;;) {
edge = (edge + 1) % 3;
if( Th(triangle, edge) == vertex )
edge = (edge + 1) % 3;
triangle = Th.ElementAdj( triangle, edge );
if( triangle == triangle0 )
return;
if( triangle < 0 )
break;
if( !func( triangle ) )
return;
}
triangle = triangle0;
edge = edge0;
for(;;) {
edge = (edge - 1) % 3;
if( Th(triangle, edge) == vertex )
edge = (edge - 1) % 3;
triangle = Th.ElementAdj( triangle, edge );
if( triangle == triangle0 )
return;
if( triangle < 0 )
break;
if( !func( triangle ) )
return;
}
}
template<typename Func>
struct for_each_neighbor_helper {
Func func;
Mesh const& Th;
bool operator()(triangle_t triangle) {
for(int e = 0; e < 3; ++e)
if(! func( Th(triangle, e), triangle, e ) )
return false;
return true;
}
};
template<typename Func>
void for_each_neighbor(Mesh const& Th, triangle_t const triangle0, int const edge0, Func func) {
for_each_neighbor_helper<Func> help = { func, Th };
// check adjacent triangles
for_each_triangle(Th, triangle0, edge0, help);
}
template<typename Cont>
void erase_unique(Cont& cont) {
std::sort(cont.begin(), cont.end());
cont.erase(
std::unique(cont.begin(), cont.end()),
cont.end()
);
}
struct maxima_helper {
KN<double> const& tff;
double& maxval;
bool& is_max;
bool operator()(vertex_t vertex, triangle_t triangle, int edge) const {
double val = tff[ vertex ];
if(val > maxval) {
is_max = false;
return false;
}
return true;
}
};
static void maxima(Mesh const& Th, KN<double> const& tff, vertices_t& vertices, double epsr)
{
const int nbt=Th.nt; // nombre de triangles
// loop over vertices
for(int it = 0; it < nbt; ++it) {
int maxiv = 0;
double maxval = tff[ Th(it,0) ];
int iv;
for(iv=1; iv < 3; ++iv) {
int i = Th(it,iv);
double val = tff[i];
if(val > maxval) {
maxiv = iv;
maxval = val;
}
}
iv = maxiv;
if(std::abs(maxval) < epsr)
continue;
bool is_max = true;
maxima_helper helper = { tff, maxval, is_max };
for_each_neighbor(Th, it, iv, helper);
if(!is_max)
continue;
// std::cout << "FOUND " << it << ' ' << maxiv << ' ' << Th(it, maxiv) << ' ' << maxval << std::endl;
vertices.push_back(fat_vertex_t( Th(it,maxiv), it, maxiv ));
}
erase_unique(vertices);
}
#if 0
static void maxima(Mesh const& Th, KN<double> const& tff, queue_t& roots, std::vector<color_t>& colors, double epsr)
{
const int nbt=Th.nt; // nombre de triangles
const int nbv=Th.nv; // nombre de vertices
enum pixel_type {
MAXIMUM,
PLATEAU,
NON_MAXIMUM
};
// the one that increments current_color
// shall push to roots
color_t current_color = 1;
std::vector<bool> visited ( nbv, false );
auto analyse_neighbors = [&](vertex_t const vertex0, triangle_t const triangle0, int edge0) {
pixel_type pxl = MAXIMUM;
for_each_neighbor(Th, triangle0, edge0,
[&](vertex_t vertex, triangle_t triangle, int edge) {
if( vertex == vertex0 )
return true;
if( tff[vertex] > tff[vertex0] ) {
pxl = NON_MAXIMUM;
return false;
}
if( tff[vertex] == tff[vertex0] )
pxl = PLATEAU;
return true;
});
return pxl;
};
auto analyse_plateau = [&](vertex_t const vertex0, triangle_t const triangle0, int edge0) {
colors[vertex0] = current_color;
// early exit
color_t new_label = current_color;
// do not forget marked nodes
std::deque<fat_vertex_t> queue;
queue.push_back({ vertex0, triangle0, edge0 });
auto it = queue.begin();
auto const end = queue.end();
for(; it != end; ++it ) {
fat_vertex_t const& vv = *it;
for_each_neighbor(Th, vv.triangle, vv.edge,
[&](vertex_t vertex, triangle_t triangle, int edge) {
if( colors[vertex] == -1 && tff[vertex] == tff[vertex0] ) {
colors[vertex] = current_color;
queue.push_back({ vertex, triangle, edge });
visited[vertex] = true;
}
else if( tff[vertex] > tff[vertex0] )
new_label = -1;
return true;
});
}
if( new_label == -1 )
for(fat_vertex_t const& vv : queue)
colors[vv.vertex] = -1;
else {
++current_color;
roots.push({ { vertex0, triangle0, edge0 }, tff[vertex0] });
}
};
// loop over vertices
for(triangle_t triangle = 0; triangle < nbt; ++triangle)
for(int edge = 0; edge < 3; ++edge) {
vertex_t vertex = Th( triangle, edge );
if( visited[vertex] )
continue;
pixel_type pxl = analyse_neighbors(vertex, triangle, edge);
if( pxl == MAXIMUM ) {
for_each_neighbor(Th, triangle, edge,
[&](vertex_t vertex2, int,int) {
ffassert( tff[vertex2] <= tff[vertex] );
return true;
});
colors[vertex] = current_color++;
roots.push({{ vertex, triangle, edge }, tff[vertex] });
}
// else if( pxl == PLATEAU )
// analyse_plateau(vertex, triangle, edge);
visited[vertex] = true;
}
ffassert( roots.size() == current_color-1 );
}
#endif
struct color_one_neighbor {
KN<double> const& tff;
fat_vertex_t const& current;
std::vector<color_t>& colors;
color_t const current_color;
queue_t& queue;
bool operator()(vertex_t vertex, triangle_t triangle, int edge) {
fat_vertex_t vv ( vertex, triangle, edge );
if(vertex == current.vertex)
return true;
color_t& color = colors[vertex];
if( color == -1 ) {
color = current_color;
queue.push(ver_val_t( vv, tff[vertex] ));
}
else if( color != current_color ) {
color = 0;
frontier.push_back( vv );
// ffassert( tff[vertex] <= tff[current.vertex] ); // TODO ça explose ici
// std::cout << "FOUND " << vertex << " -> " << color << std::endl;
}
return true;
}
};
AnyType WATERSHED_P1_Op::operator()(Stack stack) const
{
MeshPoint *mp(MeshPointStack(stack));
ret_type& ret = *GetAny<ret_type* >( (*eret)(stack) );
Mesh* pTh = GetAny<Mesh *>( (*eTh)(stack) );
ffassert(pTh);
double epsr = arg(0,stack,1e-5);
Mesh const& Th = *pTh;
const int nbv=Th.nv; // nombre de sommet
const int nbt=Th.nt; // nombre de triangles
const int nbe=Th.neb; // nombre d'aretes fontiere
const double unset = -1e-100;
KN<double> tff(nbv, unset);
// loop over triangle
for(int it=0; it < nbt; ++it) {
for(int iv=0; iv<3; ++iv) {
int i = Th(it,iv);
if(tff[i]==unset) {
mp->setP(pTh,it,iv);
tff[i]=GetAny<double>((*eff)(stack));
}
}
}
queue_t queue;
std::vector<color_t> colors ( nbv, -1 );
vertices_t frontier;
// prefill
{
vertices_t roots;
maxima(Th, tff, roots, epsr);
color_t color = 1;
vertices_t::iterator it = roots.begin(), en = roots.end();
for(; it != en; ++it) {
fat_vertex_t const& current = *it;
colors[current.vertex] = color++;
queue.push(ver_val_t( current, tff[current.vertex] ));
}
}
// loop
while( !queue.empty() ) {
fat_vertex_t const current = queue.top().first; queue.pop();
color_t const current_color = colors[current.vertex];
ffassert( current_color != -1 );
if( current_color == 0 )
continue;
// check adjacent triangles
for_each_neighbor(
Th, current.triangle, current.edge,
color_one_neighbor(tff, current, colors, current_color, queue)
);
}
erase_unique(frontier);
std::cout << "OUT " << frontier.size() << std::endl;
ret.resize(2, frontier.size());
for(int k = 0; k < frontier.size(); ++k) {
fat_vertex_t const& vv = frontier[k];
ret(0, k) = vv.triangle;
ret(1, k) = vv.edge;
}
return 0l;
}
class WATERSHED_P1: public OneOperator { public:
typedef Mesh *pmesh;
typedef std::pair<FEbase<double, v_fes>*, int> fem_t;
WATERSHED_P1() : OneOperator(atype<long>(),atype<pmesh>(),atype<double>(), atype<ret_type*>() ) {}
E_F0 * code(const basicAC_F0 & args) const
{
return new WATERSHED_P1_Op( args,
t[0]->CastTo(args[0]),
t[1]->CastTo(args[1]),
t[2]->CastTo(args[2]) );
}
};
void finit()
{
Global.Add("watershed","(",new WATERSHED_P1);
}
LOADFUNC(finit); |
