如何在Java中对某个形状进行三角化/镶嵌？

Question

我希望能够使用GeoTools中的国家形状进行镶嵌，以在地球表面上以3D显示。 GeoTools内部使用JTS拓扑套件，看起来功能丰富。

它是否包含用于镶嵌某些形状的实用程序？我看到有三角剖分包，但无法弄清楚如何将其用于具有孔的形状。

此外，我不希望像这样仅连接现有顶点。

它应该用多个顶点填充形状。

更新

我发现JTS包含类ConformingDelaunayTriangulationBuilder，可以实现所需的镶嵌，但效果不佳。首先，它只允许约束，这意味着需要额外的代码来从凹陷区域中删除三角形。而且它试图保持镶嵌的 Delaunay 特性，导致创建许多额外的部分。最后，对于像国家这样的复杂形状会引起ConstraintEnforcementException并且无法使用。

此外，我发现triangle包，它是用C编写的，实现了Chew的第二个算法，并且运行良好。

现在我想知道，它是被移植到Java中还是包装进去了？

- Suzan Cioc

---

我并不是一个足够熟练的程序员，无法为您提供解决方案，但也许您可以从沿边的顶点列表开始。然后，找到形状内部的一个点，并将最近的顶点连接到它。然后，再找到更远的一个点，并重复此过程。直到每个顶点要么A（连接的边数达到最小值），要么B（点之间的距离永远不超过x）。无论哪种方式，上述简单算法只连接现有的点；您所需的算法必须在现有点附近创建新点。 - Aarowaim

之前想对这个进行评论：创建一个“好”的三角形网格非常具有挑战性。我使用了http://www3.math.tu-berlin.de/jtem/numericalMethods/中的“Ruppert”类，取得了一些有希望的结果，但它不支持处理孔洞。我认为你提到的“triangle”包是三角剖分的**最佳解决方案**(真的很好)。但是，它的实现方式非常可怕且" C"风格，无法在Java中远程移植（绝对不可能...太可怕了）。我曾经用JNI编写过一个小的包装器来封装这个库，但它尚未发布，可能仍需要一些清理工作。 - Marco13

@Marco13 也许你应该尝试一下我回答中建议的库 :) 到目前为止，它对我来说效果非常好... - DarkCygnus

@DarkCygnus，有一些（Java）三角剖分库可用（请参见Github），但是从“按照维基百科上描述的耳剪法实现”到具有斯坦纳点、孔处理、角度约束等好的、健壮的库还有很长的路要走。你提供的那个至少看起来不是简单的，并且已经维护和测试了一段时间（尽管在我测试之前我不会点赞）。遗憾的是，triangle库的创建者没有回应我的请求，以发布他的库的Java绑定。 - Marco13

@Marco13 是的，请试试，它迄今为止对我来说表现得很好。我曾经考虑过Triangle库，但没有找到任何Java版本（现在我知道原因了 :/），并发现他们的许可证在商业计划方面有一些限制。谢谢你包含的另一个链接，我会查看它的。 - DarkCygnus

Answer 1

我知道这篇文章比较旧，但最近我遇到了同样的情况，并需要一些 Java 库或类似工具来三角剖分一些复杂的多边形（因为我想在 OpenGL 上显示它们，而 OpenGL 只能绘制三角形作为基本操作）。

经过相当长时间的搜索和测试，适合我的库是 Orbgis 的 Poly2Tri。您可以从 Maven 这里^*获取该库。

这个库有许多功能，包括带孔的多边形，Steiner 点以优化您的三角剖分，以及其他东西。以下是一个基本的使用示例（基于链接存储库中的示例）。

//Create the polygon passing a List of PolygonPoints
Polygon polygon = new Polygon(
    Arrays.asList(
        new PolygonPoint(0, 0, 0),
        new PolygonPoint(10, 0, 1),
        new PolygonPoint(10, 10, 2),
        new PolygonPoint(0, 10, 3)));
//Here you could add holes as needed, passing them as Polygons
polygon.addHole(someHoleYouCreated);
//Next, proceed to calculate the triangulation of the polygon 
Poly2Tri.triangulate(polygon);
//Finally, obtain the resulting triangles
List<DelaunayTriangle> triangles = polygon.getTriangles();

编辑： 不知道你是否已经尝试过，但是JTS拓扑套件也有一个DelaunayTriangulationBuilder类（没有Conforming部分）。它位于org.locationtech.jts.triangulate.DelaunayTriangulationBuilder，也许它比你尝试过但表现不佳的其他类更好用。

^*注意：不要像我一开始那样使用this one，因为我发现那不是正确的依赖项（不是“-core”版本）

- DarkCygnus

---

请注意，如果您需要在三维空间中三角剖分多边形，则此库将无法使用。虽然它的PolygonPoint类具有Z坐标，但三角剖分代码仅查看X和Y，因此如果您有一个垂直的多边形（例如墙壁），该库将把其顶点视为共线并拒绝进行三角剖分。 - Annonymus

Answer 2

这里有一个使用JTS的快速而简单的方法：

首先：

使用JTS的DelaunayTriangulationBuilder对几何图形进行三角剖分。 准备一组站点，sites；从初始三角剖分中复制顶点站点。

循环：

迭代三角形的几何图形，将三角形质心**添加到sites中。 使用sites(现在包括原始站点和新的质心站点)重新进行三角剖分。

最后：

将三角剖分与原始几何图形相交，以恢复其凹壳和任何孔洞。

**对于这种简单技术，我发现使用三角形质心比使用三角形外心产生更好的结果，尽管后者通常在更正式的细化中使用(Chew, Ruppert等)。

代码

static Geometry refinedTriangulation(Geometry g, int nRefinements, double tolerance) {

    DelaunayTriangulationBuilder builder = new DelaunayTriangulationBuilder();
    builder.setSites(g); // set vertex sites
    builder.setTolerance(tolerance); // set tolerance for initial triangulation only

    Geometry triangulation = builder.getTriangles(geometryFactory); // initial triangulation

    HashSet<Coordinate> sites = new HashSet<>();
    for (int i = 0; i < triangulation.getCoordinates().length; i++) {
        sites.add(triangulation.getCoordinates()[i]);
    }

    for (int refinement = 0; refinement < nRefinements; refinement++) {
        for (int i = 0; i < triangulation.getNumGeometries(); i++) {
            Polygon triangle = (Polygon) triangulation.getGeometryN(i);

            if (triangle.getArea() > 50) { // skip small triangles
                sites.add(new Coordinate(triangle.getCentroid().getX(), triangle.getCentroid().getY()));
            }
        }
        builder = new DelaunayTriangulationBuilder();
        builder.setSites(sites);
        triangulation = builder.getTriangles(geometryFactory); // re-triangulate using new centroid sites
    }

    triangulation = triangulation.intersection(g); // restore concave hull and any holes
    return triangulation;
}

你可以使用 triangle.getExteriorRing().getLength() > N 或者 triangle.getArea() > N 来跳过对已经足够小的三角形进行细化。

示例

原始形状

JTS三角剖分。

JTS三角剖分与交集

1 精炼

3 个改进

- micycle