基于角平分线法的凸与非凸多边形精确缩放算法（An Accurate Scaling Algorithm for Convex and Non-convex Polygons Based on the Angle Bisector Method）

《Array》：An Accurate Scaling Algorithm for Convex and Non-convex Polygons Based on the Angle Bisector Method

　　

摘要：本文提出一种基于角平分线（angular bisector）的凸与非凸多边形精确偏移算法，称为ABO（Angular Bisector Offset，角平分线偏移）算法。该算法通过计算相邻边的单位向量及其叉积（cross product）判断顶点凹凸性，并根据缩放方向（内缩或外扩）沿角平分线方向定位新顶点，实现复杂多边形轮廓的等距缩放。针对外扩过程中可能出现的边自相交（edge self-intersection）问题，算法引入了基于平面图（planar graph）与外边界搜索的拓扑修复机制，通过交点检测与顶点替换确保输出多边形的简单性与拓扑一致性。对于含曲边图形，采用等误差直线逼近法（equal-error line approximation method）进行离散化以扩展算法适用性。实验结果表明，ABO算法在保持几何精度与拓扑结构方面优于传统方法，适用于CAD/CAM、GIS缓冲区分析（buffer zone analysis）及机器人路径规划等领域，为凸与非凸多边形的精确缩放提供了统一、高效且鲁棒的解决方案。

论文解读：《基于角平分线法的凸与非凸多边形精确缩放算法——ABO算法研究》

一、研究背景与意义

多边形缩放（polygon scaling / offsetting，亦称offset或缓冲buffer分析）是计算机辅助设计（CAD/CG）、数控加工（CNC toolpath generation）、地理信息系统（GIS buffer zone analysis）及机器人运动规划（configuration space computation）中的基础几何操作。现有主流方法如直骨架法（straight-skeleton algorithm）在处理含弧或非凸多边形时计算复杂且易产生事件管理困难；凸分解法（convex decomposition）将非凸多边形拆分后分别偏移再合并，依赖分解质量且易引入合并误差；距离场法存在量化误差。此外，传统角平分线法在外扩大距离时易产生全局自相交导致拓扑退化，且缺乏统一的凹凸顶点位移方向框架。因此，亟需一种能统一处理凸与非凸多边形、保持几何等距精度、主动修复外扩自相交且计算高效的二维通用算法。该论文发表于《Array》，提出了ABO（Angular Bisector Offset）算法以解决上述问题。

二、主要关键技术方法

研究人员采用以下关键技术开展研究：(1) 基于二维向量叉积（cross product）符号统计的顶点凹凸性（convexity/concavity）自动判别法——遍历所有顶点叉积符号，以多数符号定义凸/凹属性；(2) 角平分线（angle bisector）单位向量计算与新顶点定位公式——依据内外缩方向及凹凸性决定沿角平分线或其反向偏移距离d/sin(θ/2)得新顶点（θ为内角）；(3) 外扩自相交检测与拓扑修复——计算初步偏移多边形边两两相交点，将边在交点处打断构建平面图（planar graph），求各交点集凸包（convex hull）中心，以最小转角法则追踪外边界（outer boundary）替换自交环；(4) 等误差直线逼近法（equal-error line approximation）对曲线段离散为折线，保证给定公差ε内拟合精度。实验以含凹凸特征原始多边形及三组合成复杂模型（交替凹凸窄缝、多级台阶凹口、含圆弧边界）为对象，设梯度偏移距做内缩/外扩测试，并与枚举四顶点凸四边形算法对比运行时间。

三、研究结果

3.1. Vertex convexity and non-convexity detection algorithm（顶点凹凸性检测算法）

通过对多边形各相邻边向量e_i-1=V_i-1-V_i与e_i+1=V_i+1-V_i作二维叉积(e_i-1×e_i+1)_z=x₁y₂-y₁x₂，统计全顶点叉积正负号数量，以占多数的符号对应凸顶点（convex vertex），少数对应凹顶点（concave vertex）。该方法具O(n)线性复杂度，无需反三角函数，实现简洁。

