原点を通る直線を想像してください。回転と反射は簡単なので、勾配が 0 から 1 の範囲にあると仮定します。デカルト平面に整数点のグリッドがあります。0 より大きく、線が最も近くを通過する <= D のグリッド ポイントを見つけたい。
簡単なアプローチは、1 .. D の各 x について、線の上と下の点を見つけ、線までの垂直距離を計算することです。これには、最小値を見つけるために 2 x D の比較が必要です。
それは悪くありませんが、log(D) アプローチを考え出そうとしています。ありますか？
同等の問題は、d <= D で最も近い有理数 n / d を見つけることです。
この質問はあなたのものと同等のようです: Finding the closest integer fraction to a given random real
そこで受け入れられた答えは、Farey Sequenceを使用しています。
この興味深いブログ投稿へのリンクもあります。
完全な答えではありませんが、場合によっては最適化します。線の傾きが有理数の場合、繰り返しが発生し、D が分母よりも大きい場合は、より少ないポイントを確認できます。
例: 勾配が 12/17 の場合、原点から 17 点を超える点を見る必要はありません。その後、それが繰り返されます。
もちろん、その例で D < 17 の場合、メリットはありません。
また、勾配がπの場合は運が悪い...