A Javascript/Silverlight implementation of polygon triangulation

Triangulation of polygons is the procedure that divides a polygon into triangles. The algorithm discussed below accepts a polygon in the form of an array of Point2D objects that contain the polygon vertices in counter-clockwise order, and return an array of type Triangle2D objects, if the given polygon is valid.

If the given polygon is valid and has n vertices, the result triangle array should have length n - 2. The algorithm works as follows. Traversing the vertices of the polygon in counter-clockwise order, for every three successive vertices P, Q and R of which Q is a convex vertex (with an angle less than 180°), we cut the triangle PQR off the polygon if this triangle does not contain any of the other polygon vertices.

The Silverlight plugin is used to visualise the given polygon and its constituent triangles, which appear in different colors.

The algorithm is started by specifying a CircularLink class that implementation a circularly-linked list. The initializefunction build the circular list by assign the next property of each element, thanks for the advanced Javascript Object-Oriented features.

The CircularLink class also has a remove function that is used when removing vertices from the polygon. The linear circular list is maintained after an element is removed.

CircularLink  = Class.create();

CircularLink.prototype = {
  initialize: function(nodes) {
    this.nodes = nodes;
    var n = this.nodes.length;
    for(var i= 0;i<n-1;i++) {
      this.nodes[i].next = this.nodes[i+1];
    }
    this.nodes[n-1].next = this.nodes[0];
    },

  remove: function(node) {
    var n = this.nodes.length;

    for(var i= 0;i<n;i++){
      if (this.nodes[i] == node) {
        if (i == 0) {
          this.nodes[n-1].next = node.next;
        }
        else {
          this.nodes[i-1].next = node.next;
        }
        this.nodes.splice(i,1);
        return true;
      }
    }
    return false;
  },

  get: function(index) {
    return this.nodes[index];
  }
};

The Polygon2D class implements the above triangulation algorithm in its triangulate function.

Point2D = Class.create();

Point2D.prototype = {
  initialize: function(x, y) {
    this.x = x;
    this.y = y;
  },
};

Polygon2D = Class.create();

Polygon2D.prototype = {
  initialize: function(vertices) {
    this.vertices = vertices;
  },

    triangulate: function() {
    if (!((this.vertices) && (this.vertices.length > 0))) {
      return false;
    }
    var result = new Array();

    var link = new CircularLink(this.vertices);
    var n = this.vertices.length;

    var A = link.get(0);

    for(var k =0; k<n-2;k++) {
      var triaFound = false;
      var count = 0;

      while (!triaFound && ++count < n) {
        var B = A.next;
        var C = B.next;

        var t = new Triangle2D([A, B, C]);

        if (t.area() > 0) {
          var p = C.next;
          while (p != A) {
            if (t.contain(p)) {
              break;
            }
            p = p.next;
          }

          if (p == A) {
            result.push(t);
            link.remove(B);
            triaFound = true;
          }
        }
        A = A.next;
      }

      if (count == n) {
        return false;
      }
    }
    return result;
    }
};

The Triangle2D class, which is a subclass of Polygon2D, defines two useful tools: area computes the area of the triangle, and contain checks if the triangle contains the given point p.

Triangle2D = Class.create();

Triangle2D.prototype = Object.extend(new Polygon2D(), {
  area: function() {
    var a = this.vertices[0];
    var b = this.vertices[1];
    var c = this.vertices[2];

    return ((a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x))/2.0;
  },

  contain: function(p) {
    var a = this.vertices[0];
    var b = this.vertices[1];
    var c = this.vertices[2];

    var t1 = new Triangle2D([a,b,p]);
    var t2 = new Triangle2D([b,c,p]);
    var t3 = new Triangle2D([c,a,p]);

    return ( t1.area() >= 0 &&
        t2.area() >= 0 &&
        t3.area() >= 0 );
  }
});

The Silverlight onLoad function testTriangulate creates Silverlight Polygon objects for each of the result triangle using different Fill color based on given test data set.

