java - Delaunay 三角形点连通性？

Question

我在看这个视频:Delaunay Triangulation我想用它以相同的方式生成程序内容。我很难弄清楚如何使用 LibGDX 提供的 DelaunayTriangulation 类，但我想我终于弄明白了。

然而，我的问题是如何以简单的方式知道哪个点连接到哪个点？这就是我目前设置测试点的方式，这些点最终需要由生成的房间提供。

private void TriangleTest()
    {
        DelaunayTriangulator triangulator = new DelaunayTriangulator();

        points = new float[8];
        points[0] = 80;
        points[1] = 30;
        points[2] = 40;
        points[3] = 45;
        points[4] = 0;
        points[5] = 10;
        points[6] = -100;
        points[7] = 100;

        indices = triangulator.computeTriangles(points, false);

        System.out.println(indices);
        //Output [1, 0, 2, 1, 2, 3]
    }

这就是我绘制点和线/三角形的方式，只是为了可视化和理解。

private void DrawTriangles()
    {
        //Draw points
        for (int i = 0; i < points.length / 2; i++)
        {
            DebugHelper.DrawDebugPoint(new Vector2(points[i * 2], points[i * 2 + 1]), camera.combined);
        }

        //Draw lines
        for (int i = 0; i < indices.size / 3; i++)
        {
            Vector2 v1 = new Vector2(points[indices.get(i * 3) * 2],
                    points[indices.get(i * 3) * 2 + 1]);
            Vector2 v2 = new Vector2(points[indices.get(i * 3 + 1) * 2],
                    points[indices.get(i * 3 + 1) * 2 + 1]);
            Vector2 v3 = new Vector2(points[indices.get(i * 3 + 2) * 2],
                    points[indices.get(i * 3 + 2) * 2 + 1]);

            DebugHelper.DrawDebugLine(v1, v2, camera.combined);
            DebugHelper.DrawDebugLine(v2, v3, camera.combined);
            DebugHelper.DrawDebugLine(v3, v1, camera.combined);
        }
    }

假设我正确使用它(正确绘制点和三角形)我正在绘制双线:

[1, 0, 2] //1st indices (2nd point connects to 1st point)
[1, 2, 3] //2nd indices (1st point connects to 2nd point)

那么有什么方法可以过滤掉这些吗？因为我只对连通性感兴趣，而不是实际并排绘制三角形来生成网格。

另外，在 the video I mentioned on top你注意到电影中有一些台词被删除，以便在 50 秒时有一些死亡结局。这是如何计算的？有些也有颜色，它留下了死亡结局和循环的完美组合。我很想知道这是如何实现的。

Answer 1

我是原始问题中链接的视频的作者。视频中演示的源代码可以在这里找到:https://bitbucket.org/NathisGreen/pcgdungeons

这是我在大学最后一年创建的，所以我有一份详细的报告来解释整个事情是如何运作的，可以在这里阅读: http://www.nathanmwilliams.com/files/AnInvestigationIntoDungeonGeneration.pdf

第 2.3.2 节和第 4.1 节与此处讨论的 Delaunay 三角剖分有关。

但基本上创建最终图所发生的一切都是我找到由三角剖分生成的图的最小生成树，然后将原始图的一些边随机添加回最小生成 TreeMap 中。