如何高效过滤重叠圆形？保留异色彩重叠圆形、删除无重叠或同色重叠圆形

核心判断逻辑 #

要保留的圆形满足存在至少1个颜色不同的其他圆形和自身重叠，满足以下任一条件的圆形直接删除：

• 没有和任何其他圆形重叠
• 所有重叠的圆形颜色都和自身相同

性能优化核心 #

因为数据量大，绝对不能用O(n²)的两两暴力匹配，用R树空间索引先圈定每个圆形邻域内的候选匹配对象，把时间复杂度降到O(n log n)量级，百万级数据也可以在分钟级处理完。

代码实现 #

依赖geopandas和shapely，两个库的空间计算底层都是C实现，性能远高于纯Python手写逻辑：

import geopandas as gpd
from shapely.geometry import Point

# 加载你的原始数据，替换这部分即可，单条数据结构：(圆心x, 圆心y, 半径r, 颜色标签)
raw_circles = [
    (1.0, 2.0, 0.5, "red"),
    (1.2, 2.1, 0.5, "blue"),
    (3.0, 4.0, 0.5, "red"),
    (3.1, 4.1, 0.5, "red"),
    (5.0, 6.0, 0.3, "green")
]

# 构造空间数据对象
gdf = gpd.GeoDataFrame(
    raw_circles,
    columns=["x", "y", "r", "color"],
    geometry=[Point(x, y).buffer(r) for x, y, r, _ in raw_circles]
)

# 构建R树空间索引
space_index = gdf.sindex

keep = [False] * len(gdf)

for idx, circle in gdf.iterrows():
    # 快速查询和当前圆形边界相交的所有其他圆形索引，过滤掉99%以上不相关的对象
    candidate_idx = list(space_index.intersection(circle.geometry.bounds))
    candidate_idx = [i for i in candidate_idx if i != idx]
    if not candidate_idx:
        continue
    # 仅对候选对象做精确重叠+颜色判断
    has_cross_overlap = any(
        gdf.loc[cid, "color"] != circle["color"] and 
        gdf.loc[cid, "geometry"].intersects(circle.geometry)
        for cid in candidate_idx
    )
    if has_cross_overlap:
        keep[idx] = True

# 筛选得到最终结果
result = gdf[keep]
# 可以根据需要导出为csv、json等格式
print(result[["x", "y", "r", "color"]])

超大数据量优化方案 #

如果你的数据量超过千万级，可以做进一步优化：

• 先按空间格网做数据分片，每片单独处理，避免全量数据加载到内存
• 用numba对重叠判断逻辑做JIT编译，速度可以提升数十倍
• 分布式场景下可以用Dask-Geopandas做并行计算，支持TB级数据处理

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