CODEWITHSUNDEEP
algorithmgridpolygon
MOnsDaR
MOnsDaR

Reputation: 8654

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?

Upvotes: 7

Views: 4056

Answers (2)

user1722155
user1722155

Reputation: 1

See Boost Geometry. Maybe it helps you.

Upvotes: 0

acraig5075
acraig5075

Reputation: 10756

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.

Upvotes: 1

Related Questions