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。现在，如果我查看 boost 多边形库中 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.6gtl::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 回答