## Delaunay Triangulation stucked

Apr 20, 2012 at 12:51am

# Delaunay Triangulation stucked

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

Has anyone tried this or something similar?

Thanks,
JM

#63098
Apr 20, 2012 at 8:14am

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

#227680
Apr 20, 2012 at 8:29am

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

function: Process()

best,
l.

###### Attachments:
1. triangulate.js
#227681
Apr 20, 2012 at 1:34pm

Hi,

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 () {

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

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

#227682
Apr 20, 2012 at 5:13pm

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

hth

#227683
Apr 20, 2012 at 8:24pm

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

}
}
}

}
}
}

#227684
Apr 20, 2012 at 11:47pm

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

#227685
Apr 21, 2012 at 3:43pm

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

#227686

You must be logged in to reply to this topic.