当前位置：首页 > article >正文

一些需要学习的C++库：CGAL和Eysshot

article 2025/4/1 17:59:59

写在前面：

从开始工作到现在，去过多家公司，多个行业，
虽然大部分时间在通信业，但也有其它的行业的工作没有做完，但也很感兴趣。每次想要研究一下时，总是想不起来。
这里写一些信息，作为备忘。

几何库

CGAL：

几何是我最喜欢思考与研究的事情之一
有很多原因。这里不多说了，其中一个，是时下的AI还不能理解几何。
这方面，我可以稍说几句（当然不是全部）：当下的AI是线性的语言学的范畴。这么说吧，语言，不太恰当地说，像计算机的外设那样，驱动的作用之一就是串行化，以前吉尼斯记录中，有一个长着两个舌头的人，不幸的是他的父母分别是两个国家的人，说两种语言，有一次父母因为什么，同时在责难他，结果，你猜怎么着？他小宇宙爆发：同时用两种语言怼父母。注意，这里的同时，不是我们日常理解的同时，而是并行的意思。
不过，显然，地球上有这能力的人没几个，不要说大脑，两个舌头这事，就不太好找是吧。

Transformer的attention是伟大的发明，因为尽管DNN需要极大的算力，但attention即大大减少了算力，但缺点是，即使是多头，还是将并行的神经网络，从某种方式，再次来到串行的领域。事实上，前面我也描述了，你不可能并行对别人输出语言，所以，这的确不是transformer的问题，因为我们程序员讲求：实现的目标与自然一致性。所以，如果你是合格的程序员，就会明白我说什么了。

而大脑的确是并行的。
不要说别的事，就是最最基础的三段论，你只要稍稍思考一下，它就是并行的。要知道三段论，是我们世界构建的基础。是逻辑的最小粒度。

所以，当前的AI对几何毫无办法，就很容易理解了。不仅仅是因为几何是一种有架构的存在，更是因为其证明过程不仅需要辅助线这类的创造性的、探索性的、试探性的，这种并行思维模式，这是当前的AI无法处理的。

实际上，我在Windriver的几年，真的对安全（Safe(对外安全),Security（对内安全））这两个字有了新的理解。这么说吧，现在所有的AI的公司，所谓的安全，其实是一种一厢情愿的说词。真正的安全，不仅仅来自于外部，更重要是主动对象能通过最起码的类比和比较，进行比较（人类没有正确的概念，只是从所有的错误中选择危害最小的）。这样它才能真正理解规则（订立规则已经很难了，但针对不同的context还能够基于其类比能力来比对这些规则）。所以，如果细想一下，你就知道，现在的包括OpenAI所说的安全，是没有可信的基础的。

几何库，有很多，但其它的我没有接触过。
只接触过 CGAL。
https://www.cgal.org/
在这里插入图片描述 csdn上有一些文章：
https://blog.csdn.net/qq_32867925/article/details/146365861

CAD

Eysshot

这个我不想多说了。一家意大利的公司，当时我想开发二维的CNC一类的产品，具体是什么不好说。但当时我调研了许多种CAD库，包括中国的。当然我不会评论，很失望，不是说对产品失望，而是那种现状。当然，这几年也许好一点。
我想他们公司人数很少，但一直在开发。价格便宜，1.5万。
也许你认为1.5W也很贵，那我是没有说国内的的价格，一家似乎出名的公司，要我一千万。我问为什么这么贵，说要要给我源代码。我说，我不要源码，我双不是CAD公司，你封装成COM组件再报价，然后就没了下文，我怀疑这家公司（中国最出名的）已没有任何一名开发者了。真的。
有兴趣的可以研究一下这个库。

(Computational Geometry Algorithms Library)，这是一个非常强大的计算几何库，特别适合需要精确几何计算的2D（以及3D）应用，包括CAD相关开发。以下是对 CGAL 的详细介绍：

(3) CGAL 示例与Clipper

CGAL特点是高精度浮点。更学术，重精度，轻执行效率。
Clipper相反，是定点运算的，更快速。但要注意精度，例如，需要四舍五入时，要自己round，不要norm.

(3.1) CGAL (Computational Geometry Algorithms Library)

CGAL 是一个开源的C++库，专注于计算几何算法和数据结构。它不仅限于2D，还支持3D几何，但其2D功能非常强大，适用于2D CAD 或图形处理。

