算法:通过网格切割多边形

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