Boost Polygon的用途是什么？

Question

这是一个关于Boost Polygon的问题(不是关于Boost几何)

最近我试图玩一些几何多边形结构.由于Boost Geometry(一个也处理多边形的不同库)在Boost 1.58中不能正常工作我虽然我会尝试Boost Polygon.

在尝试理解库并且没有获得预期结果后,我发现该库仅适用于整数坐标.起初我虽然这是对输入的限制,但事实上所有内部操作和输出都是整数,这使得所有输出都非常古怪,例如,多边形的交点稍微变形(因为顶点的坐标必须是整数) ).

主页引用(强调我的):

坐标数据类型是库提供的所有数据类型和算法的模板参数,并且预期是完整的. 由于实现浮点鲁棒性的(原文如此)意味着不同的算法集和通常关于浮点表示的平台特定假设,因此库中实现的算法不支持浮点坐标数据类型.

起初我认为这是精确和不精确表示之间的问题所以我试图使它与Rational(Boost Rational)类型一起工作(我想出了一个包装器有理类来使它编译)但实际上整数坐标是一个严格的要求(代码中有一些部分实际上添加和减去一个构造中间结果).

回到整数,我不得不使坐标非常大(用整数表示)来使这个离散问题消失.换句话说,我必须来回规范化一切.好吧,最后它不像我原先想的那样有用或方便.

我错过了使用这个库的重要事项吗？

该库是否针对"像素化"问题？如果坐标被限制为整数,有什么用处？

想法是将坐标缩放到非常大的数字,然后在几何应用中重新归一化结果吗？

我知道带有浮点的计算几何是非常痛苦的,但是为什么这个库甚至不试图与精确的理性兼容？

有真正的使用示例吗？(手册非常糟糕,举例)是否有人真正使用这个库？

奖金问题:这是一个废弃的图书馆吗？

---

这是库如何从整数坐标行为的示例:

这里是积分多边形发生的一个例子,如果我用小数来表示坐标,结果甚至几何上都不一致.(这两个多边形是polygon(-2,0)(2,-2)(6,4)(0,2)和polygon(-5,0)(-1,-2)(3,4)(-3,2))

(注意一切都出来了.)

但是,当我将多边形缩放为具有大整数坐标时,结果会更精确(两个多边形是,polygon(-200,0)(200,-200)(600,400)(0,200)以及polygon(-500,0)(-100,-200)(300,400)(-300,200)上面两个的缩放版本.):

---

编辑:我学到了更多的计算几何,显然计算几何的稳健性是一个非常困难的问题.其中一个策略是使用整数运算.看起来像Boost.Polygon采用这种方法.连续空间中的问题应适当缩放.

Answer 1

它没有被遗弃。

是的，它被（很多）人使用。

它所做的一件事似乎拥有坚实的用户基础，例如 Voronoi 图和相关算法。你也可以在 SO 上找到很多关于这方面的问题，所以你可以去看看他们用它做什么。

奖励答案

您甚至可以使用以下方式组合库

#include <boost/geometry/geometries/adapted/boost_polygon.hpp>

Answer 2

Boost 多边形对于半导体制造中的 VLSI（超大规模集成）布局非常有用。boost 多边形页面上甚至还有一个示例。它对于曼哈顿几何形状具有极其良好的性能，并且整数类型足够精确，可以表示几分之一纳米内的芯片设计。整数很重要，因为在芯片设计的整个范围内需要统一的精度，而浮点数随着数字变大而精度降低。

它是由英特尔开发并仍在使用的。

https://www.youtube.com/watch?v=6MGLiIwc1_0&t=205s&ab_channel=nerd_mmccoo