计算两个任意形状的并集

Question

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

这些形状以顺时针方式存储为点序列。

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

我一直在阅读维基百科 多边形的布尔运算 其中提到了 扫线算法 但我无法将其与我的目标联系起来，唉，我不是数学家。

我正在使用 ActionScript 3 开发应用程序，但我熟悉 C#、Java，并且可以选择 C ​​和 C++。

Answer 1

正确地执行布尔运算是不平凡的;幸运的是，有库，已经实现此功能。

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

Answer 2

鉴于点（A和B）的两个列表，点击    - [1]中所述的每行做它相交在乙结果，一个线     -.- [2]，如果没有（更多）线相交，不存在重叠，点击     -.- [3]如果在（A）的线相交在B中的行，然后，点击      -.-.- [4]添加交点到输出结果      -.-.- [5]的确从A下一行相交乙结果        -.-。-.- [6]如果没有，此添加到输出（它是内部B）转到5，点击        -.-。-.- [7]如果这样，则相交添加到输出和开关列表A＆B转到2

另请参见交点两条线状。我不会写代码抱歉：）

Answer 3

请参阅也 GPC 。

Answer 4

该算法为你工作？

Answer 5

怎么样：

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

我认为，如果你继续沿着当前的任何形状蜿蜒，寻找交叉点，那就应该达到你想要的效果。我认为这也应该能处理凹形的形状......

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

Answer 6

有似乎也是一个javascript API：

https://github.com/bjornharrtell/jsts/

这似乎实施JTS标准，并具有几个不同的充实现：

http://tsusiatsoftware.net/jts/jts-links.html#ports

所有这些应该能够执行联合等：

http://tsusiatsoftware.net/jts/JTSUser/contents.html

但是csg.js是最令人印象深刻的项目IMO

https://github.com/evanw/csg.js