主要特点:
- 2D几何支持:
  点、线段、多边形、直线、圆等基本几何对象。
  - 多边形操作（交集、并集、差集、偏移等）。
  - Delaunay 三角剖分和 Voronoi 图。
  - 凸包计算。
- 精确性: 使用精确的算术（如有理数或浮点数过滤器），避免浮点误差，非常适合CAD应用。
- 模块化: 提供多种独立模块，可以按需选择使用（如 2D Triangulation、2D Boolean Operations 等）。
- 灵活性: 支持自定义数据类型和几何内核（例如 Cartesian 或 Homogeneous 坐标系）。
- 与可视化工具集成: 可结合 Qt 或其他库进行图形化展示。
适用场景:
2D CAD 软件开发（例如多边形建模、路径规划）。
- 地理信息系统 (GIS)。
- 机器人路径规划或计算机图形学中的几何处理。
- 许可证: 双重许可 - LGPL（核心部分）和 GPL（某些高级功能），具体取决于使用的模块。
依赖:
- 需要 Boost 库。
- 可选依赖 GMP（大数运算）和 MPFR（高精度浮点运算）以提升性能和精度。
链接: cgal.org

(3.2)CGAL 的 2D 功能示例

基本几何操作:
- 计算两线段的交点。
- 判断点是否在多边形内。
多边形处理:
- 支持带孔多边形 (Polygons with Holes)。
- 布尔运算（例如两个多边形的并集或差集）。
高级功能:
- 2D 最小外接圆或矩形。
- 点集的三角剖分。

最简示例: 展示如何使用 CGAL 计算两个线段的交点：

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <iostream>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef K::Segment_2 Segment_2;

int main() {
    Point_2 p1(0, 0), p2(2, 2), p3(0, 2), p4(2, 0);
    Segment_2 s1(p1, p2), s2(p3, p4);

    auto result = CGAL::intersection(s1, s2);
    if (result) {
        if (const Point_2* p = boost::get<Point_2>(&*result)) {
            std::cout << "交点: (" << p->x() << ", " << p->y() << ")\n";
        }
    } else {
        std::cout << "无交点。\n";
    }
    return 0;
}

CGAL 示例

示例 1: 多边形布尔运算（并集）
计算两个多边形的并集，这在 CAD 中常用于合并形状。


#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <iostream>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Polygon_2<K> Polygon_2;

int main() {
    // 定义第一个多边形（矩形）
    Polygon_2 p1;
    p1.push_back(K::Point_2(0, 0));
    p1.push_back(K::Point_2(2, 0));
    p1.push_back(K::Point_2(2, 2));
    p1.push_back(K::Point_2(0, 2));

    // 定义第二个多边形（另一个矩形）
    Polygon_2 p2;
    p2.push_back(K::Point_2(1, 1));
    p2.push_back(K::Point_2(3, 1));
    p2.push_back(K::Point_2(3, 3));
    p2.push_back(K::Point_2(1, 3));

    // 计算并集
    std::list<Polygon_2> result;
    CGAL::join(p1, p2, std::back_inserter(result));

    // 输出结果
    for (const auto& poly : result) {
        std::cout << "并集多边形顶点数: " << poly.size() << "\n";
        for (const auto& vertex : poly.vertices()) {
            std::cout << "(" << vertex.x() << ", " << vertex.y() << ")\n";
        }
    }
    return 0;
}

示例 2: 多边形偏移（Offset）
在 CNC 中，偏移多边形常用于生成刀具路径。


#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/create_offset_polygons_2.h>
#include <iostream>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Polygon_2<K> Polygon_2;

int main() {
    // 定义一个简单多边形
    Polygon_2 poly;
    poly.push_back(K::Point_2(0, 0));
    poly.push_back(K::Point_2(2, 0));
    poly.push_back(K::Point_2(2, 2));
    poly.push_back(K::Point_2(0, 2));

    // 计算向外偏移 0.5 个单位
    double offset_distance = 0.5;
    std::vector<std::shared_ptr<Polygon_2>> offset_polys =
        CGAL::create_exterior_offset_polygon_2(poly, offset_distance);

    // 输出偏移后的多边形
    for (const auto& offset_poly : offset_polys) {
        std::cout << "偏移多边形顶点数: " << offset_poly->size() << "\n";
        for (const auto& vertex : offset_poly->vertices()) {
            std::cout << "(" << vertex.x() << ", " << vertex.y() << ")\n";
        }
    }
    return 0;
}

