00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 #ifndef MLN_CANVAS_DISTANCE_GEODESIC_HH
00028 # define MLN_CANVAS_DISTANCE_GEODESIC_HH
00029
00033
00034 # include <mln/core/concept/image.hh>
00035 # include <mln/core/concept/neighborhood.hh>
00036 # include <mln/core/routine/duplicate.hh>
00037
00038 # include <mln/core/site_set/p_queue_fast.hh>
00039 # include <queue>
00040
00041 # include <mln/data/fill.hh>
00042 # include <mln/extension/adjust_fill.hh>
00043
00044
00045 namespace mln
00046 {
00047
00048 namespace canvas
00049 {
00050
00052 template <typename I, typename N, typename D,
00053 typename F>
00054 mln_ch_value(I, D)
00055 distance_geodesic(const Image<I>& input, const Neighborhood<N>& nbh,
00056 D max, F& functor);
00057
00058
00059
00060 # ifndef MLN_INCLUDE_ONLY
00061
00062
00063
00064
00065 namespace internal
00066 {
00067
00068 template <typename I, typename N, typename D,
00069 typename F>
00070 void
00071 distance_geodesic_tests(const Image<I>& input_,
00072 const Neighborhood<N>& nbh_, D max,
00073 F& functor)
00074 {
00075 const I& input = exact(input_);
00076 const N& nbh = exact(nbh_);
00077
00078 mln_precondition(input.is_valid());
00079 mln_precondition(nbh.is_valid());
00080
00081 (void) input;
00082 (void) nbh;
00083 (void) max;
00084 (void) functor;
00085 }
00086
00087
00088 }
00089
00090
00091
00092
00093
00094 namespace impl
00095 {
00096
00097 namespace generic
00098 {
00099
00100 template <typename I, typename N, typename D,
00101 typename F>
00102 mln_ch_value(I, D)
00103 distance_geodesic(const Image<I>& input_, const Neighborhood<N>& nbh_,
00104 D max, F& functor)
00105 {
00106 trace::entering("canvas::impl::generic::distance_geodesic");
00107
00108 const I& input = exact(input_);
00109 const N& nbh = exact(nbh_);
00110
00111 internal::distance_geodesic_tests(input, nbh, max, functor);
00112
00113 mln_precondition(input.is_valid());
00114 mln_precondition(nbh.is_valid());
00115
00116 mln_ch_value(I, D) dmap;
00117 initialize(dmap, input);
00118
00119 typedef mln_site(I) P;
00120 p_queue_fast<P> q;
00121
00122
00123 {
00124 functor.init(input);
00125 data::fill(dmap, max);
00126
00127 mln_piter(I) p(input.domain());
00128 mln_niter(N) n(nbh, p);
00129 for_all(p)
00130 if (functor.inqueue_p_wrt_input_p(input(p)))
00131 {
00132 functor.init_p(p);
00133 dmap(p) = 0;
00134 for_all(n)
00135 if (input.domain().has(n) &&
00136 functor.inqueue_p_wrt_input_n(input(n)))
00137 {
00138 q.push(p);
00139 break;
00140 }
00141 }
00142 }
00143
00144
00145 {
00146 P p;
00147 mln_niter(N) n(nbh, p);
00148 while (! q.is_empty())
00149 {
00150 p = q.pop_front();
00151 if (dmap(p) == max)
00152 {
00153
00154 q.clear();
00155 break;
00156 }
00157 for_all(n)
00158 if (input.domain().has(n) && dmap(n) == max)
00159 {
00160 dmap(n) = dmap(p) + 1;
00161 functor.process(p, n);
00162 q.push(n);
00163 }
00164 }
00165 }
00166
00167 trace::exiting("canvas::impl::generic::distance_geodesic");
00168 return dmap;
00169 }
00170
00171 }
00172
00173
00174
00175
00176
00177 template <typename I, typename N, typename D,
00178 typename F>
00179 mln_ch_value(I, D)
00180 distance_geodesic_fastest(const Image<I>& input_,
00181 const Neighborhood<N>& nbh_,
00182 D max,
00183 F& functor)
00184 {
00185 trace::entering("canvas::impl::distance_geodesic_fastest");
00186
00187 const I& input = exact(input_);
00188 const N& nbh = exact(nbh_);
00189
00190 internal::distance_geodesic_tests(input, nbh, max, functor);
00191
00192 extension::adjust(input, nbh);
00193
00194 mln_ch_value(I, D) dmap;
00195 initialize(dmap, input);
00196
00197 std::queue<unsigned> q;
00198
00199
00200 {
00201 functor.init_(input);
00202 data::fill(dmap, max);
00203
00204 extension::fill(input, true);
00205 extension::fill(dmap, D(0));
00206
00207 mln_pixter(const I) p(input);
00208 mln_nixter(const I, N) n(p, nbh);
00209 for_all(p)
00210 if (functor.inqueue_p_wrt_input_p_(p.val()))
00211 {
00212 functor.init_p_(p);
00213 dmap.element(p.offset()) = 0;
00214 for_all(n)
00215 if (functor.inqueue_p_wrt_input_n_(n.val()))
00216 {
00217 q.push(p.offset());
00218 break;
00219 }
00220 }
00221 }
00222
00223
00224 {
00225 unsigned p;
00226
00227 util::array<int> dp = offsets_wrt(input, nbh);
00228 const unsigned n_nbhs = dp.nelements();
00229
00230 while (! q.empty())
00231 {
00232 p = q.front();
00233 q.pop();
00234 if (dmap.element(p) == max)
00235
00236 break;
00237 for (unsigned i = 0; i < n_nbhs; ++i)
00238 {
00239 unsigned n = p + dp[i];
00240 if (dmap.element(n) == max)
00241 {
00242 dmap.element(n) = dmap.element(p) + 1;
00243 functor.process_(p, n);
00244 q.push(n);
00245 }
00246 }
00247 }
00248 }
00249
00250 trace::exiting("canvas::impl::distance_geodesic_fastest");
00251 return dmap;
00252 }
00253
00254
00255 }
00256
00257
00258
00259
00260
00261 namespace internal
00262 {
00263
00264 template <typename I, typename N, typename D,
00265 typename F>
00266 inline
00267 mln_ch_value(I, D)
00268 distance_geodesic_dispatch(metal::false_,
00269 const Image<I>& input,
00270 const Neighborhood<N>& nbh, D max,
00271 F& functor)
00272 {
00273 return impl::generic::distance_geodesic(input, nbh, max,
00274 functor);
00275 }
00276
00277 template <typename I, typename N, typename D,
00278 typename F>
00279 inline
00280 mln_ch_value(I, D)
00281 distance_geodesic_dispatch(metal::true_,
00282 const Image<I>& input,
00283 const Neighborhood<N>& nbh, D max,
00284 F& functor)
00285 {
00286 return impl::distance_geodesic_fastest(input, nbh, max, functor);
00287
00288
00289 }
00290
00291 template <typename I, typename N, typename D,
00292 typename F>
00293 inline
00294 mln_ch_value(I, D)
00295 distance_geodesic_dispatch(const Image<I>& input,
00296 const Neighborhood<N>& nbh, D max,
00297 F& functor)
00298 {
00299 enum {
00300 test = mlc_equal(mln_trait_image_speed(I),
00301 trait::image::speed::fastest)::value
00302 &&
00303 mln_is_simple_neighborhood(N)::value
00304 };
00305 return distance_geodesic_dispatch(metal::bool_<test>(),
00306 input, nbh, max,
00307 functor);
00308 }
00309
00310
00311 }
00312
00313
00314
00315
00316
00317 template <typename I, typename N, typename D,
00318 typename F>
00319 inline
00320 mln_ch_value(I, D)
00321 distance_geodesic(const Image<I>& input, const Neighborhood<N>& nbh,
00322 D max, F& functor)
00323 {
00324 trace::entering("canvas::distance_geodesic");
00325
00326 internal::distance_geodesic_tests(input, nbh, max, functor);
00327
00328 mln_ch_value(I,D) output;
00329 output = internal::distance_geodesic_dispatch(input, nbh, max, functor);
00330
00331 trace::exiting("canvas::distance_geodesic");
00332 return output;
00333 }
00334
00335
00336 # endif // ! MLN_INCLUDE_ONLY
00337
00338 }
00339
00340 }
00341
00342
00343 #endif // ! MLN_CANVAS_DISTANCE_GEODESIC_HH