Delaunay Triangulation stucked

    Apr 20 2012 | 12:51 am
    Hi guys,
    I've been trying to port a delaunay triangulation algorithm to work with max.
    The idea is to calculate a delaunay triangulation from a given list , representing x y point coordinates. [x y x y x y ... ]. Actually i just need the values of the edges, i don't even need to draw the result.
    I'm currently using a .jar file from this processing library ( However, when i send the list, it gives me a null pointer exception, and i can't figure out whats wrong... :S
    Has anyone tried this or something similar?
    Thanks, JM

    • Apr 20 2012 | 8:14 am
      Hello João,
      This is likely to be due to not instantiating an object properly before calling its methods. Can you post your mxj code? It's impossible to diagnose otherwise!
      Best, Owen
    • Apr 20 2012 | 8:29 am
      here is a triangulation algorithm of a contour implementation in javascript. perhaps it helps.
      function: Process()
      best, l.
    • Apr 20 2012 | 1:34 pm
      Lee, thanks for the code but i think it does a constrained delaunay triangulation, based on the contour area. What i need is a simple delaunay triangulation in a set of given points.
      Here is my mxj code.
      import com.cycling74.max.*; import megamu.mesh.*;
      public class triangulateTest extends MaxObject {
      float[] [] points; public Delaunay myDelaunay;
      public void list (float[][] points) {
      Delaunay myDelaunay = new Delaunay (points);
      public void bang () {
      int[] [] myLinks = myDelaunay.getLinks();
      for (int i=0; i< myLinks.length; i++) { int endIndex = myLinks[i][0]; int startIndex = myLinks[i][1];
      float startX = points[startIndex][0]; float startY = points[startIndex][1]; float endX = points[endIndex][2]; float endY = points[endIndex][3]; //trying to return something outlet(0,"links" + startX + " " + startY + " " + endX + " " + endY);
      Cheers, JM
    • Apr 20 2012 | 5:13 pm
      You've got confused about the scope of variables in Java.
      myDelaunay gets declared twice, once at class-wide scope and then again in your list(float[][]) method. As far as Java is concerned, the more local declaration overrides the more general one, so the class level object is never being created, hence the exception.
      Note that you're doing a similar thing with the points array that you use both as a class variable and as a method argument.
      There are a couple of other things. list(float[][]) won't work for receiving lists from max. You'll need to override list(float[]) or list(Atom[]) and then wrap things up into a 2D array yourself.
      The designer of this library has made life more difficult than it should really be with the way the class is designed as well. There is no way of updating the points without creating a new instance of the object, which is pretty inefficient (at least the source comes with it, so it's easy to address).
    • Apr 20 2012 | 8:24 pm
      Hi Owen,
      I've understand the issues you pointed out. Thanks.
      I've been searching another approach and found some code that doesn't require an external library.
      Trying to get it to work in max, changed the way the variables are declared and wrap a given list into a float array. (as you pointed) :)
      however, the condition [ if (Pontos[a].inside(Pontos[i], Pontos[j], Pontos[k])) ] says that cannot invoke inside in primitive type float.
      I'v been searching for this inside method and found nothing :(
      import com.cycling74.max.*;
      public class delauTest extends MaxObject {
      private float [] Pontos; //points private int N; //number of points
      // private int N = args.length;
      public void list (Atom[] args) {
      //wraping list into float array for (int i = 0; i< args.length; i++) { float x = Pontos[i]; float y = Pontos[i+1]; int N = Pontos.length/2 ; // number of points } }
      public void bang () {
      for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { for (int k = j+1; k < N; k++) { boolean isTriangle = true; for (int a = 0; a < N; a++) { if (a == i || a == j || a == k) continue; // why this doesn't work? if (Pontos[a].inside(Pontos[i], Pontos[j], Pontos[k])) { isTriangle = false; break; } } if (isTriangle) {
      outlet(0, " " + Pontos[i] + " " + Pontos[j] );
      //Pontos[i].drawTo(pontos[j], draw); //pontos[i].drawTo(pontos[k], draw); //pontos[j].drawTo(pontos[k], draw);
      } } }
      } } }
    • Apr 20 2012 | 11:47 pm
      Primitive types in Java (float, double, int, char, short, long) don't behave like normal object references that you can call methods on. To confuse matters there are a setting of corresponding classes - Float, Double, Integer, etc. (note the capital letters) that do expose methods. Under certain circumstances new(ish) versions of Java (>1.5?) are able to magically turn a primitive into an instance of its associated class, but I forget exactly what circumstances these are.
      However, even then, I'm pretty sure that there isn't an inside() method like you show here. I'm guessing that it means if the value of x appears in the set [w y z] in which case just do it long-hand: if(point[a]==point[i]||point[a]==point[j]||point[a]==point[k]).
      Note that in your list(Atom[] args) method you are making the same mistake again by re-declaring N: if you write int N then that is declaring a new variable called N local to the method, which will hide the object variable N. You are also storing up a further NullPointerException by not allocating your array, and also not assigning your input to anything (rather you are assigning the values from your (unallocated) array to two new variables x and y.
      It would be well worth your while to get hold of a decent Java reference to have to hand whilst you're doing this, as it'll go much quicker once you're on top of how to properly declare and use variables.
      Meanwhile, try this (untested, and assuming that all else is right with your code - I'm guessing the array length, could be wrong)
      void list(float[] arg) { N = (int) (arg.length / 2); Pontos = new float[N*2]; for(int i = 0; i < N*2; i++) { Pontos[i] = arg[i]; } }
    • Apr 21 2012 | 3:43 pm
      Hi Owen,
      First, the solution you post is working. I'm very appreciated :)
      It makes sense, the long-hand way, i'v thought about it, just couldn't get the correct syntax. Also, the list function, i understand the issue with the N variable. With your example i'm just setting the variable N to the given list.
      Regarding the decent Java reference you'r pretty right, it's been a while since i learn code languages and from those time's till now i'v been just patching :)
      I'm now reading the c74 java-doc and when some specific doubts appear i just googled them, but you know, somewhere, someone on the internet is wrong :)
      I'm very appreciated by your times and examples, this algorithm will take a part my Master thesis project, a toolkit for interactive data sonification. The triangulation will allow to draw the links in a physical model. Each link and mass will have their physical attributes according to the dynamics of the dataset under analysis, therefore, the user can play de data set. Of course i'll reference you and the original source as well.
      Best regards, JM
    • Feb 04 2015 | 6:19 am
      Hi guys,
      Here follows the link for the external that computes the delaunay triangulaton.
      best, JM
    • Jan 16 2016 | 2:42 pm
      Thank you so much for making and sharing this JM...!
    • Jan 17 2016 | 7:22 am
      Hi Masa, Glad you find it useful. Let me know what are you doing with it.
      Best, João Menezes