在線上查找最大等距點

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() 

現在你只需要弄清楚如何找到最大的一組等距點。這可能會很棘手，特別是如果你被允許跳過點。