将任意多边形（无论凸凹）分解为三角形，算法有很多种，我这种比较简单，容易理解和实现。
原理：任意多边形必有一个角是凸角。
方法：先找到多边形的凸角，此点和相邻的2个点构成一个三角形，然后将此点删除 ，剩余的点又构成一个多边形。
继续执行此方法，就可以将多边形分解为三角形了。
寻找多边形凸点的方法可以采用面积法。
a,b,c三点为多边形上连续的三个点。
设S = (a.X - c.X) * (b.Y - c.Y) - (a.Y - c.Y) * (b.X - c.X);
当多边形顶点是按顺时针排列的时候，if S < 0, 则b点是凸点.
当多边形顶点是按逆时针排列的时候，if S > 0, 则b点是凸点.
下面是我写的一个类。
//--------------------------------------------------------
// Copyright (C), 2000-2008, 黄博文.
// File name: PolygonAnalyze.cs
// Author: flysky Version: 1.0 Date: 2008-8-17
// Description: 任意多边形分解为三角形
// Others: 将一任意多边形（无论凸凹，但内部不能有空心）分解为三角形，多边形顶点顺序必须是 顺时针排列。
//--------------------------------------------------------
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.Drawing;
namespace PolygonAnalyze
{
/*---------------------------------------------------------
* 核心算法：
* 定理：任何一个多边形至少都有一个点是凸点。
* 1,找出多边形的一个凸点。
* 2，此凸点与相邻的两个点构成一个三角形。
* 3，将此凸点剔除，剩下的点又构成一个新的多边形。
* 4，回到步骤继续进行，直到多边形剩余的顶点数小于等于个为止。
*
* 寻找多边形凸点的方法是面积法：
*设a,b,c三点是多变形上连续的三个点。
* 1，首先判断a,b,c三点构成的两条线段是否垂直，如果垂直则排除它是凸点。
* 2，设S = (a.X - c.X) * (b.Y - c.Y) - (a.Y - c.Y) * (b.X - c.X);
* 当多边形顶点是按顺时针排列的时候，if S < 0, b点是凸点.
* 当多边形顶点是按逆时针排列的时候，if S > 0, b点是凸点.
*--------------------------------------------------------*/
class PolygonAnalyze
{
public PolygonAnalyze()
{
polygonPoint = new ArrayList();
}
public PolygonAnalyze(ArrayList points)
{
polygonPoint = points;
}
public PolygonAnalyze(Point[] pointList)
{
polygonPoint = new ArrayList ();
for (int i = 0; i < pointList.Length; i++)
{
polygonPoint.Add(pointList[i]);
}
}
/// <summary>
/// 存储多边形点集的动态数组
/// </summary>
private ArrayList polygonPoint;
public ArrayList PolygonPoint
{
get { return polygonPoint; }
set { polygonPoint = value; }
}
/// <summary>
/// 判断b点是否是凸点(多边形点集要以顺时针排列)
/// </summary>
/// <param name="a">b点的前一个点 </param>
/// <param name="b">b点</param>
/// <param name="c">b点的后一个点 </param>
/// <returns></returns>
private bool IsBulge(Point a, Point b, Point c)
{
//判断a,b,c三点组成的线段是否垂直 ，如果垂直返回false
if (c.X - b.X == 0 && b.Y - a.Y == 0)
{
return false;
}
else if (c.Y - b.Y == 0 && b.X - a.X == 0)
{
return false;
}
else if (c.X - b.X != 0 && b.X - a.X != 0 && ((c.Y - b.Y) / (c.X - b.X) * (b.Y - a.Y) / (b.X - a.X)) == -1)
{
return false;
}
//用面积法判断b点是否是凸点。（ 注意多边形顶点的顺序应是顺时针排列，如果是逆时针排列，返回值刚好相反）
int S = (a.X - c.X) * (b.Y - c.Y) - (a.Y - c.Y) * (b.X - c.X);
if (S < 0)
return true;
else
return false;
}
/// <summary>
/// 执行分解算法，返回三角形顶点数组
/// </summary>
/// <returns></returns>
public ArrayList ExcectAnalyze()
{
ArrayList trianglePoints = new ArrayList();
while (polygonPoint.Count > 3)
{
for (int i = 0; i < polygonPoint.Count && polygonPoint.Count > 3; i++)
{
; if (i < polygonPoint.Count - 2)
; {
; if (IsBulge((Point)polygonPoint[i], (Point)polygonPoint[i + 1], (Point)polygonPoint[i + 2]))
; {
; trianglePoints.Add((Point)polygonPoint [i]);
; trianglePoints.Add((Point)polygonPoint [i + 1]);
; trianglePoints.Add((Point)polygonPoint [i + 2]);
&n bsp; polygonPoint.RemoveAt(i + 1);
; }
; }
; else if (i == polygonPoint.Count - 2)
; {
; if (IsBulge((Point)polygonPoint[i], (Point)polygonPoint[i + 1], (Point)polygonPoint[0]))
; {
; trianglePoints.Add((Point)polygonPoint [i]);
; trianglePoints.Add((Point)polygonPoint [i + 1]);
; trianglePoints.Add((Point)polygonPoint [0]);
&n bsp; polygonPoint.RemoveAt(i + 1);
; }
; }
; else if (i == polygonPoint.Count - 1)
; {
; if (IsBulge((Point)polygonPoint[i], (Point)polygonPoint[0], (Point)polygonPoint[1]))
; {
; trianglePoints.Add((Point)polygonPoint [i]);
; trianglePoints.Add((Point)polygonPoint [0]);
; trianglePoints.Add((Point)polygonPoint [1]);
&n bsp; polygonPoint.RemoveAt(0);
; }
; }
}
}
//将剩余的顶点加入数组
for (int i = 0; i < polygonPoint.Count; i++)
{
trianglePoints.Add((Point)polygonPoint[i]);
}
return trianglePoints;
}
}
}
调用很简单：
假设pointlist是多边形按顺时针排列的顶点数组，
PolygonAnalyze polygon = new PolygonAnalyze(pointlist);
ArrayList ary = polygon.ExcectAnalyze();
这个ary就是分解后的三角形的顶点列表。
