python - 数组中两点之间的最长路径

我有一个代码，使用旋转卡尺的算法，用最长的距离定义两个点。
代码在第一行中取点的数目N，然后N次取点的坐标X，Y。之后显示最长距离的长度。
例如：

INPUT
6
1 1
-1 0
-3 -1
-2 -2
2 3
4 -2

OUTPUT
7.0710678119

INPUT
6
2 2
0 -3
5 7
3 3
2 1
-1 1

OUTPUT
4.47213595499958 #my comment: from (3,3) to (5,7)

但也可能有3个或更多点位于一条直线上的情况。
那我该怎么做呢？

from math import *

def rast(x1, x2, y1, y2):
        x = x2-x1
        y = y2-y1
        l = sqrt(pow(fabs(x), 2)+pow(fabs(y), 2));
        return l

def orientation(p,q,r):
    '''Return positive if p-q-r are clockwise, neg if ccw, zero if colinear.'''
    return (q[1]-p[1])*(r[0]-p[0]) - (q[0]-p[0])*(r[1]-p[1])

def hulls(Points):
    '''Graham scan to find upper and lower convex hulls of a set of 2d points.'''
    U = []
    L = []
    Points.sort()
    for p in Points:
        while len(U) > 1 and orientation(U[-2],U[-1],p) <= 0: U.pop()
        while len(L) > 1 and orientation(L[-2],L[-1],p) >= 0: L.pop()
        U.append(p)
        L.append(p)
    return U,L

def rotatingCalipers(Points):
    '''Given a list of 2d points, finds all ways of sandwiching the points
between two parallel lines that touch one point each, and yields the sequence
of pairs of points touched by each pair of lines.'''
    U,L = hulls(Points)
    i = 0
    j = len(L) - 1
    while i < len(U) - 1 or j > 0:
        yield U[i],L[j]

        # if all the way through one side of hull, advance the other side
        if i == len(U) - 1: j -= 1
        elif j == 0: i += 1

        # still points left on both lists, compare slopes of next hull edges
        # being careful to avoid divide-by-zero in slope calculation
        elif (U[i+1][1]-U[i][1])*(L[j][0]-L[j-1][0]) > \
                (L[j][1]-L[j-1][1])*(U[i+1][0]-U[i][0]):
            i += 1
        else: j -= 1

def diameter(Points):
    '''Given a list of 2d points, returns the pair that's farthest apart.'''
    diam,pair = max([((p[0]-q[0])**2 + (p[1]-q[1])**2, (p,q))
                     for p,q in rotatingCalipers(Points)])
    return pair

n=int(input())
dots = []
for i in range(n):
    tmp = [int(j) for j in input().split()]
    dots.append([tmp[0],tmp[1]])
tmp = diameter(dots)
d1,d2=tmp[0],tmp[1]
print(rast(d1[0],d2[0],d1[1],d2[1]))

最佳答案

一旦你做了凸面外壳，你将需要按最长的线排序在我的例子中，你将有红线，在这之后是带箭头的蓝色。

取最长的线（红色）并得到它的角度在凸包的每个点上，检查S和P之间的线是否等于角度。如果是这样，则计算两条线sp和ep的距离，如果其中一条线比蓝线（即最长的线）长，则可以停止。否则，忽略红线，取下一个最长的当没有相等的角度时，你可以停下来。

关于python - 数组中两点之间的最长路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54200451/