使用NetTopologySuite进行多边形三角剖分的异常问题求助

我对NetTopologySuite经验不足，现有如下带凹结构的多边形：

POLYGON((10 12,10 8,9 8,9 13,10 13,10 15,11 15,11 13,12 13,12 15,14 15,14 13,15 13,15 8,13 8,13 12,12 12,12 9,11 9,11 12,10 12))

我尝试用以下代码对其进行三角剖分，期望得到完全贴合多边形内部的三角形集合：

var reader = new WKTReader();
var polygon = (Polygon)reader.Read("POLYGON((10 12,10 8,9 8,9 13,10 13,10 15,11 15,11 13,12 13,12 15,14 15,14 13,15 13,15 8,13 8,13 12,12 12,12 9,11 9,11 12,10 12))");

var builder = new DelaunayTriangulationBuilder();

builder.SetSites(polygon);
var triangles = builder.GetTriangles(GeometryFactory.Default);

但实际得到的剖分结果包含跨越多边形凹部的三角形，不符合预期：

MULTIPOLYGON (((9 13, 9 8, 10 12, 9 13)), ((9 13, 10 12, 10 13, 9 13)), ((9 13, 10 13, 10 15, 9 13)), ((10 15, 10 13, 11 13, 10 15)), ((10 15, 11 13, 11 15, 10 15)), ((11 15, 11 13, 12 13, 11 15)), ((11 15, 12 13, 12 15, 11 15)), ((12 15, 12 13, 14 13, 12 15)), ((12 15, 14 13, 14 15, 12 15)), ((14 15, 14 13, 15 13, 14 15)), ((15 13, 14 13, 13 12, 15 13)), ((15 13, 13 12, 15 8, 15 13)), ((13 8, 15 8, 13 12, 13 8)), ((13 8, 13 12, 12 9, 13 8)), ((13 8, 12 9, 10 8, 13 8)), ((10 8, 12 9, 11 9, 10 8)), ((10 8, 11 9, 9 8, 10 8)), ((9 8, 11 9, 10 12, 9 8)), ((10 12, 11 9, 11 12, 10 12)), ((10 12, 11 12, 10 13, 10 12)), ((10 13, 11 12, 11 13, 10 13)), ((11 13, 11 12, 12 12, 11 13)), ((11 13, 12 12, 12 13, 11 13)), ((12 13, 12 12, 13 12, 12 13)), ((12 13, 13 12, 14 13, 12 13)), ((13 12, 12 12, 12 9, 13 12)), ((12 9, 12 12, 11 12, 12 9)), ((12 9, 11 12, 11 9, 12 9)))

请问我哪里操作有误？

问题原因 #

DelaunayTriangulationBuilder.SetSites(polygon)仅对多边形的顶点做无约束的Delaunay三角剖分，它不会识别多边形的边界约束，因此会生成跨越多边形凹区域的三角形，无法贴合多边形内部形状。

解决方案 #

要实现多边形内部的精准三角剖分，需要使用约束Delaunay三角剖分或专门的多边形三角剖分工具：

方法1：使用ConstrainedDelaunayTriangulationBuilder

通过添加多边形的边界作为约束条件，确保剖分结果不跨越多边形的边：

var reader = new WKTReader();
var polygon = (Polygon)reader.Read("POLYGON((10 12,10 8,9 8,9 13,10 13,10 15,11 15,11 13,12 13,12 15,14 15,14 13,15 13,15 8,13 8,13 12,12 12,12 9,11 9,11 12,10 12))");

var builder = new ConstrainedDelaunayTriangulationBuilder();

// 添加多边形所有顶点
builder.SetSites(polygon.Coordinates);

// 添加多边形的外壳和内部洞作为约束边
var constraints = new List<LineString>();
constraints.Add(polygon.Shell);
foreach (var hole in polygon.Holes)
{
    constraints.Add(hole);
}
builder.SetConstraints(constraints);

// 获取贴合内部的三角形
var triangles = builder.GetTriangles(GeometryFactory.Default);

方法2：使用PolygonTriangulator

NetTopologySuite提供了专门的PolygonTriangulator类，可直接对多边形进行三角剖分，自动处理内部凹结构：

var reader = new WKTReader();
var polygon = (Polygon)reader.Read("POLYGON((10 12,10 8,9 8,9 13,10 13,10 15,11 15,11 13,12 13,12 15,14 15,14 13,15 13,15 8,13 8,13 12,12 12,12 9,11 9,11 12,10 12))");

var triangulator = new PolygonTriangulator(polygon);
var triangles = triangulator.Triangulate();

这两种方式都能生成完全贴合多边形内部的三角形集合，不会出现跨越凹部的无效三角形。

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