使用Shapely检测椭圆重叠时出现误报问题求助

我正在检测两个椭圆是否重叠，测试所用的200个椭圆本应互不重叠，但使用Shapely库时偶尔会出现随机误报，不清楚原因。相关代码如下：

import numpy as np
from shapely.geometry import LinearRing

def ellipse_polyline(ellipses, n=100):
    t = np.linspace(0, 2*np.pi, n)
    st = np.sin(t)
    ct = np.cos(t)
    result = []
    for x0, y0, a, b, angle in ellipses:
        angle = np.deg2rad(angle)
        sa = np.sin(angle)
        ca = np.cos(angle)
        p = np.empty((n, 2))
        p[:, 0] = x0 + a * ca * ct - b * sa * st
        p[:, 1] = y0 + a * sa * ct + b * ca * st
        result.append(p)

    return result

def overlap(ellipse1, ellipse2):
    ea = LinearRing(ellipse1)
    eb = LinearRing(ellipse2)
    mp = ea.intersects(eb)

    if mp == False:
        C = 0

    if mp == True:
        C = 1

    return C

我曾检查椭圆几何是否为闭合环，使用Shapely的is_closed函数得到的结果均为True。

误报原因分析 #

• 多边形近似误差：当前代码用100个采样点的多边形模拟椭圆，并非真正的椭圆几何。当两个椭圆距离极近时，离散采样点的位置偏差可能让近似多边形产生虚假交点，触发误判。
• 浮点数精度问题：Shapely的几何计算依赖浮点数运算，当两个线性环的边非常接近时，浮点数舍入误差可能导致intersects误判为相交。

解决办法 #

1. 提升采样点数量
   增加ellipse_polyline函数的n参数（比如设为500或1000），让多边形更接近真实椭圆，降低离散近似带来的误差：

   # 调用示例
   ellipses_poly = ellipse_polyline(your_ellipses_list, n=500)
   

2. 添加负缓冲过滤虚假相交
   对线性环做微小的负缓冲，消除因精度问题产生的虚假接触：

   def overlap(ellipse1, ellipse2):
       # 缓冲值根据你的坐标尺度调整，比如1e-6适合小尺度坐标
       ea = LinearRing(ellipse1).buffer(-1e-6)
       eb = LinearRing(ellipse2).buffer(-1e-6)
       return 1 if ea.intersects(eb) else 0
   

3. 使用解析几何直接判断（推荐）
   跳过多边形近似，用解析方法判断两个椭圆是否相交，从根源避免近似误差。比如联立两个椭圆的方程，判断是否存在实根；或者基于分离轴定理（SAT）实现椭圆相交检测。

4. 调整Shapely计算精度
   通过set_precision设置合适的精度阈值，减少浮点数误差带来的误判：

   from shapely.geos import set_precision
   
   def overlap(ellipse1, ellipse2):
       ea = set_precision(LinearRing(ellipse1), 1e-6)
       eb = set_precision(LinearRing(ellipse2), 1e-6)
       return 1 if ea.intersects(eb) else 0
   

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