geometry 标签归档 | 土法炼钢兴趣小组的算法知识备份

凸包算法：Graham Scan、Andrew 与 Chan 的进化

从 Graham Scan 的极角排序到 Chan 算法的 output-sensitive 最优性，凸包问题展示了计算几何算法设计的精妙思维。

扫描线是计算几何中最通用的算法范式——用一条虚拟的线从左到右扫过平面，将二维问题降维为一维动态问题。

Voronoi 图和 Delaunay 三角剖分是计算几何中最优美的对偶结构。从最近邻查询到有限元网格生成，它们的应用无处不在。

地理信息系统如何在数百万个多边形中快速找到附近的餐厅？R-tree 用层级化的边界矩形将空间搜索从暴力扫描变为对数级查询。

给定一个被线段划分的平面，如何快速确定一个查询点落在哪个区域？梯形分解用随机增量法构建 O(log n) 查询的优雅结构。

在 n 个点中找最近的一对，暴力需要 O(n^2)。分治法将其优化到 O(n log n)，而 Rabin 的随机化方法更进一步达到期望 O(n)。

详解欧几里得距离与曼哈顿距离的区别，平方距离优化技巧，以及点到直线、点到平面的距离计算方法。

从射线检测到包围盒碰撞。详解 Raycast 原理、AABB 碰撞检测算法以及它们在物理引擎中的应用。