Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithm: Cutting Polygon by grid

I have a polygon which is located in a 2D grid:
(lets assume I'm able to paint a grid where the distances between each line is the same)

enter image description here

I'm now searching for an algorithm or some sort of implementation which could cut the polygon into several smaller polygons along the grid.

Some example code in C++ which 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 which could do that?

like image 832
MOnsDaR Avatar asked Sep 17 '12 14:09

MOnsDaR


1 Answers

The General Polygon Clipper (GPC) library would help you in this. It's a robust and reliable algorithm: give it two polygons and get the intersection of the two. So it doesn't do exactly what you want, but it can certainly be used to solve your problem. E.g. iterate each grid square.

like image 95
acraig5075 Avatar answered Oct 16 '22 06:10

acraig5075