示例 3: 点集的凸包
在几何推理中，凸包常用于边界检测。


#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
#include <vector>
#include <iostream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;

int main() {
    // 定义点集
    std::vector<Point_2> points = {
        Point_2(0, 0), Point_2(1, 2), Point_2(2, 1),
        Point_2(3, 3), Point_2(0, 4)
    };

    // 计算凸包
    std::vector<Point_2> hull;
    CGAL::convex_hull_2(points.begin(), points.end(), std::back_inserter(hull));

    // 输出凸包
    std::cout << "凸包顶点数: " << hull.size() << "\n";
    for (const auto& p : hull) {
        std::cout << "(" << p.x() << ", " << p.y() << ")\n";
    }
    return 0;
}

Clipper 示例

Clipper 使用整数坐标（需要缩放浮点数），更轻量，专注于多边形剪裁和偏移。
示例 1: 多边形布尔运算（交集）
计算两个多边形的交集。


#include <clipper.hpp>
#include <iostream>

using namespace ClipperLib;

int main() {
    // 定义路径（坐标乘以 100 以转换为整数）
    Paths subj(2), clip(1), solution;
    subj[0] << IntPoint(0, 0) << IntPoint(200, 0) << IntPoint(200, 200) << IntPoint(0, 200); // 矩形
    subj[1] << IntPoint(100, 100) << IntPoint(300, 100) << IntPoint(300, 300) << IntPoint(100, 300); // 另一个矩形

    // 执行交集操作
    Clipper c;
    c.AddPaths(subj, ptSubject, true);
    c.AddPath(subj[1], ptClip, true);
    c.Execute(ctIntersection, solution);

    // 输出结果（除以 100 恢复浮点数）
    std::cout << "交集多边形数: " << solution.size() << "\n";
    for (const auto& poly : solution) {
        for (const auto& p : poly) {
            std::cout << "(" << p.X / 100.0 << ", " << p.Y / 100.0 << ")\n";
        }
    }
    return 0;
}

示例 2: 多边形偏移
生成刀具路径的偏移多边形。


#include <clipper.hpp>
#include <iostream>

using namespace ClipperLib;

int main() {
    // 定义多边形
    Path subj;
    subj << IntPoint(0, 0) << IntPoint(200, 0) << IntPoint(200, 200) << IntPoint(0, 200);

    // 设置偏移量（乘以 100）
    ClipperOffset co;
    Paths solution;
    co.AddPath(subj, jtSquare, etClosedPolygon);
    co.Execute(solution, 50.0); // 偏移 0.5 个单位

    // 输出结果
    for (const auto& poly : solution) {
        std::cout << "偏移多边形顶点数: " << poly.size() << "\n";
        for (const auto& p : poly) {
            std::cout << "(" << p.X / 100.0 << ", " << p.Y / 100.0 << ")\n";
        }
    }
    return 0;
}

示例 3: 多边形面积计算
在 CNC 中，面积计算可用于材料估算。


#include <clipper.hpp>
#include <iostream>

using namespace ClipperLib;

int main() {
    // 定义多边形
    Path poly;
    poly << IntPoint(0, 0) << IntPoint(200, 0) << IntPoint(200, 200) << IntPoint(0, 200);

    // 计算面积（结果为整数，需除以 10000 转换为平方单位）
    double area = Area(poly) / 10000.0;
    std::cout << "多边形面积: " << area << "\n";
    return 0;
}

CGAL vs Clipper 比较

特性	CGAL	Clipper
功能范围	全面（凸包、三角剖分、多边形操作等）	专注多边形剪裁和偏移
精度	高（支持精确算术）	基于整数（需手动缩放浮点数）
性能	稍慢（强调正确性）	更快（轻量设计）
易用性	较复杂（需熟悉模板和几何概念）	简单（API 直观）
依赖	Boost、GMP 等	无外部依赖
适用场景	复杂几何推理、CAD 开发	CNC 刀具路径、多边形处理

Clipper的定点示例和round

下面提定标的示例. 例如Q13.

Clipper 中“定点到浮点”是指定标（Scaling）。
Clipper 内部使用整数（long long 类型）来表示坐标，以避免浮点运算带来的精度问题。为了处理浮点数坐标，需要手动将浮点数“定标”到整数（通常通过乘以一个比例因子），然后在结果输出时再“反定标”回浮点数。
这种方法在 CAD 和 CNC 应用中非常常见，因为它兼顾了精度和性能。

