JTS几何库中多边形凹包算法的嵌套多边形处理问题分析

问题背景

在JTS(Java Topology Suite)几何库中，ConcaveHullOfPolygons算法用于计算一组多边形的最小凹包边界。该算法在处理普通多边形集合时表现良好，但在面对特殊嵌套结构的多边形时会出现计算错误。

问题现象

当输入的多边形集合中存在"孔洞中包含岛屿"的嵌套结构时，算法会抛出异常"Unable to find shell join index with interior join line"。例如以下MultiPolygon几何体：

MULTIPOLYGON (
  ((1 9, 9 9, 9 1, 1 1, 1 9), (2 8, 8 8, 8 2, 2 2, 2 8)),
  ((3 3, 4 7, 7 4, 3 3))
)

这个几何体由一个外框多边形(1-9)、一个内部孔洞(2-8)和孔洞内的三角形(3-3)组成。算法无法正确处理这种结构。

技术分析

算法原理

ConcaveHullOfPolygons算法的核心思想是：

1. 首先构建多边形集合的框架(frame)，即所有多边形外壳的并集
2. 然后对这个框架计算凹包
3. 最后将原始多边形的内边界(孔洞)重新整合到结果中

问题根源

当前算法在处理框架构建阶段存在缺陷。具体来说：

1. 框架构建时没有考虑多边形之间的包含关系
2. 当存在外壳完全位于另一个多边形的孔洞内时，算法无法正确处理
3. 导致后续步骤无法找到合适的连接线来构建完整凹包

解决方案思路

正确的处理方式应该：

1. 在框架构建阶段识别并移除被其他多边形外壳完全包含的多边形
2. 只保留最外层的多边形外壳参与框架构建
3. 确保框架是一个简单的多边形集合，没有复杂的嵌套关系

技术影响

这个问题会影响以下场景：

1. 地理信息系统中处理复杂行政区划边界
2. CAD软件中处理带有嵌套结构的图形
3. 任何需要计算复杂多边形集合外包络线的应用

总结

JTS几何库中的凹包算法在处理嵌套多边形结构时需要改进框架构建逻辑。通过识别并移除被包含的多边形外壳，可以解决当前算法在处理"孔洞中包含岛屿"结构时的问题。这一改进将增强算法的鲁棒性，使其能够处理更复杂的几何场景。