c++ - 使用 boost 生成一组矩形以在不规则多边形中形成网格

Question

我需要创建一组预定大小的矩形，这些矩形在不规则(可能不是凸)多边形内部形成网格。 (我知道边缘上会有一些不适合矩形的位。这些可以删除。)一切都是二维的，我的点类型是 double 的。我正在处理 UTM 数据，所以我的多边形离原点很远。我必须使用 C++。我有两个问题:

这可以用boost来完成吗？我查看了 Voronoi 图生成器，但在我的多边形内生成矩形点格时遇到了问题。

是否有另一个我可以使用的几何库，它更适合在多边形内生成一组矩形？

Answer 1

我编写了自己的函数来执行此操作。它可能不漂亮，但它确实有效。我首先确定了最高和最低的 x 和 y 值。然后我将它们传递给这个函数并根据常量值定义我的单元格的边界。

using namespace std;

typedef boost::geometry::model::d2::point_xy<double> point_xy;
typedef boost::geometry::model::polygon<point_xy> polygon_type;

vector<polygon_type> createNScells(double nex, double ney, double swx, double swy) {
    vector<polygon_type> cells;

    double x1 = swx;
    double x2 = swx;

    point_xy first;
    point_xy second;
    point_xy third;
    point_xy fourth;

    while (x2 > nex) {//move x's
        x2 -= const1;
        double y1 = ney;
        double y2 = ney;
        while (y2 > swy) {//move y's
            y2 -= const2;
            //assign x's and y's to points
            first.x(x1);
            first.y(y1);
            second.x(x2);
            second.y(y2);
            third.x(x1);
            third.y(y2);
            fourth.x(x2);
            fourth.y(y1);
            polygon_type r;
            //assign points to polygon
            boost::geometry::append(r, first);
            boost::geometry::append(r, third);
            boost::geometry::append(r, second);
            boost::geometry::append(r, fourth);
            boost::geometry::append(r, first);
            cells.push_back(r);

            y1 = y2;
        }
        x1 = x2;
    }
    return cells;
}

const1 和 const2 定义我的单元格的大小。最后，我编写了一个函数来删除不在多边形边界内的单元格。

for (int i = 0; i < cells.size(); ++i) {
    if (!boost::geometry::within(cells.at(i), polygons)) {
        swap(cells.at(i), cells.back());
        cells.pop_back();
    }
}

这当然不是最简洁的解决方案，但我欢迎 boost 代码效率的方法。