オーバーフローせずに整数平面上のユークリッド距離を近似するには？

Question

私は整数演算のみを持つプラットフォームで作業しています。アプリケーションは地理情報を使用しており、私は（x、y）座標でポイントを表しています。xとyは距離をメートルで測定したものです。 近似として、2点間のユークリッド距離を計算したいと思います。しかし、これを行うには、私は距離を二乗する必要があります.32ビットの整数では、表現できる最大の距離は32キロです。良くない。 私のニーズは1000キロメートルほどです。しかし、私は30メートル以下のスケールで距離を解決できるようにしたいと思っています。

したがって、私の質問ユークリッド距離を計算するにはどうすればよいでしょうか？オーバーフローなしで整数計算を使用して、四角形が1つの単語に収まらない距離では？

ETA：私は距離を計算することができたいと思っていますが、私はそれらを比較することができるために解決するかもしれません。

Answer 1

多分octagonal distance approximationを比較するには十分でしょうか？

やや最新のバージョンはthis article on fast approximate distance functionsです。

Answer 2

私はを遊びの中でのままにして、ユークリッド距離を近似することができます。しかし、距離を比較する場合、この方法は100％の精度を提供します。なぜなら、距離を二乗すると比較は同じになるからです。

高次元空間で最近傍点を検索するときにこのアプローチを使用していたので、私はそれについてかなり確信しています。私のコードと理論はkd-GeRaFで確認できます。