Generate set of rectangles to form grid in irregular polygon using boost

Question

I need to create a set of rectangles of a predetermined size that form a grid inside of an irregular (probably not convex) polygon. (I realize there will be bits on the edges that won't fit in a rectangle. Those can just be dropped.) Everything is in 2-dimensions and my point type is a double. I'm working with UTM data so my polygons are nowhere near origin. I have to work with c++. I have two questions:

Can this be done with boost? I looked into the Voronoi diagram builder, but I'm having trouble generating a rectangular lattice of points within my polygon.

Is there another geometry library I can use that's better suited to generating a set of rectangles inside a polygon?

Answer 1

I wrote my own function that does this. It may not be pretty, but it works. I first determined the highest and lowest x and y values. Then I pass those to this function and define the boundaries of my cells based on the constant values.

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 and const2 define the size of my cells. Finally, I wrote a function to remove cells not within the boundaries of my polygon.

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();
    }
}

This is certainly not the neatest solution, but I would welcome ways to improve the efficiency of my code.