Question

Half-plane

一条直线把二维平面划分为两半，其中一半就是“半平面”。半平面可以包含直线，也可以不包含直线。

半平面的一些图示方式：

实作时，通常以两个点来记录半平面的直线、以两个点的顺序来记录半平面的方向。

Half-plane Intersection

“半平面交集”就是许多个半平面的交集区域。半平面交集的结果可能是：一个开放区域、一个凸多边形、一条线、一条线段、一个点、空集合。

Half-plane Intersection: Incremental Method

演算法

一、预先使用四个半平面，设定一个极大的正方形边界，让半平面交集拥有边界。
二、逐一加入每个半平面，求出当下的半平面交集（凸多边形）。

online 演算法，随时维护一个半平面交集。每次更新需时 O(N)，总时间複杂度为 O(N^2)，N 是半平面数目。

Half-plane Intersection: Divide and Conquer

演算法

时间複杂度为 O(NlogN)，N 是半平面数目。

Divide：把半平面分成两堆。
Conquer：分别递迴求解。
Combine：求两个凸多边形的交集。O(N)

两个凸多边形的交集，可以用旋转卡尺求解，也可以用扫描线求解。

Half-plane Intersection: 不知名演算法

演算法

2006 年由竞赛选手南京外国语学校朱泽园《 半平面交的新算法及其实用价值 》提出。我不清楚是否已有正式学术论文，也不确定演算法是否正确。

半平面交集是一个凸多边形，凸多边形的边很有顺序的沿著外围绕行一圈，越来越倾斜。运用 Graham's Scan 的精神，预先排序所有半平面，依照极座标角度（不是斜率），逐步找出凸多边形的边。

一、所有半平面按照极座标角度排序。O(NlogN)
　　角度相同的半平面只需留下最内侧的一个。
二、建立一个 deque，加入前面两个半平面。O(1)
三、从第三个半平面开始，依序将半平面加入 deque。O(N)
　甲、deque 右端持续弹出，直到 deque 右端的两个半平面的交点，位于此半平面内。
　乙、deque 左端持续弹出，直到 deque 左端的两个半平面的交点，位于此半平面内。
　丙、deque 右端加入此半平面。
四、删除 deque 两端多馀的半平面。O(N)
　甲、deque 右端持续弹出，直到 deque 右端的两个半平面的交点，位于 deque 左端的半平面内。

时间複杂度为 O(NlogN)，主要取决于排序的时间。N 是半平面数目。

有点类似简单多边形的凸包演算法 Melkman's Algorithm，但是两者并非点线对偶。