algorithm - 找到线段上等距点的最大数量

Question

给定直线段上的一组点。这些点可能位于线上的任何位置。我需要一个算法来定期找到位于线上的最大点数。

例如，在 y = 0 表示的直线上，我可能有一些点，例如:

[3,0], [1,0], [4,0], [7,0],[11,0], [10,0]

Output : 4 
     [1,0] , [4,0], [7,0], [10,0]

示例 2:

[2,1], [2,5], [2,3], [2,7], [2,6]

Output: 4
    [2,1], [2,3],[2,5], [2,7]

[注意:直线可能有任何斜率。我只需要算法的草图。这些点可以被认为存储在二维矩阵中] 请帮忙。

Answer 1

这是一个伪代码的蛮力算法:

for each point X
  for each point Y != X
    find number of connected points from X using the distance between X and Y
  next Y
next X

如何使用 X 和 Y 之间的距离从 X 中找到连接点的数量:

dXY = Y - X
i = 0
while point_exists(X + i * dXY)
  i = i + 1
end while