algorithm - アルゴリズム：グリッドによるポリゴンの切断

Question

2Dグリッドに配置されたポリゴンがあります:(
各線の間の距離が同じであるグリッドをペイントできると仮定しましょう）

私は今、ポリゴンをグリッドに沿っていくつかの小さなポリゴンにカットできるアルゴリズムまたはある種の実装を探しています。

基本的に私がやりたいことを示すC++のサンプルコード：

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...
}

それを行うことができるアルゴリズムまたは実装されたライブラリはありますか？

Answer 1

General Polygon Clipper（GPC）ライブラリがこれに役立ちます。これは堅牢で信頼性の高いアルゴリズムです。2つのポリゴンを指定し、2つの交差点を取得します。したがって、それはあなたが望むことを正確には行いませんが、それは確かにあなたの問題を解決するために使用することができます。たとえば、各グリッドの正方形を繰り返します。

Answer 2

BoostGeometryを参照してください。多分それはあなたを助けます。