给定情况下的散列函数是什么？

在二维平面中给出了一个点，我想要计算最大共线点，因为我计算了所有可能的线斜率和它们的截距。为了解决这个问题，我试图建立一个哈希表，但我无法找到一个哈希函数，通过它我可以轻松地将所有共线点指向一个哈希键。那么请帮我找出适合这种情况的散列函数？给定情况下的散列函数是什么？

来源

2012-06-19 devsda

你想散列每个点到一个int，使它会给你任何其他点的共线性？这似乎不可能。也许你的问题不是很清楚。 –

我简单地通过使用每两个点来计算所有可能的线，并计算斜率和截距。如果对于任何两条线他们的斜率和截距是相同的，我可以说这些点是共线的。 – devsda

是的，但看到我的答案。你不能把这些点联系起来，因为这会造成一些不需要的传递性。看我的编辑。 – gexicide

这是不可能的，因为共线性不是传递性的。也就是说，A B和C位于一条线上（即共线）。因此，A B和C应该得到相同的散列键。接下来，C D和E也位于另一条线上。因此，C D和E也应该得到相同的散列键。因此，A B接收与D和E相同的散列键，这是错误的，因为这些点不共线。

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

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

来源

2012-06-19 08:15:19 gexicide

这给我任何其他方法，以便我可以计算共线点的最大数量。 – devsda

编辑答案，看我最后一段。 – gexicide

为了应对*给我的代码*态度，你很勇敢。 –

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

来源

2012-06-19 12:05:17 PermanentGuest

给定情况下的散列函数是什么？

回答

相关问题