使用Javascript/Silverlight实现多边形的三角形划分

多边形的三角形划分指的是将一个多边形分成若干个三角形。下述算法以一个对应多边形顶点的Point2D对象数组（逆时针顺序）为输入，返回一组Triangle2D对象作为划分结果。

如果给定的多边形是有效的n边形，则返回的结果集应包含n-2个三角形。划分算法可以描述如下：以逆时针方向遍历多边形顶点，对每三个紧邻的顶点P, Q和R进行测试，如果Q是凸顶点（角PQR小于180°），且P, Q和R三点定义的三角形中不包含任何其他的顶点，则将该三角形放入结果集，并从多边形中割除该三角形。

我们使用Silverlight来显示给定的多边形和其划分结果，每个三角形使用不同颜色表示。

我们首先定义一个CircularLink类来实现一个循环链表。该循环链表的构造是通过在initialize方法中对各元素的next属性进行赋值而完成。

CircularLink类还实现了remove方法，从多边形中删除节点的代码将使用该方法，该方法的实现保证了循环链表的完整性。

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];
  }
};

Polygon2D类的 triangulate方法实现了上述的划分算法。

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;
    }
};

Triangle2D 类是Polygon2D的子类，并实现了两个有用的方法：area返回三角形的面积，contain用于判断该三角形是否包含某个给定的点。

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 );
  }
});

Silverlight的onLoad方法 testTriangulate 定义一组测试数据并调用上述划分算法，并根据划分结果创建不同填充颜色的Silverlight Polygon 对象。

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);
  }
}