跳到主要内容

Boost.Geometry

阅读量

0

阅读人次

0

介绍​

Boost.Geometry(又名通用几何库，GGL)是Boost C++库的一部分，它定义了解决几何问题的概念，原语和算法。

Boost.Geometry包含基于概念，元函数和标签分发的不可知尺寸，可坐标系不可伸缩的可扩展内核。在该内核之上，构建了算法：面积，长度，周长，质心，凸包，交点（剪切），内部（多边形中的点），距离，包络（边界框），简化，变换等等。该库支持高精度算术数，例如ttmath。

Boost.Geometry包含可实例化的几何类，但库用户也可以使用自己的类。使用注册宏或特征类，可以调整其几何形状以实现Boost.Geometry概念。

Boost.Geometry可能会在所有几何都起作用的领域中使用：制图和GIS，游戏开发，计算机图形和widgets，机器人技术，天文学等。核心被设计为尽可能通用并支持那些域。目前，开发主要是面向GIS的。

该库遵循现有约定：

  • boost惯例
  • std库中的约定
  • 规范和名称来自OGC的一种几何标准，更具体地说是来自OGC简单特征规范

该库最初与Boost 1.47.0一起发布，从那时起，它正式成为Boost C ++库的一部分。

Boost打包的发行版中包含源代码的最新稳定版本。也可以从Boost GitHub存储库（主分支）下载。

上游的库开发可从Boost.Geometry（开发分支）获得。

请注意，库扩展名并未在Boost的正式发行版中分发，而仅在Boost.Geometry（开发分支）中可用，并且它们可能会发生变化。

Boost.Geometry在2009年11月28日被Boost接受（审查报告）。

有一个Boost.Geometry邮件列表。邮件列表及其消息也可以从Nabble作为Boost Geometry访问。还在Boost开发人员列表和Boost用户列表中讨论了Boost.Geometry。

汇编​

设计原理​

假设您需要一个C++程序来计算两点之间的距离。 您可以定义一个结构：

struct mypoint {
    double x, y;
};

和一个包含该算法的函数：

