Delaunay Triangles

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

DelaunayErrors

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?

Answers

  • 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.

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

Sign In or Register to comment.