Triangulation

Given a set of points it is sometimes useful to have a mesh of triangles made up from those points. For example, you might have a set of height measurements for a terrain, and want to show the landscape in three dimensions. You might also want to display contours for the surface. One common method to do this is called Delaunay Triangulation.

This hack uses code originally by Paul Bourke and converted to Java by Florian Jenett, with a few modifications to make it simpler to use and more Java-like. The algorithms and potential applications are explained perfectly by Paul Bourke at http://local.wasp.uwa.edu.au/~pbourke/papers/triangulate/index.html

Very simple Triangle, Edge and Point3f classes are included in this library - the bare minimum to get it working. The Point3f class has x, y and z coordinates such that for a point p then p.x is the x coordinate, and so on. The Triangle class uses references to three Point3fs p1, p2 and p3, such that if you have a triangle called t then t.p1.x is the x coordinate of the first point, and so on. The triangulate method expects a Java Vector of Point3fs.

Unzip the triangulate folder into your Processing libraries folder, and restart Processing.

/**
triangulation taken from http://processinghacks.com/hacks:triangulation
@author Tom Carden
*/
 
import com.processinghacks.triangulate.*;
 
Vector triangles = new Vector();
Vector points = new Vector();
 
void setup() {
  size(400,400);
  smooth();
  noLoop();
 
  // fill the points Vector with points from a spiral
  float r = 1.0;
  float rv = 1.01;
  float a = 0.0;
  float av = 0.3;
 
  while(r < min(width,height)/2.0) {
    points.addElement(new Point3f(width/2 + r*cos(a), height/2 + r*sin(a), 0));
    a += av;
    r *= rv;
  }
 
  // get the triangulated mesh
  triangles = Triangulate.triangulate(points);
}
 
void draw() {
  background(200);
 
  // draw points as red dots     
  noStroke();
  fill(255,0,0);
 
  for (int i = 0; i < points.size(); i++) {
    Point3f p = (Point3f)points.elementAt(i);
    ellipse(p.x,p.y,2.5,2.5);
  }
 
  // draw the mesh of triangles
  stroke(0,40);
  fill(255,40);
  beginShape(TRIANGLES);
 
  for (int i = 0; i < triangles.size(); i++) {
    Triangle t = (Triangle)triangles.elementAt(i);
    vertex(t.p1.x,t.p1.y);
    vertex(t.p2.x,t.p2.y);
    vertex(t.p3.x,t.p3.y);
  }
  endShape();
}

triangulate.zip

• Paul Bourke's Triangulate page
• Paul Bourke's original C implementation
• Florian Jenett's Java implementation