2

2 つの長方形間のユークリッド距離を計算することになっている次のコードがあります。GCC 4.7.3 と Boost v1.58.0 を使用してコンパイルしました

#include <iostream>
#include <cmath>
#include <boost/polygon/polygon.hpp>
#include <boost/geometry.hpp>

namespace gtl = boost::polygon;
using namespace boost::polygon::operators;

typedef gtl::rectangle_data<int> LayoutRectangle;

int main(int argc, char** argv)
{
    LayoutRectangle t(16740130,29759232,16740350,29760652);
    LayoutRectangle n(16808130,29980632,16808350,29982052);

    std::cout << gtl::euclidean_distance(t, n) << std::endl;

    std::cout << gtl::euclidean_distance(t, n, gtl::HORIZONTAL) << " "
              << gtl::euclidean_distance(t, n, gtl::VERTICAL) << std::endl;

    std::cout << gtl::square_euclidean_distance(t, n) << std::endl;
    std::cout << std::sqrt(gtl::square_euclidean_distance(t, n)) << std::endl;
    std::cout << (int) std::sqrt(gtl::square_euclidean_distance(t, n)) << std::endl;

    return 0;
}

上記のコードは、次の出力を生成しました。

38022.6
67780 219980
52985328800
230185
230185

正解は 230185 です。ブースト ポリゴン ライブラリの euclidean_distance() の実装を見てみると、次のようになります。

  template <typename rectangle_type, typename rectangle_type_2>
  typename enable_if< typename gtl_and_3<y_r_edist2, typename is_rectangle_concept<typename geometry_concept<rectangle_type>::type>::type,
                                                          typename is_rectangle_concept<typename geometry_concept<rectangle_type_2>::type>::type>::type,
                       typename rectangle_distance_type<rectangle_type>::type>::type
  euclidean_distance(const rectangle_type& lvalue, const rectangle_type_2& rvalue) {
    double val = (int)square_euclidean_distance(lvalue, rvalue);
    return std::sqrt(val);
  }

std::sqrt(gtl::square_eclidean_distance(t,n))これは、正しい答え (230185) を与える私のコードの行と同じに見えます。では、なぜ で 38022.6 になるのgtl::euclidean_distance()でしょうか? ここには何が表示されていませんか?

ここに画像の説明を入力

4

1 に答える 1

0

内部計算がオーバーフローしているようです。これはライブラリのバグではないと思います。ライブラリが基になる (チェックされていない)int型で間違って使用されています。(ただし、最後に言及するライブラリには別のバグがあります。)

問題のより小さな「整数表現」を使用してみてください。

例えば：

LayoutRectangle t(167402,297592,167404,297607);
LayoutRectangle n(168082,299806,168084,299821);

残念ながら、整数演算の問題の一般的な解決策はありません。ただし、0) より高い精度を使用すると何かが得られる、1) 問題をスケーリングする、2) 多倍精度を使用する、3) 有理演算と整数部分を使用する、を除きます。

(浮動小数点の場合、解決策は単純にコンポーネントを正規化することです。これは、浮動小数点のオーバーフローを回避する方法std::absです)std::complex<double>

幾何学的問題を表すために大きな整数を使用することは良いことですが、この理由から、回避策として、最大で の距離にわたる (int)std::sqrt((double)std::numeric_limits<int>::max()/2) = 2^15 = 32768座標を使用してください。これは驚くほど少ない数です。

完全なコード:

#include <iostream>
#include <cmath>
#include <boost/polygon/polygon.hpp>
#include <boost/geometry.hpp>

int main(){

namespace gtl = boost::polygon;
using namespace boost::polygon::operators;

typedef gtl::rectangle_data<int> LayoutRectangle;

    LayoutRectangle t(167401,297592,167403,297606);
    LayoutRectangle n(168081,299806,168083,299820);

    std::cout << gtl::euclidean_distance(t, n) << std::endl;

    std::cout << gtl::euclidean_distance(t, n, gtl::HORIZONTAL) << " "
              << gtl::euclidean_distance(t, n, gtl::VERTICAL) << std::endl;

    std::cout << gtl::square_euclidean_distance(t, n) << std::endl;
    std::cout << std::sqrt(gtl::square_euclidean_distance(t, n)) << std::endl;
    std::cout << (int) std::sqrt(gtl::square_euclidean_distance(t, n)) << std::endl;

}

出力：

2302.1
678 2200
5299684
2302.1
2302

これは期待される結果です。

コードを見ると、ライブラリにバグがあるようです。これは、オーバーフローが発生するためではintなく、基になる汎用整数データ型ではなく、内部計算がキャストされるためです。これは、おそらく多倍長整数を使用しても、結果がオーバーフローすることを意味します。

于 2016-08-13T10:07:25.820 に答える