Clipper 没有内置的定点格式（如 Q13），但你可以通过选择适当的定标因子（例如 $2^{13}$ ）来模拟类似 Q13 的定点运算。
Q13 是一种定点数格式，其中 13 位用于表示小数部分，通常用 2^{13} = 8192 作为定标因子。

示例 1: 使用 Q13 定标进行多边形交集

#include <clipper.hpp>
#include <iostream>

using namespace ClipperLib;

const double SCALE_FACTOR = 8192.0; // Q13 定标因子，2^13

// 将浮点坐标转换为 Q13 整数坐标
void AddPoint(Path& path, double x, double y) {
    path << IntPoint(static_cast<long long>(x * SCALE_FACTOR), 
                     static_cast<long long>(y * SCALE_FACTOR));
}

// 将整数坐标转换回浮点数
void PrintPath(const Path& path) {
    for (const auto& p : path) {
        double x = p.X / SCALE_FACTOR;
        double y = p.Y / SCALE_FACTOR;
        std::cout << "(" << x << ", " << y << ")\n";
    }
}

int main() {
    // 定义两个多边形（浮点坐标）
    Paths subj(1), clip(1), solution;
    
    // 第一个多边形（矩形）
    AddPoint(subj[0], 0.0, 0.0);
    AddPoint(subj[0], 2.0, 0.0);
    AddPoint(subj[0], 2.0, 2.0);
    AddPoint(subj[0], 0.0, 2.0);

    // 第二个多边形（部分重叠矩形）
    AddPoint(clip[0], 1.0, 1.0);
    AddPoint(clip[0], 3.0, 1.0);
    AddPoint(clip[0], 3.0, 3.0);
    AddPoint(clip[0], 1.0, 3.0);

    // 执行交集运算
    Clipper c;
    c.AddPath(subj[0], ptSubject, true);
    c.AddPath(clip[0], ptClip, true);
    c.Execute(ctIntersection, solution);

    // 输出结果
    std::cout << "交集多边形数: " << solution.size() << "\n";
    for (const auto& poly : solution) {
        std::cout << "多边形顶点:\n";
        PrintPath(poly);
    }
    return 0;
}

说明:
使用
2^{13} = 8192 作为定标因子，将浮点坐标转换为整数。输出时除以 8192 恢复浮点数。这种方法模拟了 Q13 格式，小数部分精度为 1/8192 = 0.0001220703125。

示例 2: 使用 Q13 定标进行多边形偏移

#include <clipper.hpp>
#include <iostream>

using namespace ClipperLib;

const double SCALE_FACTOR = 8192.0; // Q13 定标因子

void AddPoint(Path& path, double x, double y) {
    path << IntPoint(static_cast<long long>(x * SCALE_FACTOR), 
                     static_cast<long long>(y * SCALE_FACTOR));
}

void PrintPath(const Path& path) {
    for (const auto& p : path) {
        double x = p.X / SCALE_FACTOR;
        double y = p.Y / SCALE_FACTOR;
        std::cout << "(" << x << ", " << y << ")\n";
    }
}

int main() {
    // 定义多边形（浮点坐标）
    Path subj;
    AddPoint(subj, 0.0, 0.0);
    AddPoint(subj, 2.0, 0.0);
    AddPoint(subj, 2.0, 2.0);
    AddPoint(subj, 0.0, 2.0);

    // 设置偏移量（浮点数 0.1，定标后为整数）
    double offset_distance = 0.1;
    ClipperOffset co;
    Paths solution;
    co.AddPath(subj, jtSquare, etClosedPolygon);
    co.Execute(solution, offset_distance * SCALE_FACTOR); // 偏移量也要定标

    // 输出结果
    std::cout << "偏移多边形数: " << solution.size() << "\n";
    for (const auto& poly : solution) {
        std::cout << "偏移多边形顶点:\n";
        PrintPath(poly);
    }
    return 0;
}

说明:
偏移距离 (0.1) 被乘以 8192 转换为整数（819.2 四舍五入为 819）。结果坐标除以 8192 恢复为浮点数。

示例 3: 使用自定义定标因子（非 Q13）

如果 Q13 的精度（1/8192）不够，可以自定义更大的定标因子，例如 10000。

#include <clipper.hpp>
#include <iostream>

using namespace ClipperLib;

const double SCALE_FACTOR = 10000.0; // 自定义定标因子

