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>

Install Silverlight 2.0 on Windows 2000

I tried to install Silverlight 2.0 plug-in on my Windows 2000 pc, which has SP 4 and IE 6 SP1, but got a "Missing required system component" error message, and a link that leads me to the Silverlight supported platform page, which didn’t give any cue.

After a number of guess and try, I found the missing part is the Windows Installer. I installed the Windows Installer 3.1, and then the Silverlight 2.0 plug-in was installed without any problem.

Line style and width in Silverlight

In Silverlight, line style and width are specified using three properties: i.e. Stroke, StrokeThickness and StrokeDashArray.

Stroke is used to define line colour, the value of Stroke can be a predefined name (e.g. Red and MediumBlue), or can be a colour palette using 32-bit palette #rrggbb.

The StrokeThickness property defines the width of the line.

StrokeDashArray is a string of double values that indicates the pattern of dashes and gaps that is used to outline shapes. Each double value in the string specifies the length of a dash or gap relative to the thickness of the pen. For example, a value of 1 creates a dash or gap that has the same length as the thickness of the pen (a square).

The first double entry in the string specifies the length of a dash; the second double entry specifies the length of a gap.

Double entries can be separated by either commas or spaces.

More than one pair of entries can be included in the string, and will repeat in a pattern. Even-numbered entries specify dashes; odd-numbered entries specify gaps. If an odd-numbered total of entries is in the string, then the missing even-numbered entry of a pair will use the gap value specified by the last valid (even-numbered entry) gap value.

The following example shows three lines in a variety of widths and styles.

<Canvas>
  <!-- continues line -->
  <Line X1="100" Y1="100"
    X2="180" Y2="80"
    Stroke="Blue"
    StrokeThickness="2" />

  <!-- dotted line -->
  <Line X1="100" Y1="100"
    X2="100" Y2="20"
    Stroke="#FFD2691E"
    StrokeThickness="2"
    StrokeDashArray="1 1" />

  <!-- dashed line -->
  <Line X1="100" Y1="100"
    X2="20" Y2="80"
    Stroke="Green"
    StrokeThickness="2"
    StrokeDashArray="2.5 1" />
</Canvas>

Drawing and filling ellipse arc in Silverlight

Draw a ellipse arc in Silverlight

Our first XAML example shows how to draw an ellipse arc. The color and width of the arc line are defined by the Stroke and StrokeThickness attributes of the Path element. The PathFigure element specifies the StartPoint attribute that defines where the arc starts. The ArcSegment defines the following properties of the arc:

Size : the X and Y radius of the ellipse
Point : where the arc ends
IsLargeArc : is the arc greater than 180 degrees
SweepDirection : the direction in which the arc is drawn.

<Path Stroke="Red" StrokeThickness="1">
  <Path.Data>
    <PathGeometry>
      <PathFigure
        StartPoint="201.08848540793832,
                    53.183541121547776">
        <ArcSegment
            SweepDirection="CounterClockwise"
            Size="100,80"
            Point="38.91151459206168,
                   53.183541121547776"
            IsLargeArc="false" />
      </PathFigure>
    </PathGeometry>
  </Path.Data>
</Path>

Fill a ellipse arc in Silverlight

The second XAML example shows how to fill an ellipse arc. The colour and width of the arc line are defined by the Stroke and StrokeThickness attributes of the Path element, the Fill attribute defines the colour used to fill the arc. The PathFigure element specifies the StartPoint attribute that defines the centre point of the ellipse. The first LineSegment element specifies the Point attribute that defines where the arc starts, the ArcSegment defines the arc attributes (e.g. Size, Point, IsLargeArc and SweepDirection), and the last LineSegment element close the geometry by specifies the Point attribute using the centre point of the ellipse again.

<Path Stroke="Red"
  StrokeThickness="1" Fill="Blue">
  <Path.Data>
    <PathGeometry>
      <PathFigure StartPoint="120,100">
        <LineSegment
          Point="201.08848540793832,
                 53.183541121547776" />
        <ArcSegment
          SweepDirection="CounterClockwise"
          Size="100,80"
          Point="38.91151459206168,
                 53.183541121547776"
          IsLargeArc="false" />
        <LineSegment Point="120,100" />
      </PathFigure>
    </PathGeometry>
  </Path.Data>
</Path>

Based on above examples, methods that generate pie-charts can be easily developed.

Silverlight graphics output primitives

In computer graphics literature output primitives are defined as basic and the simplest geometric structures that can be rendered by a graphics engine. A set of output primitives can be grouped to describe more complex structures.

Examples of Silverlight output primitives include Line, Polyline, Polygon, Rectangle and Ellipse. Usages of these objects are illustrated in following examples.

Line

<Line X1="10" Y1="10"
    X2="70" Y2="70"
    Stroke="Red"
    StrokeThickness="5"/>

Polyline

<Polyline
    Points="10,10,70,10,10,70,70,70"
    Stroke="Green" StrokeThickness="1"/>

Polygon

<Polygon Points="40,10, 10,40,
    40,70,70,40,
    40,10"
    Stroke="Red" StrokeThickness="1"
    Fill="Blue"/>

Rectangle

<Rectangle Width="40" Height="60"
    Canvas.Left="20" Canvas.Top="10"
    Stroke="Red" StrokeThickness="1"/>

Ellipse

<Ellipse Width="40" Height="60"
    Canvas.Left="20" Canvas.Top="10"
    Fill="Green"/>