计算任意形状的重叠区域

Question

我想知道什么是计算Java中两个任意多边形重叠区域的最佳方法。

这里的研究，我这样做的远：

• 我读过区级（从java.awt.geom中）的文档。它似乎并不支持这个选项。
• 我试过看其他类可能支持这个，并在其他类似的场合（例如实现Shape接口的类）提供。他们中没有一个似乎有这个选择。
• 我知道有第三方模块支持这一点，但我正在寻找一个免费许可证用于每种用途（包括商业用途）。

有关多边形更多的细节：

• 唯一的假设对多边形是，他们是“简单” - 即 - 不包含任何漏洞。
• 多边形以坐标列表形式给出。我也有代表它们的Area和GeneralPath对象。

有没有办法在没有下载外部库的情况下在Java中实现这个任务？ 我想到目前为止唯一的解决方案是通过找到边界矩形创建一组内部点，并使用Area的包含函数，然后找到这两个集合的联合。这个解决方案的问题是效率很低。

Answer 1

您需要适合于非凸多边形的多边形裁剪算法。一些已知的算法：

• Vatti's algorithm，可与任意多边形，包括复杂的，在快船库使用

• Weiler-Atherton algorithm

• Greiner-Hormann algorithm，页面有链接到一些实现