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

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

所有的

先画部分已完成。这些形状是弧和线的组合。现在，当我要计算这些形状之间的最小距离时，我正面临着问题。使用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的点的集合。

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

代替计算两个设定点之间的最小距离，我们可以通过计算线之间的距离线或线电弧或电弧电弧做它在最优化的方式。通过这种方式，我们可以通过优化的方式计算出最小距离。

来源

2015-09-18 Shiladittya Chakraborty

准备你的数学，然后用Java编写 –

你必须首先做出一些假设，比如你的程序将在什么基础上计算距离，例如。他们的位置，最重要的是你如何在程序中表现这些形状。 – itwasntme

关于如何开始的第一个想法：定义你的形状。 Java代码中的形状如何表示？如果你不能告诉Java代码你的形状，你会如何期待它做任何事情？ – Andreas

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

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

来源

2015-09-18 08:33:58 Nyavro

将两种形状考虑为平面上两组不同的点。然后测量从第一组中的每个点到第二组中的每个点的距离。

为此使用嵌套for循环，并使用坐标几何的距离公式测量距离。

只存储最短距离，如果你想两个点重合的距离。

来源

2015-09-18 09:31:14 CoderBrain

我遵循这个步骤，但由于多边形包含很多点，所以它的执行速度很慢。那么有没有优化的方法来做到这一点？ –

您可以创建二维数组，也可以存储点的图像的哪一半。例如左半边或右半边。然后，您可以只比较第一张图像右侧的左侧和右侧图像的左侧。 – CoderBrain

我已经创建了一个2D二维数组，用于存储两个多边形的所有点。但问题是如何取多边形的一半点，因为多边形可以在任何地方。那么如何得到这组点的恰好最接近的一半呢？ –

对于轮廓A和轮廓B中的每个点，使用距离公式计算斜边：hypot = sqrt（xA-xB）^ 2 +（yA-yB）^ 2）...我正在解决同样的问题问题为一组N个轮廓，所以我会在完成时分享我的代码。

来源

2015-09-24 20:32:15

我已经使用这个公式计算了两个坐标之间的距离。基本上我用两个循环找到两个多边形之间的最小距离，但由于两个多边形有很多点，所以工作很慢。 –

出现同样的问题：可行的临时解决方案可能是使用对象的几何中心。假设物体的长度“物体之间的距离，估计应该保持良好。 –

你有一些示例代码吗？ –

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

回答

相关问题