Delaunay triangles point connectivity?

Question

I was watching this video: Delaunay Triangulation and I want to use this to generate procedural content in the same way. I had a pretty hard time figuring out how to work with the DelaunayTriangulation class supplied by LibGDX but I guess I finally figured it out.

My question however is how do I know which point is connected to which point in a easy way? This is how I currently setup my points for testing, these points eventually need to be supplied by the rooms generated.

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

And this is how I am drawing the points and lines/triangles, just for visualization and understanding.

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);
        }
    }

Assuming I am using this correctly (the points and triangles get drawn correctly) I'm drawing double lines:

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

So is there someway to filter these out? Since I am only interested in connectivity and not actually drawing triangles side by side to generate meshes.

Also, in the video I mentioned on top you notice there are lines being removed to have some death ends at 50 seconds in the movie. How is this calculated? Some also get colored and it leaves a nice mix of death ends and loops. I am interested to know how this could be achieved.

Answer 1

It seems like you just want to compute the set of edges of the resulting triangles. Therefore, you can simply create an Edge class, with two special properties:

• the equals method returns true even if the vertices of the edge to compare with are swapped (so that an edge (2,1) will be considered as "equal" to an edge (1,2))
• the hashCode method is implemented in a way that is consistent with this equals implementation, as noted in the Object#hashCode documentation:

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

The above program will print

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

Thus, omitting the edge (1,2), because it is considered to be equal to the edge (2,1).

(Of course, one could convert this set back into a plain int[] array of edge indices, but that's not the point of the question)

Answer 2

IMO it's impossible to know when there isn't an explanation or example code. But it's possible to use contour lines for a maze. Here is the explanation how to use it with a minimum spanning tree (https://twitter.com/nathanpie/status/435558377964318720). BTW. the delaunay triangulation is the superset of the minimum spanning tree.

Answer 3

I'm the author of the video linked to in the original question. The source code for the demo in the video can be found here: https://bitbucket.org/NathisGreen/pcgdungeons

This was created as part of my final year at university so I have a detailed report explaining how the entire thing works that can be read here: http://www.nathanmwilliams.com/files/AnInvestigationIntoDungeonGeneration.pdf

Section 2.3.2 and Section 4.1 relate to the Delaunay triangulation being discussed here.

But basically all that is happening to create the final graph, is I find the minimum spanning tree of the graph produced by the triangulation and then randomly add back some of the edges from the original graph into the minimum spanning tree graph.