function testTriangulate(plugin, context, sender)
{
  var vertices = new Array();
  vertices.push(new Point2D(20,0));
  vertices.push(new Point2D(40,40));
  vertices.push(new Point2D(0,20));
  vertices.push(new Point2D(-40,40));
  vertices.push(new Point2D(-20,0));
  vertices.push(new Point2D(-40,-40));
  vertices.push(new Point2D(0,-20));
  vertices.push(new Point2D(40,-40));

  var center = new Point2D(150,150);

  var colors = ['#FFff5555', '#FF5555ff', '#FF55ff55', '#FFffff55', '#FFff55ff',
    '#FF55ffff', '#FFffafaf',  '#FF808080'];

  var polygon = new Polygon2D(vertices);

  var result = polygon.triangulate();
  for(var i = 0; i<result.length; i++) {
    var plugin = sender.getHost();

    var p = plugin.content.createFromXaml("<Polygon/>");

    var x0 = center.x + result[i].vertices[0].x;
    var y0 = center.y - result[i].vertices[0].y;

    var x1 = center.x + result[i].vertices[1].x;
    var y1 = center.y - result[i].vertices[1].y;

    var x2 = center.x + result[i].vertices[2].x;
    var y2 = center.y - result[i].vertices[2].y;

    var s = x0 + "," + y0  + ","
    + x1 + "," + y1  + ","
    + x2 + "," + y2  + ","
    + x0 + "," + y0;

    p.Points = s;
    p.Fill = colors[i];
    p.Stroke = "White";
    p.StrokeThickness = "2";

    sender.children.add(p);
  }
}

Drawing a wire-frame cube in Silverlight

This post describes a simple example, which draws a perspective representation of a 3D cube using wire-frame representation (i.e. with all edges visible).

The example is implemented using Javascript and Silverlight. We first define three Javascript classes to represent points in different coordinate systems:

Point2D –2D Cartesian coordinate system
Point3D – 3D Cartesian coordinate system
PointSpherical - 3D Spherical coordinate system

function Point2D(x , y)
{
  this.x = x;
  this.y = y;
}

function Point3D(x , y, z)
{
  this.x = x;
  this.y = y;
  this.z = z;
}

function PointSpherical(rho , theta, phi)
{
  this.rho = rho;
  this.theta = theta;
  this.phi = phi;
}

The perspective function implements the viewing and perspective transformations. By using the function, a point in 3D space can be projected to 2D screen coordinates. The perspective function takes three input parameters. i.e.

p – a Point3D object that defines the point in 3D Cartesian coordinate system
eye – a PointSpherical object that defines the vanishing point in 3D Spherical coordinate system
d – defines the distance between the vanishing point and the screen

The function returns a Point2D object that defines the projected point on the screen.

function perspective(p, eye, d)
{
  var costh = Math.cos(eye.theta);
  var sinth = Math.sin(eye.theta);
  var cosph = Math.cos(eye.phi);
  var sinph = Math.sin(eye.phi);

  var v11 = -sinth;
  var v12 = -cosph * costh;
  var v13 = sinph * costh;
  var v21 = costh;
  var v22 = -cosph * sinth;
  var v23 = sinph * sinth;
  var v32 = sinph;
  var v33 = cosph;
  var v43 = -1* eye.rho;

  //viewing transformation
  var x = v11 * p.x + v21 * p.y;
  var y = v12 * p.x + v22 * p.y +
    v32 * p.z;
  var z = v13 * p.x + v23 * p.y +
    v33 * p.z + v43;

  //perspective transformation
  return new Point2D(-d * x / z, -d * y / z);
}

The drawWireFrameCube function is called during the Silverlight onLoad event, which defines the cube vertices and draws the cube edges by creating Silverlight Line objects.

Silverlight.createObjectEx(
{
  source: "#xamlContent_wire_frame_cube",
  parentElement:
    document.getElementById(
      "pluginHost_wire_frame_cube"),
  id: "plugin_wire_frame_cube",
  properties:
  { width: "300",
    height: "300",
    version: "1.0",
    background: "White" },
  events: {onLoad: drawWireFrameCube}
}
);

