I have a Boost Polygon made like this :

Polygon2D create_polygon(Point2D const& p1, Point2D const& p2, Point2D const& p3, Point2D const& p4) {
    return {{p1, p2, p3, p4, p1}};
}

int main() {
    auto const& polygon = create_polygon({0., 0.}, {0., 4.}, {7., 4.}, {7., 0.});
    return 0;
}

(not exactly my code but really similar and a lot more simple so i think it's better to understand).

And basically, i want to divide my polygon into regions and get a random coordinate (x & y) from each region (or just select specific regions). Something like this :

Of course i know it's not going to be square, because a polygon is not everytime simple like this.

Do boost c have a specific "algorithm" or tool used to divide a Polygon into areas without impacting the whole Polygon ?

I have read that voronoi can do something similar to that, but when i'm looking to the example (https://www.boost.org/doc/libs/1_59_0/libs/polygon/doc/voronoi_main.htm) it's not really looking good for my problem.

Or maybe another "famous" algorithm can do something similar without the use of boost c ?

The requirement about regions are :

• We don't need a specific numbers of regions. The polygon can change size and form so it's more simple without "limits".
• If we can have regions with equal areas, it's better (but not mandatory, if an algorithm exists without a perfect equality, but a good repartition of areas, it's ok for me).

CodePudding user response：

If you only want to use the subdivision to get the random points in your polygon, you can avoid that by combining the idea of marching squares with Monte Carlo:

1. Take the bounding box of your polygon and divide it into squares of equal size.
2. For each square, determine if it is wholly or partially inside the polygon.
3. Generate random points inside each square until you find one inside the polygon.