本文详解如何使用 shapely 高效计算 multipolygon 中每个子多边形内部所能容纳的最长直线段（即最大内接弦），核心是基于“最长内接线必过两个顶点”这一几何性质，结合边界扩展、精确交点计算与合法性校验。
本文详解如何使用 shapely 高效计算 multipolygon 中每个子多边形内部所能容纳的最长直线段（即最大内接弦），核心是基于“最长内接线必过两个顶点”这一几何性质，结合边界扩展、精确交点计算与合法性校验。
在计算几何与地理空间分析中，寻找多边形内部最长的完全包含线段（又称 maximum inscribed chord）是一个经典问题。该线段不一定是直径，也不一定连接重心或中心点——理论已严格证明：任意简单多边形内部最长的完全位于其内部的线段，其两个端点必定落在多边形的顶点上（参见 Math StackExchange 及相关算法文献）。这一结论极大缩小了搜索空间，使暴力枚举成为可行方案（对中小规模多边形而言）。
然而，直接连接两顶点形成的线段往往超出多边形边界。正确做法是：以两顶点确定一条无限长直线，求该直线与多边形边界的全部交点，再在这些交点中枚举所有可能的线段，并筛选出完全落在多边形内部且长度最大的那一条。关键难点在于：
- 原始 LineString([p1,p2]) 是有限线段，无法捕获多边形外延交点；
- 交点需在多边形 边界（polygon.boundary）上精确计算，而非仅与边列表逐条比对；
- 多重嵌套循环的位置必须合理：顶点对循环 → 直线扩展与交点采集 → 交点对校验，三者层级不可错位。
以下为经过验证、可直接运行的专业实现（兼容 Shapely ≥ 2.0）：
from shapely import LineString, Point, GeometryCollection
from shapely.ops import linemerge
import numpy as np
def extend_line_to_bounds(p1, p2, bounds):
"""将两点确定的直线无限延伸至包围盒边界，返回跨越包围盒的线段"""
minx, miny, maxx, maxy = bounds
x1, y1 = p1
x2, y2 = p2
# 处理垂直与水平退化情况
if abs(x1 - x2) 1e-10 else None
if x_bottom is not None and minx 1e-10 else None
if x_top is not None and minx max_len:
max_len = length
max_seg = seg
return max_seg, max_len
def longest_segments_in_multipolygon(multipolygon):
"""
对 MultiPolygon 中每个子多边形执行 longest_inscribed_segment，
返回字典：{polygon_index: (segment, length)}
"""
results = {}
for idx, poly in enumerate(multipolygon.geoms):
seg, length = longest_inscribed_segment(poly)
results[idx] = {'segment': seg, 'length': length}
return results
# ✅ 使用示例
from shapely.geometry import MultiPolygon, Polygon
mp = MultiPolygon([
Polygon([(7, 10), (8, 11), (9, 11), (8, 10), (7, 9.5), (7, 10)]),
Polygon([(9.5, 8.5), (10, 9), (10, 10), (11, 9), (9.5, 8.5)]),
])
results = longest_segments_in_multipolygon(mp)
for idx, res in results.items():
print(f"Polygon {idx}: longest segment length = {res['length']:.6f}")
if res['segment']:
print(f" Coordinates: {list(res['segment'].coords)}")
注意事项与优化建议
- 性能：时间复杂度为 $O(V^2 \cdot E)$（$V$ 为顶点数，$E$ 为边界线段数），适用于顶点数
- 数值鲁棒性：代码中引入 atol=1e-8 容差比较，避免浮点误差导致重复点或遗漏交点。
- 退化情形：自动处理垂直/水平线、共线顶点、自相交多边形（此时 polygon.is_valid 为 False，函数跳过）。
- Shapely 版本：本实现适配 Shapely 2.x（推荐 ≥ 2.0.2）。若使用 1.x，请将 polygon.boundary.coords 替换为 list(polygon.boundary.coords) 并注意 intersection 返回类型差异。
- 扩展性：如需获取所有候选最长线段（而不仅是首条），可将 max_seg 改为列表并在长度相等时追加。
该方案兼顾理论严谨性与工程可用性，可直接集成至地理围栏分析、路径规划、空间索引优化等实际场景。
