多边形的偏移填充算法

1、多边形的偏移填充算法多边形偏移（polygon offset）算法可能我们印象不深，不过用过autoCAD的同学也印象autoCAD上面也还是有这个功能的。我们可以用autoCAD上的“正多边形”功能画一个多边形，然后用修改工具中“偏移”按钮，对多边形进行偏移，见图1，从外面的一个大的5边形按照边偏移至里面小的5边形，其中相应边偏移的距离定义为offset值。图1 AutoCAD中的多边形偏移效果图        当然，这只是简单的情况，复杂的情况可能是有多个多边形，其中1个outer多边形，多个inner多边形，然后offset的时候应该是outer多

2、边形向内offset，inner多边形向外offset。当一个多边形（特别是凹多边形）初步offset时，可能会发生自交；然后多边形之间也可能会发生相交。大概思路：这里就需要首先将自交的多边形分裂出来，并选择正确的多边形；然后将选择出来的多边形进行求交计算，再一次将有相交的多边形合并分裂出来，并且选择正确的多边形，这个时候得到的全部多边形就是一次offset出来的结果。1、为了保证outer多边形能向内offset，inner多边形能向外offset，这里需要保证outer多边形是逆时针方向旋转的，inner多边形是顺时针方向旋转的。1.1 这里就稍稍讲下多边形的顺逆判断。在多边形是简单多边形

3、的前提下，其实还是挺简单的，只要找出多边形左下角的一个顶点，然后判断与这个顶点相连的两条边的叉积是否大于0就行了；如果多边形不是简单多边形，比如有自相交，有顶点夹角为0的情况等等，这个时候多边形就不应该有顺逆这种属性吧2、对单个多边形，根据角平分线初步偏移得到角点对于一个角点，可以设这个顶点为curPoint，相连的前一个点为prePoint，下一个点为nexPoint，于是可以得到两个向量a = prePoint curPoint，b=nexPoint curPoint。将向量a和b设置为单位向量之后，相加就能得到角平分线的方向向量c。然后对单位向量a和b做点乘和叉乘，就能得到这个角度的co

4、s和sin值了，我们假设这个角度的一般为，则cos=cos2，sin=sin2。根据三角函数，就能得到sin值，之后将就能得到该顶点的角平分线方向的偏移向量d=c/|c|×offset÷sin。3、考虑到有些边在偏移的过程中会消失，即一些边有退化的offset值，见图3。如果初步偏移的值大于它的退化offset值，则该边就会反向出现，见图3中的边【4,5】，会给后面的程序带来很大的麻烦。图2图3         由此对于一个特定的offset值，需要当前多边形每条边的退化offset值，当然有些边是没有退化offset值的，

5、比如凸的inner多边形，offset的时候是向外扩张的，如果没有outer多边形限制的话，是不会结束offset的。我们就假设被有退化offset值的边的offset值为无穷大。而对于会退化的边来说，只需要将该边的两个顶点做的角平分线做求交计算得到交点，计算该交点到边的距离就得到这条边的退化offset值了。由此遍历每条边，得到最大的offset值和最小的offset值。3.1、如果当前的offset值最大的退化offset值，多边形的offset操作就结束了3.2、如果当前offset值最小的退化offset值，那就直接使用当前offset值做角平分线求初步offset角点3.3、如果当前

6、offset值在最小和最大退化offset值之间，则先使用最小offset值做初步offset角点，然后将当前offset值减去最小offset值，并重新计算全部的边的最小和最大offset值，重复上面过程，直至当前offset值最小offset值，进入3.24、第3步之后，多边形的初步offset已经完成，并且不存在反向边的情况。但此时的多边形可能存在自相交的情况以及顶点夹角为0的情况，见图4,5。图4 初步偏移多边形自相交图5 初步偏移多边形的一个顶点夹角为0         4.1 检测顶点夹角为0的全部顶点，并将该点以及相关的边分裂出来

7、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上，并继续按照多边形的方向行进，直到回到起点，则其中一个多边形分裂出来。见图8，将多边形【1,2,3,4

8、】分裂为【1,2,S】和【S,3,4】。图6 初步偏移多边形子分裂        4.4 重复上述过程，直至全部的多边形分裂出来。4.5 从分裂出来的多边形中，删除顺逆转向和原多边形不同的多边形5、根据步骤3、4，将全部的inner多边形和outer多边形初步偏移并且自分裂之后，将剩余的多边形做合并，同样是相互求交，记录交点信息（包括两个多边形的id，两条边的id，交点到对应边的起点的比率rate0和rate1）。并从一个未标记过的顶点开始行进，遇到交点行进方向改变，直至行进返回起点，形成一个新的多边形环。其中对行进过程中碰到的点都做上标记。6、重复步骤

9、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】是不合法的多边形。 图7 初步多边形之间的合并       6.1 选择的多边形规则如下：A、outer多边形内的下一级多边形不能有outer多边形；B、inner多边形内的下一级多边

10、形不能有inner多边形，除了图5中【1,2,1】这种类型的多边形，不能删除C、inner多边形的外面的上一级多边形一定是一个outer多边形图7中，可见【5,s0,s1,7】是inner多边形（顺时针方向），而它并没有包含在outer多边形【1,s0,6,s1,2,3,4】（逆时针方向）内，因此会被删除，而【1,s0,6,s1,2,3,4】会被保留。7、由上就是多边形offset的基本过程，不过还是有一些边界情况需要处理，这里需要定义线段求交的规则：A、为避免图8的（3,6）处出现4个交点，定义线段的起点为实心的，而终点为空心的，见图9.图8 此处应为1个交点图9 线段定义  &#

11、160;     B、排除图10,11中的两种情况的交点，因为此时并不需要分裂 图10  图11          C、选段可能会出现重合的情况，而此时也需要定义交点，假设线段1和线段2有重合，其中线段1的起点Start1在线段2的当中时，定义Start1为一个交点，由此可见图10.图12 一个交点图13 一个交点图14 一个交点图15 没有交点图16 两个交点          D、另外考虑到图14，用B的规则并不能成功分离图14中的图形，因此

12、定义图10这种情况没有交点。（不过后面发现用分步offset的方法，图14的情况其实也不会出现，o()o）图17 s0是【2,3】与【6,7】的交点，s1是【7,8】与【2,3】的交点          8、剩下比较麻烦的就是几个多边形合并的时候，出现的交点重合的问题了，见图15。此时，对于前面的使用行进走向的方法合并分裂多边形就无法处理了。图18 交点重合的情况         不能一次性合并多边形，那就尝试采用多边形一个接一个的合并，而又考虑到，两个多边形合并可能会产生n个多边形，见图19。而后面将产生的n个多边形再和剩余的多边形合并，情况会变得很复杂。所以这里仅对inner多边形进行这种处理，见图19，不难发现，2个inner多边形合并，可能是没有相交点，也可能产生一个更大的inner多边形和多个outer多边形，并且这些outer多边形在inner多边形里面。然后可以发现如果里面的outer多边形与其他的inner多边形合并的话，可能会产生多个更小的outer多边形，而这些outer多边形之间是不会发生相交的，这样子问题就能变得简单了。通过inner多边形两两合并的方法，避免了交点重合的问题，最后将全