凸包中点之间的最大距离
Maximum distance between points in a convex hull
我正在解决一个问题,我需要找到平面 (2D) 上两点之间的最大距离。所以有一种 O(n^2) 方法,我可以在其中计算平面中每个点之间的距离图。我还实现了一个凸包算法,现在我的方法是在 O(nlogn) 中计算凸包,然后使用 O(n^2) 算法计算凸包中点之间的最大距离。有没有比这更好的方法来计算凸包中的最大距离
这是我的算法:
O(n^2)
def d(l1,l2):
return ((l2[0]-l1[0])**2+(l2[1]-l1[1])**2)
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
convex hull
def convex_hull(points):
"""Computes the convex hull of a set of 2D points.
Input: an iterable sequence of (x, y) pairs representing the points.
Output: a list of vertices of the convex hull in counter-clockwise order,
starting from the vertex with the lexicographically smallest coordinates.
Implements Andrew's monotone chain algorithm. O(n log n) complexity.
"""
# Sort the points lexicographically (tuples are compared lexicographically).
# Remove duplicates to detect the case we have just one unique point.
points = sorted(set(points))
# Boring case: no points or a single point, possibly repeated multiple times.
if len(points) <= 1:
return points
# 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
# Returns a positive value, if OAB makes a counter-clockwise turn,
# negative for clockwise turn, and zero if the points are collinear.
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
# Build lower hull
lower = []
for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
# Build upper hull
upper = []
for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
# Concatenation of the lower and upper hulls gives the convex hull.
# Last point of each list is omitted because it is repeated at the beginning of the other list.
return lower[:-1] + upper[:-1]
overall algorithm
l=[]
for i in xrange(int(raw_input())): # takes input denoting number of points in the plane
n=tuple(int(i) for i in raw_input().split()) #takes each point and makes a tuple
l.append(n) # appends to n
if len(l)>=10:
print find_max_dist(convex_hull(l))
else:
print find_max_dist(l)
现在我该如何改进我的方法的 运行 时间,是否有更好的计算方法?
一旦有了凸包,就可以在线性时间内找到两个最远的点。
想法是保留两个指针:一个指向当前边(并且总是递增一个),另一个指向一个顶点。
答案是边的端点与所有边的顶点之间的最大距离。
可以证明(证明既不短也不琐碎,所以我不会在这里post)如果我们在移动第一个指针后每次都继续递增第二个指针,只要它增加通过边和顶点的线之间的距离,我们将找到最佳答案。
我正在解决一个问题,我需要找到平面 (2D) 上两点之间的最大距离。所以有一种 O(n^2) 方法,我可以在其中计算平面中每个点之间的距离图。我还实现了一个凸包算法,现在我的方法是在 O(nlogn) 中计算凸包,然后使用 O(n^2) 算法计算凸包中点之间的最大距离。有没有比这更好的方法来计算凸包中的最大距离
这是我的算法:
O(n^2)
def d(l1,l2):
return ((l2[0]-l1[0])**2+(l2[1]-l1[1])**2)
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
convex hull
def convex_hull(points):
"""Computes the convex hull of a set of 2D points.
Input: an iterable sequence of (x, y) pairs representing the points.
Output: a list of vertices of the convex hull in counter-clockwise order,
starting from the vertex with the lexicographically smallest coordinates.
Implements Andrew's monotone chain algorithm. O(n log n) complexity.
"""
# Sort the points lexicographically (tuples are compared lexicographically).
# Remove duplicates to detect the case we have just one unique point.
points = sorted(set(points))
# Boring case: no points or a single point, possibly repeated multiple times.
if len(points) <= 1:
return points
# 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
# Returns a positive value, if OAB makes a counter-clockwise turn,
# negative for clockwise turn, and zero if the points are collinear.
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
# Build lower hull
lower = []
for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
# Build upper hull
upper = []
for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
# Concatenation of the lower and upper hulls gives the convex hull.
# Last point of each list is omitted because it is repeated at the beginning of the other list.
return lower[:-1] + upper[:-1]
overall algorithm
l=[]
for i in xrange(int(raw_input())): # takes input denoting number of points in the plane
n=tuple(int(i) for i in raw_input().split()) #takes each point and makes a tuple
l.append(n) # appends to n
if len(l)>=10:
print find_max_dist(convex_hull(l))
else:
print find_max_dist(l)
现在我该如何改进我的方法的 运行 时间,是否有更好的计算方法?
一旦有了凸包,就可以在线性时间内找到两个最远的点。
想法是保留两个指针:一个指向当前边(并且总是递增一个),另一个指向一个顶点。
答案是边的端点与所有边的顶点之间的最大距离。
可以证明(证明既不短也不琐碎,所以我不会在这里post)如果我们在移动第一个指针后每次都继续递增第二个指针,只要它增加通过边和顶点的线之间的距离,我们将找到最佳答案。