2

我发现了许多处理通过给定线分割多边形的实现,但我只需要分割一个四边形(具有 4 个顶点的矩形)。

是否有针对此任务优化的算法?简单比性能更重要。

我缩小了 4 种类型的交叉点:

邻近的

线路从一侧进入并从相邻侧离开的位置。
这将生成 1 个具有3 个点的多边形和 1 个具有5 个点的多边形。

邻近的

对面的

线路从一侧进入并从另一侧离开的位置。
这将生成 1 个带有4 个点的多边形和 1 个带有4 个点的多边形。

对面的

对角线对面

线进入一个角落并通过对角离开的地方。
这将生成 1 个具有3 个点的多边形和 1 个具有3 个点的多边形。

对角线对面

对角相邻

线路进入一个角落并从相邻一侧离开的地方。
这将生成 1 个具有3 个点的多边形和 1 个具有4 个点的多边形。

对角相邻

到目前为止,我无法想出一个好的简单算法。

谢谢!

4

1 回答 1

1

很多有效的算法可以通过矩形窗口剪裁一条线。

我已经为我的目的使用了Liang-Barski 之一(查看“外部链接”部分以获得有效实施)

于 2013-01-29T04:35:44.343 回答