如何在CGAL中使用自定义顶点实现球面Delaunay三角剖分

问题背景 #

CGAL的2D三角剖分支持通过Triangulation_vertex_base_with_info_2实现携带自定义信息的顶点，示例代码如下：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>
#include <vector>

typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
typedef CGAL::Triangulation_vertex_base_with_info_2<unsigned, K>    Vb;
typedef CGAL::Triangulation_data_structure_2<Vb>                    Tds;
typedef CGAL::Delaunay_triangulation_2<K, Tds>                      Delaunay;
typedef Delaunay::Point                                             Point;

int main() {
   std::vector<std::pair<Point, unsigned>> points;
   Delaunay dt;
   dt.insert(points.begin(), points.end());
   return 0;
}

但在球面Delaunay三角剖分（Delaunay_triangulation_on_sphere_2）中，尝试类似逻辑：

CGAL::Delaunay_triangulation_on_sphere_2<Traits> dtos;
std::vector<std::pair<Point, unsigned>> points;
dtos.insert(points.begin(), points.end());

并参考Triangulation_vertex_base_with_info_2.h基于Triangulation_on_sphere_vertex_base_2构造自定义顶点基类，未能成功。

第一次尝试的代码与编译错误 #

按照建议编写的代码如下：

#include <vector>

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_on_sphere_vertex_base_2.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>
#include <CGAL/Delaunay_triangulation_on_sphere_traits_2.h>
#include <CGAL/Delaunay_triangulation_on_sphere_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel                 K;
typedef CGAL::Delaunay_triangulation_on_sphere_traits_2<K>                  Traits;
typedef CGAL::Triangulation_on_sphere_vertex_base_2<Traits>                 Vbb;
typedef CGAL::Triangulation_vertex_base_with_info_2<unsigned, Traits, Vbb>  Vb;
typedef CGAL::Triangulation_on_sphere_face_base_2<Traits>                   Cb;
typedef CGAL::Triangulation_data_structure_2<Vb, Cb>                        Tds;
typedef CGAL::Delaunay_triangulation_on_sphere_2<Traits, Tds>               DToS2;
typedef DToS2::Point_3                                                      Point;

int main() {
    std::vector<std::pair<Point, unsigned>> points;
    points.emplace_back(Point(-1, 0, 0), 0);
    points.emplace_back(Point(0, -1, 0), 1);
    points.emplace_back(Point(0, 0, -1), 2);
    points.emplace_back(Point(1, 0, 0), 3);
    points.emplace_back(Point(0, 1, 0), 4);
    points.emplace_back(Point(0, 0, 1), 5);
    
    DToS2 dt;
    dt.insert(points.begin(), points.end());
    return 0;
}

编译报错：

>------ Build All started: Project: kitti2discarto, Configuration: x64-Release ------
  [1/2] Building CXX object CMakeFiles\kitti2discarto.dir\main.cpp.obj
  FAILED: CMakeFiles/kitti2discarto.dir/main.cpp.obj 
  C:\PROGRA~1\MICROS~2\2022\ENTERP~1\VC\Tools\MSVC\1431~1.311\bin\Hostx64\x64\cl.exe  /nologo /TP -DBOOST_ALL_DYN_LINK=1 -DBOOST_ALL_NO_LIB -DCGAL_USE_GMPXX=1 -DDISABLE_QHULL -DGLOG_NO_ABBREVIATED_SEVERITIES -DNOMINMAX -DQT_CORE_LIB -DQT_GUI_LIB -DQT_NO_DEBUG -DQT_WIDGETS_LIB -D_CRT_SECURE_NO_WARNINGS -D_SILENCE_CXX17_ITERATOR_BASE_CLASS_DEPRECATION_WARNING -D_USE_MATH_DEFINES -D__SSE2__ -D__SSE3__ -D__SSE4_1__ -D__SSE4_2__ -D__SSE__ -D__SSSE3__ -external:I C:\vcpkg\installed\x64-windows\include -external:I C:\vcpkg\installed\x64-windows\include\eigen3 -external:I C:\vcpkg\installed\x64-windows\include\openni2 -external:I C:\vcpkg\installed\x64-windows\include\vtk-9.0 -external:I C:\vcpkg\installed\x64-windows\include\qt5 -external:I C:\vcpkg\installed\x64-windows\include\qt5\QtWidgets -external:I C:\vcpkg\installed\x64-windows\include\qt5\QtGui -external:I C:\vcpkg\installed\x64-windows\include\qt5\QtCore -external:I C:\vcpkg\installed\x64-windows\tools\qt5\mkspecs\win32-msvc -external:W0 /std:c++20 /WIN32 /D_WINDOWS /W3 /GR /EHsc /MD /Zi /O2 /Ob1 /DNDEBUG   /bigobj -D_SCL_SECURE_NO_DEPRECATE -D_SCL_SECURE_NO_WARNINGS /fp:strict /fp:except- /bigobj /showIncludes /FoCMakeFiles\kitti2discarto.dir\main.cpp.obj /FdCMakeFiles\kitti2discarto.dir\ /FS -c C:\Users\User\workspace\kitti2discarto\kitti2discarto\main.cpp
