У меня есть следующие два входных полигона, для которых я хочу вычислить вычтенный полигон:
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, я как-то неправильно использую библиотеку или мне чего-то не хватает?
Некоторая дополнительная информация:
double
вместо int
не решает проблему.Отвечая на мой собственный вопрос …
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)
,
Я рассматриваю это как ограничение алгоритма разрыва замочной скважины.
Других решений пока нет …