如何高效计算一个二维多边形到另一个多边形的投影？

我有两个二维多边形，其中一个尺寸小于等于另一个。需要将较小的多边形投影到较大的多边形上，目前可通过暴力法实现，但希望找到更高效的直接计算方式。

简单场景 #

小多边形b尺寸小于大多边形a，二者的红色顶点是彼此距离最近的顶点，通过这两个顶点确定的投影向量，可以直接找到a上对应的蓝色目标顶点。

复杂场景 #

此时红色顶点确定的投影向量无法直接找到蓝色交点，需要将投影向量调整至接近红色箭头的方向，调整后投影得到的a视觉上小于b。如果以红色顶点的投影向量为基础，在±90度范围内暴力搜索可行方向，耗时过长，希望找到直接计算投影并定位蓝色顶点的方法。

高效计算方案 #

1. 聚焦多边形边的法向量候选集 #

不用在±90度范围暴力采样搜索，而是将候选投影方向限定为两个多边形所有边的单位法向量（含正反方向）：

• 最优投影方向必然会让其中一个多边形的某条边与另一个多边形的边对齐，或是某个顶点落在对方的边上，因此有效方向只需要从这些边的法向量中筛选；
• 候选方向的数量是O(n+m)（n、m分别为两个多边形的顶点数），远少于暴力搜索的采样量，遍历计算每个方向的投影效果即可快速找到符合要求的方向。

2. 利用闵可夫斯基差简化问题 #

• 计算大多边形a与小多边形b的闵可夫斯基差a - b（由所有a的顶点 - b的顶点的集合构成的多边形）；
• 需求中的投影等价于找到向量v，使得b + v完全包含在a内，且满足顶点/边的对齐条件。通过闵可夫斯基差，问题转化为在差多边形的边界上寻找符合条件的向量v，遍历差多边形的边和顶点即可快速定位。

3. 顶点到边的投影匹配验证 #

针对复杂场景中红色顶点投影无效的情况：

• 取小多边形b的红色顶点，计算它到大多边形a所有边的投影点，得到候选的蓝色顶点；
• 同时取大多边形a的红色顶点，计算它到小多边形b所有边的投影点，验证对应的投影向量是否满足整体适配要求；
• 这些候选点的数量为O(n+m)，逐一验证即可，无需暴力搜索角度。

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