algorithm - 特殊方向的多边形分解

Question

我正在寻找一个可以分解多边形的库。我想定义定义多边形应该被分割的方向或线，如下所示：

这样我就得到了小多边形。有人知道支持这个的图书馆吗？

或者有什么想法？

Answer 1

我不确定您使用的是哪种语言。我有一个为我的目的而编写的库，它可以通过给定的线集获得一个完整的分区，并因此返回多边形。它是用 PHP 编写的，称为维度，使用它，您可以像这样解决您的问题：

1. 通过一组线 LineSet_2D 或 Polygon_2D 定义您的多边形
2. 也通过 Line_2D 定义分割线
3. 使用 LineSet_2D 方法 getPolygons 查找所有多边形

我写了一个例子：

//define or polygon. Note that Polygon_2D can also be used
$rPolygon = new LineSet_2D(
    new Line_2D( 0, 3, 1, 1),
    new Line_2D( 1, 1, 3, 0),
    new Line_2D( 3, 0, 1,-1),
    new Line_2D( 1,-1, 0,-3),
    new Line_2D( 0,-3,-1,-1),
    new Line_2D(-1,-1,-3,0),
    new Line_2D(-3, 0,-1, 1),
    new Line_2D(-1, 1, 0, 3)
);
//define partition line set
$rPartition = new LineSet_2D(
    new Line_2D(-1, 1, 1,-1),
    new Line_2D(-1,-1, 1, 1)
);
//result line set:
$rResultSet    = LineSet_2D::createFromArray(array_merge(
    $rPolygon->getLines(), 
    $rPartition->getLines()
));
//for example, dump plain result:
var_dump($rResultSet->getPolygons());

您也可以在此处找到此示例但我认为这不是您问题的确切解决方案，因为我的 LineSet_2D 类将返回所有循环多边形（即不仅是“片段”）。

Answer 2

您正在寻找“多边形切割”布尔运算。你可以用谷歌搜索可用的资源。

一些自己做的队列..对于每条切片线..

1. 找到切片线与多边形边缘的交点。
2. 对于它相交的每条边，将边一分为二。
3. 将分割后的边对应的多边形分割成两个多边形。

对所有多边形执行相同的操作。您将不得不处理特殊情况，例如穿过顶点的分割线等等......