Неверный результат вычитания с использованием Boost Polygon

У меня есть следующие два входных полигона, для которых я хочу вычислить вычтенный полигон:

A:

               * (0, 8)
/ \
/   \
/     \
(-3, 0) *-------* (3, 0)

B:

      (-1, 2) *-----* (1, 2)
|     |
(-1, 1) *-----* (1, 1)

Таким образом, я хочу рассчитать A - B, что должно привести к треугольнику с квадратным вырезом. Расчет этого с использованием Boost Polygon приводит к неправильному частичному треугольнику с вырезом. Это трудно рисовать; недостающая часть результирующего треугольника представлена ​​треугольником (3, 0) => (0, 8) => (1, 2), Я использую следующий код для вычисления вычитания:

#include <boost/polygon/polygon.hpp>

namespace bp = boost::polygon;

int main()
{
using Polygon = bp::polygon_data<int>;
using Point = bp::point_data<int>;
using PolygonSet = bp::polygon_set_data<int>;
using SimplePolygons = std::vector<bp::polygon_data<int>>;

using namespace boost::polygon::operators;

Polygon A;
{
std::vector<Point> points{{-3, 0}, {3, 0}, {0, 8}};
bp::set_points(A, points.begin(), points.end());
}

Polygon B;
{
std::vector<Point> points{{-1, 1}, {1, 1}, {1, 2}, {-1, 2}};
bp::set_points(B, points.begin(), points.end());
}

PolygonSet result{A - B};

SimplePolygons simplePolygons;
result.get<SimplePolygons>(simplePolygons);
for (const auto& polygon : simplePolygons)
{
for (const Point& p : polygon)
{
std::cout << '(' << std::to_string(p.x()) << ", " << std::to_string(p.y()) << ")\n";
}
}

return 0;
}

Это печатает следующие последующие точки, составляющие треугольник выреза:

(3, 0)
(1, 2)
(1, 1)
(-1, 1)
(-1, 2)
(1, 2)
(0, 8)
(-3, 0)
(3, 0)

Итак, края (1, 2) => (3, 0) а также (3, 0) => (0, 8) отсутствуют в результате. Верхняя правая часть входного треугольника отсутствует в результате.

Правильный вывод может выглядеть следующим образом:

(3, 0)
(1, 2)
(1, 1)
(-1, 1)
(-1, 2)
(1, 2)
(3, 0)
(0, 8)
(-3, 0)
(3, 0)

Это ошибка в Boost Polygon, я как-то неправильно использую библиотеку или мне чего-то не хватает?

Некоторая дополнительная информация:

  • Я использую GCC 7.2.0, Boost 1.60.0. С тех пор Boost Polygon не обновлялся, поэтому обновление Boost, скорее всего, не поможет.
  • Параметризация типа точки и всех других геометрических типов с использованием double вместо int не решает проблему.
  • Например, расчет вырезов с использованием выровненных по оси прямоугольников работает без проблем.
  • Для моего приложения я хочу использовать Boost Polygon вместо Boost Geometry, потому что он обеспечивает поддержку разрыва многоугольника замочной скважины.

2

Решение

Отвечая на мой собственный вопрос …

Boost Polygon был написан с учетом целочисленных типов данных. Из документации:

В общем случае тип данных должен определять std :: numeric_limits и быть целочисленным. Типы координат с плавающей точкой не поддерживаются всеми алгоритмами и в настоящее время вообще не подходят для использования с библиотекой (http://www.boost.org/doc/libs/1_60_0/libs/polygon/doc/gtl_coordinate_concept.htm)

Я подозревал, что это какая-то проблема точности, которую я не понимаю полностью. Действительно, масштабирование всех входных координат с коэффициентом 1000 например, приводит к правильному многоугольнику:

(3000, 0)
(1000, 5333)
(1000, 2000)
(1000, 1000)
(-1000, 1000)
(-1000, 2000)
(1000, 2000)
(1000, 5333)
(0, 8000)
(-3000, 0)
(3000, 0)

Таким образом, для исходного ввода, кажется, что алгоритм разрыва замочной скважины намеревается добавить новую вершину на ребре (3, 0) -> (0, 8) из которого нужно ввести «многоугольник замочной скважины». Лучшая возможная вершина на целочисленной позиции сетки, которую это может создать для этого, в (0, 8), Таким образом, результат представляет собой приближение.

Действительно, предоставление алгоритма с подобным входом, для которого на ребре треугольника существует хорошая вершина-кандидат, приводит к правильному выводу. Один из таких входных треугольников будет, например, (-4, 0) - (4, 0) - (0, 8),

Я рассматриваю это как ограничение алгоритма разрыва замочной скважины.

2

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

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

По вопросам рекламы [email protected]