Snap rounding issue for closely spaced input value

[Alison-97]

I encountered an issue with snap rounding in CGAL when inserting two line segments to be snap rounded. In my case, the horizontal line is slightly slanted, where the starting point and ending point are different by a very small value. When the ending point is 99.99999999999995 (14dp), the output of snap rounding is (0.5, 100.5), (100.5, 99.5), where the two points lie on different y-axes. However, when the ending point is 99.999999999999995 (15dp), they lie on the same y-axis (0.5, 100.5), (100.5, 100.5). I tried to resolve the issue by replacing the Kernel type with CGAL::Exact_predicates_exact_constructions_kernel to make the geometric computations in the code exact. Unfortunately, this did not solve the issue.

Any explanations why this could be the case? My understanding is that regardless of whether it’s 15dp or 14dp, they should always be located in the same hot pixel, because a hot pixel must start and end at 0 and 1. Which is what makes the behavior especially puzzling.

Source Code

#include <CGAL/Cartesian.h>
#include <CGAL/Quotient.h>
#include <CGAL/MP_Float.h>
#include <CGAL/Snap_rounding_traits_2.h>
#include <CGAL/Snap_rounding_2.h>
#include <CGAL/number_utils.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>

typedef CGAL::Quotient<CGAL::MP_Float>           Number_type;
//typedef CGAL::Cartesian<Number_type>             Kernel;
typedef CGAL::Exact_predicates_exact_constructions_kernel    Kernel;
typedef CGAL::Snap_rounding_traits_2<Kernel>     Traits;
typedef Kernel::Segment_2                        Segment_2;
typedef Kernel::Point_2                          Point_2;
typedef std::list<Segment_2>                     Segment_list_2;
typedef std::list<Point_2>                       Polyline_2;
typedef std::list<Polyline_2>                    Polyline_list_2;

int main()
{
    Segment_list_2 seg_list;
    Polyline_list_2 output_list;

    seg_list.push_back(Segment_2(Point_2(0, 100), Point_2(100, 99.999999999999995)));   //15dp: (0.5, 100.5), (100.5, 100.5)
    //seg_list.push_back(Segment_2(Point_2(0, 100), Point_2(100, 99.99999999999995)));    // 14dp: (0.5, 100.5), (100.5, 99.5)

    CGAL::snap_rounding_2<Traits, Segment_list_2::const_iterator, Polyline_list_2>
    (seg_list.begin(), seg_list.end(), output_list, 1.0, true, false, 5);

    int counter = 0;
    Polyline_list_2::const_iterator iter1;
    for (iter1 = output_list.begin(); iter1 != output_list.end(); ++iter1) {
        std::cout << "Polyline number " << ++counter << ":\n";
        Polyline_2::const_iterator iter2;
        for (iter2 = iter1->begin(); iter2 != iter1->end(); ++iter2)
            std::cout << "    (" << to_double(iter2->x()) << ", " << to_double(iter2->y()) << ")\n";
    }

    return(0);
}

[mglisse]

Your C++ compiler already rounds 99.999999999999995 to 100 (type double has limited precision) before CGAL has any chance to see that number. For more precision, you would need a different way to initialize your number, for instance from a string "99.999999999999995", or from 100 and then subtract something, etc.