python - 找到一条直线上的最大等距点

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

为了克服这个问题，我创建了一个 O(n*n) 解决方案，方法是使用 2 个循环进行迭代，并找到任意 2 点之间的最小距离的频率:

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

如果你想把点按顺序排列，你不需要按与任何东西的距离对它们进行排序。你可以直接按照默认的字典顺序排序，这与沿线的顺序一致:

lop.sort()

现在你只需要弄清楚如何找到最大的等距点集。这可能会很棘手，尤其是在允许跳过点的情况下。