矩形多边形上的布尔操作

Question

Avast在那里的程序员！

我有以下问题：

我有两个矩形重叠的像显示在下面的图片。

我想弄清楚由点ABCDEF的多边形。

备用圣诞节描述：红色的饼干切割了一些黑色的饼干。我想计算黑色的饼干。

每个矩形是具有4个2d顶点的数据结构。

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

Answer 1

这是一般的2D多边形裁剪的一种特殊情况。 Weiler-Atherton算法是一个很好的开始。 Wikipedia has a summary和links to the original paper。该算法似乎与您描述的数据结构非常吻合。

请注意，很有可能你会得到一个带有洞的矩形（如果红色的是完全在黑色的里面）或者甚至是两个矩形（例如，如果红色比黑色更高，更瘦）。如果你确定在黑色矩形内只有一个红色矩形的一个角落，那么解决方案应该更简单。

Answer 2

constructive solid geometry

Answer 3

我发现了一些东西在这里我可以使用：

http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html

其实我下载了CGAL源之前，我甚至张贴了这个问题，但我想我会仔细看进去。

Answer 4

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

另一种方法是将坐标网格划分为基于矩形所有边的一组矩形（不包括无限长矩形，如果有两个原始矩形，则最多可生成9个矩形）。然后，只需测试这些矩形中每个矩形的代表点，以获得特定多边形中的成员资格，以确定哪些矩形位于哪个矩形中，哪些矩形位于外面。