如何利用CGAL加速球面上闭合曲线自相交检测与拓扑构建？

核心处理流程 #

针对单位球面上离散为球面线段折线的有向闭合曲线，核心处理流程为：

• 识别曲线排列的每个面并遍历面的顶点
• 基于曲线方向构建有向对偶图（共享边的面相连）

现有实现与性能对比 #

当前采用两种算法实现：

• CGAL实现：时间复杂度O((N+K)logN)，其中N为曲线段数，K为交点数
• 自定义朴素O(N²)球面线段相交算法

实验性能数据：

针对60段的目标曲线（检测到2个交点）：

• 自定义O(N²)算法耗时343微秒
• CGAL精确构造版本耗时7929微秒
• CGAL非精确构造版本耗时约1700微秒

由于多数数据的N处于50-500区间，此区间内朴素算法因常数项更小速度更快，导致CGAL代码实用性不足。

已尝试的优化措施 #

• 将CGAL内核从精确谓词+精确构造切换为精确谓词+非精确构造，但程序大部分耗时仍集中在CGAL::insert的扫面过程中
• 查阅CGAL官方性能优化文档后评估：
  • 1-6、9-10条优化建议不适用
  • 第7条已正确执行
  • 第8条改用非精确构造，但性能提升仍未达到预期

优化诉求 #

• 寻找CGAL的有效性能优化点
• 优化方案需支持后续多条球面上的有向闭合曲线的处理需求
• 不得影响后续构建有向对偶图和遍历面顶点的操作

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