CGAL中side_of_bounded_circle()在双曲约束三角剖分中异常求助

1. 精确内核Exact_predicates_exact_construction_kernel_with_sqrt的性能瓶颈 #

CGAL的带平方根精确内核依赖任意精度有理数运算（如Gmpq）来保证几何计算的绝对正确性。双曲几何中的bounded_side_2圆内点判断涉及大量平方根、分式运算：

• 每一步计算都要维护高精度分子分母，运算成本随数据复杂度呈指数级上升
• 当点接近圆边界时，精确内核需要额外的计算步骤来区分点的位置，导致单步运算时间大幅波动

2. includes_edge()调用时耗时放大的原因 #

includes_edge()在约束Delaunay三角剖分中负责验证边的合法性，插入相交约束时会触发大量orientation调用（你的重写实现依赖双曲线段位置判断，最终会调用bounded_side_2）：

• 非相交约束场景下，测试次数少且点位置相对明确，精确运算的耗时不显著
• 相交约束场景下，三角剖分需要频繁进行局部调整（边翻转、冲突处理），每一步都依赖高精度圆内点测试，累积的运算量直接导致卡顿；同时相交约束带来的点位置更接近决策边界，进一步放大了精确运算的时间波动

3. 替换方案生效的逻辑 #

换成Exact_predicates_inexact_constructions_kernel后，底层使用浮点运算（如double），运算速度远快于任意精度有理数。你自定义的代码：

Point_2 thirdPoint = Point_2(FT(2)*center.x() - p.x(), FT(2)*center.y() - p.y());
Bounded_side bs = CGAL::side_of_bounded_circle(p, q, thirdPoint, query);

将双曲几何的圆内点判断转化为欧氏几何的等价测试（利用圆心关于线段的对称点构造圆），避开了双曲特有的复杂精确运算，同时浮点运算的低延迟直接解决了耗时问题——虽然牺牲了绝对精确性，但在你的场景下足以满足需求。

内容的提问来源于stack exchange，提问作者Traubenzucker