Question

Polygon

多边形是由许多条边、端点对著端点串接成一圈的图形。

资料结构

想要记录一个多边形的资讯，有许多种方法，例如：一、按照连接顺序把多边形的边放到一个阵列裡面；二、按照连接顺序把多边形的顶点放到一个阵列裡面；三、挑一个顶点作为起点，从起点开始按照连接顺序把各条边的长度、边与边之间的夹角放到一个阵列裡面。

这几种方法的空间複杂度都是 O(N)，N 为多边形的顶点数目，也可以说是边的数目。

多边形分类：数学的观点

多边形（Polygon）：由许多条边、端点对著端点串接成一圈的图形。
简单多边形（Simple Polygon）：所有的边都不相交，只有相邻的边可以相交于一个顶点。
凹多边形（Convave Polygon）：多边形内部必有两点连线，穿过多边形外部。
凸多边形（Convex Polygon）：多边形内部所有两点连线，都在多边形内部。

正多边形（Regular Polygon）：每条边都一样长、每个角都一样大的多边形。
凸的正多边形：就是我们熟悉的正三角形、正方形、正五边形、……。
凹的正多边形：就是正五角星、正七角星、正八角星、……。
　　　　　　　详细资料请自行搜寻关键字 Regular Star Polygon。

UVa 12300

多边形分类：计算学的观点

简单多边形（Simple Polygon）。所有的边都不相交，只有相邻的边可以相交于一个顶点。

简单多边形围出一个明确的封闭区域。一般的多边形无法分辨内外，而简单多边形可以明确分辨内外。

沿边走一回，刚好自旋 360°；所有外角相加是 360°。我们习惯让顶点顺序是逆时针方向，以符合叉积的方向。

单调多边形（Monotone Polygon）。至少存在一条直线，这条直线的每一条垂直线，与单调多边形的交点在两点以下。

换句话说，单调多边形旋转至某个角度之后，可以切割成上下两条链，两条链都符合函数定义。单调多边形可以写成两个函数。

换句话说，单调多边形有两条链，在某个方向上先单调递增、再单调递减，彷彿单峰函数。

简单一句话：单调多边形是两条已排序的链。

凸多边形（Convex Polygon）。总是朝同一个方向转弯。

凸多边形同时是简单多边形和单调多边形，无论哪种方向都是单调多边形。数学性质非常强！

正交多边形（Orthogonal Polygon、Rectilinear Polygon）。每条边都平行于座标轴，转弯总是转 90°或 270°。

有洞的多边形（Polygon with Hole）。多边形的内部有数个洞，洞的内部有数个多边形。有洞的多边形，其实不属于多边形，其实是数个多边形。我们可以用顺时针代表多边形、逆时针代表洞。多边形的联集、交集、差集，结果常常是有洞的多边形。

Polygon Area

多边形面积（Surveyor's Formula）

凸多边形是特例中的特例，我们试著从凸多边形开始观察。

运用分治法的思想，把凸多边形分割成三角形，就容易计算面积了。取凸多边形内部一点作为基准点，连线至各个顶点，把凸多边形切开成许多个三角形。现在我们可以利用叉积，计算每个三角形的面积；然后通通加起来，得到凸多边形面积。

详细的步骤是：
一、建立基准点往各个顶点的向量。
二、依照顶点顺序，计算相邻向量的叉积，得到平行四边形面积。
三、除以二，得到三角形面积。
四、三角形面积通通加起来，得到凸多边形面积。

步骤三和步骤四可以颠倒，除以二的次数变成只有一次：
三、平行四边形面积通通加起来，得到凸多边形面积的两倍。
四、除以二，得到凸多边形面积。

事实上，基准点也可以在凸多边形边界、甚至是外部。此时叉积的结果有正值和负值，正值恰好对应到总面积，负值刚好对应到多馀面积。通通加起来，正负相消之后，恰好仍是凸多边形面积。

基准点设定在原点是最方便的，如此一来就不必特地计算基准点往各个顶点的向量，可以直接拿相邻两点的座标计算叉积。

此演算法可以推广到简单多边形，甚至是一般的多边形。时间複杂度为 O(N)，N 为多边形的顶点数目。

我们可以把结果写成数学式子，正是知名的行列式公式：

        1    | x1   x2   x3     xN-1   xN   x1 |
area = --- * |    ×    ×    ...      ×    ×    |
        2    | y1   y2   y3     yN-1   yN   y1 |

右下斜线相乘取正号，左下斜线相乘取负号，然后通通加起来，除以二。
如果是逆时针旋转，求出来为正值。
如果是顺时针旋转，求出来为负值，必须再取绝对值。

一般来说我们会让多边形顶点顺序为逆时针顺序，以求得正值。

