多边形的螺旋线填充
在前面多边形偏移填充的基础上,如果把相邻的偏移多边形连接起来,就能形成螺旋线的形式。这里关键就是如何寻找各偏移多边形的分裂开的起点和终点。算法大概过程如下:
- 将每次进行多边形偏移算法得到的多边形的层级记录下来,如图 2,最低层为 1,最高层为 4
文章图片
image图 1
文章图片
image图 2
- 对于逆时针旋转的 outer 多边形,记录最底层并且未分裂过的 outer 多边形记录为开始多边形,如图 2 中的 outer 多边形 1。而对于顺时针旋转的 inner 多边形,可以找到 inner 多边形 1,并根据多边形的内外包含关系(因为各偏移多边形之间并不存在在相交,由此仅需判断多边形的其中一个顶点是否在另一个多边形的内外,就可得到多边形之间的包含关系),得到包含当前 inner 多边形 1 的最高层 inner 多边形 2,由此将 inner 多边形 2 记录为开始多边形。
由上可以一个开始多边形的集合ICollection startPolygons
(对于startPolygons
中每个成员在进行第 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 之间没有交点
- a. 更高一层没有未分裂过的
- 3.5 对于
inner polygon
,和outer polygon
的处理情况大体相同,仅在 3.1 中搜索下一层inner polygon
时,搜索最高最左(对于outer polygon
为最低最左)的顶点;3.2 中射线的方向为startEdge.Direction
的方向 (对于outer polygon
为反方向),其余基本相同
- 3.1 若当前
- 重新从全部 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
推荐阅读
- Python+turtle绘制对称图形的示例代码
- 微信小游戏开发实战7:图形的数据验证
- [OpenCV实战]9 使用OpenCV寻找平面图形的质心
- 查找正方形和矩形的周长/周长的程序
- 如何检查给定点位于多边形内部还是外部()
- Canvas|Canvas 线性图形(五)(多边形)
- #yyds干货盘点#探索 CSS Paint API(多边形边框)
- 玩转阿拉善沙漠地形的秘诀是啥(长城炮车主有话说)
- 多边形指令
- 在安卓手机中rem单位border-radius:50%画圆变形的解决方案