确定共球的数值鲁棒谓词

Question

我想知道是否有任何库/包提供数值鲁棒的谓词用于测试n点(在我的情况下n=5)是否位于公共球体上?

我想在Delaunay四面体化的背景下执行这个测试。我在CGAL中看到过包，但找不到任何针对此问题的显式函数。

我能想到的一种方法是使用CGAL CGAL::Sphere_d类使用4个点初始化球体，对于所有剩余的点，我将使用has_on_boundary()函数来测试是否所有点都位于公共球体上，但我不确定它是否可以在一般情况下工作，我的意思是可以证明正确以这种方式进行公共球体测试。

Answer 1

您可以使用CGAL::side_of_bounded_sphere()或CGAL::side_of_oriented_sphere()与具有精确谓词的内核，如CGAL::Exact_predicates_inexact_constructions_kernel。

你可以这样使用:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_3 Point_3;
int main()
{
   Point_3 p1(XX,XX,XX), p2(XX,XX,XX), p3(XX,XX,XX), p4(XX,XX,XX), p5(XX,XX,XX);
   if (CGAL::side_of_bounded_sphere(p1,p2,p3,p4,p5) == CGAL::ON_BOUNDARY)
     //the points are co-spherical
}

Answer 2

在J. Schewchuk的Triangle三角测量包中有用于" inccircle check"的健壮的2D和3D原语

Answer 3

如何将所有点转换为整数坐标，使用合适的缩放

InSphere测试是坐标的第五度表达式。粗略地说，使用64位算术，您可以测试直径为6000左右的球体。使用扩展精度，128位，您最多可以覆盖44,000,000(只需要+，-，*)。

这样做的好处是避免了由谓词不一致引起的算法失败的风险。