本文共 3229 字，大约阅读时间需要 10 分钟。

读《An Adaptable and Extensible Geometry Kernel》

利用Curiously Recurring Template Pattern替代虚函数

本文将详细探讨几何内核（Kernel）的设计与实现，重点分析其如何通过模板编程提升几何算法的适配性与可扩展性。

为什么需要Kernel

几何内核（Kernel）旨在解决代码适配性和可扩展性问题。传统的几何算法通常依赖于特定的几何类型（如点、线、多边形等），其实现难以适应不同几何问题的需求。几何内核通过将几何类型与算法操作进行抽象与封装，为用户提供一致的接口，从而降低了代码的耦合度。

Kernel的概念与架构

几何内核的核心概念是将几何类型和相关算法操作封装到一个统一的框架中。其典型架构包括三层：几何原语（Geometric Primitives），数值原语（Numeric Primitives），以及几何内核本身（Kernel）。

几何内核通过提供一系列预定义的操作对象（如Point_2、Line_2、Construct_line_2、Less_xy_2等），用户可以通过这些对象轻松构建和操作几何对象。例如：

K::Point_2 p(0, 1), q(1, -4);K::Line_2 line = K::Construct_line_2()(p, q);if (K::Less_xy_2()(p, q)) {    // 处理逻辑}

Kernel的实现

几何内核的实现可以分为多个版本，逐步优化其结构和功能。

第一版本

template 
   
    struct MyPoint { };template 
    
     struct MyLine { };template 
     
      struct MyConstruct { };template 
      
       struct MyLess { };struct Kernel {    typedef MyPoint
       
         Point_2;    typedef MyLine
        
          Line_2; typedef MyConstruct
         
           Construct_line_2; typedef MyLess
          
            Less_xy_2;};
          
         
        
       
      
     
    
   

第二版本

为了解决依赖关系和循环引用的问题，引入了Kernel_base作为基础接口：

template 
   
    struct MyPoint { };template 
    
     struct MyLine { };template 
     
      struct MyConstruct { };template 
      
       struct MyLess { };template 
       
        struct Kernel_base {    typedef MyPoint
        
          Point_2; typedef MyLine
         
           Line_2; typedef MyConstruct
          
            Construct_line_2; typedef MyLess
           
             Less_xy_2;};struct Kernel : public Kernel_base
            
              { };
            
           
          
         
        
       
      
     
    
   

第三版本

进一步优化，通过函数对象的方式实现操作逻辑：

template 
   
    struct MyPoint { };template 
    
     struct MyLine { };template 
     
      struct MyConstruct {    typedef k::Line_2 Line_2;    typedef k::Point_2 Point_2;    Line_2 operator()(Point_2, Point_2) const {        return Line_2();    }};template 
      
       struct MyLess {    typedef k::Point_2 Point_2;    bool operator()(Point_2, Point_2) const {        return true;    }};template 
       
        struct Kernel_base {    typedef MyPoint
        
          Point_2; typedef MyLine
         
           Line_2; typedef MyConstruct
          
            Construct_line_2; typedef MyLess
           
             Less_xy_2; static Construct_line_2 construct_line_2_object(); static Less_xy_2 less_xy_2_object();};
           
          
         
        
       
      
     
    
   

Kernel的使用示例

以2D点集凸包计算为例，展示Kernel的实际应用：

template 
   
    OutputIterator ch_graham_andrew(InputIterator first, InputIterator last, OutputIterator result) {    // 使用Kernel进行具体实现    return ch_graham_andrew(first, last, result, Kernel());}
   

简单的完整Kernel

以下是几何内核的完整实现示例：

template 
   
    FT determinant2x2(FT a00, FT a01, FT a10, FT a11) {    return a00 * a11 - a10 * a01;}template 
    
     void line_from_pointsC2(ft px, ft py, ft qx, ft qy, ft &a, ft &b, ft &c) {}template 
     
      struct Point_2 {    typedef k_ K;    typedef ft_ FT;    Point_2(ft x_, ft y_) : x(x_), y(y_) {}    ft x, y;};template 
      
       struct Line_2 {    typedef k_ K;    typedef Point_2
       
         Point_2;    Line_2(Point_2 p, Point_2 q) {        *this = K::Construct_line_2()(p, q);    }    ft a, b, c;};template 
        
         struct Kernel_bae : public Kernel_base
         
           { static Point_2 Point_2; static Line_2 Line_2; static Segment_2 Segment_2; static Less_xy_2 Less_xy_2; static Left_turn_2 Left_turn_2; static Construct_line_2 Construct_line_2;};
         
        
       
      
     
    
   

参考

[1] 《An Adaptable and Extensible Geometry Kernel》

转载地址：http://ykvuz.baihongyu.com/