c++ - 轻量级 Delaunay 三角函数库（用于 c++）

Question

我想玩一些（2D）Delaunay 三角测量，并且正在寻找一个相当小的库来使用。我知道 CGAL，但我想知道那里是否有一些相当简单明了的东西。

我想做的事情：

• 创建任意点集的三角剖分
• 找到任意点所在的三角形，并获取顶点
• 创建三角测量的图像（可选）

建议？

Answer 1

您可能应该详细说明您的目标，以便可以提供更相关的答案，但让我先提一下Triangle，这是一个 2D Delaunay 生成工具，用 C 编写，既可以用作独立程序，也可以从你自己的代码。

那么，关于CGAL，这里举一个典型的小例子，万一你还在考虑：

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

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Delaunay_triangulation_2<K>                   Delaunay;    
typedef K::Point_2                                          Point;

void load_points(std::vector< Point >& points)
{
  points.push_back(Point(1., 1.));
  points.push_back(Point(2., 1.));
  points.push_back(Point(2., 2.));
  points.push_back(Point(1., 2.));      
}

int main()
{
  std::vector< Point > points;
  load_points(points);
  Delaunay dt;
  dt.insert(points.begin(), points.end());
  std::cout << dt.number_of_vertices() << std::endl;
  return 0;
}

Answer 2

另见 poly2tri，它看起来不错：https ://github.com/greenm01/poly2tri

Answer 3

我使用Gnu Triangulated Surface 库进行 2D Delaunay 三角剖分，效果很好。调用有点奇怪，因为它使用 OOP-in-C GLib 风格，但它可以很容易地被包裹起来。