JTS中STRTree+IndexedPointInAreaLocator点面查询性能优化求助

问题描述 #

我使用以下代码实现点在多边形内的查询：先将所有多边形、多多边形存入STRTree，再通过IndexedPointInAreaLocator在STRTree查询结果之上做二次校验，确认点是否真的位于几何图形内。

private List<ZoneDefinitionCacheMemory> findZonesForShipPosition(Point point) {
    List<Object> zoneDefinitionCacheHits = new ArrayList<>();
    strTree.query(point.getEnvelopeInternal(), zoneDefinitionCacheHits::add);
    return zoneDefinitionCacheHits.stream()
        .filter(ZoneDefinitionCacheMemory.class::isInstance)
        .map(ZoneDefinitionCacheMemory.class::cast)
        .filter(zoneDefinition -> isPointInsideGeometry(point, zoneDefinition.getGeometry()))
        .toList();
}

private boolean isPointInsideGeometry(Point point, Geometry geometry) {
    PointOnGeometryLocator pointOnGeometryLocator = new IndexedPointInAreaLocator(geometry);
    int location = pointOnGeometryLocator.locate(point.getCoordinate());
    boolean isInside = location == Location.INTERIOR;
    return isInside;
}

我的部分多边形规模极大，包含近160万个顶点。当前实现处理单个点至少需要100ms，无法满足业务需求。

业务场景为：需处理大量点，判断它们是否位于给定的多边形/多多边形内部。曾尝试使用polygon.contains(point)方法，但耗时比IndexedPointInAreaLocator方案更长。

请问问题出在哪里？有哪些优化建议？

问题根源分析 #

1. 重复构建空间索引：isPointInsideGeometry方法中，每次校验都重新创建IndexedPointInAreaLocator实例，这个实例初始化时需要为百万级顶点的多边形构建空间索引，这是最核心的性能损耗点。
2. STRTree过滤效率低：超大多边形的外接矩形覆盖范围极广，STRTree通过外接矩形过滤后返回的候选多边形数量过多，导致后续二次校验的工作量剧增。
3. 未复用预处理资源：没有针对批量点处理的场景做资源复用，单点点处理的重复操作累积了大量不必要的开销。

优化建议 #

• 预缓存空间索引实例：在多边形存入STRTree前，提前为每个多边形创建IndexedPointInAreaLocator实例并缓存到ZoneDefinitionCacheMemory中，避免每次校验重复构建索引。示例修改：

  // 在ZoneDefinitionCacheMemory中新增字段
  private PointOnGeometryLocator prebuiltLocator;
  
  // 初始化时预构建索引
  public ZoneDefinitionCacheMemory(Geometry geometry) {
      this.geometry = geometry;
      this.prebuiltLocator = new IndexedPointInAreaLocator(geometry);
  }
  
  // 修改校验方法，直接复用预构建的索引
  private boolean isPointInsideGeometry(Point point, ZoneDefinitionCacheMemory zone) {
      int location = zone.getPrebuiltLocator().locate(point.getCoordinate());
      return location == Location.INTERIOR;
  }
  

• 拆分/简化超大多边形：将百万级顶点的多边形拆分为多个子多边形，缩小每个子多边形的外接矩形范围，减少STRTree返回的候选数量；或者用Douglas-Peucker算法生成简化版多边形，先通过简化版快速过滤点，仅对疑似命中的情况再用原始多边形做精确校验。
• 优化STRTree存储逻辑：为超大多边形单独建立二级空间索引，STRTree命中后先通过二级索引做进一步过滤，再进入精确校验环节，减少对复杂几何的计算次数。
• 批量点处理：将多个点按空间范围分组，针对同一区域的多边形批量处理所有点；或者利用JTS的PreparedGeometry批量判断能力，复用预处理资源减少重复开销。
• 并行处理：将大量点拆分为多个子任务并行计算，充分利用多核CPU资源（STRTree和预缓存的Locator都是线程安全的，无需额外同步）。

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