2

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 :

enter image description here

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).
Konat Undoshy
  • 411
  • 3
  • 13
  • What are your requirements concerning regions? Do you want at least a specific number? Do they need to have equal areas? Same question for the points you try to put in these regions. – Botje Jun 08 '22 at 09:10
  • @Botje True, i'm going to update my post with the requirements. But to put it simple, the polygon can be change size, so no, we don't need to have a specific number. For the "equal areas", i really don't know if it's possible. It's probably better to have an equal area for each "region". (But i don't know if it's possible with complex polygons). For the points in my regions, i just need to have random coordinates in the region. I don't have specific requirement about that. – Konat Undoshy Jun 08 '22 at 09:27
  • Perhaps [this question/answer](https://stackoverflow.com/questions/34342038/how-to-triangulate-polygons-in-boost) can put you on the right track – Botje Jun 08 '22 at 09:38

1 Answers1

1

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.
Botje
  • 26,269
  • 3
  • 31
  • 41
  • yes, a lot more simple than what i was doing. But i have a little question here. In case of a square partially in the polygon (i'm using within to check that), you're just ignoring this square ? – Konat Undoshy Jun 08 '22 at 12:33
  • 1
    No, you can generate points for partially-overlapping squares as well. Keep in mind that it might take a large amount of tries before you get a point inside the polygon. I suggest you skip squares where less than 10% is covered by the polygon or where you hit >100 tries. – Botje Jun 08 '22 at 12:38