COMPUTATIONAL GEOMETRY · SPATIAL ALGORITHMS
计算几何可视化实验室
八个交互式模块，可视化经典计算几何算法：凸包构造、Delaunay 三角剖分、Voronoi 图、KD-Tree 最近邻、碰撞检测、空间分割、扫描线求交与多边形裁剪。每个模块均提供可交互的 SVG 可视化、算法步进与实时统计，全部基于纯 HTML/CSS/JS + SVG 实现，零外部依赖。
01CONVEX HULL · CONVEXITY
凸包
Andrew 单调链与 Graham 扫描算法。按 x 坐标排序后分别构建下凸包与上凸包，逐步回溯去除右拐点，最终合并得到包围所有点的最小凸多边形。
算法可视化
02TRIANGULATION · EMPTY CIRCLE
Delaunay 三角剖分
基于空圆性质的三角剖分。对每三个点构造外接圆，若圆内不含其他点则该三角形属于 Delaunay 三角剖分，最大化最小角，避免狭长三角形。
算法可视化
03VORONOI · NEAREST REGION
Voronoi 图
Fortune 扫描线思想的可视化。每个站点拥有离它最近的区域，单元边界为相邻站点的垂直平分线。扫描线自左向右移动，逐步揭示各单元。
算法可视化
04KD-TREE · NEAREST NEIGHBOR
最近邻搜索
KD-Tree 的构造与最近邻查询。沿交替轴在中位数处递归划分空间，查询时优先搜索近侧子树并利用超平面距离剪枝远侧，可视化访问路径与剪枝。
算法可视化
05COLLISION · BOUNDING VOLUMES
碰撞检测
AABB 轴对齐包围盒、OBB 有向包围盒（分离轴定理 SAT）与 GJK（基于 Minkowski 差）。拖动多边形对象，观察不同算法的包围体与碰撞响应。
算法可视化
06PARTITIONING · SUBDIVISION
空间分割
四叉树、KD-Tree 与 BSP 三种空间细分结构。四叉树四向递归划分，KD-Tree 沿交替轴二分，BSP 使用斜分割超平面。可调节最大深度观察细分过程。
算法可视化
07SWEEP LINE · INTERSECTION
扫描线
Bentley-Ottmann 扫描线求线段交点。垂直扫描线自左向右移动，事件队列处理端点与交点，状态结构维护活跃线段，逐步发现所有交点。
算法可视化
08INTERSECTION · CLIPPING
几何求交
Sutherland-Hodgman 多边形裁剪与线段求交。拖动多边形顶点与裁剪窗口，实时观察裁剪结果；线段模式下计算两线段交点并显示参数。
算法可视化