前言
多边形偏移 (polygon offset) 算法可能我们印象不深，不过用过 autoCAD 的同学应该有印象：autoCAD 上面也还是有这个功能的。我们可以用 autoCAD 上的“正多边形”功能画一个多边形，然后用修改工具中“偏移”按钮，对多边形进行偏移，从外面的一个大的5边形按照边偏移至里面小的5边形，其中相应边偏移的距离定义为offset值。
AutoCAD中的多边形偏移效果图
当然，这只是简单的情况，复杂的情况可能是有多个多边形，其中 1 个 outer 多边形，多个 inner 多边形，然后 offset 的时候应该是 outer 多边形向内 offset，inner 多边形向外 offset。当一个多边形（特别是凹多边形）初步 offset 时，可能会发生自交；然后多边形之间也可能会发生相交。
算法考虑
大概思路：这里就需要首先将自交的多边形分裂出来，并选择正确的多边形；然后将选择出来的多边形进行求交计算，再一次将有相交的多边形合并分裂出来，并且选择正确的多边形，这个时候得到的全部多边形就是一次 offset 出来的结果。
-
为了保证 outer 多边形能向内 offset，inner 多边形能向外 offset，这里需要保证 outer 多边形是逆时针方向旋转的，inner 多边形是顺时针方向旋转的。
这里就稍稍讲下多边形的顺逆判断：在多边形是简单多边形的前提下，其实还是挺简单的，只要找出多边形左下角的一个顶点，然后判断与这个顶点相连的两条边的叉积是否大于 0 就行了；如果多边形不是简单多边形，比如有自相交，有顶点夹角为 0 的情况等等，这个时候多边形就不应该有顺逆这种属性吧
-
对单个多边形，根据角平分线初步偏移得到角点
对于一个角点，可以设这个顶点为
curPoint，相连的前一个点为prePoint，下一个点为nexPoint，于是可以得到两个向量a = prePoint - curPoint，b=nexPoint - curPoint。将向量a和b设置为单位向量之后，相加就能得到角平分线的方向向量c。然后对单位向量a和b做点乘和叉乘，就能得到这个角度的 cos 和 sin 值了，我们假设这个角度的一般为 Θ，则cos=cos2Θ，sin=sin2Θ。根据三角函数，就能得到sinΘ值，之后将就能得到该顶点的角平分线方向的偏移向量d=c/|c|×offset÷sinΘ。image图2
-
边退化情况处理
考虑到有些边在偏移的过程中会消失，即一些边有退化的 offset 值，见图 3。如果初步偏移的值大于它的退化 offset 值，则该边就会反向出现，见图 3 中的边[4, 5]，会给后面的程序带来很大的麻烦。
image图3
由此对于一个特定的 offset 值，需要当前多边形每条边的退化 offset 值，当然有些边是没有退化 offset 值的，比如凸的 inner 多边形，offset 的时候是向外扩张的，如果没有 outer 多边形限制的话，是不会结束 offset 的。我们就假设被有退化 offset 值的边的 offset 值为无穷大。而对于会退化的边来说，只需要将该边的两个顶点做的角平分线做求交计算得到交点，计算该交点到边的距离就得到这条边的退化 offset 值了。由此遍历每条边，得到最大的 offset 值和最小的offset 值。
3.1 如果当前的 offset 值 ≥ 最大的退化 offset 值，多边形的 offset 操作就结束了
3.2 如果当前 offset 值 ≤ 最小的退化 offset 值，那就直接使用当前 offset 值做角平分线求初步 offset 角点
3.3 如果当前 offset 值在最小和最大退化 offset 值之间，则先使用最小 offset 值做初步 offset 角点，然后将当前 offset 值减去最小 offset 值，并重新计算全部的边的最小和最大 offset 值，重复上面过程，直至当前 offset 值 ≤最小 offset 值，进入 3.2
-
第 3 步之后，多边形的初步 offset 已经完成，并且不存在反向边的情况。但此时的多边形可能存在自相交的情况以及顶点夹角为 0 的情况，见图4，5。
image图4 初步偏移多边形自相交
image图5 初步偏移多边形的一个顶点夹角为 0
4.1 检测顶点夹角为0的全部顶点，并将该点以及相关的边分裂出来
4.2 计算多边形的每条边的相交关系，并将全部的交点信息记录下来，其中包含交点坐标
point(x, y)，交点在所在的两条边的id0和id1，交点在两条边的位置rate0,rate1，其中
point = edge0.Start + (edge0.End - edge0.Start) * rate0 = edge1.Start + (edge1.End - edge1.Start) * rate1;- 4.3 以其中一个初步偏移多边形的顶点为起点，顺着多边形的方向开始行进，遇到交点则行进方向改变，跳到交点相关的另一条 edge 上，并继续按照多边形的方向行进，直到回到起点，则其中一个多边形分裂出来。见图 6，将多边形
[1,2,3,4]分裂为[1,2,S]和[S,3,4]。
img图6 初步偏移多边形子分裂
4.4 重复上述过程，直至全部的多边形分裂出来。
4.5 从分裂出来的多边形中，删除顺逆转向和原多边形不同的多边形
根据步骤 3、4，将全部的 inner 多边形和 outer 多边形初步偏移并且自分裂之后，将剩余的多边形做合并，同样是相互求交，记录交点信息（包括两个多边形的 id，两条边的 id，交点到对应边的起点的比率 rate0 和 rate1）。并从一个未标记过的顶点开始行进，遇到交点行进方向改变，直至行进返回起点，形成一个新的多边形环。其中对行进过程中碰到的点都做上标记。
-
重复步骤 5，直至全部点都标记完。由此得到全部的分裂出来的多边形，见图 7，outer 多边形
[1,2,3,4]和 inner 多边形[5,6,7]相交于s0和s1，由此分裂为两个多边形[1,s0,6,s1,2,3,4]和[5,s0,s1,7]。在全部分裂出来的多边形中，从中选择出正确的多边形，图 7 中可以看出[1,s0,6,s1,2,3,4]是合法的多边形，而[5,s0,s1,7]是不合法的多边形。image图7 初步多边形之间的合并
-
6.1 选择的多边形规则如下：
outer 多边形内的下一级多边形不能有 outer 多边形
inner 多边形内的下一级多边形不能有 inner 多边形，除了图 5 中
[1,2,1]这种类型的多边形，不能删除inner 多边形的外面的上一级多边形一定是一个 outer 多边形
图 7 中，可见
[5,s0,s1,7]是 inner 多边形（顺时针方向），而它并没有包含在 outer 多边形[1,s0,6,s1,2,3,4]（逆时针方向）内，因此会被删除，而[1,s0,6,s1,2,3,4]会被保留。 -
-
由上就是多边形 offset 的基本过程，不过还是有一些边界情况需要处理，这里需要定义线段求交的规则：
-
为避免图 8 的
(3,6)处出现 4 个交点，定义线段的起点为实心的，而终点为空心的，见图 9.image图 8 此处应为 1 个交点
image图 9 线段定义
-
排除图10,11中的两种情况的交点，因为此时并不需要分裂
image图 10
image图 11
-
选段可能会出现重合的情况，而此时也需要定义交点，假设线段 1 和线段 2 有重合，其中线段 1 的起点
Start1在线段 2 的当中时，定义Start1为一个交点，由此可见图 10.[图片上传失败...(image-3ab34d-1527731219753)]
图 12 一个交点
image图 13 一个交点
image图 14 一个交点
image图 15 没有交点
image图 16 两个交点
-
另外考虑到图 14，用 B 的规则并不能成功分离图 14 中的图形，因此定义图 10 这种情况没有交点。（不过后面发现用分步 offset 的方法，图 14 的情况其实也不会出现，o(╯□╰)o）
image图 17 s0 是
[2,3]与[6,7]的交点，s1 是[7,8]与[2,3]的交点
-
-
剩下比较麻烦的就是几个多边形合并的时候，出现的交点重合的问题了，见图 15。此时，对于前面的使用行进走向的方法合并分裂多边形就无法处理了。
image图 18 交点重合的情况
不能一次性合并多边形，那就尝试采用多边形一个接一个的合并，而又考虑到，两个多边形合并可能会产生 n 个多边形，见图 19。而后面将产生的 n 个多边形再和剩余的多边形合并，情况会变得很复杂。所以这里仅对 inner 多边形进行这种处理，见图 19，不难发现，2 个 inner 多边形合并，可能是没有相交点，也可能产生一个更大的 inner 多边形和多个 outer 多边形，并且这些outer多边形在inner多边形里面。然后可以发现如果里面的 outer 多边形与其他的 inner 多边形合并的话，可能会产生多个更小的 outer 多边形，而这些 outer 多边形之间是不会发生相交的，这样子问题就能变得简单了。通过 inner 多边形两两合并的方法，避免了交点重合的问题，最后将全部的inner变形和最外面的outer合并，于是就能得到最后的结果了。
image图 19 两个inner多边形合并产生多个多边形
到这里算法应该差不多了，虽然仅仅考虑的是多边形，对于样条曲线、圆弧等复杂的情况也是通过离散化得到多边形，问题简单了很多很多，下面那就贴下效果图吧
image图 20
image图 21
image图 22
image图 23
image图 24
image图 25
image图 26
