NetTopologySuite ConcaveHullByLengthRatio抛出LocateFailureException求助

问题背景 #

调用NetTopologySuite.Algorithm.Hull.ConcaveHull.ConcaveHullByLengthRatio(Geometry geom, double lengthRatio, bool isHolesAllowed)构建凹包时，偶尔会抛出如下异常：

NetTopologySuite.Triangulate.QuadEdge.LocateFailureException: Locate failed to converge (at edge: LINESTRING( 38.52788223 59.20800324999999, 38.529696464538574 59.20393475499401)). Possible causes include invalid Subdivision topology or very close sites
at NetTopologySuite.Triangulate.QuadEdge.QuadEdgeSubdivision.LocateFromEdge(Vertex v, QuadEdge startEdge)
at NetTopologySuite.Triangulate.QuadEdge.LastFoundQuadEdgeLocator.Locate(Vertex v)
at NetTopologySuite.Triangulate.IncrementalDelaunayTriangulator.InsertSite(Vertex v)
at NetTopologySuite.Triangulate.IncrementalDelaunayTriangulator.InsertSites(ICollection`1 vertices)
at NetTopologySuite.Triangulate.DelaunayTriangulationBuilder.Create()
at NetTopologySuite.Triangulate.DelaunayTriangulationBuilder.GetSubdivision()
at NetTopologySuite.Algorithm.Hull.HullTriangulation.CreateDelaunayTriangulation(Geometry geom)
at NetTopologySuite.Algorithm.Hull.ConcaveHull.GetHull()
at NetTopologySuite.Algorithm.Hull.ConcaveHull.ConcaveHullByLengthRatio(Geometry geom, Double lengthRatio, Boolean isHolesAllowed)

调整lengthRatio（0.1到1.0）、设置isHolesAllowed=false均无法解决，输入为包含坐标的MultiPoint。

解决方案 #

1. 清理重复/极近点 #

异常提示明确提到"very close sites"，这是触发问题的常见原因。先对输入的MultiPoint去重：

• 使用内置方法快速去重：

  Geometry cleanedGeom = geom.Deduplicate();
  

• 自定义阈值过滤（适用于需要更精确控制的场景）：

  var sourcePoints = ((MultiPoint)geom).Geometries.Cast<Point>().ToList();
  var uniquePoints = new List<Point>();
  double tolerance = 1e-6; // 根据坐标精度调整，比如小数点后6位
  foreach (var pt in sourcePoints)
  {
      if (!uniquePoints.Any(p => p.Distance(pt) < tolerance))
      {
          uniquePoints.Add(pt);
      }
  }
  Geometry cleanedGeom = geom.Factory.CreateMultiPoint(uniquePoints.ToArray());
  

2. 替换三角剖分的点定位器 #

默认的LastFoundQuadEdgeLocator在特定拓扑下可能出现收敛问题，尝试改用SimpleQuadEdgeLocator。需要手动构建凹包流程（而非直接调用静态方法）：

var concaveHull = new ConcaveHull(geom)
{
    LengthRatio = 0.2,
    IsHolesAllowed = true
};

// 自定义Delaunay三角剖分，替换定位器
var triangulationBuilder = new DelaunayTriangulationBuilder();
triangulationBuilder.SetSites(geom);
var subdivision = triangulationBuilder.GetSubdivision();
subdivision.Locator = new SimpleQuadEdgeLocator(subdivision);

// 通过反射将自定义剖分注入凹包（需确保版本兼容）
var field = typeof(ConcaveHull).GetField("_triangulation", BindingFlags.NonPublic | BindingFlags.Instance);
if (field != null)
{
    var hullTriangulation = new HullTriangulation(geom);
    var triField = typeof(HullTriangulation).GetField("_subdivision", BindingFlags.NonPublic | BindingFlags.Instance);
    triField?.SetValue(hullTriangulation, subdivision);
    field.SetValue(concaveHull, hullTriangulation);
}

// 生成凹包
var result = concaveHull.GetHull();

3. 升级NetTopologySuite版本 #

该异常属于Delaunay三角剖分的已知问题，新版本可能已修复。建议升级到2.5.0及以上版本，新版本对三角剖分的稳定性有优化。

4. 修复无效几何 #

确保输入的MultiPoint是有效几何，无空点、NaN坐标：

if (!geom.IsValid)
{
    geom = geom.Buffer(0); // 自动修复无效几何结构
}

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