在 CGAL 中转换坐标值

Converting coordinate values in CGAL

我目前使用的是来自 CGAL 的以下软件包: Boolean operations on polygons

因为我对多边形很感兴趣,除了线段之外,边也可以是圆段,所以我使用以下构建作为我的基本类型定义:

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2                                   Point_2;
typedef Kernel::Circle_2                                  Circle_2;
typedef Kernel::Line_2                                    Line_2;
typedef CGAL::Gps_circle_segment_traits_2<Kernel>         Traits_2;

typedef CGAL::General_polygon_set_2<Traits_2>             Polygon_set_2;
typedef Traits_2::General_polygon_2                       Polygon_2;
typedef Traits_2::General_polygon_with_holes_2            Polygon_with_holes_2;
typedef Traits_2::Curve_2                                 Curve_2;
typedef Traits_2::X_monotone_curve_2                      X_monotone_curve_2;
typedef Traits_2::Point_2                                 Point_2t;
typedef Traits_2::CoordNT                                 coordnt;
typedef CGAL::Arrangement_2<Traits_2>                     Arrangement_2;
typedef Arrangement_2::Face_handle                        Face_handle;

如上面的类型所示,我有两个点类型,即 Point_2 即 Kernel::Point_2 和我所说的 Point_2t 即 Traits_2::Point_2。

它们之间的区别在于,Point_2 具有有理坐标 x(), y() 而 Point_2t 具有 Q(alpha) 中的坐标,其中 Q 代表有理场和 alpha是有理数的平方根。

或者换句话说,Point_2的坐标在Kernel::FT,而Point_2t的坐标在Traits_2::CoordNT.

所以从 Point_2 转换为 Point_2t 没问题,但我还必须从 Point_2t 转换为 Point_2,希望能提供一种方式控制丢失的精度。

翻阅文档,利用eclipse的自动补全功能,整理了如下套路:

const int use_precision = 100;

CGAL::Gmpfr convert(CGAL::Gmpq z)
{
    CGAL::Gmpz num = z.numerator();
    CGAL::Gmpz den = z.denominator();

    CGAL::Gmpfr num_f(num);
    CGAL::Gmpfr den_f(den);

    return num_f/den_f;
}


CGAL::Gmpfr convert(Traits_2::CoordNT z)
{
    Kernel::FT a0_val = z.a0();
    Kernel::FT a1_val = z.a1();
    Kernel::FT root_val = z.root();

    CGAL::Gmpq a0_q = a0_val.exact();
    CGAL::Gmpq a1_q = a1_val.exact();
    CGAL::Gmpq root_q = root_val.exact();

    CGAL::Gmpfr a0_f = convert(a0_q);
    CGAL::Gmpfr a1_f = convert(a1_q);
    CGAL::Gmpfr root_f = convert(root_q);

    CGAL::Gmpfr res = a0_f + a1_f * root_f.sqrt(use_precision);

    return res;
}

Point_2 convert(Point_2t p)
{
    CGAL::Gmpfr xx = convert(p.x());
    CGAL::Gmpfr yy = convert(p.y());

    CGAL::Gmpq xx1 = xx;
    CGAL::Gmpq yy1 = yy;

    Kernel::FT xx2 = xx1;
    Kernel::FT yy2 = yy1;

    Point_2 pp(xx2, yy2);
    return pp;
}

基本上我将坐标从 Traits_2::CoordNT 转换为

的形式

(*) a0 + a1 * sqrt(根)

with a0, a1, root from Kernel::FT (=rational field),然后将 a0, a1, root 转换为 Gmpq 有理数,这些转换为 Gmpfr 精度为 100 位小数,然后计算表达式 (*) 和转换回 Gmpq,然后 Kernel::FT。所有转换(或多或少)都是通过 CGAL 的赋值和自动转换完成的。

在我的测试中,这似乎是正确的,但我仍然不能 100% 确定,如果根据 CGAL 定义,(*) 中的 sqrt(root) 表达式总是表示正平方根。

我看了一下定义:

description of sqrt-extended Number type in CGAL

但即使那样我也不完全相信,只取了 sqrt(root) 的正值。

所以我想问那些在这一点上完全了解 CGAL 系统的人:

我上面的转换例程是否正确假设要取的根的值始终为正值?

是的,你是对的。在 CGAL Sqrt_extension 中,在表达式 a0+a1√(root) 中,平方根始终为正数或为空。