如何高效检测上千个Polygon是否存在重叠？

针对1000+多边形的重叠检测，两两对比的O(n²)复杂度确实会导致性能瓶颈，以下是几个实用的优化方向：

• 空间分区（Spatial Partitioning）
  把布局空间划分成网格、四叉树或R树这类分区结构，让每个多边形只和同一分区/相邻分区的多边形做碰撞检测，避免全量遍历。比如用网格分区：先计算每个多边形覆盖的网格单元，后续仅检查同网格及邻接网格内的多边形，对比次数能从50万级（1000*999/2）降到每个多边形最多几十次，效率提升明显。

• 边界盒预过滤（Bounding Box Pre-filter）
  先给每个多边形生成最小外接矩形（MBR），优先对比边界盒是否重叠——只有边界盒相交的多边形，才进行后续精确的多边形相交检测。边界盒碰撞计算是简单的矩形坐标对比，速度远快于多边形相交，能快速排除绝大多数不重叠的无效对比。

• 并行计算（Parallel Computing）
  利用CPU多核特性拆分任务：把多边形分成若干组，分配到不同线程/进程并行处理。比如用Python的multiprocessing模块，或C++的OpenMP，将1000个多边形拆成4组并行检测，能把耗时压缩到接近单线程的1/4（忽略调度开销）。

• 多边形简化（Polygon Simplification）
  如果检测精度要求允许，先用道格拉斯-普克算法简化多边形顶点数量。比如把50个顶点的多边形简化为10个顶点，多边形相交计算的复杂度会大幅降低，且基本不影响重叠判断的准确性。

• 增量检测模式
  如果是分批添加多边形的场景，无需每次全量检测：只将新加入的多边形与已存在的多边形做对比，或维护一个重叠对集合，仅更新与新多边形相关的检测结果，避免重复计算。

内容的提问来源于stack exchange，提问作者user17862830