function drawWireFrameCube(plugin,
  context, sender)
{
  var v = new Array();

  // Bottom surface:
  v[0] = new Point3D(1, -1, -1);
  v[1] = new Point3D(1, 1, -1);
  v[2] = new Point3D(-1, 1, -1);
  v[3] = new Point3D(-1, -1, -1);

  // Top surface:
  v[4] = new Point3D(1, -1, 1);
  v[5] = new Point3D(1, 1, 1);
  v[6] = new Point3D(-1, 1, 1);
  v[7] = new Point3D(-1, -1, 1);

  var eye = new PointSpherical(18, 0.5,1.0);
  var d = 1000;

  var center = new Point2D(150,150);

  var scrPoints = new Array();

  for(var i=0; i<8;i++) {
      scrPoints[i] = perspective(v[i], eye, d);
  }

  line(sender,scrPoints[0],scrPoints[1],center);
  line(sender,scrPoints[1],scrPoints[2],center);
  line(sender,scrPoints[2],scrPoints[3],center);
  line(sender,scrPoints[3],scrPoints[0],center);
  line(sender,scrPoints[4],scrPoints[5],center);
  line(sender,scrPoints[5],scrPoints[6],center);
  line(sender,scrPoints[6],scrPoints[7],center);
  line(sender,scrPoints[7],scrPoints[4],center);
  line(sender,scrPoints[0],scrPoints[4],center);
  line(sender,scrPoints[1],scrPoints[5],center);
  line(sender,scrPoints[2],scrPoints[6],center);
  line(sender,scrPoints[3],scrPoints[7],center);
}

function line(sender, p1, p2, center)
{
  var plugin = sender.getHost();

  var l =
    plugin.content.createFromXaml("<Line/>");
  l.X1 = center.x + p1.x;
  l.Y1 = center.y - p1.y;

  l.X2 = center.x + p2.x;
  l.Y2 = center.y - p2.y;

  l.Stroke = "WhiteSmoke";
  sender.children.add(l);
}
  

Fill primitives in Silverlight

Silverlight defines a number of brush types to fill primitives and geometry objects. A Brush "paints" an area with its output. Different brushes have different types of output. The following examples describe the different types of brushes and their usage:

SolidColorBrush: Paints an area with a solid color.

<Rectangle Width="50" Height="50"
  Canvas.Left="10" Canvas.Top="10"
  Fill="Red"
/>

LinearGradientBrush: Paints an area with a linear gradient.

<Rectangle Width="50" Height="50"
  Canvas.Left="10" Canvas.Top="70">
  <Rectangle.Fill>
    <LinearGradientBrush
      StartPoint="0.5,1" EndPoint="0.5,0">
      <GradientStop
        Color="Blue" Offset="0.0" />
      <GradientStop
        Color="Transparent" Offset="1.0" />
    </LinearGradientBrush>
  </Rectangle.Fill>
</Rectangle>

RadialGradientBrush: Paints an area with a radial gradient.

<Rectangle Width="50" Height="50"
  Canvas.Left="70" Canvas.Top="70">
  <Rectangle.Fill>
    <RadialGradientBrush>
      <GradientStop
        Color="Green" Offset="0.0" />
      <GradientStop
        Color="Transparent" Offset="1.0" />
    </RadialGradientBrush>
  </Rectangle.Fill>
</Rectangle>

In LinearGradientBrush and RadialGradientBrush, the ramp of colors to use on a gradient is defined by the GradientStop elements.

ImageBrush: Paints an area with an image.

<Rectangle Width="150" Height="166"
  Canvas.Left="70" Canvas.Top="10">
  <Rectangle.Fill>
    <ImageBrush
      ImageSource="Silverlight.png"
      Stretch="None" />
  </Rectangle.Fill>
</Rectangle>