Delaunay 三角形点连通性？

Question

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

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

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]
    }

这就是我绘制点和 lines/triangles 的方式，只是为了可视化和理解。

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

在没有解释或示例代码的情况下，IMO 无法知道。但是可以使用迷宫的等高线。以下是如何将其与最小生成树 (https://twitter.com/nathanpie/status/435558377964318720) 一起使用的说明。顺便提一句。 delaunay 三角剖分是最小生成树的超集。

Answer 2

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

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

第 2.3.2 节和第 4.1 节涉及此处讨论的 Delaunay 三角剖分。

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

Answer 3

您似乎只想计算所得三角形的边集。因此，您可以简单地创建一个 Edge class，具有两个特殊属性：

equals 方法 returns true 即使要比较的边的顶点被交换（因此边 (2,1) 将被视为 "equal" 到边缘 (1,2))
hashCode 方法的实现方式与此 equals 实现一致，如 Object#hashCode 文档中所述：

If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

This way, these Edge objects can simply be put into a Set, and the Set will take care of the rest: Even if "duplicate" edges are added, the set will eventually contain each edge only once.

import java.util.LinkedHashSet;
import java.util.Set;

public class DelaunayEdges
{
    public static void main(String[] args)
    {
        int triangleIndices[] = new int[] { 1, 0, 2, 1, 2, 3 };
        Set<Edge> edges = computeEdges(triangleIndices);
        System.out.println("Edges: "+edges);
    }

    static class Edge
    {
        private final int vertex0;
        private final int vertex1;
        public Edge(int vertex0, int vertex1)
        {
            this.vertex0 = vertex0;
            this.vertex1 = vertex1;
        }
        @Override
        public String toString()
        {
            return "("+vertex0+","+vertex1+")";
        }
        @Override
        public int hashCode()
        {
            return vertex0 ^ vertex1;
        }
        @Override
        public boolean equals(Object object)
        {
            if (this == object)
            {
                return true;
            }
            if (object == null)
            {
                return false;
            }
            if (getClass() != object.getClass())
            {
                return false;
            }
            Edge that = (Edge) object;
            return 
                (this.vertex0 == that.vertex0 &&
                 this.vertex1 == that.vertex1) ||
                (this.vertex0 == that.vertex1 &&
                 this.vertex1 == that.vertex0);
        }
    }

    private static Set<Edge> computeEdges(int triangleIndices[])
    {
        Set<Edge> edges = new LinkedHashSet<Edge>();
        for (int i=0; i<triangleIndices.length; i+=3)
        {
            int i0 = triangleIndices[i+0];
            int i1 = triangleIndices[i+1];
            int i2 = triangleIndices[i+2];
            edges.add(new Edge(i0, i1));
            edges.add(new Edge(i1, i2));
            edges.add(new Edge(i2, i0));
        }
        return edges;
    }
}

以上程序会打印

Edges: [(1,0), (0,2), (2,1), (2,3), (3,1)]

因此，省略边(1,2)，因为它被认为等于边(2,1)。

（当然，可以将此集合转换回普通的 int[] 边缘索引数组，但这不是问题的重点）

Delaunay 三角形点连通性？

Delaunay triangles point connectivity?

java

procedural-generation

triangulation

libgdx