C:\vcpkg\installed\x64-windows\include\CGAL\Delaunay_triangulation_on_sphere_2.h(635): error C2338: (std::is_same<typename std::iterator_traits<InputIterator>::value_type, Point>::value)
  C:\Users\User\workspace\kitti2discarto\kitti2discarto\main.cpp(28): note: see reference to function template instantiation 'unsigned __int64 CGAL::Delaunay_triangulation_on_sphere_2<Traits,Tds>::insert<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>>(InputIterator,InputIterator,void *)' being compiled
          with
          [
              _Ty=std::pair<Point,unsigned int>,
              InputIterator=std::_Vector_iterator<std::_Vector_val<std::_Simple_types<std::pair<Point,unsigned int>>>>
          ]
  C:\Users\User\workspace\kitti2discarto\kitti2discarto\main.cpp(28): note: see reference to function template instantiation 'unsigned __int64 CGAL::Delaunay_triangulation_on_sphere_2<Traits,Tds>::insert<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>>(InputIterator,InputIterator,void *)' being compiled
          with
          [
              _Ty=std::pair<Point,unsigned int>,
              InputIterator=std::_Vector_iterator<std::_Vector_val<std::_Simple_types<std::pair<Point,unsigned int>>>>
          ]
C:\vcpkg\installed\x64-windows\include\CGAL\Delaunay_triangulation_on_sphere_2.h(636): error C2338: !(std::is_same<Point, Point_3>::value)
  ninja: build stopped: subcommand failed.

Build All failed.

最终可行代码 #

修改后可正常运行的示例代码：

#include <iostream>
#include <vector>

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_on_sphere_vertex_base_2.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>
#include <CGAL/Delaunay_triangulation_on_sphere_traits_2.h>
#include <CGAL/Delaunay_triangulation_on_sphere_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel                 K;
typedef CGAL::Delaunay_triangulation_on_sphere_traits_2<K>                  Traits;
typedef CGAL::Triangulation_on_sphere_vertex_base_2<Traits>                 Vbb;
typedef CGAL::Triangulation_vertex_base_with_info_2<size_t, Traits, Vbb>    Vb;
typedef CGAL::Triangulation_on_sphere_face_base_2<Traits>                   Cb;
typedef CGAL::Triangulation_data_structure_2<Vb, Cb>                        Tds;
typedef CGAL::Delaunay_triangulation_on_sphere_2<Traits, Tds>               DToS2;
typedef DToS2::Point_3                                                      Point;
typedef DToS2::Vertex_handle                                                VH;

int main() {
    std::vector<Point> points;
    points.emplace_back(-1, 0, 0);
    points.emplace_back(0, -1, 0);
    points.emplace_back(0, 0, -1);
    points.emplace_back(1, 0, 0);
    points.emplace_back(0, 1, 0);
    points.emplace_back(0, 0, 1);
    
    Traits traits(Point(0, 0, 0), 1);
    DToS2 dt(traits);

    for (size_t i = 0; i < points.size(); i++) {
        const VH vh = dt.insert(points[i]);
        if (vh != VH()) vh->info() = i;
    }

    for (DToS2::Finite_faces_iterator face_itr = dt.finite_faces_begin(); face_itr != dt.finite_faces_end(); face_itr++) {
        std::cout << face_itr->vertex(0)->info() << ", " << face_itr->vertex(1)->info() << ", " << face_itr->vertex(2)->info() << std::endl;
    }

    return 0;
}

内容的提问来源于stack exchange，提问作者Gil-Dong Hong