寻求从路径段生成无重叠多边形的图案填充算法

问题核心 #

需要实现这样一个算法：输入定义路径的顶点序列（如v1、v2、v3…）和指定线宽，为每个路径段（如v1→v2）生成对应多边形。核心要求如下：

• 各段多边形绝对不能重叠，若存在重叠风险，需将重叠区域平均分配给涉及的路径段
• 支持将图案经旋转、平移后填充至各段多边形中
• 必须支持斜接、斜角两种线条连接方式，且可设置斜接限制

现有方案的问题 #

已基于Rust完成初步实现，但在部分边缘场景（如锐角转弯、极短线段拼接等）下表现不佳，存在重叠或连接错误的情况。

具体实现思路&建议 #

1. 基础逻辑：路径偏移与顶点衔接 #

每个路径段的多边形本质是对线段做双向偏移（偏移距离为线宽的一半），核心难点在顶点处的衔接处理：

• 斜接连接：计算相邻两段偏移线的交点形成斜接角；当斜接长度超过设定的斜接限制时，自动切换为斜角连接
• 斜角连接：在顶点位置截断两段的偏移线，生成垂直于夹角平分线的截断线段，从根源避免重叠

2. 重叠区域的分配处理 #

当相邻路径段的偏移多边形出现重叠时，以顶点处的夹角平分线为界，将重叠区域平分给前后两段：

• 先计算顶点处的夹角平分线方向
• 以此平分线为边界，分别裁剪前后段的偏移多边形，保留各段所属区域
• 推荐使用Sutherland-Hodgman裁剪算法完成精确裁剪，确保无重叠

3. 边缘场景的特殊处理 #

• 锐角顶点：斜接长度极易超过限制，提前计算夹角大小，当夹角小于阈值时直接使用斜角连接
• 连续同方向线段：直接合并为单段处理，避免不必要的顶点衔接计算
• 极短线段：若线段长度小于线宽，需特殊处理（如生成圆形或方形端点），防止偏移后出现畸形多边形

4. 跨语言参考思路 #

可借鉴成熟矢量图形库的描边逻辑，比如Skia、Cairo的路径描边算法，核心均围绕偏移线计算与交点处理展开。若使用Rust，lyon库（专注2D路径渲染）的描边模块可直接参考，其内置了斜接、斜角连接的处理逻辑及重叠避免机制。

现有Rust代码的优化方向 #

• 增加顶点夹角预计算步骤，提前判断连接方式，避免斜接过长导致的重叠
• 引入多边形裁剪逻辑，在顶点处对相邻段的偏移多边形做精确裁剪
• 补充边缘场景的单元测试，覆盖锐角、极短线段、连续同方向线段等情况

内容的提问来源于stack exchange，提问作者Martin Ždila