Polygon - Voronoi - clip to rectangular bounding box

Hello

I am a hobby programmer and I hope to make use of the polygon library to procedurally generate voronoi diagrams for the purpose of defining world maps in a videogame.

My use case includes a requirement that the voronoi diagram be clipped to a rectangular bounding box.  The corollary to this requirement is that every voronoi cell is therefore (as a result of being clipped to the bounding box where necessary) a complete convex polygon.  

By this I mean that an edge must not extend outside the bounding box.  If the edge would extend beyond the bounding box, it must be be clipped to the bounding box creating a new vertex at the intersection of the edge and the bounding box.  I believe there would also need to be a vertex created at each corner of the bounding box.  In order for a voronoi cell to be a complete convex polygon, new edge(s) must be created  which run between the newly created vertices.

My understanding is that the polygon library does not include a method to clip edges to a bounding box.  Do you have any recommendations about how to approach defining a method which does so?

- It should be possible to define the rectangular bounding box dimensions similarly to how points and segments are defined

- For the sake of efficiency I assume it would be appropriate only to consider edges which extend beyond the given bounding box

- While a general solution should probably be able to clip parabolic edges, my use case will likely only involve sites comprised of points (no segments) so a solution clipping straight line edges only would be sufficient for my own purposes

If you have any thoughts I would be very grateful to receive them.  Many thanks in advance.
_______________________________________________
Boost-users mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://lists.boost.org/mailman3/lists/boost-users.lists.boost.org/
Archived at: https://lists.boost.org/archives/list/[email protected]/message/2P35X2L7GJWNRIKQ74BAYCL4JCEAIHDJ/