计算两个任意形状之间的最小距离

Question

我有两个任意形状。现在我想计算两个形状之间的最小距离。这里我附上图片

首先绘制部分完成。这个形状是圆弧和直线的组合。现在，当我要计算这些形状之间的最小距离时，我遇到了问题。使用 GWT (java) html5 canvas 绘制此形状。

为了计算两个形状之间的最小距离，我在java中使用了下面的代码，但我没有得到任何优化的方法来做到这一点 -

private double calculateMinimumDistance(Coordinate[] coordinates_1, Coordinate[] coordinates_2) { 
    double minDistance = 100000;
    double currentDistance = 0;

    for(int i = 0; i < coordinates_1.length; ++i) {
      for(int j = 0; j < coordinates_2.length; ++j) {
        currentDistance = coordinates_1[i].distanceTo(coordinates_2[j]);
        if(currentDistance < minDistance) {
          minDistance = currentDistance;
        }  
      } 
    }

    return minDistance;
}

坐标_1包含形状1的点的集合。
坐标_2包含形状2的点的集合。

有没有优化的方法来计算两个形状之间的距离？这些形状可以是任何地点和任何类型的形状。

我们可以通过计算线到线、线到圆弧或圆弧到圆弧之间的距离来以优化的方式来计算两组点之间的最小距离。这样我们就可以以优化的方式计算出最小距离。

Answer 1

这个想法是将形状表示为顶点列表。然后，为了找到任意形状之间的最小距离，我将实现基本算法来查找两个凸形状之间的距离。然后将任意形状分割成一组不相交的凸形状，计算不同对之间的所有距离并获得最小距离。

要计算两个凸形状之间的距离，只需迭代顶点对的所有组合，计算距离并取最小值。当然，这种方法需要 n^2 次操作，因此您可能需要对其进行优化。您可以使用形状的一些简化形式：例如，将每个形状表示为 8-10 个基本点形状，然后在每个形状上找到最接近另一个形状的边缘，然后搜索边缘内部的点。