給定情況下的散列函數是什麼？

在二維平面中給出了一個點，我想要計算最大共線點，因爲我計算了所有可能的線斜率和它們的截距。爲了解決這個問題，我試圖建立一個哈希表，但我無法找到一個哈希函數，通過它我可以輕鬆地將所有共線點指向一個哈希鍵。那麼請幫我找出適合這種情況的散列函數？給定情況下的散列函數是什麼？

來源

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

給定情況下的散列函數是什麼？

回答

相關問題