3.2. Detection and processing of edge self-intersection（边自相交检测与处理）

外扩初步连接新顶点若形成自交，则枚举所有非邻接边对求交点集I，在原边于I处打断插入交点得新边集构成平面图。计算I的凸包及各边邻接关系，取凸包中心为参考点，从任一外端边出发按同绕向（顺/逆时针）选取邻点发出边中夹角最小的边进行深度优先追踪，提取最外层闭合边界即为修复后偏移多边形，剔除内部自交环。

3.3. Curve Discretization Processing（曲线离散化处理）

以起始点为圆心、允许误差ε为半径作圆，求该圆与待近似曲线的公切线，过起始点作公切线平行线交曲线于下一点，迭代至曲线终点，实现变步长等误差折线化，为ABO提供纯线段输入。

3.4. The overall framework of the ABO algorithm（ABO算法整体框架）

步骤包括：顶点排序与方向标准化（鞋带公式Shoelace formula判定向）、曲线段等误差离散化插入序列、逐顶点算邻边单位向量u_prev、u_next及内角θ=arccos(u_prev·u_next)、角平分线单位向量b?=(u_prev+u_next)/|u_prev+u_next|)；凹凸性判定；新顶点位置P'_i=P_i±(d/sin(θ/2))·b?（凸顶点外扩取负号内缩取正号，凹顶点反之）；外扩时调自相交修复模块；顺序连接新顶点输出偏移多边形。内缩最大允许距离为各顶点到对边最小距离之最小值以防过缩自交。

3.5. Experimental Results and Analysis（实验结果与分析）

• •
  Inward Offset Experiment（内缩实验）：原始含凹凸多边形设d=3内缩，各边与原边严格等距，凸顶点沿b?内移、凹顶点沿-b?内移，轮廓均匀收缩无畸变无自交。
• •
  Non-self-intersecting outward offset experiment（无非自交外扩实验）：d=8外扩，凸顶点反b?外移、凹顶点沿b?外移，形状比例保持，无局部扭曲。
• •
  Self-intersecting outward offset experiment（自交外扩实验）：增大d至触发自交，ABO自动检测交点、打断边、追踪外边界剔除内环，输出拓扑连贯简单多边形。
• •
  Complex Case Experiments（复杂案例实验）：对交替凹凸窄缝模型（最小内角35°，狭缝宽=平均边长1/5）、多级台阶凹模型及含圆弧边界模型（先等误差离散化），分别做内缩0.5/0.8与外扩0.5/0.8/2.0/2.3，ABO均保持拓扑连续、几何保真，无断裂或退化，验证对极端非正交及含弧边界的适应性。
• •
  Algorithm Complexity（算法复杂度）：内缩需算顶点到各边距为O(n2)，外扩含自交处理最坏O(n2)平均接近O(n)，远低于对比凸四边形枚举算法的O(n?)。n=100时ABO外扩耗时约0.19s，n=200仍可行，对比算法n=100已达1.38s且更大规模不可行。

四、讨论与结论总结（Conclusion部分翻译与归纳）

研究人员提出ABO算法——一种基于角平分线与顶点凹凸性判别的统一凸与非凸多边形等距缩放算法。其主要优势在于较传统方法能更有效保留原始形状特征与拓扑结构，兼具更高几何精度、拓扑鲁棒性及计算效率。当前局限为尚未内建外扩时自相交的快速预检测机制。未来可将ABO应用于移动机器人在复杂二维环境中生成更精确非凸障碍物安全膨胀区（clearance zone），以及扩展至三维多边形网格（polygonal mesh）的保拓扑缩放。实验证实ABO为CAD/CAM、GIS缓冲区分析及增材制造路径规划中的高精度几何处理提供了理论支撑与工程工具。