寫在前面：
從開始工作到現在，去過多家公司，多個行業，
雖然大部分時間在通信業，但也有其它的行業的工作沒有做完，但也很感興趣。每次想要研究一下時，總是想不起來。
這里寫一些信息，作為備忘。
幾何庫
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幾何支持:
-
適用場景:
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 2^{13} 213）來模擬類似 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 ≈ 1.125 × 1 0 15 2^{63} / 8192 \approx 1.125 \times 10^{15} 263/8192≈1.125×1015，遠超實際需求。
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::roundusing 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;
}
 leetcode刷題)
 Practice 1028 List Sorting)
