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?
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.