Boost Polygon的用途是什么? [英] What is the utility of Boost Polygon?

问题描述

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

This is a question about Boost Polygon (not about Boost Geometry)

最近，我正尝试使用一些几何多边形构造.由于 Boost Geometry (a 库(也处理多边形)在Boost 1.58中不能正常工作，尽管我会尝试

Recently I was trying to play with some geometrical polygon constructions. Since Boost Geometry (a different library which also deals with polygons) is not working circumstantially in Boost 1.58 I though I would give a try to Boost Polygon.

尝试理解该库并没有得到预期的结果后，我发现该库仅适用于整数坐标.最初，我虽然这是输入的限制，但实际上是所有内部输入运算和输出是整数，这使得所有输出都变得很古怪，例如，多边形的相交会稍微变形(因为顶点的坐标必须是整数).

After trying to understand the library and not getting the expected results I discovered that the library only works for integer coordinates. At first I though that this was a limitation for input, but in fact all internal operations and outputs are integers, this makes all output quite quirky, for example, the intersections for polygons are slightly deformed (because the coordinates of vertices have to be integers).

主页上的引号(重点是我的话):

A quote from the main page (emphasis mine):

坐标数据类型是所有数据类型的模板参数， 该库提供的算法，并且预计是不可缺少的. 不支持浮点坐标数据类型 由于(sic) 实现浮点鲁棒性意味着有一组不同的 算法和有关浮动的一般平台特定假设 点表示.

The coordinate data type is a template parameter of all data types and algorithms provided by the library, and is expected to be integral. Floating point coordinate data types are not supported by the algorithms implemented in the library due to the fact that the (sic) achieving floating point robustness implies a different set of algorithms and generally platform specific assumptions about floating point representations.

起初，我虽然认为这是精确表示和不精确表示之间的问题，所以我尝试使其与理性(Boost Rational)类型一起工作(我想出了一个封装合理类来进行编译)，但实际上整数坐标是严格的要求(代码中的某些部分实际上将一个部分相加并相减以构造中间结果).

At first I though that it was a problem between exact and inexact representation so I tried to make it work with rational (Boost Rational) types (I figured out a wrapper rational class to make it compile) but actually the integer coordinates is a strict requirement (There are parts in the code that actually add and substract one to construct intermediate results).

回到整数，我必须使坐标非常大(以整数表示)，以使此离散性问题消失.换句话说，我必须将所有来回标准化.好吧，最后它不是我最初想的那样有用或方便.

Going back to integers, I had to make the coordinates very big (in integer terms) to make this discreteness problem disappear. In other words I have to normalized everything back and forth. Well, at the end it is not very useful or convenient as I originally thought.

我是否缺少有关此库使用的重要信息?

该库用于解决像素化"问题吗?如果将坐标限制为整数，那么该工具有什么用?

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

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

I understand that Computational Geometry with floating-points is very painful, but why this library doesn't even try to be compatible with exact rationals?

有真实的使用示例吗?(本手册很难给出示例)有人在实际使用此库吗?

Are there real examples of use? (The manual is pretty bad at giving examples) Is anyone actually using this library?

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

这是一个如何根据整数坐标显示库的示例:

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

Here it is an example of what happens with integral polygons, If I use small numbers to represent the coordinates the results are not even geometrically consistent. (The two polygons are polygon(-2,0)(2,-2)(6,4)(0,2) and polygon(-5,0)(-1,-2)(3,4)(-3,2))

(请注意所有内容如何倾斜.)

(note how skew everything comes out.)

但是当我将多边形缩放为具有大整数坐标时，结果将变得更加准确(两个多边形分别是polygon(-200,0)(200,-200)(600,400)(0,200)和polygon(-500,0)(-100,-200)(300,400)(-300,200)，这是上述两个多边形的缩放版本.):

But when I scale the polygons to have large integer coordinates the results get more exact (The two polygons are polygon(-200,0)(200,-200)(600,400)(0,200) and polygon(-500,0)(-100,-200)(300,400)(-300,200), scaled versions of the two above.):

我学到了更多的计算几何学，显然，计算几何学的鲁棒性是一个非常困难的问题.策略之一是使用整数算术.看起来Boost.Polygon就采用了这种方法.连续空间中的问题应适当缩放.

I learned a bit more of computational geometry, apparently the robustness of computational geometry is a very difficult problem. One of the strategies is to use integer arithmetic. It looks like Boost.Polygon takes this approach. Problems in continuous space should be scaled appropriately.

推荐答案

它没有被放弃.

是的，(很多)人都在使用它.

Yes it's used by (many) people.

它做的一件事情似乎拥有扎实的用户基础，例如Voronoi图和相关算法.您还可以在SO上找到很多与此有关的问题，因此您可以直接去看看他们的用途.

One thing that it does that seems to have a solid user base is e.g. Voronoi diagrams and related algorithms. You can find a good number of questions about that on SO too, so you could head over to see what they use it for.

奖励答案

您甚至可以使用

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

这篇关于Boost Polygon的用途是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！