标签: boost-polygon

这是一个关于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采用这种方法.连续空间中的问题应适当缩放.

我在SUSE Enterprise Linux 11上使用GCC 4.7.2和Boost 1.58.0.我有以下代码片段,它基本上通过一个多边形列表来计算它们的长度/宽度.当使用带有std :: minmax函数的'auto'关键字时,我看到了奇怪的输出.为了比较,我还声明了第二个变量,其中明确声明了类型(即dim vs dim1).

namespace gtl = boost::polygon;
typedef gtl::polygon_90_data<int> LayoutPolygon;
typedef gtl::rectangle_data<int> LayoutRectangle;
static LayoutFeatureVec
calc_stats(LayoutPolygonSet const& lp)
{
   LayoutFeatureVec v;
   LayoutFeature f;
   LayoutRectangle y;
   for (LayoutPolygon const& p : lp) {
      // Compute bounds.
      gtl::extents(y, p);

      // Get width/length (shorter/longer).
      // FIXME: Why does this not work with auto??
      cout << gtl::delta(y, gtl::HORIZONTAL) << " " << gtl::delta(y, gtl::VERTICAL) << endl;

      auto dim = std::minmax(gtl::delta(y, gtl::HORIZONTAL),
                             gtl::delta(y, gtl::VERTICAL));

      std::pair<int, int> dim1 = …

使用Boost对多边形进行三角测量的最佳方法是什么？

我使用Boost.polygon.

我目前的算法:

1. 从我的多边形顶点计算voronoï图.

2. 为每个单元格边创建一个有向多边形边(这将为每个单元格边创建两个有向多边形边)

3. 迭代所有创建的边以创建三角形(不是微不足道的)

更好的解决方案？

编辑:我刚刚意识到可能以特殊方式遍历单元格直接创建三角形(3个相邻单元格创建一个三角形).

我正在与Boost :: Polygon斗争 - 显然除了我想要的东西之外它可以做任何事情.我有几个边界描述多边形及其孔(在2d空间中).一般来说,我们甚至可以在一个孔(较大的多边形的孔中较小的多边形)或一个多边形中的许多孔中有孔.如果有必要,我可以检查哪个边界描述了一个孔,哪个描述了一个多边形.有时边界是分开的(并且不相互包含),这意味着我们有许多多边形.我想要的是一种方法,它给了我一组简单的,不包含任何孔多边形,它们一起形成输入'多孔'多边形.

有没有一种简单的方法来确定一个点是否在voronoi单元内？

例如,以下代码生成如下图所示的内容:

using namespace boost::polygon;

point_data<int> p1(0, 0);
point_data<int> p2(-10, 10);
point_data<int> p3(-10, -10);
point_data<int> p4(10, -10);
point_data<int> p5(10, 10);

std::vector<point_data<int>> pts = { p1, p2, p3, p4, p5 };
construct_voronoi(pts.begin(), pts.end(), vd);

在这种情况下,我怎样才能知道点(5,5)是否在中心单元内？

我可以从每个单元格中创建一个多边形并找出使用多边形算法中的点,但我很有兴趣知道库提供"免费"的东西.

我需要一个好的(稳健的)算法,用于将一个多边形分成两组(左/右)一个线段.我的多边形表示只是一个整数坐标列表(顺序时钟顺序,从不自相交),线段由起点和终点表示.该线始终在多边形外部开始和结束,即与多边形相交偶数次.

这是一个例子:

算法的输出应该是两组(顺时针行进):

• 左:HABCH,FGDEF
• 右:HCDGH,BAB,FEF

我可以通过迭代多边形并检查多边形线是否穿过线来识别点AH,注意尊重边界情况.我还可以确定每条多线所属的哪一侧.但是,对于我的生活,我不能决定如何将这些片段串在一起.

在你建议使用通用剪辑库之前:我正在使用提升多边形,它非常擅长将多边形相互修剪,但是我没有找到任何可以让你在一个线段上剪切多边形的库,一般来说它是不可能的将线段转换为我可以剪辑的多边形.

编辑:我错过了FEF以及多边形可以在线段两侧都有零件的事实.

我有以下两个输入多边形，我想为其计算减去的多边形：

A：

               * (0, 8)
              / \
             /   \
            /     \
   (-3, 0) *-------* (3, 0)

乙：

      (-1, 2) *-----* (1, 2)
              |     |
      (-1, 1) *-----* (1, 1)

因此，我想计算A - B，这应该会产生一个带有方形切口的三角形。使用 Boost Polygon 计算此结果会导致带有切口的不正确的部分三角形。画起来很难；结果三角形的缺失部分由三角形 表示(3, 0) => (0, 8) => (1, 2)。我使用以下代码来计算减法：

               * (0, 8)
              / \
             /   \
            /     \
   (-3, 0) *-------* (3, 0)

这将打印构成剪切三角形的以下后续点：

(3, 0)
(1, 2)
(1, 1)
(-1, 1)
(-1, 2)
(1, 2)
(0, 8)
(-3, 0)
(3, 0) …

遵循这两个资源:

• 提升基础教程
• 所以问题

我写了一个Delaunay三角剖分boost.如果点坐标是积分的,它可以正常工作(我生成了几个随机测试,但没有观察到错误).但是,如果这些点是非整数的,我会发现许多不正确的三角剖分,边缘缺失或边缘错误.

例如,此图像已使用舍入值构建并且是正确的(请参阅下面的代码)

但是这个图像是用原始值构建的并且不正确(参见下面的代码)

此代码重现了这两个示例(没有显示).

#include <boost/polygon/voronoi.hpp>
using boost::polygon::voronoi_builder;
using boost::polygon::voronoi_diagram;

struct Point
{
  double a;
  double b;
  Point(double x, double y) : a(x), b(y) {}
};

namespace boost
{
  namespace polygon
  {
    template <>
    struct geometry_concept<Point>
    {
      typedef point_concept type;
    };

    template <>
    struct point_traits<Point>
    {
      typedef double coordinate_type;

      static inline coordinate_type get(const Point& point, orientation_2d orient)
      {
        return (orient == HORIZONTAL) ? point.a : point.b;
      }
    };
  }  // polygon
}  // boost

int …

我有处理过的多边形数据.现在我想看看我的处理数据与原始数据的匹配程度.对于此任务,我想使用BOOST的多边形集合运算符.以下代码给了我一个段错误:

#include <iostream>
#include <boost/polygon/polygon.hpp>

using namespace boost::polygon::operators;
using namespace std;

typedef boost::polygon::polygon_data<double> BPolygon;
typedef boost::polygon::polygon_traits<BPolygon>::point_type BPoint;
typedef boost::polygon::polygon_set_data<double> BPolygonSet;
typedef std::vector<BPolygon> BPolygonVec;


double meassureError(BPolygonVec &polys1, BPolygonVec &polys2)
{
  BPolygonSet set1;
  BPolygonSet set2;

  assign(set1, polys1);
  assign(set2, polys2);

  return area(set1 ^ set2);
}

int main(int argc, char *argv[])
{
  BPolygonVec polys1;
  BPolygonVec polys2;

  loadPolysFromFile(polys1);
  loadPolysFromFile(polys2);

  cout << meassureError(polys1, polys2) << endl;
  return 0;
}

GDB输出:

Program received signal SIGSEGV, Segmentation fault.
0x08156ce7 in std::list<boost::polygon::point_data<double>, std::allocator<boost::polygon::point_data<double> > >::begin (this=0x0) at /usr/include/c++/4.8.2/bits/stl_list.h:759
759 …

我正在尝试使用 Boost Polygon 库使两个多边形相交。我从 boost 网站提出的 custom_polygon 示例开始：

http://www.boost.org/doc/libs/1_59_0/libs/polygon/doc/gtl_custom_polygon.htm

在 test_polygon 函数中，我填充了两个多边形。我的问题是是否可以调用 poly1 和 poly2 的交集函数。如果我编译的话，我会得到一长串错误。

#include <boost/polygon/polygon.hpp>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>

#include <list>


// My Point class
class MyPoint {
public:
    double x, y;
};

// MyPolygon as a list of MyPoint
typedef std::list<MyPoint> MyPolygon;



template <>
struct boost::polygon::geometry_concept<MyPoint> {
    typedef point_concept type;
};

template <>
struct boost::polygon::point_traits<MyPoint> {

    typedef double coordinate_type;

    static inline coordinate_type get(const MyPoint& point, boost::polygon::orientation_2d orient) {
        if (orient == boost::polygon::HORIZONTAL)
            return point.x;
        return point.y; …