12

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

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

在尝试了解该库但未获得预期结果后,我发现该库仅适用于整数坐标。一开始我以为这是对输入的限制,但实际上所有内部操作和输出都是整数,这使得所有输出都非常古怪,例如多边形的交点略有变形(因为顶点的坐标必须是整数)。

主页上的引用(强调我的):

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

起初我认为这是精确和不精确表示之间的问题,所以我试图让它与理性(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 采用了这种方法。连续空间中的问题应适当缩放。

4

3 回答 3

3

它没有被遗弃。

是的,它被(很多)人使用。

它所做的一件事似乎拥有稳固的用户群,例如 Voronoi 图和相关算法。你也可以在 SO 上找到很多关于这个的问题,所以你可以去看看他们用它做什么。

奖励答案

您甚至可以使用组合库

#include <boost/geometry/geometries/adapted/boost_polygon.hpp>
于 2015-07-15T17:03:50.067 回答
2

由于公认的答案是 6 年,我认为值得指出的是,虽然图书馆并没有完全放弃,但它肯定会朝着这个方向发展,并且坚定地处于维护模式。

在撰写本文时,最近的合并拉取请求已超过 1 年。

于 2021-06-25T17:38:32.527 回答
2

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

它是开发出来的,并且仍在英特尔使用。

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

于 2021-12-24T00:51:32.753 回答