Algorithm: Cutting polygon mesh

Question

I have a polygon that is in a 2D grid:
(let's assume that I can draw a grid where the distances between each line are the same)

Now I'm looking for an algorithm or some kind of implementation that could cut a polygon into several smaller polygons along the grid.

Sample C ++ code that basically shows what I want to do:

struct Point2D { double x; double y; } struct Polygon { std::vector<Point2D> points; } /** * givenPolygon is the 'big' polygon which should be divided * gridSize is the distance between the gridlines * return value is a vector of the resulting subpolygons */ std::vector<Polygon> getSubpolygons( Polygon givenPolygon, double gridSize ) { Code here... } 

Are there any algorithms or implemented libraries that could do this?

Answer 1

The General Polygon Clipper (GPC) library will help you with this. This is a reliable and reliable algorithm: give it two polygons and get the intersection of two. Thus, it does not do what you want, but it can certainly be used to solve your problem. For example. iterate over each square of the grid.

Answer 2

See Boost Geometry . Maybe this will help you.