double distance(mypoint const& a, mypoint const& b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

很简单，它是可用的，但不是通用的。 对于库，必须进一步设计。上面的设计仅可用于笛卡尔坐标系中的2D点，mypoint结构体。 通用库应该能够计算距离：

  • 对于任何点类或结构，不仅限于此mypoint类型
  • 在两个以上的维度
  • 用于其他坐标系，例如在地球上或在球体上
  • 点和线之间或其他几何组合之间
  • 比双精度更高
  • 避免平方根：通常我们不想这样做，因为它是一个相对开销比较大的函数，并且比较距离来说，它不重要。

在本节及以下各节中，我们将逐步使设计更加通用。

使用模板​

distance函数可以更改为模板函数。 这很简单，可以计算除mypoint以外的其他点类型之间的距离。 我们添加了两个模板参数，允许输入两种不同的点类型。

template <typename P1, typename P2>
double distance(P1 const& a, P2 const& b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return std::sqrt(dx * dx + dy * dy);
}

此模板版本稍好一些，但不多。

考虑一个成员变量受保护的C++类。此类不允许直接访问x和y成员。 因此，本段很短，我们继续。

使用Traits​

我们需要采用通用方法，并允许将任何点类型用作distance函数的输入。 代替访问x和y成员，我们将使用traits system添加一些levels of indirection。 该函数将变为：

template <typename P1, typename P2>
double distance(P1 const& a, P2 const& b) {
    double dx = get<0>(a) - get<0>(b);
    double dy = get<1>(a) - get<1>(b);
    return std::sqrt(dx * dx + dy * dy);
}

这种经过调整的distance函数使用通用的get函数(将维度作为模板参数)来访问点的坐标。 这将转至traits system，定义如下：

namespace traits {
    template <typename P, int D>
    struct access {};
}

然后专门用于我们的mypoint类型，实现一个称为get的静态方法：

namespace traits {
    template <>
    struct access<mypoint, 0> {
        static double get(mypoint const& p) {
            return p.x;
        }
    };
    // same for 1: p.y
    ...
}

调用traits::access<mypoint,0>::get(a)现在返回我们的x坐标。 很好，不是吗？ 对于库中经常使用的此类函数而言，它太冗长了。 我们可以通过添加一个额外的free函数来缩短语法：

template <int D, typename P>
inline double get(P const& p) {
    return traits::access<P, D>::get(p);
}

这使我们能够为具有trait::access特化的任何point调用get<0>(a)，如本段开头的distance算法所示。 因此，我们希望使用x()之类的方法来启用类，并且只要访问结构具有特殊化，该类具有静态get函数(对于维度0，返回x()，对于1和y()类似)，就可以支持它们。

维度不可知论​

现在我们可以计算2D点，任何结构或类的点之间的距离。 但是，我们也希望拥有3D。 因此，我们必须使其与尺寸无关。 这使我们的距离函数变得复杂。 我们可以使用for循环遍历维度，但是for循环具有比最初存在的简单坐标添加功能更高的性能。 但是，我们可以更多地使用模板，并使distance算法如下所示，虽然更复杂，但对模板迷很有吸引力：

template <typename P1, typename P2, int D>
struct pythagoras {
    static double apply(P1 const& a, P2 const& b) {
        double d = get<D-1>(a) - get<D-1>(b);
        return d * d + pythagoras<P1, P2, D-1>::apply(a, b);
    }
};

template <typename P1, typename P2 >
struct pythagoras<P1, P2, 0> {
    static double apply(P1 const&, P2 const&) {
        return 0;
    }
};

distance函数正在调用pythagoras结构，并指定维数：

template <typename P1, typename P2>
double distance(P1 const& a, P2 const& b)
{
    BOOST_STATIC_ASSERT(( dimension<P1>::value == dimension<P2>::value ));

    return sqrt(pythagoras<P1, P2, dimension<P1>::value>::apply(a, b));
}

引用的维度是使用另一个特征类定义的：

namespace traits
{
    template <typename P>
    struct dimension {};
}

总结​

在此设计原理中，Boost.Geometry是使用tag dispatching，概念，特征(traits)和元编程逐步设计的。 我们使用了众所周知的distance函数来展示设计。

Boost.Geometry的设计如此处所述，具有更多的技术，例如自动反转模板参数，标记强制转换以及将实现类或调度类重用作为其他调度类中的策略。

快速开始​

本“快速入门”部分以带注释的相对简单的代码片段的形式展示了Boost.Geometry的某些功能。

下面的代码假定包含boost/geometry.hpp，并使用命名空间boost::geometry。 Boost.Geometry仅是头文件，因此包含头文件就足够了。 没有与任何库的链接。

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

using namespace boost::geometry;

笛卡尔坐标系(直角坐标系)​

仅使用库的一小部分。 例如：两点之间的距离是一个常见的用例。 Boost.Geometry可以根据各种类型进行计算。 使用自己的一种类型：

model::d2::point_xy<int> p1(1, 1), p2(2, 2);
std::cout << "Distance p1-p2 is: " << distance(p1, p2) << std::endl;

如果包含正确的头文件并且类型绑定到坐标系，则可以将其他各种类型用作点：普通C数组，Boost.Array，Boost.Tuple，Boost.Fusion导入的结构，您自己的类...

注册和使用C数组：

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

BOOST_GEOMETRY_REGISTER_C_ARRAY_CS(cs::cartesian)
int a[2] = {1,1};
int b[2] = {2,3};
double d = distance(a, b);
std::cout << "Distance a-b is: " << d << std::endl;

另一个常用的算法是多边形中点。 它在Boost.Geometry中的内部名称下实现。 我们在这里通过检查位于填充有C数组点对的多边形内的Boost.Tuple（作为点）来显示其用法。

但是首先需要注册一个Boost.Tuple，就像注册C数组那样：

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

BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)
double points[][2] = {{2.0, 1.3}, {4.1, 3.0}, {5.3, 2.6}, {2.9, 0.7}, {2.0, 1.3}};
model::polygon<model::d2::point_xy<double> > poly;
append(poly, points);
boost::tuple<double, double> p = boost::make_tuple(3.7, 2.0);
std::cout << "Point p is in polygon? " << std::boolalpha << within(p, poly) << std::endl;

