一、概述

CGAL ，计算几何算法库，是一个大型C + +库的几何数据结构和算法，如Delaunay三角网，网格生成，布尔运算的多边形，以及各种几何处理算法。 CGAL是用来在各个领域：计算机图形学，科学可视化，计算机辅助设计与建模，地理信息系统，分子生物学，医学影像学，机器人学和运动规划，和数值方法。

二、模块

Arithmetic and Algebra

  • Algebraic Foundations
  • Number Types
  • Modular Arithmetic
  • Polynomial

  • Algebraic kernel

    Combinatorial Algorithms

  • Monotone and Sorted Matrix Search

  • Linear and Quadratic Programming Solver

    Geometry Kernels

  • 2D and 3D Linear Geometry Kernel

  • dD Geometry Kernel
  • 2D Circular Geometry Kernel

  • 3D Spherical Geometry Kernel

    Convex Hull Algorithms

  • 2D Convex Hulls and Extreme Points

  • 3D Convex Hulls

  • dD Convex Hulls and Delaunay Triangulations

    Polygons

  • 2D Polygons

  • 2D Regularized Boolean Set-Operations
  • 2D Boolean Operations on Nef Polygons
  • 2D Boolean Operations on Nef Polygons Embedded on the Sphere
  • 2D Polygon Partitioning
  • 2D Straight Skeleton and Polygon Offsetting
  • 2D Minkowski Sums
  • 2D Polyline Simplification
  • 2D Visibility Computation

  • 2D Movable Separability of Sets

    Cell Complexes and Polyhedra

  • 3D Polyhedral Surface

  • Halfedge Data Structures
  • Surface Mesh
  • Combinatorial Maps
  • Generalized Maps
  • Linear Cell Complex
  • 3D Boolean Operations on Nef Polyhedra
  • Convex Decomposition of Polyhedra

  • 3D Minkowski Sum of Polyhedra

    Arrangements

  • 2D Arrangements

  • 2D Intersection of Curves
  • 2D Snap Rounding
  • 2D Envelopes

  • 3D Envelopes

    Triangulations and Delaunay Triangulations

  • 2D Triangulations

  • 2D Triangulation Data Structure
  • 2D Triangulations on the Sphere
  • 2D Periodic Triangulations
  • 2D Hyperbolic Delaunay Triangulations
  • 2D Periodic Hyperbolic Triangulations
  • 3D Triangulations
  • 3D Triangulation Data Structure
  • 3D Periodic Triangulations
  • dD Triangulations
  • 2D Alpha Shapes

  • 3D Alpha Shapes

    Voronoi Diagrams

  • 2D Segment Delaunay Graphs

  • L Infinity Segment Delaunay Graphs
  • 2D Apollonius Graphs (Delaunay Graphs of Disks)

  • 2D Voronoi Diagram Adaptor

    Mesh Generation

  • 2D Conforming Triangulations and Meshes

  • 3D Surface Mesh Generation
  • 3D Skin Surface Meshing
  • 3D Mesh Generation
  • Tetrahedral Remeshing

  • 3D Periodic Mesh Generation

    Shape Reconstruction

  • Poisson Surface Reconstruction

  • Scale-Space Surface Reconstruction
  • Advancing Front Surface Reconstruction
  • Polygonal Surface Reconstruction
  • Optimal Transportation Curve Reconstruction

    Geometry Processing

    Polygon Mesh Processing

    3D Surface Subdivision Methods