使用 Boost Polygon 的减法结果不正确
Incorrect subtract result using Boost Polygon
我有以下两个输入多边形,我想为其计算减去的多边形:
甲:
* (0, 8)
/ \
/ \
/ \
(-3, 0) *-------* (3, 0)
乙:
(-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,因为它提供多边形锁孔破裂支持。
回答我自己的问题...
Boost Polygon 在编写时考虑了整数数据类型。来自文档:
In general a data type should define std::numeric_limits and be integer-like. Floating point coordinate types are not supported by all the algorithms and generally not suitable for use with the library at present (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)
上添加一个新顶点,从中进入 'keyhole polygon'。它可以为此创建的整数网格位置上的最佳顶点位于 (0, 8)
。所以结果代表一个近似值。
确实,为算法提供类似的输入,三角形边上存在一个好的候选顶点确实会产生正确的输出。例如,一个这样的输入三角形是 (-4, 0) - (4, 0) - (0, 8)
.
我认为这是锁眼压裂算法的局限性。
我有以下两个输入多边形,我想为其计算减去的多边形:
甲:
* (0, 8)
/ \
/ \
/ \
(-3, 0) *-------* (3, 0)
乙:
(-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,因为它提供多边形锁孔破裂支持。
回答我自己的问题...
Boost Polygon 在编写时考虑了整数数据类型。来自文档:
In general a data type should define std::numeric_limits and be integer-like. Floating point coordinate types are not supported by all the algorithms and generally not suitable for use with the library at present (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)
上添加一个新顶点,从中进入 'keyhole polygon'。它可以为此创建的整数网格位置上的最佳顶点位于 (0, 8)
。所以结果代表一个近似值。
确实,为算法提供类似的输入,三角形边上存在一个好的候选顶点确实会产生正确的输出。例如,一个这样的输入三角形是 (-4, 0) - (4, 0) - (0, 8)
.
我认为这是锁眼压裂算法的局限性。