Shapely中考虑浮点误差的多边形拓扑等价检测方案咨询

问题背景 #

使用Shapely 2.0.0处理多个shapely.Polygon，需判断其中是否存在矩形（核心逻辑：多边形的最小旋转矩形与自身拓扑等价），但现有方法因浮点误差或拓扑匹配规则限制失效：

尝试过的方法及问题 #

• shapely.equals：拓扑等价检测，但无容差参数，浮点误差直接导致返回False（如示例中面积仅差1e-16就判定不等）。
• shapely.equals_exact：要求顶点顺序、数量一致且坐标在容差内匹配，无法处理顶点数量/顺序不同但拓扑等价的情况（如原多边形和其最小旋转矩形）。
• 面积容差检查：仅为必要非充分条件，存在不同形状但面积相同的误判场景，并非严格拓扑等价检测。

最小可复现示例 #

from shapely import minimum_rotated_rectangle, Polygon
from shapely.plotting import plot_polygon
import matplotlib.pyplot as plt

# 构造测试多边形
box1 = Polygon([(0,0),(0.5,0),(0.5,0.8),(0.2,0.8),(0,0.8),(0,0)])
box2 = minimum_rotated_rectangle(box1)

# 可视化（可选）
plot_polygon(box1)
plt.show()
plot_polygon(box2)
plt.show()

各方法执行结果 #

方法1：equals因浮点误差失效

>>> box1.equals(box2)
False
>>> box1.area
0.4
>>> box2.area
0.4000000000000001

方法2：equals_exact因顶点不匹配失效

>>> box1.equals_exact(box2, tolerance=1e-3)
False
>>> box1.boundary
LINESTRING (0 0, 0.5 0, 0.5 0.8, 0.2 0.8, 0 0.8, 0 0)
>>> box2.boundary
LINESTRING (0 0, 0.5 0, 0.5 0.8000000000000002, 0 0.8000000000000002, 0 0)

当前方法：面积容差检查（非严格拓扑等价）

>>> import math
>>> math.isclose(box1.area, box2.area, rel_tol=1e-9)
True

最佳解决方案 #

方案1：基于差集面积的拓扑等价检测 #

若两个多边形拓扑等价，它们的双向差集面积之和应趋近于0（浮点误差范围内）：

import math
from shapely import minimum_rotated_rectangle, Polygon

box1 = Polygon([(0,0),(0.5,0),(0.5,0.8),(0.2,0.8),(0,0.8),(0,0)])
box2 = minimum_rotated_rectangle(box1)

# 计算双向差集的总面积
total_diff_area = box1.difference(box2).area + box2.difference(box1).area
# 检查差集面积是否在容差内
is_topologically_equal = math.isclose(total_diff_area, 0.0, rel_tol=1e-9)
print(is_topologically_equal)  # 输出: True

方案2：基于交集面积的重合度验证 #

拓扑等价的多边形，其交集面积应与各自面积在容差内完全相等：

intersection_area = box1.intersection(box2).area
is_equal = (math.isclose(intersection_area, box1.area, rel_tol=1e-9) 
            and math.isclose(intersection_area, box2.area, rel_tol=1e-9))
print(is_equal)  # 输出: True

额外注意事项 #

1. 先验证多边形有效性：在拓扑计算前调用polygon.is_valid，无效多边形可能导致计算结果异常。
2. 简化多边形（可选）：若存在冗余顶点，可先通过polygon.simplify(tolerance=1e-9)去除，减少浮点误差干扰。
3. 针对矩形判断的优化：除拓扑检测外，可辅助验证多边形的内角是否为直角（需处理浮点误差），但核心仍以拓扑等价检测为准。

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