空間幾何運算庫 cgal32.dll 設計說明與介面文件

專案背景與授權策略

• 基於非商業開源代碼片段，不開源核心庫，以二進制 cgal32.dll (Win32, ANSI C) 形式免費提供。
• 作者保留 90%+ 原始碼版權，使用者可免費使用但不可聲稱版權或販售庫本身。
• 與 CGAL 開源專案 (www.cgal.org) 無關，未參考其代碼。
• 目標：跨平台（未來支援 Linux），解決空間幾何領域通用問題。

核心功能範疇

• 幾何實體：點/點集、線/多線、面、體、面片、圓弧、樣條、貝茲曲線。
• 布爾運算：Union、Difference、XOR、Intersection。
• 空間查詢：點包含測試、包圍盒、距離/面積/長度計算、幾何關係 (相交/包含/相離/相切/重疊/相等)。
• 輔助功能：緩衝區生成、三角剖分、序列化 (Blob/GZIP)、坐標轉換。

關鍵資料結構 (不透明控制碼)

typedef struct _cg_polygon_t*  cg_polygon;
typedef struct _cg_shape_t*    cg_shape;      // 統一幾何容器
typedef struct _cg_geometry_t* cg_geometry;   // 3D 延伸
typedef struct _cg_tristrip_t* cg_tristrip;   // 三角帶渲染優化
typedef struct _cg_blob_t*     cg_blob_t;     // 二進制塊 {BYTE* chunk; size_t size;}

核心 API 分類節錄

庫生命週期

void CGAL_init(double epsilon);   // 進程級初始化，設定幾何容差
void CGAL_fini(int reserved);

多邊形操作

BOOL CG_polygon_create(cg_polygon*);
void CG_polygon_destroy(cg_polygon);
void CG_polygon_add_part(cg_polygon, const cg_vertexlist_t*, int is_hole);
double CG_polygon_get_area(const cg_polygon);
BOOL CG_polygon_get_relation(CG_RELATION, cg_polygon, cg_polygon);
void CG_polygon_clip(CG_OPCLIP op, cg_polygon subj, cg_polygon clip, cg_polygon result);
// 布爾運算：CG_DIFF, CG_INT, CG_XOR, CG_UNION

幾何關係枚舉

typedef enum { REL_CONTAIN, REL_CROSS, REL_DISJOINT,
               REL_EQUAL, REL_OVERLAP, REL_TOUCH, REL_WITHIN } CG_RELATION;

形狀容器 (統一 2D/3D)

BOOL CG_shape_create(cg_shape*);
void CG_shape_read(FILE*, cg_shape);
size_t CG_shape_write_blob(cg_blob_t*, const cg_shape);
RESULT CG_shape_read_blob(const cg_blob_t*, cg_shape);
void CG_polygon_to_shape(cg_polygon, cg_shape);  // 互轉

幾何實體定義

typedef struct { double x, y; } cg_vertex_t, cg_point_t;
typedef struct { double x, y, z; } cg_vector_t, cg_pointZ_t;
typedef struct { int num_vertices; cg_vertex_t* vertex; } cg_vertexlist_t;
typedef struct { double min_x, min_y, max_x, max_y; } cg_rect_t;

使用流程範例

1. CGAL_init(1e-9) 設定精度。
2. 建立物件：CG_polygon_create(&poly) → CG_polygon_add_part 輸入頂點。
3. 運算：CG_polygon_clip(CG_UNION, polyA, polyB, polyResult)。
4. 查詢：CG_polygon_get_area(polyResult)、CG_polygon_get_relation(REL_OVERLAP, ...)。
5. 序列化：CG_shape_write_blob / CG_shape_read_blob 持久化或網路傳輸。
6. CGAL_fini(0) 釋放資源。

現狀與展望

功能尚在完善中，暫不提供下載。未來規劃：Linux 版本、3D 布爾運算、空間索引 (R-tree)、GPU 加速三角剖分。