c++ - 矩形多边形的布尔运算

Question

Avast 那里的程序员同胞！

我有以下问题：

我有两个重叠的矩形，如下图所示。

替代文字

我想找出由点 ABCDEF 组成的多边形。

替代圣诞节描述：红色饼干切割器正在切掉一点黑色饼干。我想计算黑色饼干。

每个矩形是一个具有 4 个二维顶点的数据结构。

实现这一目标的最佳算法是什么？

score 5 · Accepted Answer

这是一般 2D 多边形裁剪的一个特例。Weiler-Atherton 算法是一个很好的起点。维基百科有一个摘要和原始论文的链接。该算法似乎与您描述的数据结构非常匹配。

请注意，您很可能最终会得到一个带有孔的矩形（如果红色的完全在黑色的内部）或什至两个矩形（例如，如果红色比黑色更高更瘦）。如果您确定黑色矩形内只有红色矩形的一个角，那么解决方案应该简单得多。

score 2 · Accepted Answer

2

于 2008-12-22T15:05:59.493 回答

score 2 · Accepted Answer

坐标有多精确？如果矩形相当小，最简单的方法可能是在画布上绘制它们，首先是黑色矩形，然后是红色。画布上剩余的黑色像素是剩下的多边形。

另一种方法是根据矩形的所有边将坐标网格拆分为一堆矩形（不计算无界矩形，如果您有两个原始矩形，则最多生成 9 个矩形）。然后只需测试每个矩形中的一个代表点是否属于特定多边形，以确定哪些矩形在其中，哪些在外面。

score 0 · Accepted Answer

我在这里找到了一些我可能会用到的东西：

在发布这个问题之前，我实际上已经下载了 CGAL 源代码，但我想我会仔细研究一下。

4 回答 4