矩形多边形的布尔运算

Question

6

程序员们，注意啦！

我有以下问题：

我有两个矩形如下图所示重叠在一起。

alt text

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

圣诞描述：红色饼干切掉了黑色饼干的一部分。我要计算黑色饼干。

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

哪种算法最好实现这个功能？

- Nailer

多边形是否总是如所示的轴对齐？ - Judge Maygarden

4个回答

2

- Steven A. Lowe

2

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

另一种方法是根据所有矩形的边（不包括无限大矩形）将坐标网格分成一堆矩形。然后只需测试每个这些矩形的一个代表点是否属于特定的多边形，以确定哪些矩形在内部，哪些在外部。

- Yuliy

+1 切成 9 个部分的方法最简单也最快。 - Nils Pipenbrinck

只是一个澄清的说明： "在画布上绘制它们" 可以通过两种方式完成：从图形 API 到画布上，或者在简单的 2-D 数组上绘制。 - Yuliy

0

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

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

- Nailer

1

使用CGAL来做这件事就像用大炮打猎麻雀一样。 - Nils Pipenbrinck

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jblocksom · Accepted Answer

这是一种特殊的二维多边形裁剪。一个好的起点是Weiler-Atherton算法。维基百科有一个概述和原始论文的链接。该算法似乎很好地匹配了您所描述的数据结构。

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