GC友好的凸裁剪（联合和差异）算法

Question

我正在寻找将基于另一个凸多边形切割我的凸多边形的算法。它将用于可破坏的地形（差异）和用于在2D地图中创建地形（联合）。

算法必须是垃圾收集器友好的，唯一需要的布尔操作是Union &差异。

我已经做了一些研究，并且有一些github项目，但它们都会或多或少产生一些垃圾。

https://github.com/tmpvar/2d-polygon-boolean

https://github.com/w8r/GreinerHormann

我想最好的解决办法是学习的其中一个，并重新让自己的路。但也许你听说过一些适合我的需求？

谢谢。

Answer 1

这个问题涉及到两个子问题

1. 找到两个轮廓

2. 加入该每亩要连接的顶点之间的交叉点。

对于1.您可以利用凸性：将两个多边形看作两个单调链。当你同时通过两个双链的链条时，比如说增加x，当纵坐标在两个横坐标之间相交时，就可以检测到交叉点。

对于2.注意到联合或差异是由轮廓的一部分在一个多边形和另一个多边形之间交替的部分组成，在每个间隔点处。

请注意，在差异的情况下，可能有几个断开连接件。

我想，你可以在所有（但对于输出多边形）实现这一点没有任何分配/释放。