2008年8月20日星期三

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


2008年8月18日星期一

使用透视法在Silverlight中绘制三维线框模型的立方体

本文描述了一个使用透视法在Silverlight中绘制三维线框模型的立方体的例程。所谓的线框模型指的是立方体的各条边线都在视图中可见。

首先定义了三个Javascript类来描述不同的坐标系统中的点。

Point2D –二维笛卡尔坐标系
Point3D – 三维笛卡尔坐标系
PointSpherical - 三维球坐标系

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

下述的perspective函数实现了从三维坐标到二维坐标的透视画法。该函数接受以下三个输入参数,并返回一个Point2D对象.使用该函数,一个三维空间中的点可以被投影到二维屏幕坐标中。

p – 三维笛卡尔坐标系中的一个点 eye – 透视没影点,(三维球坐标系) d – 透视没影点和屏幕之间的距离


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

Silverlight的onLoad事件触发以下的drawWireFrameCube方法。该方法定义了立方体的顶点坐标,并使用Silverlight Line对象绘制立方体边线。


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

2008年8月8日星期五

Silverlight的填充类型

Silverlight定义了若干种填充画笔(brush)类型, 不同的brush输出不同的图形来填充图元内部. 以下示例给出了几种不同的brush基本用法.

SolidColorBrush: 使用单一颜色填充.

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

LinearGradientBrush: 使用线性渐变色填充.

<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: 使用放射状渐变色填充.

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

在LinearGradientBrush和RadialGradientBrush种,颜色的变化通过GradientStop元素进行控制.

ImageBrush: 使用图案填充.

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

2008年8月7日星期四

在Windows 2000上安装Silverlight 2.0

Silverlight的官网上说可以在Windows 2000上安装Silverlight 2.0的plug-in,可安装程序报错说缺少必须的系统模块.

试着几次系统更新,最后确认所需的是Windows Installer,安装了Windows Installer 3.1之后,Silverlight 2.0 plug-in就可以安装了.

2008年8月6日星期三

Silverlight线型和线宽

Silverlight中线型和线宽由Stroke, StrokeThicknessStrokeDashArray三个属性控制。

Stroke 用于设置画笔的颜色和类型,其属性值可以是预定义的颜色名称如Red和MediumBlue等,也可以通过32bit的#rrggbb格式设置。

StrokeThickness 用于设置线宽

StrokeDashArray用于设置虚线模式,其属性值包含若干个体现与线宽比率的浮点数,奇数位上的数值设置虚线的长度,偶数位上的数值设置虚线的间隔,

以下示例显示了三种不同线型和线宽的实线,点线和虚线。


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

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

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

2008年8月4日星期一

在Silverlight中绘制和填充椭圆弧

在Silverlight中画椭圆弧

以下给出了一个画椭圆弧的XAML示例,PathStrokeStrokeThickness属性定义了弧线的颜色和宽度,PathFigureStartPoint属性定义了弧线的起点,ArcSegment则定义了以下弧线属性:

Size : 椭圆的X,Y 半径
Point : 弧线的终点
IsLargeArc : 弧度是否大于180度
SweepDirection : 弧线方向(顺时针或逆时针)

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

在Silverlight中填充椭圆弧

以下给出了一个填充椭圆弧的XAML示例,PathStrokeStrokeThickness属性定义了弧线的颜色和宽度,Fill则定义了填充色,PathFigureStartPoint属性定义了椭圆的中心点,第一个LineSegmentPoint定义了弧线的起点,其后的ArcSegment定义了椭圆弧的大小,终点,方向,是否大于180度等属性,最后的LineSegment则连接了椭圆弧的终点和椭圆的中心点。

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


上述方法可以用于饼图等图形的绘制。

2008年8月3日星期日

Silverlight中的基本图形元素

在计算机图形学中,图形元素(或图元)指的是图形引擎可以输出的最简单的几何形状,一组图元组合在一起则可以用于描绘复杂的结构。

Silverlight中的基本图形元素包括:直线(Line),折线(Polyline),多边形(Polygon),长方形(Rectangle)和椭圆(Ellipse)等。以下是这些元素的基本用法。

直线(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"/>