Question

Sweep Line

“扫描线”是计算几何领域的基础手法，可以用来解决许多计算几何的问题，有如图论中的 BFS 与 DFS 一样经典。它并不是一个物品，而是一个概念。

平移的扫描线

一条（或两条）无限长平行线，沿其垂直方向不断移动，从画面一端移动到另一端，只在顶点处停留。

实作时，通常是先按座标大小排序所有顶点，然后以两索引值，记录平行线的位置在哪个顶点上面。两条平行线，一条为主，穿越整个画面；一条为辅，跟著主线的状况进行平移。这是阴阳的道理。

后面章节 Closest Pair，将实际示范扫描线的实作方式。

UVa 920 972

旋转的扫描线

一条（或两条）从原点射出的射线，做 360°旋转，只在顶点处停留。

实作时，通常是先按极角大小排序所有顶点，然后以两索引值，记录射线的位置在哪个顶点上面。两条射线，一条为主，转过整个画面；一条为辅，跟著主线的状况进行平移。这是阴阳的道理。

UVa 270 10691 10927 11529 11696 11704 ICPC 3259 4064

Sweep Line 的基本精神

说穿了，扫描线的基本精神就是：先排序、再搜寻。

计算几何当中，有一个重要的特性是“区域性”。比如说，距离相近的点，总是群聚在一起；距离相远的点，总是被距离相近的点隔开。

排序的目的，就是建立“区域性”，使得搜寻的条件更精确，搜寻的速度更快。

观察问题是否有“不重叠”、“不相交”、“间隔”、“相聚”之类的性质，然后以扫描线进行扫描。或者换句话说，排序所有的顶点，进行搜寻。

平移的扫描线：座标排序

旋转的扫描线：极角排序

Rotating Caliper

Rotating Caliper

“旋转卡尺”也是计算几何领域的基础手法，它并不是一个物品，而是一个概念。

平面上的图形，做 360°旋转；以两条垂直线，随时从左右夹紧图形，找到极端顶点。

切换视点，就变成：两条无限长平行线，做 360°旋转，尝试夹紧平面上的图形，找到极端顶点。

实作时，通常是以两索引值，记录平行线的位置在哪个顶点上面。两条平行线，一条为主，转过整个画面；一条为辅，跟著主线的状况进行鬆紧。这是阴阳的道理。

实作时，只需转 180°即可。转半圈，两条平行线对调，效果同 360°。

后面章节 Farthest Pair，将实际示范旋转卡尺的实作方式。

UVa 303 10173 10416 11243

Rotating Caliper 的基本精神

说穿了，旋转卡尺的基本精神就是：穷举斜率，判断目标对象有多斜。

旋转卡尺：凸包

使用旋转卡尺夹住图形，卡尺夹不进的地方，刚好是该图形的凸包。旋转卡尺夹到的顶点顺序，就是凸包的顶点顺序。因此，旋转卡尺适合用于凸包、凸多边形的相关问题。

尚未学过凸包的读者，请参考本站文件“ Convex Hull ”。

Closest Pair

Closest Pair

一群点当中，距离最近的两个点叫作“最近点对”。

演算法（Enumeration）

穷举法的时间複杂度是 O(N^2)，可以找出所有的最近点对。

Farthest Pair

Farthest Pair

一群点当中，距离最远的两个点叫作“最远点对”。

穷举法的时间複杂度是 O(N^2)，可以找出所有的最远点对。

运用旋转卡尺，时间複杂度是 O(NlogN)，可以找出所有的最远点对。

距离变远

距离变远，就是扩张。无论是扩张两点连线，或者是扩张边界，距离都是变远。

要找最远点对，可以使用扩张边界的概念。扩张边界直到极限，碰触到最偏远的点，最后形成凸包。

因此，最远点对一定是凸包的对角线。就如同日常生活中，边边角角的宽度是最宽的、最容易卡到。

凸多边形范围内，最远的距离是对角线距离。

也许方才的论述太过抽象、不够严谨。来详细推敲一番吧！此处改用扩张两点连线的概念。