void AddPoint(Path& path, double x, double y) {
    path << IntPoint(static_cast<long long>(x * SCALE_FACTOR), 
                     static_cast<long long>(y * SCALE_FACTOR));
}

void PrintPath(const Path& path) {
    for (const auto& p : path) {
        double x = p.X / SCALE_FACTOR;
        double y = p.Y / SCALE_FACTOR;
        std::cout << "(" << x << ", " << y << ")\n";
    }
}

int main() {
    // 定义多边形
    Path subj;
    AddPoint(subj, 0.0, 0.0);
    AddPoint(subj, 1.5, 0.0);
    AddPoint(subj, 1.5, 1.5);
    AddPoint(subj, 0.0, 1.5);

    // 计算面积
    double area = Area(subj) / (SCALE_FACTOR * SCALE_FACTOR);
    std::cout << "多边形面积: " << area << "\n";

    // 输出顶点（验证）
    std::cout << "多边形顶点:\n";
    PrintPath(subj);
    return 0;
}

说明:定标因子为 10000，小数精度为 0.0001。面积计算时需要除以 SCALE_FACTOR^2，因为面积是二维的。
关于 Q13 和定标的注意事项

Q13 的精度:
Q13 使用 13 位表示小数部分，适合中等精度需求。最大整数部分取决于 long long 的位数（通常 64 位），减去 13 位小数后仍有约 50 位整数部分，足够大多数 CAD/CNC 应用。
选择定标因子:
如果你的坐标范围较小（如 0 到 10），可以用较大的因子（如 10000 或 2^{16} = 65536）以提高精度。
如果坐标范围很大（如 0 到 10000），用较小的因子（如 100 或 1000）以避免整数溢出。
溢出检查:
Clipper 使用 long long（64 位），最大值为 2^{63} - 1。定标后的坐标不能超过这个值。例如，若因子为 8192，最大浮点坐标约为 $2^{63} / 8192 \approx 1.125 \times 10^{15}$ ，远超实际需求。

CAD 和 CNC: Clipper 的定标机制非常适合 CNC 刀具路径生成，因为它快速且专注于多边形操作。Q13 或类似定标因子可以满足大多数加工精度的需求（例如 0.0001 mm）。
几何推理: 如果你需要更复杂的推理（例如点在多边形内的判断），Clipper 的功能较有限，可能需要结合其他库（如 CGAL）。
如果你有具体的坐标范围或精度要求（例如“精度要到 0.001 mm”）。

如果需要考虑截断误差: 显式四舍五入

我们可以改进代码，在定标时加入四舍五入，以减少误差。C++ 中可以用 std::round 或手动加 0.5 后取整。以下是改进后的示例：
示例 1: 四舍五入的多边形交集


#include <clipper.hpp>
#include <iostream>
#include <cmath> // 为了 std::round

using namespace ClipperLib;

const double SCALE_FACTOR = 8192.0; // Q13 定标因子

// 使用四舍五入将浮点坐标转换为整数
void AddPoint(Path& path, double x, double y) {
    path << IntPoint(static_cast<long long>(std::round(x * SCALE_FACTOR)), 
                     static_cast<long long>(std::round(y * SCALE_FACTOR)));
}

void PrintPath(const Path& path) {
    for (const auto& p : path) {
        double x = p.X / SCALE_FACTOR;
        double y = p.Y / SCALE_FACTOR;
        std::cout << "(" << x << ", " << y << ")\n";
    }
}

int main() {
    Paths subj(1), clip(1), solution;
    
    // 第一个多边形（矩形）
    AddPoint(subj[0], 0.0, 0.0);
    AddPoint(subj[0], 2.0, 0.0);
    AddPoint(subj[0], 2.0, 2.0);
    AddPoint(subj[0], 0.0, 2.0);

    // 第二个多边形（带小数坐标）
    AddPoint(clip[0], 1.499, 1.499);
    AddPoint(clip[0], 3.501, 1.499);
    AddPoint(clip[0], 3.501, 3.501);
    AddPoint(clip[0], 1.499, 3.501);

    // 执行交集运算
    Clipper c;
    c.AddPath(subj[0], ptSubject, true);
    c.AddPath(clip[0], ptClip, true);
    c.Execute(ctIntersection, solution);

    // 输出结果
    std::cout << "交集多边形数: " << solution.size() << "\n";
    for (const auto& poly : solution) {
        std::cout << "多边形顶点:\n";
        PrintPath(poly);
    }
    return 0;
}