Delaunay Triangles

PJMcPrettypants

I want to get Delaunay triangles from an array of points.

I tried using the code I found here: https://github.com/GlitchTools/Atagen/blob/master/GRDelaunay/Triangulator.pde

That gave me my triangles but also always added one extra point stretching off outside the canvas!

Lee Byron's mesh library seemed like it might be a better way to go http://leebyron.com/mesh/

However, the Delaunay class in that library doesn't actually return triangles or groups of three points - just links between pairs of indices in the points array.

I tried using getLinked() to find the points that link to each point, but that was a mess. My guess is that while the numbers it returns are indices to the original array, the number it takes as a parameter is not.

Finally I tried using getLinks(), and nested loops to search through all the links to find matches.

   ArrayList<Triangle> triangles  = new ArrayList<Triangle>();  //the Triangle class just stores 3 PVectors

   int[][] myLinks = myDelaunay.getLinks();

    //search the links
    for (int a = 0; a < myLinks.length; a++) { // loop through all links

                     int aStart = myLinks[a][0];
                     int aEnd = myLinks[a][1];

                     for (int b = 0; b < myLinks.length; b++) { //loop through all links again...

                           //...except a
                           if (!(b == a)){

                                   //Links that connect to the starting point could be either way round

                                   //if start of b connects to start of a
                                   if  (myLinks[b][0] == aStart){      

                                                     for (int c = 0; c < myLinks.length; c++) {

                                                       //And the remaining link could be either way round

                                                       if  ((myLinks[b][1] == myLinks[c][0])&&(myLinks[c][1] == aEnd)){

                                                                   Triangle foundTri = new Triangle(); 
                                                                   foundTri.p1 = new PVector(floatPoints[aStart][0], floatPoints[aStart][1]);
                                                                   foundTri.p2 = new PVector(floatPoints[myLinks[b][1]][0], floatPoints[myLinks[b][1]][1]);
                                                                   foundTri.p3 = new PVector(floatPoints[aEnd][0], floatPoints[aEnd][1]);
                                                                   triangles.add(foundTri);

                                                       }

                                                       if  ((myLinks[b][1] == myLinks[c][1])&&(myLinks[c][0] == aEnd)){

                                                                   Triangle foundTri = new Triangle();
                                                                   foundTri.p1 = new PVector(floatPoints[aStart][0], floatPoints[aStart][1]);
                                                                   foundTri.p2 = new PVector(floatPoints[myLinks[b][1]][0], floatPoints[myLinks[b][1]][1]);
                                                                   foundTri.p3 = new PVector(floatPoints[aEnd][0], floatPoints[aEnd][1]);
                                                                   triangles.add(foundTri);

                                                       }      
                                               }
                                   }

                                   //if end of b connects to start of a
                                   if  (myLinks[b][1] == aStart){

                                           for (int c = 0; c < myLinks.length; c++) {

                                                       //And the remaining link could be either way round

                                                       if  ((myLinks[b][0] == myLinks[c][0])&&(myLinks[c][1] == aEnd)){

                                                                   Triangle foundTri = new Triangle();
                                                                   foundTri.p1 = new PVector(floatPoints[aStart][0], floatPoints[aStart][1]);
                                                                   foundTri.p2 = new PVector(floatPoints[myLinks[b][0]][0], floatPoints[myLinks[b][0]][1]);
                                                                   foundTri.p3 = new PVector(floatPoints[aEnd][0], floatPoints[aEnd][1]);
                                                                   triangles.add(foundTri);

                                                       }

                                                       if  ((myLinks[b][0] == myLinks[c][1])&&(myLinks[c][0] == aEnd)){

                                                                   Triangle foundTri = new Triangle();
                                                                   foundTri.p1 = new PVector(floatPoints[aStart][0], floatPoints[aStart][1]);
                                                                   foundTri.p2 = new PVector(floatPoints[myLinks[b][0]][0], floatPoints[myLinks[b][0]][1]);
                                                                   foundTri.p3 = new PVector(floatPoints[aEnd][0], floatPoints[aEnd][1]);
                                                                   triangles.add(foundTri);

                                                       }                                                 
                                             }
                                   }    
                           }
              }
    }

This had two problems: it takes several minutes to run and it seems to find extra larger triangles around groups of smaller ones.

Is there a good way to go from the links in the mesh library to Delaunay triangles?

PJMcPrettypants

I searched the forum and found a link to an old library called Triangulate here: http://n.clavaud.free.fr/processing/triangulate/triangulate-20100628.zip

This is very similar to the first code I used but it doesn't produce that weird extra vertex, so problem solved.

I will still have to use the mesh library as well because I also want to find a convex hull for the same set of points. It would be good if there was a nice way to do it all with just one library and one array of points but for now I'll use Triangulate for the triangles and mesh for the convex hull.

jeremydouglass

@PJMcPrettypants -- thanks for sharing your solution with the forum.