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

Question

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

首先，绘图部分已完成。这些形状是弧线的组合。现在，当我要计算这些形状之间的最小距离时，我遇到了问题。使用GWT（Java）HTML5画布绘制这些形状。

为了计算两个形状之间的最小距离，我在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;
}

coordinates_1 包含形状1的点集。
coordinates_2 包含形状2的点集。

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

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

- Shiladittya Chakraborty

---

先准备好数学内容，然后用Java编写。 - Suresh Atta

你首先需要做一些假设，比如你的程序将根据什么基础来计算距离，例如它们的位置，最重要的是你将如何在程序中表示这些形状。 - itwasntme

开始的第一个想法：定义你的形状。在Java代码中，形状是如何表示的？如果你不能告诉Java代码关于你的形状，你怎么能指望它做任何事情呢？ - Andreas

可能是寻找轮廓之间的最小距离的重复问题。 - Orace

@Marco13 不是的。这些是一般形状，意味着它们是通过使用moveTo、lineTo和arcTo来绘制的。 - Shiladittya Chakraborty

Answer 1

对于轮廓A和轮廓B中的每个点，请使用距离公式计算斜边长度：hypot=sqrt(xA-xB)^2+(yA-yB)^2)... 我正在解决一组N个轮廓的相同问题，完成后我会分享我的代码。

- David Shaked

---

遇到了同样的问题：可行的临时解决方案可能是使用对象的几何中心。假设对象长度<<对象间距离，则估计值应该很好。 - David Shaked

我正在使用Java，而你却用Python写了所有内容。 - Shiladittya Chakraborty

这种方法可以在许多不同的编程语言中实现。如果您有任何特定问题，请告诉我。 - David Shaked

http://stackoverflow.com/questions/32773476/opencv-minimum-distance-between-arbitrarily-large-sets-of-contours-python - David Shaked

你能否通过Java/GWT访问定义轮廓的所有(x,y)坐标？另外，我很不好意思地问一下，你能发布你的代码吗？我认为我可能足够熟练，可以更好地帮助你。 - David Shaked

Answer 2

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

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

- Nyavro

Answer 3

考虑这两个形状是平面上的两组不同点集。然后测量第一组中每个点到第二组中每个点的距离。

使用嵌套的for循环进行此操作，并使用坐标几何的距离公式来测量距离。

仅存储最短距离，如果您想要两个点与距离重合。

- CoderBrain

---

我按照这些步骤操作了，但由于多边形包含大量点，因此性能较慢。那么有没有优化的方法呢？ - Shiladittya Chakraborty

你可以创建一个二维数组，并存储点所在的图像的哪一半。例如左半部分或右半部分。然后，您可以仅将第一个图像的左侧或右侧点与第二个图像的左侧部分进行比较。 - CoderBrain

我已经创建了一个二维数组，用于存储两个多边形的所有点。但问题是如何获取多边形的一半点，因为多边形可以在任何地方。那么如何获取最接近点集的确切一半呢？ - Shiladittya Chakraborty

将值存储在两个不同的数组中。接下来，对于每个数组找到最左边和最右边的值。然后找到它们的平均值。现在你可以大致知道哪一半是右边，哪一半是左边。 - CoderBrain

Answer 4

使用Imgproc.distanceTransform函数来查找图像中所有点到第一个形状的距离。将结果与第二个形状相交。在结果地图中找到最小的非零值，这就是您的最小距离。

- Felix Pîrvan