Triangulation

From Processing

Jump to: navigation, search
Versions: 1.0+
Contributors: tomc, antiplastik
Started: 2006-02-24


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.

File:Triangulate.png

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

Personal tools