geometry - 移动两个多边形以便它们接触边缘的距离

Question

最好在下图中描述。



我需要知道在一个轴(仅 y)上移动引用多边形(以红色显示)的最小距离，以便仅接触另一个多边形。如果它在多边形内，则需要向外移动。

我试图查看一个多边形中的所有线和另一个多边形中的所有点，将点投影到线上，并得到点 y 和投影点 y 之间的差异，然后找到最小距离。但是，这有一个问题，如果多边形重叠并且一个多边形中最远的线和另一个多边形中最远的点的距离最小，则会产生使多边形重叠的结果。

编辑:通过投影线上的点，我的意思是找到线上与原始点具有相同 x 值的点的 y 值。如果 x 值位于线外，则跳过此步骤。

Answer 1

我不确定我是否正确理解了您的建议(什么是“将点投影到线上”？)。

无论如何，我会尝试这个(伪代码)，:

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)

但不幸的是，如果您的多边形是凹的，这可能并不好，这似乎就是这种情况。