寻求可约束多边形边为特定倾角且最小化边长面积变化的算法

我希望对多边形进行简化处理，使其达到美观的视觉效果，具体要求如下：

• 将多边形的边调整为仅具有特定倾角，如0°、45°、90°等；
• 尽可能减小边长的变化幅度；
• 不添加或删除顶点，仅允许移动顶点位置。

该需求类似于部分编辑工具中点吸附至特定位置与角度的功能。我想了解是否已存在实现此类功能的算法；若不存在，是否可通过线性规划或二次规划来求解——即通过移动顶点固定边的倾角，同时最小化多边形的边长变化量与面积变化量？

已存在的相关算法 #

1. 角度约束型顶点吸附算法 #

这是图形编辑工具中“角度吸附”功能的核心逻辑延伸：先为每条边指定允许的倾角集合（0°、45°、90°等），然后针对每个顶点，计算其在满足相邻两边角度约束的前提下，距离原顶点最近的可行位置。这种方法计算速度快，适合实时交互场景，但属于局部优化，可能无法全局平衡边长与面积的变化幅度。

2. CAD约束求解器逻辑 #

不少CAD软件的“约束编辑”模块会用到类似方案：以原多边形的顶点顺序为拓扑约束，为每条边添加角度硬约束，通过局部迭代调整顶点位置，在满足约束的同时最小化顶点位移。这类算法结合了几何约束求解器，能较好兼顾约束满足和原形状保留。

3. 带角度约束的ICP迭代算法 #

将目标形状定义为“满足角度约束的多边形”，可以用带约束的迭代最近点（ICP）算法：每次迭代中，先根据当前顶点位置生成符合角度约束的边方向，再将顶点向原位置投影，逐步收敛到最优解。这种方法适合复杂多边形，但收敛速度依赖初始位置的合理性。

线性/二次规划求解的可行性 #

完全可以用**二次规划（QP）**实现全局优化求解，具体建模思路如下：

1. 变量定义 #

设原多边形顶点为 (P_i = (x_i^0, y_i^0))，调整后的顶点为 (P_i' = (x_i, y_i))，每个顶点的横纵坐标为优化变量。

2. 约束条件 #

• 角度硬约束：对每条边 (P_i'P_{i+1}')（(P_{n+1}'=P_1')），其方向向量必须与预设倾角对应的方向共线，转化为线性约束：
  • 0°边：(y_{i+1} - y_i = 0)
  • 90°边：(x_{i+1} - x_i = 0)
  • 45°边：(x_{i+1} - x_i = y_{i+1} - y_i)
  • -45°边：(x_{i+1} - x_i = -(y_{i+1} - y_i))
• 多边形闭合约束：最后一个顶点调整后需与第一个顶点形成闭合边，满足对应角度约束。

3. 目标函数 #

构建加权二次目标函数，平衡边长变化与面积变化的优先级：
[
\min \sum_{i=1}^n w_1 \cdot (||P_{i+1}' - P_i'|| - ||P_{i+1}^0 - P_i^0||)2 + w_2 \cdot (A' - A⁰⁾2
]
其中：

• (w_1)、(w_2) 为自定义权重，用于调整边长和面积变化的重视程度；
• (A^0) 为原多边形面积，(A') 为调整后面积（可通过鞋带公式表示为顶点坐标的二次函数）。

注意事项 #

• 线性规划（LP）不适合该场景，因为目标函数是二次平方误差形式，QP能更高效处理这类最小化问题；
• 需提前校验角度约束的一致性，避免出现矛盾约束导致无解；
• 可额外添加顶点最大位移约束，防止调整后的形状过度偏离原多边形。

内容的提问来源于stack exchange，提问作者nickponline