什么是计算在列表的两个点的最大距离的最有效的方式是什么？ [英] What is the most efficient way to calculate the maximum distance of two points in a list?
问题描述
我有一个列表→分（X，Y）和平常的欧氏距离测量
I have a list L of points (x, y) and the usual euclidean distance measure
我如何找到最远距离两分在这个名单？或者，更正式的：我要如何找到
How do I find the maximum distance two points have in this list? Or, more formally: How do I find
要解决这个问题，最简单的方法似乎是尝试一切：
The simplest way to solve this problem seems to be to try everything:
def find_max_dist(L):
max_dist = d(L[0], L[1])
for i in range(0, len(L)-1):
for j in range(i+1, len(L):
max_dist = max(d(L[i], L[j]), max_dist)
return max_dist
为使计算速度更快，我可以用在循环的平方距离，并返回根在最后。
To make computation faster, I can use the squared distance in the loops and return the root at the end.
该方法具有运行时间复杂度
ñ是列表→的lenght。 （和恒定的空间复杂度）。
This approach has a run time complexity of where n is the lenght of the list L. (And a constant space complexity).
显然，不能有任何的算法，比O（n）的速度更快，因为人们必须寻找至少一次在列表中的每个元素。
Obviously, there cannot be any algorithm that is faster than O(n), as one has to look at least once at every element in the list.
最高距离将是凸包的元件之间。但很容易证明凸包的计算是至少在为O（n log n）的和格雷厄姆的扫描似乎做它。但找到复杂的船体后，我还是要得到的最大距离。因此，我将结束与
The highest distance will be between elements of the convex hull. But it is easy to prove that the computation of the convex hull is at least in O(n log n) and Graham's scan seems to do it. But after finding the complex hull I still have to get the maximum distance. So I would end up with
def find_max_dist_graham_triv(L):
H = Graham_scan(L)
return find_max_dist(L)
现在，这是一个点，我不知道。我想，一方面可以提高该像这样：
Now, this is a point where I am not sure. I think one can improve this like so:
def find_max_dist_graham_c1(L):
H = Graham_scan(L) # Get ordered list of convex hull points
max_dist = d(L[0], L[1])
for i in range(0, len(L)-1):
loop_max_dist = 0
for j in range(i+1, len(L):
curr_dist = d(L[i], L[j])
if curr_dist < loop_max_dist:
break
loop_max_dist = curr_dist
max_dist = max(loop_max_dist, max_dist)
return max_dist
我们的想法是，当你把一分一凸包和与其相邻的点开始，对角线不断增加，到最大值，然后继续下降。我不知道如果这是真的，虽然。
The idea is that when you take one point of a convex hull and start from its neighboring point, the diagonals keep increasing, get to a maximum and then keep decreasing. I'm not sure if this is true, though.
直觉上，我将继续提高算法：只要第一个内部循环结束后，我们找到了最长对角线的循环。这对角线分隔两间断会将所有的船体点。每一个较长的对角线必须从这两个组的组成分（改正）：
Intuitively, I would continue to improve the algorithm: As soon as the first inner loop finishes, we found a "longest diagonal" of that loop. This diagonal separates all other hull points in two disjunct sets. Every longer diagonal has to consist of points from both of those sets (correct?):
def find_max_dist_graham_c1(L):
H = Graham_scan(L) # Get ordered list of convex hull points
max_dist = d(L[0], L[1]) # Get a fist idea what the longest distance might be
i = 0
p1 = L[i] # Grab a random point
loop_max_dist = 0
for j in range(1, len(L):
curr_dist = d(L[i], L[j])
if curr_dist < loop_max_dist:
break
loop_max_dist = curr_dist
max_dist = max(loop_max_dist, max_dist)
# Every diagonal that is longer than the best one found with L[0]
# has to have points in both of the following two sets (correct?):
# [1...j] and [j+1...len(L)]
# Try to find a neighboring diagonal that is longer.
change = True
while change:
change = False
if d(L[i-1], L[j+1]) > max_dist:
max_dist = d(L[i-1], L[j+1])
i -= 1
j += 1
change = True
elif d(L[i+1], L[j-1]) > max_dist:
max_dist = d(L[i+1], L[j-1])
i += 1
j -= 1
change = True
return max_dist
在凸包的每个点P对凸包，使得PQ的最长对角线包括P.不过是那么P也是端点最长对角线的Q点Q？
Every point P on the convex hull has a point Q on the convex hull such that PQ is the longest diagonal including P. But is then P also the "endpoint" for the longest diagonal of Q?
我真的不知道，如果这个算法是正确的。这将是为O（n log n）的。
I am really not sure if this algorithm is correct. It would be in O(n log n).
我想这个问题很好分析，所以可能有人请留一些注意事项是什么？
I guess the problem is well analyzed, so could somebody please leave some notes for that?
虽然我有很多的子问题的主要问题是：
Although I had a lot of sub-questions the main question is:
什么是一个有效的方式找到点列表点的最大距离是多少？
推荐答案
您应该看看上旋转卡钳（<一href="http://en.wikipedia.org/wiki/Rotating_calipers">http://en.wikipedia.org/wiki/Rotating_calipers) - 他们广泛用于那样的问题。 另外，你的假设是错误的。对于固定点的 P 上的凸多边形：对角可以先增加，后减小，再增大，然后再次下降。至少，我有一个情况下，发生这种情况。
You should look up on Rotating calipers(http://en.wikipedia.org/wiki/Rotating_calipers) - they're widely used for that kind of problems. Also, your assumption is wrong. For a fixed point p on the convex polygon: the diagonal can first increase, then decrease, then increase, and then decrease again. At least, I've got a case where this happens.
一个启发式的方法也：选择一个点的 X 。查找它的最远点的是。查找是的最远点的以Z 。 D（Z，Y）是一个很好的估计。
A heuristic approach also: select a point x. Find the furthest point y from it. Find the furthest point z from y. d(z,y) is a good estimation.
这说明对角线的图像：
1> 2：增加; 2-> 3递减; 3-> 4增加; 4-> 5下降。图中可能并不precise，移动点3和4点到一点更远离P（在同一行）。
1->2: increasing; 2->3 decreasing; 3->4 increasing; 4->5 decreasing. The figure may not be precise, move the points that 3 and 4 point to a bit further away from p (on the same line).
这篇关于什么是计算在列表的两个点的最大距离的最有效的方式是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
