c# - 合并多边形的高效算法

Question

我有一个多边形列表，在这个列表中，一些多边形重叠，或者与其他多边形接触。

我的任务是合并所有相互重叠或接触的多边形。我有一个执行此操作的 union 方法。

最有效的方法是什么？我目前能想到的是遍历多边形列表，检查合并列表以查看该多边形是否已经以某种方式属于合并列表中的多边形之一，如果是，则合并它们，如果不是，则添加此多边形到合并列表的末尾。

再次重复上述步骤几次，确保所有多边形都正确组合。

这种方法看起来很不优雅；有更好的方法吗？

Answer 1

如果边界框/圆还不是 union 方法的一部分，您可以对其进行预测试，但是对于 < 1000 个左右的多边形，您的简单实现似乎没问题，甚至可能是 10000 个，具体取决于它们的复杂程度。之后可以改进的一种方法是将多边形存储在某种空间树中，例如四叉树、kd 树、bsp 树或 R 树。请注意，相对于对它们的操作，将数据放入这些树中往往代价高昂，因此在这种情况下，您将不得不在整个软件中使用它。