在线上查找最大等距点

Question

我需要一种算法来查找同一线上等距离点的最大数量。

输入：共线点的名单

例如：我的分数可能是

[(1, 1), (1, 2), (1, 3)] 

在这种情况下，我可以做的是那种基于他们从起源和寻找距离点距离顺序。但是，在下面的情况下，该情况失败。所有点都在同一行y=-x+6，并且彼此等距。

[(3, 3), (2, 4), (4, 2), (5, 1), (1, 5)] 

因为所有的点都与原点等距，并且排序顺序可能是任何东西，所以顺序遍历是不可能的。例如，如果最终字典变成这个[(3, 3), (5, 1), (4, 2), (2, 4), (1,5)]，我们最终将计算（3,3）和（5,1）之间的距离，这是不正确的。理想情况下，我想计算最近点之间的距离，因此顺序应该是（1,5），（2,4）。

为了克服这个问题，我通过使用2个循环迭代，并发现最小距离的频率的任何2个点之间产生的O（N * N）溶液：

import sys 
distance_list=[] 
lop=[(1, 3), (2, 4), (3, 5), (4, 6), (10, 12), (11, 13), (12, 14), (13, 15), (14, 16)] 
lop.sort(key=lambda x: x[0]*x[0] + x[1]*x[1]) 
for k in range(0, len(lop)): 
    min_dist=sys.maxint 
    for l in range(0, len(lop)): 
     if k!=l: 
      temp_dist = ((lop[k][0] - lop[l][0])*(lop[k][0] - lop[l][0]) + (lop[k][1] - lop[l][1])*(lop[k][1] - lop[l][1])) 
      min_dist= min(min_dist, temp_dist) 
    distance_list.append(min_dist) 

print distance_list.count (max(distance_list,key=distance_list.count)) 

然而，上述解决方案失败以下测试案例：

[(1, 3), (2, 4), (3, 5), (4, 6), (10, 12), (11, 13), (12, 14), (13, 15), (14, 16)] 

预期的答案应该是：5 但是，我越来越：9

从本质上讲，我不能确保，如何我是否区分包含等距点的2个点集合;在上面的例子中，这将是

[(1, 3), (2, 4), (3, 5), (4, 6)] AND [(10, 12), (11, 13), (12, 14), (13, 15), (14, 16)] 

Answer 1

因为你要连续点的距离，也没有必要计算所有的组合，你只需要计算（P0，P1）的距离（P1，P2 ），（p2，p3）等等，并按照它们的距离值按顺序对这些对进行分组，一旦你完成了这些，你只需要其中最长的序列，这样做就可以实现itertools模块派上用场了

from itertools import groupby, tee, izip 

def pairwise(iterable): 
    "s -> (s0,s1), (s1,s2), (s2, s3), ..." 
    a, b = tee(iterable) 
    next(b, None) 
    return izip(a, b) 

def distance(a,b): 
    ax,ay = a 
    bx,by = b 
    return (ax-bx)**2 + (ay-by)**2 

def longest_seq(points): 
    groups = [ list(g) for k,g in groupby(pairwise(points), lambda p:distance(*p)) ] 
    max_s = max(groups,key=len) # this is a list of pairs [(p0,p1), (p1,p2), (p2,p3),..., (pn-1,pn)] 
    ans = [ p[0] for p in max_s ] 
    ans.append(max_s[-1][-1]) # we need to include the last point manually 
    return ans 

这里goupby功能基团一起连续对具有相同距离的点的，成对是recipe做欲望配对，其余是自我解释。

这里是一个测试

>>> test = [(1, 3), (2, 4), (3, 5), (4, 6), (10, 12), (11, 13), (12, 14), (13, 15), (14, 16)] 
>>> longest_seq(test) 
[(10, 12), (11, 13), (12, 14), (13, 15), (14, 16)] 
>>> 

Answer 2

如果你想把点进行排序，你不需要通过距离任何对它们进行排序。您可以通过默认的字典顺序，这与沿线顺序一致只是对它们进行排序：

lop.sort() 

现在你只需要弄清楚如何找到最大的一组等距点。这可能会很棘手，特别是如果你被允许跳过点。