JoãoMenezes

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?

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 (http://www.leebyron.com/else/mesh/).
However, when i send the list, it gives me a null pointer exception, and i can't figure out whats wrong... :S

delaunay-triangulation-stucked

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!

here is a triangulation algorithm of a contour implementation in javascript.

here is a triangulation algorithm of a contour implementation in javascript.
perhaps it helps.

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.

public class triangulateTest extends MaxObject {

    Delaunay myDelaunay = new Delaunay (points);

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

import com.cycling74.max.*;
import megamu.mesh.*;

	float[] [] points;
	public Delaunay myDelaunay;

	Delaunay myDelaunay = new Delaunay (points);

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

You've got confused about the scope of variables in Java.

 gets declared twice, once at class-wide scope and then again in your 

 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 

 array that you use both as a class variable and as a method argument.

 won't work for receiving lists from max. You'll need to override 

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

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

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 :(

public class delauTest extends MaxObject {

    private float [] Pontos; //points

    private int N; //number of points

//    private int N = args.length;    

        //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

        for (int i = 0; i < N; i++) {

     if (a == i || a == j || a == k) continue;

     if (Pontos[a].inside(Pontos[i], Pontos[j], Pontos[k])) {

         outlet(0, " " + Pontos[i] + " " + Pontos[j] );

     //Pontos[i].drawTo(pontos[j], draw);

     //pontos[i].drawTo(pontos[k], draw);

     //pontos[j].drawTo(pontos[k], draw);

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) :)

I'v been searching for this inside method and found nothing :( 

	private float [] Pontos; //points
	private int  N; //number of points

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

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

	                    }
	                }
	            }

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 

 method like you show here. I'm guessing that it means if the value of 

if(point[a]==point[i]||point[a]==point[j]||point[a]==point[k])

 method you are making the same mistake again by re-declaring 

 then that is declaring a new variable called 

 local to the method, which will hide the object variable 

 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 

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)

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. 

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

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.

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.

Here follows the link for the external that computes the delaunay triangulaton.

Thank you so much for making and sharing this JM...!

Hi Masa,
Glad you find it useful.
 Let me know what are you doing with it.

Delaunay Triangulation stucked