c++boostgeometryboost-polygon

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


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?


Solution

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