CGAL users discussion list

[Yaoyu Hu <>]

Hi Sebastien,

Thank you for the further explanation. As far as I understand, the correct way should be the following:

auto it = cloud.begin();
while ( it != cloud.end() ) {
    if ( c_size <= size_limit )
        cloud.remove(it);
    else
        ++it;
}

I did not look at the source code, but I guess what cloud.remove() does might be swapping an element with the current cloud.end()-1 element and decreasing cloud.end() by 1.

Yaoyu

On Mon, Nov 29, 2021 at 3:55 AM Sebastien Loriot <> wrote:

In the while loop of the example you mentioned, please notice that
the iterator is not increased when the element is not removed.
This is because the current iterator will point to the next
non-removed element if removed.

In your case, you were always increasing the iterator. So it means that
if the element removed was the last one, the iterator would then point
to .end(). But since you increase it nonetheless, it now post to past
the end, which is a removed element (explaining the error message you
had).

So it means that what I proposed earlier is not valid. Indeed, since
some swap is happening, it might be that a collected iterator will point
to past the end.
If you want to stick to a for-all, you need to increase the iterator
only if the element is not removed.

Sorry for the confusion.

Best,

Sebastien.

On 11/29/21 3:33 AM, Yaoyu Hu ( via cgal-discuss
Mailing List) wrote:
> Hi Sebastien,
>
> Thank you for the reply. You are right, I need to put the elements that
> need to be removed into a container like std::vector then remove the
> elements in one go.
>
> In my last question, I was trying to follow the example here:
> https://doc.cgal.org/latest/Point_set_3/Point_set_3_2point_set_property_8cpp-example.html
> <https://doc.cgal.org/latest/Point_set_3/Point_set_3_2point_set_property_8cpp-example.html>
>
> In the example, the points in a Point_set_3 are directly removed inside
> a while-loop by calling the remove() function. So I thought I can do the
> same. But it did not work. Do you think the example code needs some
> revision regarding the correct way of explicitly removing a bunch of
> points from Point_set_3?
>
> Thank you!
>
> Yaoyu
>
> On Tue, Nov 23, 2021 at 1:01 PM Sebastien Loriot <
> <mailto:>> wrote:
>
>     You should not iterate on a range and remove elements at the same time.
>     Put elements to be removed in a std::vector and remove them after the
>     main loop over all elements. Removing an element may invalidate its
>     iterator for any container.
>
>     Something like that:
>        for ( auto it = cloud.begin(); it != cloud.end(); ++it )
>        {
>          if ( c_size <= size_limit ) to_remove.push_back(*it);
>        }
>        for(auto i : to_remove)
>           cloud.remove(i);
>
>     Best,
>
>     Sebastien.
>
>
>     On 11/18/21 4:18 PM, Yaoyu Hu (
>     <mailto:> via cgal-discuss
>     Mailing List) wrote:
>      > Hi,
>      >
>      > I am trying to clean the points of a Point_set_3 by removing small
>      > clusters of points.
>      >
>      > The way I did it is first computing the clusters
>      > by CGAL::cluster_point_set() and saving the cluster indices to a
>      > property map with the name "cluster". Then I count the number of
>     points
>      > in each cluster. Finally, the points belonging to a cluster that
>     has a
>      > small cluster size are removed by issuing the remove() function (
>      > followed by collect_garbage() after all remove() calls).
>      >
>      > The problem is when I iterate through the Point_set_3 point cloud
>     and
>      > send the de-referenced iterator value to the property map, the
>     property
>      > map throws an exception triggered by a CGAL::assertion_fail(). The
>      > following is the code I use to do the small cluster removal. And
>     I also
>      > create a gist if that is more convenient.
>      >
>      > https://gist.github.com/huyaoyu/ea9919a1ff6e4c4b49d55020998d1e46
>     <https://gist.github.com/huyaoyu/ea9919a1ff6e4c4b49d55020998d1e46>
>      > <https://gist.github.com/huyaoyu/ea9919a1ff6e4c4b49d55020998d1e46
>     <https://gist.github.com/huyaoyu/ea9919a1ff6e4c4b49d55020998d1e46>>
>      >
>      > === Code begins. ===
>      >
>      > template < typename Iterable_t >
>      > static std::map<int, int>
>      > compute_cluster_size(const Iterable_t& cluster_map) {
>      >      std::map<int, int> cluster_size;
>      >
>      >      for ( const auto& idx : cluster_map ) {
>      >          if ( cluster_size.find(idx) == cluster_size.end() ) {
>      >              // New idx.
>      >              cluster_size[idx] = 1;
>      >          } else {
>      >              // Existing cluster.
>      >              cluster_size[idx]++;
>      >          }
>      >      }
>      >
>      >      return cluster_size;
>      > }
>      >
>      > // sr::PointSet_t is CGAL::Point_set_3.
>      > void sr::compute_and_remove_small_clusters(
>      >      sr::PointSet_t& cloud,
>      >      double avg_spacing,
>      >      int size_limit,
>      >      std::ostream& os ) {
>      >      sr::PointSet_t::Property_map<int> cluster_map;
>      >
>      >      // Reset or create a new property map.
>      >      if ( cloud.has_property_map<int>("cluster") ) {
>      >          boost::tie( cluster_map, boost::tuples::ignore ) =
>      >              cloud.property_map<int>("cluster");
>      >
>      >          cloud.remove_property_map(cluster_map);
>      >      }
>      >
>      >      bool success = false;
>      >      boost::tie( cluster_map, success ) =
>      >          cloud.add_property_map<int>("cluster", -1);
>      >
>      >      if ( !success ) {
>      >          os << "Cannot add cluster property map. \n";
>      >          return;
>      >      }
>      >
>      >      // Clustering.
>      >      CGAL::Real_timer rt; rt.start();
>      >      std::size_t n_clusters =
>      >          CGAL::cluster_point_set(
>      >              cloud,
>      >              cluster_map,
>      >              cloud.parameters().neighbor_radius(avg_spacing)
>      >          );
>      >      rt.stop();
>      >      os << "Find " << n_clusters << " clusters in " << rt.time()
>     << "
>      > seoncds. \n";
>      >
>      >      // Compute the cluster size.
>      >      std::map<int, int> cluster_size = compute_cluster_size(
>     cluster_map );
>      >
>      >      // Remove small clusters.
>      >      for ( auto it = cloud.begin(); it != cloud.end(); ++it ) {
>      >          // Get the cluster index.
>      >          const auto c_idx = cluster_map[*it];
>      >
>      >          // Get the cluster size.
>      >          const auto c_size = cluster_size[c_idx];
>      >
>      >          if ( c_size <= size_limit ) cloud.remove(it);
>      >      }
>      >
>      >      cloud.collect_garbage();
>      > }
>      >
>      > === Code ends. ===
>      >
>      > In the above code, the line *const auto c_idx =
>      > cluster_map[*it];* triggers the assertion failure in
>      > *CGAL::Property_array<int>::operator[]()*.
>      >
>      > I am assuming that *cluster_map* has all the points in the point
>     cloud
>      > as the key and as long as the iterator *it* comes from the point
>     cloud,
>      > **it* should be a valid key for *cluster_map*.
>      >
>      > The assertion failure does not always get triggered. Most of my
>     point
>      > clouds are OK. Only some point clouds trigger this error. I have
>      > uploaded one sample point cloud that causes this error to my Google
>      > Drive for your reference.
>      >
>     https://drive.google.com/file/d/1rfQP0mo7pj84YgAX1CZtorr6IMpsslyo/view?usp=sharing
>     <https://drive.google.com/file/d/1rfQP0mo7pj84YgAX1CZtorr6IMpsslyo/view?usp=sharing>
>
>      >
>     <https://drive.google.com/file/d/1rfQP0mo7pj84YgAX1CZtorr6IMpsslyo/view?usp=sharing
>     <https://drive.google.com/file/d/1rfQP0mo7pj84YgAX1CZtorr6IMpsslyo/view?usp=sharing>>
>      >
>      > Please help me. Any suggestions are appreciated. Thank you!
>      >
>      > Yaoyu
>      >
>      >
>      > --
>      > You are currently subscribed to cgal-discuss.
>      > To unsubscribe or access the archives, go to
>      > https://sympa.inria.fr/sympa/info/cgal-discuss
>     <https://sympa.inria.fr/sympa/info/cgal-discuss>
>      >
>
>     --
>     You are currently subscribed to cgal-discuss.
>     To unsubscribe or access the archives, go to
>     https://sympa.inria.fr/sympa/info/cgal-discuss
>     <https://sympa.inria.fr/sympa/info/cgal-discuss>
>
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss