7

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?

BenMorel
  • 34,448
  • 50
  • 182
  • 322
MOnsDaR
  • 8,401
  • 8
  • 49
  • 70
  • What are you trying to achieve? The mesh libraries used in conjunction with FEM software can do that, but they usually work only with triangular polygons. Also, could you elaborate more on how the grid and grid size affect the polygons? – Klas Lindbäck Sep 17 '12 at 14:27
  • It's about AI-software which is only able to operate on a specific grid cell. I've got a polygon which describes a forest, lake or something other barrier. To fit into the grid-structure I have to divide the big polygon and put the subpolygons into the grid. – MOnsDaR Sep 17 '12 at 14:41
  • So basically you want to map the big polygon onto a number of grid cells? – Klas Lindbäck Sep 17 '12 at 15:09
  • Right, I have to fill the grid cells with smaller polygons which then build up the big one. – MOnsDaR Sep 18 '12 at 06:33

2 Answers2

1

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.

acraig5075
  • 10,588
  • 3
  • 31
  • 50
  • Polygon intersection with the grid cell and the big polygon seems to be a good solution. I'm currently searching which library fits best. Also there is this related question: http://stackoverflow.com/questions/2272179/a-simple-algorithm-for-polygon-intersection – MOnsDaR Sep 18 '12 at 06:59
  • I just found out that Boost::Geometry does exactly what I need (Polygon intersection). I'll now try to implement it that way. Marking your answer as the right answer cause it lead to a solution. – MOnsDaR Sep 18 '12 at 07:32
  • 1
    http://www.boost.org/doc/libs/1_47_0/libs/geometry/doc/html/geometry/reference/algorithms/intersection.html – MOnsDaR Sep 18 '12 at 07:32
0

See Boost Geometry. Maybe it helps you.

user1722155
  • 1