移动两个多边形使它们接触边缘的距离

Question

以下图片最能清晰地描述问题：

我需要知道参考多边形（红色）在一个坐标轴上（仅y轴）移动的最小距离，以使其刚好与另一个多边形相接触。如果它在多边形内部，则需要向外移动。

我尝试查看一个多边形中的所有线条和另一个多边形中的所有点，将点投影到直线上，并获取点y和投影点y之间的差异，然后找到最小距离。但是，这个方法有一个问题，即如果多边形重叠，并且一个多边形中最远的线和另一个多边形中最远的点具有最小距离，那么它将给出一种结果，使多边形重叠。

编辑：通过将点投影到直线上，我指的是找到一条线上的一个点的y值，该点具有与原始点相同的x值。如果x值在线的外侧，则跳过此步骤。

- Jacob Parker

---

我建议添加标签“几何”和“计算几何”，以吸引更多读者（我自己无法做到，编辑必须超过10个字符，真烦！） - kebs

所以？你得到了两个答案，但是没有任何评论或点赞？你真的感兴趣吗？你找到了另一个解决方案吗？如果是这样，请做出贡献，你也可以回答自己的问题。 - kebs

Answer 1

你需要在两个多边形的每个顶点处画一条垂线，并确定它与多边形的交点（线/多边形的交点由不相交的间隔组成）。

在给定的垂直线上，计算一个多边形的最高端点与另一个多边形最低端点之间的差值。答案是所有垂直线中最小的差值（可以是负数）。

为了有效地执行此计算，您可以使用扫描线原理：从左到右对所有顶点进行排序，并维护“活动列表”，即与当前垂直线相交的边的列表。当您从一个顶点移到下一个顶点时，将更新此列表。

对于大小为N和M的两个多边形，排序将花费O(N+M)Log(N+M))；然后扫描将花费大约O((N+M)K)，其中K是垂直线与多边形的交点的平均数量，通常是2到4之间的小数字。

- user1196549

Answer 2

我不确定我是否正确理解了您的提议（什么是“将点投影到直线上”？）。

无论如何，我会尝试这样做（伪代码）:

for pA: points of polygon A:
   for sB: segments of polygon B
      compute distance along y-axis d(pA,sB) and store in table
Find minimum distance in table: d1
Proceed as above by reversing A and B: d2
final d = min(d1,d2)

但是不幸的是，如果你的多边形是凹的，这可能并不好用，而这似乎是情况。

- kebs