我们可以计算出多边形的面积：

std::cout << "Area: " << area(poly) << std::endl;

通过模板库的性质，可以混合point类型。 我们再次使用C数组点和Boost.Tuple点来计算距离：

double d2 = distance(a, p);
std::cout << "Distance a-p is: " << d2 << std::endl;

上面列出的snippets生成以下输出：

Distance p1-p2 is: 1.41421
Distance a-b is: 2.23607
Point p is in polygon? true
Area: 3.015
Distance a-p is: 2.87924

非笛卡尔坐标系​

也可以使用非笛卡尔点。 例如：球体上的点。 然后，使用距离之类的算法时，库会“检查”它正在处理球形点，并计算球体上的距离，而不是应用勾股定理。

Boost.Geometry支持地理坐标系(geographical coordinate system)，但这是扩展，不在当前的Boost版本中发布。

我们将地球近似为一个球体，并计算阿姆斯特丹和巴黎之间的距离：

typedef boost::geometry::model::point
    <
        double, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree>
    > spherical_point;

spherical_point amsterdam(4.90, 52.37);
spherical_point paris(2.35, 48.86);

double const earth_radius = 3959; // miles
std::cout << "Distance in miles: " << distance(amsterdam, paris) * earth_radius << std::endl;

它输出：

Distance in miles: 267.02

Adapted 结构体​

最后是一个完全不同的领域的示例：开发基于窗口的应用程序，例如使用QtWidgets。 一旦在Boost.Geometry中注册了Qt类，我们就可以使用它们。 例如，我们可以检查两个矩形是否重叠，如果重叠，则将第二个矩形移到另一个位置：

QRect r1(100, 200, 15, 15);
QRect r2(110, 210, 20, 20);
if (overlaps(r1, r2)) {
    assign_values(r2, 200, 300, 220, 320);
}

空间索引​

介绍​

Boost.Geometry.Index旨在收集称为空间索引的数据结构，该数据结构可用于加速在空间中搜索对象。 通常，空间索引存储几何对象的表示，并允许搜索占据某个空间或接近空间中某个点的对象。

当前，仅实现一个空间索引-R树。

R-tree​

R-tree是用于空间搜索的树数据结构。 它是由Antonin Guttman在1984年提出的，它是B树在多维数据上的扩展。 它可以用于存储点或体积数据，以执行空间查询。 例如，此查询可能返回位于某个区域内或接近空间中某个点的对象。 可以插入新对象或删除已存储的对象。

下图显示了R-tree结构。 每个R-tree的节点都存储一个框，描述其子节点所占用的空间。 在结构的底部，有包含值（几何对象表示形式）的叶节点。

R-tree是一种自平衡数据结构。平衡算法的关键部分是节点拆分算法。每种算法都会产生不同的拆分，因此对于每个拆分树，其内部结构可能会有所不同。通常，更复杂的算法可以更好地分析元素，并产生更少的重叠节点。在搜索过程中，必须遍历较少的节点才能找到所需的对象。另一方面，更复杂的分析需要更多时间。通常，更快的插入将导致搜索变慢，反之亦然。 R树的性能取决于平衡算法，参数和插入到容器中的数据。

