凸包

1. Introduction

一组点P的凸包是最小的凸多边形CH(P),在此多边形中,P中的每个点要么在CH(P)的边界上,要么在其内部。想象这些点是平面2D平面上的钉子,我们有一个足够长的橡皮筋可以包围所有的钉子。如果这个橡皮筋被释放,它会尽量包围尽可能小的区域。那个区域就是这些点/钉子的凸包的区域。找到一组点的凸包在打包问题中有自然的应用。

2. Graham的扫描

在这个可视化中,我们目前只支持格雷厄姆扫描算法。


我们首先选择一个枢轴点(最底部,最左边的点),然后按照这个枢轴点的逆时针顺序对其他N-1点进行排序。

3. 未来工作

这个可视化目前每年只在新加坡国立大学 (NUS) 使用一次(每年四月初,为了CS3233),因此它每年只更新一次。