CGAL
Consider NaNs as a filter failure in Filtered_construction.h
Non-definitive patch, to be discussed
Summary of Changes
Currently, the sanity of the result of a filtered construction is not checked, to the point that you can even have NaNs sneaking through. This PR is a patch that was provided to prevent NaNs from appearing in Segment_Delaunay_graph_2 under some specific kernel choices. It calls Kernel_object::operator==() as a way to get down to FT::operator== and detect NaNs. (Note that all FT have a is_valid() function that would check is_nan, but kernel objects do not have is_valid()).
Althought that patch will catch NaNs, it costs a comparison and could have some annoying effect on some exact number types.
Another way to go at it would be to aggressively check the precision of the output, see comments in https://github.com/CGAL/cgal/issues/44 and specifically https://github.com/CGAL/cgal/issues/44#issuecomment-499388882, quoted below for convenience:
After a discussion with @MaelRL one way to solve the precision issue of filtered constructions could be:
```
diff --git a/Cartesian_kernel/include/CGAL/Cartesian_converter.h b/Cartesian_kernel/include/CGAL/Cartesian_converter.h
index 33f941b330..0f75679cb5 100644
--- a/Cartesian_kernel/include/CGAL/Cartesian_converter.h
+++ b/Cartesian_kernel/include/CGAL/Cartesian_converter.h
@@ -220,6 +220,12 @@ public:
return Point_2(c(a.x()), c(a.y()));
}
+ bool has_enough_precision(const const typename K1::Point_2 &a) const
+ {
+ return a.x().width() < get_relative_precision_of_to_double() &&
+ a.y().width() < get_relative_precision_of_to_double();
+ }
+
typename K2::Weighted_point_2
operator()(const typename K1::Weighted_point_2 &a) const
{
diff --git a/Filtered_kernel/include/CGAL/Filtered_construction.h b/Filtered_kernel/include/CGAL/Filtered_construction.h
index 16e16f4cad..f9b1131e97 100644
--- a/Filtered_kernel/include/CGAL/Filtered_construction.h
+++ b/Filtered_kernel/include/CGAL/Filtered_construction.h
@@ -90,17 +90,18 @@ public:
Protect_FPU_rounding<Protection> P1;
try
{
- return From_Filtered( Filter_construction(To_Filtered(a1),
- To_Filtered(a2),
- To_Filtered(a3)) );
+ typename Filtered_construction::result_type res = Filter_construction(To_Filtered(a1),
+ To_Filtered(a2),
+ To_Filtered(a3)) );
+ if ( From_Filtered.has_enough_precision(res) )
+ return From_Filtered(res)
}
catch (Uncertain_conversion_exception&)
- {
- Protect_FPU_rounding<!Protection> P(CGAL_FE_TONEAREST);
- return From_Exact( Exact_construction(To_Exact(a1),
- To_Exact(a2),
- To_Exact(a3)) );
- }
+ {}
+ Protect_FPU_rounding<!Protection> P(CGAL_FE_TONEAREST);
+ return From_Exact( Exact_construction(To_Exact(a1),
+ To_Exact(a2),
+ To_Exact(a3)) );
}
};
```
We have to do some tricks to avoid call `width()` as a member type to restrict it `Interval_nt` but the global idea is here.
See also patch from @mglisse in Interval_nt::to_double() : https://github.com/mglisse/cgal/blob/NewKernel_d-Epack-glisse/Number_types/include/CGAL/Interval_nt.h#L1107.
@CGAL/geometryfactory
Release Management
- Affected package(s):
Filtered_kernel - Issue(s) solved (if any): -
- License and copyright ownership: No change
Currently, the sanity of the result of a filtered construction is not checked, to the point that you can even have NaNs sneaking through.
Where do NaNs come from? If there is no NaN in the input, it looks like it creates intervals (intervals don't have NaN), computes on them, then converts them, which should not be able to create a NaN. Or maybe the types are not those one would guess from the names?
Althought that patch will catch NaNs, it costs a comparison and could have some annoying effect on some exact number types.
Can this code path ever be used with an exact number type?
Currently, the sanity of the result of a filtered construction is not checked, to the point that you can even have NaNs sneaking through.
Where do NaNs come from? If there is no NaN in the input, it looks like it creates intervals (intervals don't have NaN), computes on them, then converts them, which should not be able to create a NaN. Or maybe the types are not those one would guess from the names?
It comes from having an inf (or two) as bounds of the interval, and the midpoint is a NaN.
Althought that patch will catch NaNs, it costs a comparison and could have some annoying effect on some exact number types.
Can this code path ever be used with an exact number type?
Technically, if I filter with an exact number type, yes :>. But you're right, that's not very likely. Still, I don't like this comparison much.
It comes from having an inf (or two) as bounds of the interval, and the midpoint is a NaN.
Ah, indeed, to_double([-inf, inf]) is NaN, thanks.
Still, I don't like this comparison much.
It is not that bad, it looks like a rather clever way to deal quickly with NaN without redesigning the whole thing. Of course it isn't perfect. For instance, operator== might have an optimization for some types where it first checks that the addresses are the same and returns true immediately.
I don't know what the impact would be on Segment_Delaunay_graph_2 if we started checking the precision. It should cause more filter failures, but maybe not that many, and the advantages of not producing points very far from their true position might be worth it.
Like Marc, I am also rather favorable for the PR as it is.
As for checking the validity of filtered_construction, that could be a functor, passed as template parameter:
- one model would check for NaNs, like this PR,
- another could check for nothing and let pass any constructed object,
- carefully designed ones could add a check that has a meaning for the algorithm (for example, in Mesh_3, it is important that the circumcenter of any tetrahedron is at least in the circumsphere of it).
Thinking about it a bit, isn't Inf almost as problematic as NaN? We are not allowed to convert it to an interval later to evaluate a predicate...
