c++ - 与えられた状況に適したハッシュ関数は何ですか？

Question

2次元平面に与えられた点があり、可能なすべての線の傾きとその切片を計算したために、最大の同一線上の点を数えたいと思います。この問題を解決するために、ハッシュテーブルを作成しようとしましたが、1つのハッシュキーですべての同一線上の点を簡単に指すことができるハッシュ関数を見つけることができません。では、このシナリオに適したハッシュ関数を見つけるのを手伝ってください。

Answer 1

共直線性は推移的ではないため、これは不可能です。つまり、ABとCが線上にある（つまり、同一線上にある）とします。したがって、ABとCは同じハッシュキーを取得する必要があります。次に、CDとEも別の行にあります。したがって、CDとEも同じハッシュキーを取得する必要があります。その結果、ABはDおよびEと同じハッシュキーを受け取りますが、これらのポイントは同一線上にないため、これは誤りです。

さらに、共直線性は点のセットで定義されているため、上記の定義はかなりあいまいです。つまり、AとBが同一線上にあるとは言えません（まあ、できますが、2つの点だけを考慮すると、点の各ペアは同一線上にあります）。

できることは、同一線上の点のセットをハッシュマップに保存することです。次に、優れたハッシュ関数は、傾きsと縦座標切片iで構成されます。たとえば、s*31iを使用できます。このハッシュマップを使用して、セットに新しいポイントを追加し、最後にセットのサイズをカウントして回答を取得できます。

Answer 2

また、ハフ変換に基づくアルゴリズムを検討することもできます。ハフ変換を使用すると、特定の傾きと切片（または原点からの線の角度と距離）を持つ線に含まれる点の数を数えることで、画像内の線を検出できます。したがって、特定のケースでは、各距離/角度のペアの投票を2次元マトリックスに格納し、後でこのマトリックスから最大値を取得できます。これにより、同一直線上の点の最大数が得られます。近似を許可すると、単一の値を探す代わりに、値の最大合計を提供する小さな長方形のグリッドを見つけることができます。