凸多边形范围内任一线段，必定短于、等长于某一条对角线：

一、凸多边形范围内，任取两点。

二、延长两点连线，直到边界。

三、挪动一点至顶点，尽可能远离垂足。

四、挪动另一点至顶点，同上。

藉由此性质，以旋转卡尺，穷举最长对角线的斜率，量测最长对角线的长度，就能轻鬆找到最远点对。

凸多边形的最长对角线们，斜率皆不同。

同一个斜率，如果有两条以上的最长对角线，就会产生矛盾──以两条最长对角线描出平行四边形，可以发现平行四边形的对角线更长。凸多边形范围内一定可以顺利描出平行四边形，请参考凸的定义。

凸多边形范围内，同一个斜率，最多只有一条最长对角线。因此，同一个斜率，旋转卡尺只能夹到一条最长对角线。

凸多边形的最长对角线数目，不超过顶点数目。

平面上 N 个点，其凸包最多有 N 个顶点。随著卡尺旋转，每一个顶点，都可能作为下一条最长对角线的端点，可以推理出凸包最多有 N 条最长对角线，此时形成奇数个顶点的正多角星。

平面上 N 个点的最远点对，最多只有 N 组。

演算法

一、求凸包，过滤出可能是最远点对的点。O(NlogN)
二、旋转卡尺，找出最长对角线，即是最远点对。O(N)

实作旋转卡尺，习惯用两个指标记录旋转卡尺当前夹到的点。求出凸包之后，首先将两个指标设定在凸包的最左最下点、最右最上点。要决定旋转卡尺接下来夹住的点，就观察夹角：夹角较小者，挪往下一点；夹角一样者，同时挪往下一点（亦得择一挪往下一点）。

除了观察夹角之外，也可以观察距离。要决定旋转卡尺接下来夹住的点，就观察点到直线距离：以另一边的指标及其下一点作为直线，观察指标及其下一点分别到直线的距离：距离变长者，挪往下一点；距离一样者，同时挪往下一点（亦得择一挪往下一点）。

上述两种判断方式都很麻烦，其实只需要一次叉积即可判断，读者可以动动脑想想看，谜底于程式码揭晓。

迴圈部分亦可採一主一副的形式：每穷举一个顶点，就立即找出对顶的点。

PKU 2187

Segment Intersection

判断线段们是否相交

使用穷举法穷举两线段，时间複杂度是 O(N^2)，可以求出所有交点。

使用平移的扫描线，先将线段排序，再从左到右依序穷举各线段，判断相交，时间複杂度为 O(NlogN)。

如果线段没有相交，无论扫描线如何移动，线段的上下顺序都是固定的。如果线段相交，那就一定是上下相邻的线段相交了。

随著扫描线移动，线段动态地增加减少，线段的上下顺序是固定的──可以使用二元搜寻树，记录扫描线当下扫中的线段。

一、排序所有端点：
　甲、X 座标，从小到大。
　乙、Y 座标，从小到大。
　丙、左端点先于右端点。
　　　（垂直线段，以下端点为左端点，以上端点为右端点。）
　丁、下端点先于上端点。
二、从左往右扫描端点：
　甲、若为左端点，把线段放入二元搜寻树。
　　　判断此线段、上一条线段是否相交。
　　　判断此线段、下一条线段是否相交。
　乙、若为右端点，从二元搜寻树拿出线段。
　　　判断上一条、下一条线段是否相交。

Point-Line Duality

Point-Line Duality

http://3glab.cs.nthu.edu.tw/~spoon/courses/CS631100/Lecture09_handout.pdf

http://user.frdm.info/ckhung/b/ma/duality.php

二维平面上的点和线，可以等价地转换成线和点。主要有两种转换方式，一般我们常用的是斜率与截距。

一、点 (a,b) 转换成直线 y = ax - b
二、点 (a,b) 转换成直线 ax + by = 1

事实上旋转卡尺与平移的扫描线互为点线对偶，所以平移的扫描线能解决的问题，旋转卡尺也能解决，反之亦然。