Boost Polygon有什么用处?

13

这是一个有关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),是上述两个多边形的缩放版本。)

我其实不知道数值准确性难题的正确答案。或许我稍后会在我的回答中补充。 - sehe
1
是的,它在生产VLSI工作中使用。半导体制造需要精确无误,我们处理的是单个原子和单个电子的极限...虽然在实践中,单原子或单分子仍处于研发的前沿。不过,整数很常见...无论是1微米、1纳米还是1皮米,这取决于下游工具的需求和这些工具所基于的“网格”(例如,光刻扫描仪可能具有干涉仪定位精度达到1埃(1/10纳米)。 - nmz787
@nmz787,好的了解。谢谢你。我现在注意到这个项目是(曾经是?)由英特尔赞助的。这很有道理。 - alfC
3个回答

5

它并没有被放弃。

是的,有(许多)人使用它。

它所做的一件事似乎有一个稳定的用户群,那就是 Voronoi 图和相关算法。在 SO 上可以找到很多关于此的问题,你可以前往查看他们用它来做什么。

额外回答

你甚至可以通过使用

来组合这些库。

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

昨天我创建了标签 boost-polygon,这样我们就可以在SO中开始识别这些问题。如果您发现其他问题,请使用该标签(我只找到了4或5个)。我很困惑Voronoi图(或许多其他功能)对于整数坐标的用途是什么。我有这样的印象,即将所有几何对象缩放到MAX_INT,使用Boost.Polygon并返回原始比例尺。 - alfC
就像我说的那样。我不能确认/否认那个。人们正在使用它,也许那是一个好的开始寻找的地方。我确定我看到了一些似乎没有玩弄的应用程序。我不会固执于这种假设上(我以前没有看到过Boost Polygon这种类型的扩展)。 - sehe
3
谢谢,我添加了一个多边形运算示例并展示了它们如何在设计上表现得奇怪。 - alfC

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

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

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


1
这是一个非常好的见解,使用了“ditto link”。欢迎来到[SO]! - sehe

2

鉴于被接受的答案已经有6年历史,我认为值得指出的是,尽管该库并没有完全被放弃,但它肯定正在朝着这个方向发展,并且牢固地处于维护模式。

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


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接