JTS几何库中的多边形相交检测问题分析与解决

概述

在JTS(Java Topology Suite)几何库的使用过程中，开发者报告了两个关于多边形相交检测(intersects)的异常案例。这些案例揭示了JTS核心算法在处理特定几何图形时的局限性，特别是在边界情况下的稳健性(robustness)问题。

问题案例描述

案例一：多边形与线串相交检测

第一个案例涉及一个多边形和一条线串的相交检测。测试代码创建了两个几何对象：

Geometry gc0 = reader.read("POLYGON ((414188.5999999999 6422867.1, ...))");
Geometry gc1 = reader.read("LINESTRING (414187.2 6422831.6, ...)");
assertTrue(gc0.intersects(gc1));

理论上，这条线串的终点(414188.6 6422867.1)与多边形的起点几乎重合，应该返回相交结果为真。然而，原始算法却报告了"side location conflict"(边位置冲突)错误。

案例二：多边形与多边形相交检测

第二个案例展示了两个多边形之间的相交检测问题：

Geometry gc0 = reader.read("POLYGON ((474007.37387468846 5286568.023144805, ...))");
Geometry gc1 = reader.read("POLYGON ((473936.1801007541 5286478.294544354, ...))");
assertTrue(gc0.intersects(gc1));

这两个多边形在边界处有接触点，理论上应该相交，但原始算法同样报告了边位置冲突错误。

技术背景

JTS库中的几何关系计算(如相交、包含等)依赖于精确的几何计算算法。传统算法在处理以下情况时容易出现稳健性问题：

1. 浮点数精度限制导致的坐标计算误差
2. 几何图形在边界处的接触判断
3. 共线或接近共线的边判断

这些问题在计算几何学中被称为"稳健性"(robustness)问题，是许多几何计算库面临的共同挑战。

解决方案：RelateNG算法

JTS开发团队已经意识到这些问题，并在1.20版本中引入了新的RelateNG算法来替代传统的几何关系计算。RelateNG算法通过以下改进解决了上述问题：

1. 更健壮的几何谓词计算
2. 改进的边界情况处理
3. 增强的数值稳定性

开发者可以通过两种方式使用新算法：

1. 直接调用RelateNG类：

assertTrue(RelateNG.relate(gc0, gc1, RelatePredicate.intersects()))

2. 设置系统属性全局启用：

-Djts.relate=ng

实际应用建议

对于使用JTS库的开发人员，建议：

1. 升级到JTS 1.20或更高版本
2. 对于关键几何计算，考虑直接使用RelateNG API
3. 在测试环境中验证新算法对现有功能的影响
4. 对于复杂的几何图形，仍然需要考虑添加适当的容差处理

结论

几何计算的稳健性问题在实际应用中经常遇到，特别是在处理真实世界数据时。JTS库通过引入RelateNG算法显著提高了几何关系计算的可靠性。开发者应当了解这些改进，并在适当的情况下采用新算法，以确保几何计算的准确性。

对于需要处理复杂几何关系的应用，建议深入理解几何算法的局限性，并在必要时实现额外的验证逻辑或容错机制。