Point in Polygon

判断一个点是否在凸多边形内部

很直觉但是不精准的方式，是沿著凸多边形外围绕一圈，看看点是不是在每一条边的同侧。若发现叉积皆小于零，即表示点在多边形内部：若发现叉积等于零，即表示点在凸多边形上、或在凸多边形某条边的延长线上；若发现叉积大于零，则表示点在凸多边形外部。

正确的方式，是将点到凸多边形顶点的各条向量，利用叉积运算判断是否都往同一方向旋转，如果都是往同一方向旋转，则表示点在凸多边形内部；如果中途出现反方向旋转，则表示点在凸多边形外部；如果中途出现叉积为零的情况，表示点在凸多边形上，而且就在对应的边上。

时间複杂度为 O(N)，N 为凸多边形的顶点数目。

UVa 109 361 476 477 478 10078 10291 10321

不断查询一个点是否在凸多边形内部

凸多边形内任选一点作为原点（例如所有点的平均值），然后依角度大小排序凸多边形的所有顶点。之后就可以用 Binary Search 找出给定的点在哪个夹角之内，最后判断点是不是在此夹角构成的三角形裡面。

O(NlogN) 预处理，O(logN) 求答案。

UVa 12048

判断一个点是否在简单多边形内部

从给定点开始，往随便一个方向（实作时习惯水平往右）射出一条无限长射线，看看穿过多少条边。如果穿过偶数次，表示点在简单多边形外部；如果穿过奇数次，表示点在简单多边形内部。

要小心处理射线穿过顶点、射线与边重叠的情况。也要小心处理点在多边形边界上的情况。

时间複杂度为 O(N)，N 为简单多边形的顶点数目。

UVa 634 11030 10348

不断查询一个点是否在简单多边形内部

http://en.wikipedia.org/wiki/Point_location

Polygon Clipping

用直线（半平面）裁切凸多边形

凸多边形划一道直线，切割成两个凸多边形。

直线改成半平面，裁切成一个凸多边形。

裁切前后，顶点先后顺序一样！可以循序扫描！

以点为主角、边为配角，沿凸多边形走一圈，点在半平面上则保存，边与直线有交点则保存。时间複杂度为 O(N)。

UVa 11989

用直线（半平面）裁切简单多边形

我没有研究。

UVa 10867 10974

用凸多边形裁切简单多边形

http://en.wikipedia.org/wiki/Sutherland–Hodgman_algorithm

不断查询直线是否与凸多边形相交

穷举凸多边形每一条边，判断相交。时间複杂度为 O(N)。

进阶的方法是在直线的垂线方向上，寻找凸多边形的两个极点，然后判断是否在直线两侧。时间複杂度为 O(logN)。

以凸多边形的最下最左点为头，以逆时针顺序建立一串点，其边的极角从 0°到 360°，形成严格递增数列。直线的垂线化成两个极角（相差 180°），分别二分搜寻，得到两个极点。实作时，不必计算实际极角，改用点积与叉积来比较极角大小。

ICPC 4837

不断查询直线是否与简单多边形相交

我没有研究。也许是“ Bounding Volume Hierarchy ”。

Polygon Intersection

两个凸多边形的交集

有三种演算法，时间複杂度都是 O(N+M)。

半平面交集：以 Merge Sort 排序半平面的极角。【尚待确认】

扫描线：凸多边形从左右极点切开成上下两条链。四链齐进。

交互前进：外侧边超车，直到挡住内侧边前方、或者撞到内侧边；内侧边超车，直到前方看不到外侧边、或者撞到外侧边。任选起点，先跑一圈找到任意交点；交点为起点，再跑一圈围出交集。

UVa 137 10321

两个简单多边形的交集、联集、差集

http://www.cs.jhu.edu/~misha/Spring16/16.pdf

扫描线。“ Segment Intersection ”略作修改。时间複杂度为 O(NlogN + K)，N 是所有顶点数量，K 是交点数量。

UVa 805 ICPC 7583

Polygon Offsetting

Polygon Offsetting

简单多边形，所有边一齐往垂直方向移动。往外则扩张、往内则收缩。

收缩时，顶点不断合併，直到剩下一点。夹角决定速率，速率决定顶点合併顺序。建立排序资料结构，时间複杂度为 O(NlogN)。

https://translate.googleusercontent.com/translate_c?sl=ru&tl=en&u=http://e-maxx.ru/algo/inscribed_circle

Polygon Offsetting

甲以各种姿态碰触乙的边缘，甲沿著乙的边缘扫一圈，尽可能扩张（收缩）乙。结果包含了直线和弧线，厚度均匀。

甲求凸包、求直径（最远点对），甲可以简化成线段。时间複杂度为 O(N)。

