Graham Scan

定义 Definition

Graham scan（格雷厄姆扫描法）是一种用于在平面上计算凸包（convex hull）的经典算法：先选取基准点（通常为最低、最左点），按极角排序其余点，然后用“栈”结构依次检查转向（顺时针/逆时针），把会造成凹陷的点弹出，最终得到凸包边界。

发音 Pronunciation (IPA)

/ˈɡreɪəm skæn/

例句 Examples

We used Graham scan to find the convex hull of the points.
我们用格雷厄姆扫描法来求这些点的凸包。

After sorting the points by polar angle, the Graham scan iteratively removes right turns to ensure the remaining vertices form the convex hull.
在按极角对点排序后，格雷厄姆扫描法会迭代地移除“右转”造成的凹点，从而保证剩下的顶点构成凸包。

词源 Etymology

该名称来自美国数学家与计算机科学家 Ronald L. Graham（罗纳德·L·格雷厄姆），他在 1970 年代提出并推广了这种求凸包的方法；“scan”在这里指按排序顺序“扫描/遍历”点集并逐步筛除不符合凸性条件的点。

相关词 Related Words

• Convex Hull
• Computational Geometry
• Jarvis March
• Quickhull
• Monotone Chain
• Orientation
• Cross Product
• Stack

文学与经典著作中的用例 Literary / Notable Works

• Computational Geometry: Algorithms and Applications（Mark de Berg 等）：在凸包章节中介绍并比较 Graham scan 等方法。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在计算几何/凸包相关内容中提及或作为典型算法出现。
• Algorithms（Robert Sedgewick, Kevin Wayne）：在几何算法或凸包主题中讨论相关思想与实现。