Triangulation

From Processing

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 and Edge classes are included in this library (see download below) - the bare minimum to get it working. The Triangle class uses references to three PVector objects 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 ArrayList of PVector objects.

This example requires the triangulate Processing library that you may download below.

Source Code

/**
triangulation taken from http://wiki.processing.org/w/Triangulation
@author Tom Carden, Nicolas Clavaud
*/
 
import org.processing.wiki.triangulate.*;
 
ArrayList triangles = new ArrayList();
ArrayList points = new ArrayList();
 
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.add(new PVector(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++) {
    PVector p = (PVector)points.get(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.get(i);
    vertex(t.p1.x, t.p1.y);
    vertex(t.p2.x, t.p2.y);
    vertex(t.p3.x, t.p3.y);
  }
  endShape();
}

Downloads

Media:triangulate-20100704.zip

Related Links