多边形的螺旋线填充

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

  1. 将每次进行多边形偏移算法得到的多边形的层级记录下来,如图 2,最低层为 1,最高层为 4
    多边形的螺旋线填充
    文章图片
    image
    图 1
    多边形的螺旋线填充
    文章图片
    image
    图 2
  2. 对于逆时针旋转的 outer 多边形,记录最底层并且未分裂过的 outer 多边形记录为开始多边形,如图 2 中的 outer 多边形 1。而对于顺时针旋转的 inner 多边形,可以找到 inner 多边形 1,并根据多边形的内外包含关系(因为各偏移多边形之间并不存在在相交,由此仅需判断多边形的其中一个顶点是否在另一个多边形的内外,就可得到多边形之间的包含关系),得到包含当前 inner 多边形 1 的最高层 inner 多边形 2,由此将 inner 多边形 2 记录为开始多边形。
    由上可以一个开始多边形的集合 ICollection 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,由此从 startPolygonstartPoint 开始顺着 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. 得到的 nextPolygonnextVertexstartPolygonstartEdge 的距离大于 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

    推荐阅读