c++ - 对于给定的情况，好的散列函数是什么？

Question

在二维平面中有一个点，我想计算最大共线点，因为我计算了所有可能的线斜率及其截距。为了解决这个问题，我尝试构建一个哈希表，但我无法找到一个哈希函数，通过它我可以轻松地将所有共线点指向一个哈希键。所以帮我找出适合这种情况的哈希函数？

Answer 1

这是不可能的，因为共线性不是传递的。即，假设 AB 和 C 位于一条线上（即共线）。因此，AB 和 C 应该得到相同的哈希键。接下来，CD 和 E 也位于另一条线上。因此，CD 和 E 也应该得到相同的哈希键。因此，AB 接收到与 D 和 E 相同的哈希键，这是错误的，因为这些点不是共线的。

另外，共线性是在点集上定义的，所以我上面的定义比较模糊。即你不能说 A 和 B 是共线的（好吧，你可以，但是如果你只考虑两个点，每对点都是共线的）。

您可以做的是将共线点的集合保存在哈希图中。然后，一个好的散列函数将简单地由斜率 s 和纵坐标截距 i 组成。例如，您可以使用 s * 31i。此哈希图可用于向集合添加新点，并最终计算集合的大小以检索您的答案。

Answer 2

您也可以考虑基于Hough Transform的算法。霍夫变换允许您通过计算落入具有给定斜率和截距（或线与原点的角度和距离）的线中的点数来检测图像中的线。因此，在您的特定情况下，您可以将每个距离/角度对的投票存储在二维矩阵中，然后从该矩阵中获取最大值。这将为您提供最大数量的共线点。如果您允许近似值，那么您可以找到一个小的矩形网格来提供最大的值总和，而不是寻找单个值。