第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
Delaunay三角剖分算法（包含部分源码）.doc
Delauney 三角网剖分
算法原理：分为三步：
一、凸包生成：1）求出如下四点：min(x-y)、min(x+y)、max(x-y)、
max(x+y)并顺次放入一个数组，组成初始凸包；2）对于凸包上的
点 I，设它的后续点为 J，计算矢量线段 IJ 右侧的所有点到 IJ 的距
离，求出距离最大的点 K；3）将 K 插入 I,J 之间，并将 K 赋给 J；
4）重复 2，3 步，直到点集中没有在 IJ 右侧的点为止；5）将 J 赋
给 I，J 取其后续点，重复 2，3，4 步，当遍历了一次凸包后，凸
包生成完成。
二、环切边界法凸包三角剖分：在凸包数组中，每次寻找一
个由相邻两条凸包边组成的三角形，在该三角形的内部和边界上
都不包含凸包上的任何其他点，然后去掉该点得到新的凸包链表，
重复这个过程，最终对凸包数组中的点进行三角剖分成功。
三、离散的内插：1）建立三角形的外接圆，找出外接圆包含
待插入点的所有三角形，构成插入区域；2）删除插入区域内的三
角形公共边，形成由影响三角形顶点构成的多边形；3）将插入点
与多边形所有顶点相连，构成新的 Delaunay 三角形；4）重复 1，
2，3，直到所有非凸包上的离散点都插入完为止。
功能实现流程：
1. 在绘图菜单栏下添加一个子菜单项为 Delauney，并且在工具栏
上添加一个工具项。设置 text 为 Delaunay 三角剖分，name 为 delaunay
等属性，添加单击事件，并为单击事件代码
2.为事件函数添加如下代码
Graphics gra = panel1.CreateGraphics();
List pts = new List();
foreach (Geometry_T geo in choosegeos.Geofeatures)
{
}
if (geo.GetType() == typeof(Point_T))
{
}
Point_T pt = (Point_T)geo;
pts.Add(pt);
List deltins = DelauneyTin(pts);//根据多点构建delauney三角网
foreach (Tin tin in deltins)
{
}
Point[] ctin = new Point[3];
for (int i = 0; i < 3; i++)
{
}
cp = new Point((int)tin.Pthree[i].X, (int)tin.Pthree[i].Y);
ctin[i] = cp;
gra.DrawPolygon(Pens.Red, ctin);
3．三角形 TIN 的数据结构
public class Tin
{
Point_T[] pthree = new Point_T[3];
Line_T[] lthree = new Line_T[3];
public Line_T[] Lthree
{
}
get { return lthree; }
set { lthree = value; }
public Point_T[] Pthree
{
}
get { return pthree; }
set { pthree = value; }
public Tin()
{ }
public Tin(Point_T p1, Point_T p2, Point_T p3)
{
}
pthree[0] = p1;
pthree[1] = p2;
pthree[2] = p3;
lthree[0] = new Line_T(p1, p2);
lthree[1] = new Line_T(p2, p3);
lthree[2] = new Line_T(p3, p1);
}
4.圆的数据结构
public class Circle_T:Geometry_T
{
private Point_T cpt;
public Point_T Cpt
{
}
get { return cpt; }
set { cpt = value; }
double radius;
public double Radius
{
}
get { return radius; }
set { radius = value; }
public Circle_T()
{ }
public Circle_T(Point_T pt, double r)
cpt = pt;
radius = r;
{
}
}
5.实现 Delaunay 三角剖分算法
1） public List DelauneyTin(List pts)//根据多点构建delauney三角网；
分三步：构建凸包；凸包剖分；离散点内插
{
Graphics gra = panel1.CreateGraphics();
List deltins = new List();
List envpts = EnvelopeTin(pts);//构建凸包
//for (int i = 0; i < envpts.Count - 1; i++)
//{
//
gra.DrawLine(Pens.Black, new Point((int)envpts[i].X,
(int)envpts[i].Y), new Point((int)envpts[i + 1].X, (int)envpts[i + 1].Y));
//}
//gra.DrawLine(Pens.Black, new Point((int)envpts[0].X, (int)envpts[0].Y),
new Point((int)envpts[envpts.Count - 1].X, (int)envpts[envpts.Count - 1].Y));
List dispts = new List();//非凸包上的离散点
foreach (Point_T pt in pts)
{
}
if (!envpts.Contains(pt))
{
}
dispts.Add(pt);
List envtins = EnvelopeDivision(envpts);//凸包剖分
//foreach (Tin tin in envtins)
//{
//
//
//
//
//
//
//
//}
Point[] ctin = new Point[3];
for (int i = 0; i < 3; i++)
{
}
cp = new Point((int)tin.Pthree[i].X, (int)tin.Pthree[i].Y);
ctin[i] = cp;
gra.DrawPolygon(Pens.Blue, ctin);
deltins = TinInsert(envtins, dispts);//离散点内插
return deltins;
}
2）public List EnvelopeTin(List pts)//构建凸包
{
List envpts = new List();
List othpts = new List();
foreach (Point_T pt in pts)
{
}
othpts.Add(pt);
//构建以x-y，x+y最大最小值组成的初始矩形框
CompareXaddY comxandy = new CompareXaddY();
CompareXsubY comxsuby = new CompareXsubY();
pts.Sort(comxsuby);
envpts.Add(pts[0]);
envpts.Add(pts[pts.Count - 1]);
othpts.Remove(pts[0]);
othpts.Remove(pts[pts.Count-1]);
pts.Sort(comxandy);
if(!envpts.Contains(pts[0]))
{
}
envpts.Insert(1, pts[0]);
if (!envpts.Contains(pts[pts.Count - 1]))
{
}
envpts.Add(pts[pts.Count - 1]);
othpts.Remove(pts[0]);
othpts.Remove(pts[pts.Count-1]);
//构建以x-y，x+y最大最小值组成的初始矩形框
int i = 0;
int tag = 0;
bool over = true;
while(i dismax)
{
dismax = distance;
tag = j;
over = false;
}
}
}
if (over)
{
}
i++;
else
{
}
//envpts.RemoveAt(i);
envpts.Insert(i+1, othpts[tag]);
over = true;
}
return envpts;
}
public List EnvelopeDivision(List pts)//凸包剖分
{
List envtins = new List();
List cpts = new List();
foreach (Point_T pt in pts)
{
}
cpts.Add(pt);
while (cpts.Count > 2)
{
int tag = 0;
double minangle = 120;
for (int i = 0; i < cpts.Count; i++)
{
double angle;
if (i == 0)
angle = CalcuAngle(cpts[cpts.Count - 1], cpts[i], cpts[i + 1]);
{
}
else if (i == cpts.Count - 1)
{
}
else
{
angle = CalcuAngle(cpts[i-1], cpts[i], cpts[0]);
angle = CalcuAngle(cpts[i-1], cpts[i], cpts[i + 1]);
}
if ((angle - 60) < minangle)
{
}
minangle = angle - 60;
tag = i;
}
int btag=tag-1;
int atag=tag+1;
if (tag == 0)
{
}
btag = cpts.Count - 1;
else if (tag == cpts.Count - 1)
{
}
atag = 0;
Tin ctin = new Tin(cpts[btag], cpts[tag], cpts[atag]);
envtins.Add(ctin);
cpts.RemoveAt(tag);
}
return envtins;
}
public List TinInsert(List tins, List pts)//离散点内插
{
List deltins = new List();
List ctins = new List();//临时凸包
foreach (Tin tin in tins)
{
}
ctins.Add(tin);
foreach (Point_T pt in pts)//对离散点遍历，内插
{
List cpts = new List();//临时点集
foreach (Tin tin in ctins)//找到外接圆包含离散点的三角形
{
Circle_T ccir = DelauneyCicle(tin);//构造外接圆
if (IsPointInCircle(pt, ccir))//点是否包含在圆内
{
//for (int i = 0; i < 3; i++)
//{
//
if (!cpts.Contains(tin.Pthree[i]))
{
}
//
//
//
//}
cpts.Add(tin.Pthree[i]);//记录当前点
deltins.Add(tin); //记录保存当前三角形
}
}
//List ecpts = EnvelopeTin(cpts);//求点集（外接圆包含离散的
三角形）的凸包？，接下来，插入点，构建新三角网
//for (int j = 0; j < ecpts.Count;j++ )
//{
//
//
//
//
//
//
//
//
//
//
//}
Tin tin;
if (j == ecpts.Count-1)
{
}
tin = new Tin(ecpts[j], ecpts[0], pt);
else
{
}
tin=new Tin(ecpts[j],ecpts[j+1],pt);
ctins.Add(tin);
List eli = BorderTin(deltins);
foreach (Line_T line in eli)
{
}
Tin tin = new Tin(line.Frompt, line.Topt, pt);
ctins.Add(tin);
foreach (Tin tin in deltins)//改变临时三角网（删除deltins保存的三角
网）
3）
}
{
{
}
ctins.Remove(tin);
deltins.Clear();
}
return ctins;
public bool IsLeftPoint(Point_T pt, Line_T line)//点在线的左边;叉积大于
bool yes = false;
if ((pt.X - line.Frompt.X) * line.ParaA + (pt.Y - line.Frompt.Y) *
line.ParaB > 0)
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
