我编写了一个算法，该算法迭代了带有孔的多边形集。算法 n2 的复杂性。算法检查每个多边形与其他多边形的交集。每个对象包含大约 100 到 1000 个点。但是，当处理 50 个对象需要 40 到 200 秒时，我感到害怕。我还需要检查 100,000 个对象。在CGAL中是真的吗？
CGAL中是否有任何加速优化技术？
对于每个多边形，首先计算多边形的所有边界框。如果要检查多边形的交集，首先要检查的是多边形的边界框是否相交。否则，面不能相交。
然后，为了避免所有一对潜在交集的二次计算，我建议你使用以下 CGAL 包来加快计算速度：dD Iso 定向框的相交序列。该包提供了一个函数，可以快速报告所有相交边界框对。然后，对于其中的每一对，您可以验证两个多边形是否确实相交。