Minkowski Sum / Minkowski Difference

两个简单多边形（内部所有点）的“ Pairwise Sum ”。

甲不偏不倚。甲内部任取一个基准点，甲的基准点沿著乙的边缘走一圈，补厚（削薄）乙。基准点通常是顶点。

凸多边形，有著高速演算法，时间複杂度 O(N+M)。

凹多边形，则切割成大量凸多边形（三角剖分、凸分割），分头计算，最后再联集。

http://www.cs.jhu.edu/~misha/Spring16/19.pdf

https://www.youtube.com/watch?v=3qMNuoTHNHs

Visibility of Polygon

一个点的可见区域，被一个凸多边形遮挡

点在凸多边形内部。一定可以看见整个凸多边形。回顾一下凸多边形的定义：多边形内部所有两点连线，都在多边形内部。令其中一点是给定的点，令另外一点是可见的点，两点之间一定不会被凸多边形遮挡。

点在凸多边形上面。如果归类于内部，可见区域就是整个凸多边形；如果归类于外部，可见区域的边界，就是该点碰触的边的延长线。

点在凸多边形外部。上下两条切线围住的区域受到影响，可见区域变成切线与凹面围住的区域。找切线很简单：建立点到凸多边形各顶点的向量，运用叉积找出转至最右、转至最左的向量。

时间複杂度为 O(N)。

UVa 746

一个点的可见区域，被一个简单多边形遮挡

点在多边形内部。被一个简单多边形遮挡的可见区域，也是简单多边形。採用 Incremental Method，从一个可见的顶点开始，依照逆时针顺序，一次读入一条边，随时更新当下的可见区域。一共分成六种情况：

一、可见区域直接增加一条边。
二、可见区域增加一条割线。
　　割线会撞到多边形以后的边，届时就能求得割点。
三、可见区域切除看不见的部分，改为一条割线。
　　割线会撞到可见区域以前的边，必须倒退找割点。
四、同三。
五、同一。
六、同二。

http://arxiv.org/pdf/1111.3584v2.pdf

倒退找割点，顶多倒退 N 条边。时间複杂度为 O(N)。

附带一提，如果预先找到两个以上可见的顶点，就可以切断成链，实施 Divide and Conquer。

点在多边形上面、外部。原理相同，不再赘述。

【待补程式码】

UVa 10907

一个点的可见区域，被数个凸多边形遮挡

点在凸多边形外部、凸多边形们都不相交，才有讨论价值。

处理大量几何资料，最常见的手法就是扫描线和旋转卡尺了。此处採用旋转的扫描线，以给定点为基准，依照极角大小扫描所有顶点。当下扫中的点，如果被前一点的邻边遮挡，就马上删除此点。时间複杂度 O(NlogN)。

可以加速到 O(N+HlogH)。牵涉到直线与凸多边形交点的演算法。

一个点的可见区域，被数个简单多边形遮挡

http://www.visilibity.org/

採用旋转的扫描线。先找到每个多边形的两条切线（以及到切点的距离）。所有切线按照角度排序之后，依序处理每个区间即可，用一棵二元树动态维护每个多边形的可见顺序。时间複杂度 O(NlogH)，N 是所有顶点的数目，H 是所有多边形的数目。

比较容易实作的方式。先找到视点到各顶点的射线（以及到顶点的距离）。所有射线按照角度排序之后，依序处理每个区间即可，用一棵二元树动态维护每条边的可见顺序。时间複杂度 O(NlogN)。

Visibility Graph

大量的简单多边形顶点连线，连线不与障碍物交错。亦可添加起点、终点、中继点。主要用途是寻找最短路径，绕过障碍物。

有时候主角不是点，而是多边形。当主角只平移、不旋转，则以 Minkowski Sum 补厚障碍物，并且相对地削薄主角、变成点。

UVa 10762 10376 ICPC 3306

Kernel of Polygon

凸多边形的核

位于多边形内部，可以看到整个多边形内部的地方，称作“核”。“核”是设置监视摄影机、地标、广告看板的好地方。“核”可能是风水最旺的地方。

一个多边形的核，其实就是所有边的“ 半平面交集 ”。一个多边形的核，可能是一个凸多边形、一条线段、一个点、空集合。

凸多边形的核，显然就是原本的凸多边形。

简单多边形的核

直接套用半平面交集演算法，时间複杂度为 O(NlogN)。借用 Visibility of Polygon 演算法的手法，时间複杂度得压至 O(N)。

ICPC 2512 UVa 588

Star-shaped Polygon

“星状多边形”就是拥有核的多边形。与旋转的扫描线有一点点关联。

注意到“Star-shaped Polygon”与“Star Polygon”是完全不一样的东西。

ICPC 3616