多边形的螺旋线填充

在前面多边形偏移填充的基础上，如果把相邻的偏移多边形连接起来，就能形成螺旋线的形式。这里关键就是如何寻找各偏移多边形的分裂开的起点和终点。算法大概过程如下：

1. 将每次进行多边形偏移算法得到的多边形的层级记录下来，如图 2，最低层为 1，最高层为 4

   image

   图 1

   image

   图 2

2. 对于逆时针旋转的 outer 多边形，记录最底层并且未分裂过的 outer 多边形记录为开始多边形，如图 2 中的 outer 多边形 1。而对于顺时针旋转的 inner 多边形，可以找到 inner 多边形 1，并根据多边形的内外包含关系（因为各偏移多边形之间并不存在在相交，由此仅需判断多边形的其中一个顶点是否在另一个多边形的内外，就可得到多边形之间的包含关系），得到包含当前 inner 多边形 1 的最高层 inner 多边形 2，由此将 inner 多边形 2 记录为开始多边形。

   由上可以一个开始多边形的集合 ICollection<Polygon> startPolygons (对于 startPolygons 中每个成员在进行第 3 步时，可以实现并行处理)

3. 对于每一个 startPolygon

   • 3.1 若当前 outer polygon 已经是最高层 polygon 了，或者当前 inner polygon 已经是最底层了，那么直接保存这个 polygon，为一个螺旋线，并标记为已经分裂过

   • 3.2 对于 outer startPolygon，通过寻找边长最长并且多边形剩余点均在该边同一侧的边为开始边 startEdge，并可得到两个多边形之间的连接边的方向 startEdge.Direction；将全部的多边形旋转，使得 startEdge.Direction 变为Direction(1, 0)；并搜索上一层全部多边形最低最左（y 值最低，若有多个 y 值最低的点，则取 x 值最小的点 nextVertex ），由此可得到下一个 outer 多边形（nextPolygon）；

   • 3.3 以 nextVertex 为起点，startEdge.Direction 的反向，做一个射线 halfLine，计算 halfLine 与 startPolygon 的交点 endPoint，并选择沿 startPolygon 方向与 startEdge.Start (开始顶点) 最近的一个顶点为endPoint，由此从 startPolygon 的 startPoint 开始顺着 startPolygon 方向直到 endPoint，保存全部点，接着保存 nextPolygon 中的 nextVertex。将 startPoygon 标记为已经分裂过。

   • 3.4 将 nextPolygon 作为 startPolygon，nextVertex 作为 startVertex，将 startEdge.Direction 继续作为接连线的方向；继续 3.1，3.2 的步骤

   • 3.5 3.2 ~ 3.4 步骤重复进行，直至下面 a~c 其中任一情况发生，则停止

     • a. 更高一层没有未分裂过的 outer polygon；

     • b. 得到的 nextPolygon 的 nextVertex 到 startPolygon 的 startEdge 的距离大于 2 倍的 offset 值（多边形偏移时的偏移值）

     • c. 3.2 中计算 halfLine 与 startPolygon 之间没有交点

   • 3.5 对于 inner polygon，和 outer polygon 的处理情况大体相同，仅在 3.1 中搜索下一层 inner polygon 时，搜索最高最左（对于 outer polygon 为最低最左）的顶点；3.2 中射线的方向为 startEdge.Direction 的方向 (对于 outer polygon 为反方向)，其余基本相同

4. 重新从全部 polygon 中搜索未分裂过的 polygon，执行第 3 步骤，直到全部 polygon 都标记为已经分裂过的，算法停止。

码了这么多，现在就贴下自己做的效果吧

image

图 3 初始多边形

image

图 4 多边形偏移填充结果

image

图 5 基于图 4 的多边形偏移填充结果的螺旋线填充结果

image

图 6 多边形偏移填充结果

image

图 7 基于图6的螺旋线填充结果

image

图 8 多边形偏移填充结果

image

图 9 基于图8的螺旋线填充结果

image

图 10

image

图 11