Повысьте полигон: проблема с euclidean_distance

Question

Повысьте полигон: проблема с euclidean_distance

У меня есть следующий код, который должен вычислить евклидово расстояние между двумя прямоугольниками. Я скомпилировал с использованием 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 () в библиотеке многоугольников boost, я увижу это:

  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()? Что я здесь не вижу?

2

boost boost-polygon c++

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Похоже, внутренние вычисления переполнены.
Я не думаю, что это библиотека ошибка, библиотека используется неправильно с базовым (не проверено) 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;

}

Выход:

Что является ожидаемым результатом.

Глядя на код, кажется, что в библиотеке есть ошибка не потому, что она вызывает переполнение, а потому, что внутреннее вычисление приведено к int а не основной общий целочисленный тип данных. Это означает, что, вероятно, даже если вы используете целочисленные целые числа, результаты будут переполнены.

0