Rationale

Many algorithms in Point Set Processing are parallelized, but CGAL::remove_outliers() is not: the main reason is that it originally filled a std::multimap structure which is hard to parallelize.

This small feature adds a ConcurrencyTag template parameter to CGAL::remove_outliers() similarly to what already exists in other PSP functions. The algorithm has also changed slightly in the sense that it does not sort points anymore: apart from that, the output partition (which point is outlier, which point is inlier) is unchanged.

A parallel variant of the algorithm is added, and the sequential version is also made faster (around 1.7x faster in my experiments).

In practice:

• replacing the std::multimap by a std::vector filled first and sorted afterwards makes the algorithm 1.3x faster than master version
• replacing the sorting by a std::partition (for threshold-based version) and std::nth_element (for the percentage-based version) makes the algorithm 1.7x faster than master version
• parallelization of the vector filling on a quad-core processor makes the algorithm 5.4x faster than master version

Summary of API changes

A new template parameter ConcurrencyTag is added to CGAL::remove_outliers(). Documentation is changed to make it clear that points are not sorted but only partitioned.

License and copyright ownership

(no change)

CHANGES.md

### Point Set Processing
 - **Breaking change:** `CGAL::remove_outliers()` has been
   parallelized and thus has a new template parameter
   `ConcurrencyTag`. To update your code simply add as first template
   parameter `CGAL::Sequential_tag` or `CGAL::Parallel_tag` when
   calling this function.

Submission

• User Manual
• Reference Manual

Status

• Developed and locally tested (GNU/Linux)
• Small Feature, pre-approved Andreas Fabri 16:21, 16 April 2020 (CEST)