几何算法通常考虑的对象是二维或者高维空间的点、线、多边形和其他几何体。
平面扫描算法由两个基本部分组成：
- 事件点进度表（Event），类似于一条道路的前后路标。在某些情况下需要动态更新。
- 扫面线状态（State），是扫描线上几何对象的适当描述。
基本概念：
- 简单、非简单多边形
- 凸多边形、
- 点集S的凸包CH(S)、包顶点（S）的极点
- u(x1, y1), v(x2, y2), w(x3, y3)三点形成的三角形的带符号面积
- 左旋、右旋
18.3 计算线段的交点
- 事件点进度表E 由线段的端点和交点构成，在扫描的过程中会动态地改变
- 扫描线的状态：是线段的序关系
18.4 凸包问题
给定平面上n个点的集合S，寻找它们的凸包CH(S)。教材上所讲的Graham的几何扫描算法，以某一个点为中心以放射线的形式逆时针扫描所有点（计算极角，再排序）。
它的事件点进度表E 是各个点按照极角的排序，扫描线的状态是一个栈St
18.5 计算点集的直径
点集的直径：S中任意两点距离的最大值。
计算点集直径的朴素(naive)做法是以n方的时间遍历所有的点对。课本介绍的方法，是通过在凸包上遍历把时间复杂度降到nlgn。
定义：设p是一个多边形，P的一条支撑线是指通过P顶点的一条直线l，它使得P的内部整个地在l的一边.
定义：接纳两条平行支撑线的任意两点称为跖zhi对.
推论：在凸多边中实现直径的任何顶点对是一个跖对.