math - 计算两个任意形状的并集

Question

我正在开发一个应用程序，我需要能够组合用户绘制的两个重叠的任意形状。这将是对两个形状的联合操作。最终的形状将是两个重叠形状的轮廓。

形状以顺时针方式存储为一系列点。

理想情况下，我想要一个算法，它将采用两个点数组 (x,y) 并返回结果形状的单个数组。

我一直在阅读关于多边形布尔运算的维基百科，其中提到了扫描线算法，但我无法在这与我的目标之间建立联系，唉，我不是数学家。

我正在使用 ActionScript 3 开发应用程序，但我熟悉 C#、Java，我可以通过 C 和 C++ 选择自己的方式。

score 5 · Accepted Answer

正确实现布尔运算并非易事；幸运的是，有些库已经实现了这个功能。

您使用什么语言？如果是 C++，请查看CGAL，即计算几何算法库。

score 3 · Accepted Answer

给定两个点列表（A 和 B）
- [ 1 ] A 中的每条线是否与 B 中的线相交
-.- [2] 如果没有（更多）线相交，则不存在重叠
-.- [3]如果 (A) 中的一条线与 B 中的一条线相交，则
-.-.- [4] 将交点添加到输出中
-.-.- [5] 将 A 中的下一条线与 B 相交
-.-.-。 - [6] 如果不是，则将其添加到输出（在 B 内）转到 5
-.-.-.- [7] 如果是，则将相交添加到输出并切换列表 A 和 B 转到 2

另请参见两条线的交点。对不起，我不会写代码：）

score 3 · Accepted Answer

3

另见GPC。

于 2010-01-27T10:54:22.123 回答

score 2 · Accepted Answer

2

这个算法对你有用吗？

于 2010-01-26T15:10:04.560 回答

score 1 · Accepted Answer

怎么样：

选择两个形状的最左边的点。将该形状称为 A 并使其成为当前形状。
沿着当前形状顺时针旋转到下一个点并检查是否有一条或多条线相交。
- 如果有任何线相交，请找到第一个交点并将其添加到您的新形状中。切换到沿其他形状缠绕。
- 如果没有线相交，则移动到形状 A 中的下一个点，并将其添加为新形状中的点。继续沿当前形状缠绕。
重复步骤 2。

我认为，如果您继续沿着当前的任何形状蜿蜒，寻找交叉点，那应该可以满足您的需求。我认为这也应该处理凹形......

我敢肯定，一旦您掌握了基础知识，您就可以添加很多优化。