algorithm - 算法：按网格切割多边形

Question

我有一个位于二维网格中的多边形：（
假设我能够绘制每条线之间的距离相同的网格）

我现在正在寻找一种算法或某种实现，可以将多边形沿着网格切割成几个较小的多边形。

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)库将在这方面为您提供帮助。这是一个健壮可靠的算法：给它两个多边形并得到两者的交集。所以它并不能完全满足你的要求，但它肯定可以用来解决你的问题。例如迭代每个网格正方形。

Answer 2

请参阅增强几何。也许它可以帮助你。