[Olena-patches] last-svn-commit-240-g17def89 Prevent a site from being introduced twice in thinning's queues.

* mln/topo/skeleton/breadth_first_thinning.hh, * mln/topo/skeleton/priority_driven_thinning.hh: Use an image `in_queue' to tag sites inserted in the queue. --- milena/ChangeLog | 8 ++++++ milena/mln/topo/skeleton/breadth_first_thinning.hh | 26 ++++++++++++++++--- .../mln/topo/skeleton/priority_driven_thinning.hh | 23 +++++++++++++++-- 3 files changed, 50 insertions(+), 7 deletions(-) diff --git a/milena/ChangeLog b/milena/ChangeLog index 214ccdc..4998388 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,13 @@ 2011-03-14 Roland Levillain &lt;roland(a)lrde.epita.fr&gt; + Prevent a site from being introduced twice in thinning's queues. + + * mln/topo/skeleton/breadth_first_thinning.hh, + * mln/topo/skeleton/priority_driven_thinning.hh: + Use an image `in_queue' to tag sites inserted in the queue. + +2011-03-14 Roland Levillain &lt;roland(a)lrde.epita.fr&gt; + Add routines to identify and detach (collapse) simple pairs. * mln/topo/is_simple_pair.hh, diff --git a/milena/mln/topo/skeleton/breadth_first_thinning.hh b/milena/mln/topo/skeleton/breadth_first_thinning.hh index 121c159..19cf515 100644 --- a/milena/mln/topo/skeleton/breadth_first_thinning.hh +++ b/milena/mln/topo/skeleton/breadth_first_thinning.hh @@ -1,4 +1,5 @@ -// Copyright (C) 2009, 2010 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2009, 2010, 2011 EPITA Research and Development +// Laboratory (LRDE) // // This file is part of Olena. // @@ -41,6 +42,9 @@ # include <mln/fun/p2b/tautology.hh> +# include <mln/data/fill.hh> + + namespace mln { @@ -123,20 +127,30 @@ namespace mln is_simple.set_image(output); detach.set_image(output); + // FIFO queue. typedef mln_psite(I) psite; typedef p_queue_fast<psite> queue_t; queue_t queue; + // Image showing whether a site has been inserted into the queue. + mln_ch_value(I, bool) in_queue; + initialize(in_queue, input); + data::fill(in_queue, false); + // Populate QUEUE with candidate simple points. mln_piter(I) p(output.domain()); for_all(p) { if (output(p) && constraint(p) && is_simple(p)) - queue.push(p); + { + queue.push(p); + in_queue(p) = true; + } } while (!queue.is_empty()) { psite p = queue.pop_front(); + in_queue(p) = false; if (output(p) && constraint(p) && is_simple(p)) { detach(p); @@ -144,8 +158,12 @@ namespace mln for_all(n) { if (output.domain().has(n) - && output(n) && constraint(n) && is_simple(n)) - queue.push(n); + && output(n) && constraint(n) && is_simple(n) + && !in_queue(n)) + { + queue.push(n); + in_queue(n) = true; + } } } } diff --git a/milena/mln/topo/skeleton/priority_driven_thinning.hh b/milena/mln/topo/skeleton/priority_driven_thinning.hh index ad8e63d..5d65aea 100644 --- a/milena/mln/topo/skeleton/priority_driven_thinning.hh +++ b/milena/mln/topo/skeleton/priority_driven_thinning.hh @@ -43,6 +43,9 @@ # include <mln/fun/p2b/tautology.hh> +# include <mln/data/fill.hh> + + namespace mln { @@ -133,21 +136,31 @@ namespace mln is_simple.set_image(output); detach.set_image(output); + // Priority queue. typedef mln_psite(I) psite; typedef p_queue_fast<psite> queue_t; typedef p_priority<mln_value(J), queue_t> priority_queue_t; priority_queue_t queue; + // Image showing whether a site has been inserted into the queue. + mln_ch_value(I, bool) in_queue; + initialize(in_queue, input); + data::fill(in_queue, false); + // Populate QUEUE with candidate simple points. mln_piter(I) p(output.domain()); for_all(p) { if (output(p) && constraint(p) && is_simple(p)) - queue.push(priority(p), p); + { + queue.push(priority(p), p); + in_queue(p) = true; + } } while (!queue.is_empty()) { psite p = queue.pop_front(); + in_queue(p) = false; if (output(p) && constraint(p) && is_simple(p)) { detach(p); @@ -155,8 +168,12 @@ namespace mln for_all(n) { if (output.domain().has(n) - && output(n) && constraint(n) && is_simple(n)) - queue.push(priority(n), n); + && output(n) && constraint(n) && is_simple(n) + && !in_queue(n)) + { + queue.push(priority(n), n); + in_queue(n) = true; + } } } } -- 1.5.6.5