什么样的平移使一个二维多边形完全位于另一个多边形内？

Question

给定两个2D多边形，如何计算将第一个带入第二个的最短平移？

1. 假设有一个解决方案（即第一个确实适合第二个）
2. 比起解决方案的完整性，更喜欢简单的算法。例如，如果通过假设形状有一定数量的边、是凹形等来简化算法，那么就做出这些假设

我可以想象一个蛮力解决方案，我首先计算哪些是位于初始多边形之外的违规顶点。然后迭代这些外部顶点，找到最接近每个顶点的边。那我就卡住了。从外部顶点到边缘的每个距离都会产生一个约束（“需要移动”）。然后，我需要解决这个约束系统，以找到满足所有约束的运动，而不会产生任何新的违反。

Answer 1

我不确定这是否是一个普遍的解决方案，但这里至少有一点可以开始：

我们想把绿色的多边形变成红色的多边形。我们使用几种翻译。每个翻译都有一个起点和一个终点。

第一步：起点是绿色多边形中最左边顶点和最右边顶点之间的中点。终点，与红色多边形相同的标准：

步骤2：起点是最高顶点和最低顶点之间的中点。终点，与红色多边形的标准相同：

注意，setps 1

第3步：在红色多边形中找到最靠近绿色多边形边的顶点。你需要对所有这些进行迭代。找到与该边垂直的线：

这并不完美。根据给定的多边形，最好以另一种方式进行：绿色的最近顶点到红色的边。选择最小的距离。

最后，沿该线移动绿色多边形：

如果这种方法不起作用（我相信在某些情况下它会失败），那么你也可以沿着解决问题的直线（红边或垂直线）移动内部多边形。继续前进，直到没有发现问题。