问题描述
在我的节目，我有一组点。为了重新调整的，我寻找两个节点相隔最远，然后计算通过该相乘所有坐标，使最大距离等于pdefined一个I定义一些$ P $一个因素。
In my program, I have a set of points. For purposes of rescaling, I am searching for the two nodes that are furthest apart, and then computing a factor by which to multiply all coordinates so that the maximum distance is equal to some predefined one I define.
我使用找到两个点相距最远，然而，问题的，大点的集合，因为它是 0的算法（N ^ 2）;伪code（已经计算出的距离被跳过）：
The algorithm I am using to find the two points furthest apart is, however, problematic for large sets of points, as it is O(n^2); pseudocode (distances that were already calculated are skipped):
for each point in points:
for each other point in points:
if distance between point and other point > max
max = distance between point and other point
有什么快？
推荐答案
如果你只需要规模，而不是确切的点，你可以在O做到这一点（N）与一些误差时间。想想做一个边框的简单情况。计算从所有的点，最大的x，最小y和最大的y的最小x值。这四个数字给你配了1最大误差在你点的最大边界框 - （1 / SQRT（2））约30％。您可以通过添加更多的双方你方减少这种。想想一个八角形的情况下。要计算你有你的旋转坐标系的另一侧的最小值和最大值。
If you just need the scale and not the exact points you can do this in O(n) time with some error margin. Think about the simple case of making a bounding box. Calculate the minimum x value from all the points, the maximum x, the minimum y and the maximum y. These four numbers give you a maximum bounding box around your points with max error of 1 - (1/sqrt(2)) about 30%. You can reduce this by adding more sides to your square. Think about the case of an octagon. To calculate the min and max values for the other sides you have to rotate your coordinate system.
错误VS运行时间打破了这个样子。
Error vs run time breaks down like this.
形状 - 运行时间 - 最大误差
shape - run time - max error
- 广场 - 2N - 30％
- 在八角 - 4N - 16％
- 在16侧 - 8N - 4％
- 32两面 - 16N - 1％
下面的公式为最大的错误，我想出了。
Here's the equation for the max error I came up with.
angle = 180 / sides
max_error = (1 / cos angle) - cos angle
让我知道，如果我要补充是说明这一点。
Let me know if I should add a diagram explaining this.
这篇关于算法发现是相隔最远点 - 为O更好的（N ^ 2）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！