此外，还有创建包含一些对象的R-tree的算法。这项技术称为批量加载，是通过使用打包算法[5] [6]完成的。此方法速度更快，并导致R树具有更好的内部结构。这意味着查询性能得到提高。

下面介绍了使用不同算法和示例性操作时间创建的树的结构示例。

快速开始​

本快速入门部分显示了创建典型R-tree和执行空间查询的简单方法。

下面的代码假定包含以下文件并使用了命名空间。

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>

#include <boost/geometry/index/rtree.hpp>

// to store queries results
#include <vector>

// just for output
#include <iostream>
#include <boost/foreach.hpp>

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

通常，您将存储例如std::pair<Box，MyGeometryId>在R-tree中。 MyGeometryId将是存储在其他容器中的复杂Geometry的某些标识符，例如 存储在vector中或环列表的迭代器中的多边形的索引类型。 为了使定义值变得简单，我们将使用预定义的Box和unsigned int。

typedef bg::model::point<float, 2, bg::cs::cartesian> point;
typedef bg::model::box<point> box;
typedef std::pair<box, unsigned> value;

可以使用各种算法和参数来创建R-tree。 您应该选择最适合自己目的的算法。 在此示例中，我们将使用二次算法。 参数作为模板参数传递。 节点中的最大元素数设置为16。

// create the rtree using default constructor
bgi::rtree< value, bgi::quadratic<16> > rtree;

通常，将例如从循环生成值。 存储在其他容器中的多边形。 在这种情况下，可能会使用geometry::envelope()函数创建Box对象。 但是为了简单起见，我们只需要手动生成一些框，然后使用insert()方法将它们插入R树即可。

// create some values
for ( unsigned i = 0 ; i < 10 ; ++i ) {
    // create a box
    box b(point(i + 0.0f, i + 0.0f), point(i + 0.5f, i + 0.5f));
    // insert new value
    rtree.insert(std::make_pair(b, i));
}

可以执行各种类型的空间查询，甚至可以在一个呼叫中将它们组合在一起。 为了简单起见，我们使用默认值。 以下查询返回与框相交的值。 未指定结果中的值顺序。

// find values intersecting some area defined by a box
box query_box(point(0, 0), point(5, 5));
std::vector<value> result_s;
rtree.query(bgi::intersects(query_box), std::back_inserter(result_s));

其他类型的查询是k最近邻居搜索。 它返回最接近空间中某个点的一些值。 默认的knn查询可以如下执行。 未指定结果中的值顺序。

// find 5 nearest values to a point
std::vector<value> result_n;
rtree.query(bgi::nearest(point(0, 0), 5), std::back_inserter(result_n));

最后，我们将打印结果。

// display results
std::cout << "spatial query box:" << std::endl;
std::cout << bg::wkt<box>(query_box) << std::endl;
std::cout << "spatial query result:" << std::endl;
BOOST_FOREACH(value const& v, result_s)
    std::cout << bg::wkt<box>(v.first) << " - " << v.second << std::endl;

std::cout << "knn query point:" << std::endl;
std::cout << bg::wkt<point>(point(0, 0)) << std::endl;
std::cout << "knn query result:" << std::endl;
BOOST_FOREACH(value const& v, result_n)
    std::cout << bg::wkt<box>(v.first) << " - " << v.second << std::endl;

有关更多​

有关R-tree实现，其他算法和查询的更多信息，可以在本文档的其他部分找到。

创建和修改​

查询​

例子​

参考​

访问功能​

适应模型​

算法(Algorithms)​

算术(Arithmetic)​

概念​

常数​

坐标系​

核心元功能​

DE-9IM​

枚举​

例外情况​

IO（输入/输出）​

迭代器​

楷模​

空间指数​

SRS​

策略​

观看次数​

参考矩阵​

参考字母索引​

例子​

示例：调整旧的几何对象模型​

示例源代码：调整旧式几何对象模型​

发行说明​

关于本文档​

致谢​

最后由 amass 于 更新