多边形三角剖分不适用于使用 Delaunay 三角剖分方法的某些多边形

Question

我原来的多边形WKT是这样的：

POLYGON ((98.51786360976723 78.60265688535823, 98.51786360976723 78.67546052678281, 98.78608990953424 78.67546052678281, 98.78608990953424 78.60265688535823, 98.51786360976723 78.60265688535823), (98.6858787533021 78.6463165282853, 98.6871832612985 78.6414240598725, 98.6928364041768 78.6416815519622, 98.6989240643941 78.6370468139596, 98.669789552746 78.6325836180397, 98.6537002325798 78.6281204221198, 98.6463078260456 78.6238287682832, 98.6545697447981 78.6203955416212, 98.6706590649639 78.6221981049586, 98.6810953618617 78.619537353666, 98.6723984482301 78.617906451122, 98.6854438780327 78.6145590539573, 98.6810953618617 78.6112976076985, 98.6723984482301 78.6095808747577, 98.6745728254758 78.6074352263547, 98.6654410365749 78.6063194275998, 98.6715289351125 78.6048603054588, 98.6932710411258 78.6083792447066, 98.6950105431023 78.6104393001338, 98.6854438780327 78.6112116576919, 98.6863136294706 78.6124134064538, 98.7050119638312 78.6131000523257, 98.6967499254689 78.6112116576919, 98.7041423320031 78.6106108431161, 98.7147991660487 78.6131857631126, 98.7163224224421 78.6185932157044, 98.7089240552014 78.6252880100337, 98.7108825447938 78.6279058456784, 98.7350163456279 78.6396217348555, 98.7302329541877 78.6425398586277, 98.7232755425325 78.6479473112196, 98.714143752732 78.6501789096291, 98.7093603612918 78.6488914491812, 98.691097020911 78.6484621766881, 98.6858787533021 78.6463165282853), (98.7041423320031 78.6076927184442, 98.7045772072724 78.6065769196892, 98.7110997436582 78.6070059538618, 98.7154482607287 78.6086368564059, 98.7041423320031 78.6076927184442))

我已使用以下方法将三角测量应用于此多边形：

DelaunayTriangulationBuilder delaunayTriangulationBuilder = new DelaunayTriangulationBuilder();
delaunayTriangulationBuilder.setSites(originalGeometry);

当我得到由此生成的所有三角形时：

 delaunayTriangulationBuilder.getTriangles(new GeometryFactory())

它排除了一些区域，如下图所示： Delaunay 三角测量方法排除的区域为绿色，它是我原始多边形的一部分。

我不确定为什么会出现这种情况，我也面临着与其他多边形相同的问题，我尝试运行 Covers 谓词来检查原始多边形是否覆盖了三角测量返回的所有多边形，但特别是绿色的多边形没有覆盖由三角测量过程返回。

我正在使用 JTS 拓扑套件来实现同样的目的。

Answer 1

您的问题是您正在使用文档中的

DelaunyTriangleBuilder

：

一个实用程序类，它从点集合创建 Delaunay 三角剖分，并提取生成的三角剖分边或三角形作为几何图形。

而您想要三角形填充多边形，则需要

Trianglutor

。所以，这是我的代码，显示了 2 种可能的解决方案。

import org.geotools.geometry.jts.WKTReader2;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.io.ParseException;
import org.locationtech.jts.triangulate.polygon.ConstrainedDelaunayTriangulator;
import org.locationtech.jts.triangulate.polygon.PolygonTriangulator;

public class Triangles {
    public static void main(String[] args) throws ParseException {
        String wkt = "POLYGON ((98.51786360976723 78.60265688535823, 98.51786360976723 78.67546052678281, 98.78608990953424 78.67546052678281, 98.78608990953424 78.60265688535823, 98.51786360976723 78.60265688535823), (98.6858787533021 78.6463165282853, 98.6871832612985 78.6414240598725, 98.6928364041768 78.6416815519622, 98.6989240643941 78.6370468139596, 98.669789552746 78.6325836180397, 98.6537002325798 78.6281204221198, 98.6463078260456 78.6238287682832, 98.6545697447981 78.6203955416212, 98.6706590649639 78.6221981049586, 98.6810953618617 78.619537353666, 98.6723984482301 78.617906451122, 98.6854438780327 78.6145590539573, 98.6810953618617 78.6112976076985, 98.6723984482301 78.6095808747577, 98.6745728254758 78.6074352263547, 98.6654410365749 78.6063194275998, 98.6715289351125 78.6048603054588, 98.6932710411258 78.6083792447066, 98.6950105431023 78.6104393001338, 98.6854438780327 78.6112116576919, 98.6863136294706 78.6124134064538, 98.7050119638312 78.6131000523257, 98.6967499254689 78.6112116576919, 98.7041423320031 78.6106108431161, 98.7147991660487 78.6131857631126, 98.7163224224421 78.6185932157044, 98.7089240552014 78.6252880100337, 98.7108825447938 78.6279058456784, 98.7350163456279 78.6396217348555, 98.7302329541877 78.6425398586277, 98.7232755425325 78.6479473112196, 98.714143752732 78.6501789096291, 98.7093603612918 78.6488914491812, 98.691097020911 78.6484621766881, 98.6858787533021 78.6463165282853), (98.7041423320031 78.6076927184442, 98.7045772072724 78.6065769196892, 98.7110997436582 78.6070059538618, 98.7154482607287 78.6086368564059, 98.7041423320031 78.6076927184442))";
        WKTReader2 reader = new WKTReader2();
        Geometry geom = reader.read(wkt);
        Geometry result = PolygonTriangulator.triangulate(geom);
        System.out.println(result);

        result = ConstrainedDelaunayTriangulator.triangulate(geom);
        System.out.println(result);
    }
}

这是基于阅读关于三角剖分多边形的JTS 博客文章。

第一种方法（

PolygonTriangulator

）给出了这个集合：

马丁推荐的第二种方法（

ConstrainedDelaunayTriangulator

）给出：

至于哪一个“更好”，我不确定，但您会注意到，与您的解决方案不同，多边形中的孔不是三角剖分的。