====== Triangulation ======

^versions^0095+^

|contributors|[[user:tomc]]|

|started on|2006-02-24 14:36|

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.

{{hacks: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]]

==== Supporting Code ====

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 ''Point3f''s ''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 ''Point3f''s.

===== Installation =====

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

===== Usage =====

<code 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();
}
</code>

===== Downloads =====

{{hacks:triangulate.zip}}

===== Related Links =====

  * [[http://local.wasp.uwa.edu.au/~pbourke/papers/triangulate/index.html|Paul Bourke's Triangulate page]]
  * [[http://local.wasp.uwa.edu.au/~pbourke/papers/triangulate/triangulate.c|Paul Bourke's original C implementation]]
  * [[http://local.wasp.uwa.edu.au/~pbourke/papers/triangulate/triangulate.java|Florian Jenett's Java implementation]]