精华内容
下载资源
问答
  • 三角网生长算法构建TIN
  • 三角网生长算法构建TIN

    千次阅读 热门讨论 2020-06-09 18:07:40
    三角网生长算法构建TIN(C#版)

    三角网生长算法构建TIN

    本文内容实现均用C#
    文件下载链接:三角网生长算法构建TIN(C#)https://download.csdn.net/download/weixin_43262648/13755874

    !三角网生长算法原理

    以下截图来源于《数字高程模型》一书

    在这里插入图片描述

    1、构建三角形和点存储结构

    public string Filename;
            public System.Drawing.Bitmap curBitmap;
            public Form1()
            {
                InitializeComponent();
            }
            int[] t1 = new int[1000];
            int[] t2 = new int[1000];
            int[] t3 = new int[1000];
            //创建高程点的结构,存储高程点的名称,X、Y坐标,高程H值
            public struct Point
            {
                public int Number;
                public string Name;      //存储点的名称
                public double x;         //存储点的X坐标
                public double y;         //存储点的Y坐标
                public double h;         //存储点的高程值H
            }
            Point[] pt = new Point[1000];   //定义初始的点数组大小为1000
            int Lines;                      //记录文件的行数,即点的个数
            double xmax, xmin, ymax, ymin;  //记录所有点中的x,y坐标最大最小值
            int K;
    

    2、打开高程点数据文件

    //打开高程点数据文件
            private void 打开OToolStripMenuItem_Click(object sender, EventArgs e)
            {
    
                OpenFileDialog filename = new OpenFileDialog();
                filename.Filter = "All files(*.*)|*.*|txt files(*.txt)|*.txt|dat files(*.dat)|*.dat";
                filename.FilterIndex = 2;
                //filename.RestoreDirectory = true;                          
                if (filename.ShowDialog() == DialogResult.OK)
                {
                    Filename = filename.FileName.ToString();
                    string[] lines = File.ReadAllLines(Filename);
                    Lines = lines.Length;
                    for (int i = 1; i <= Lines; i++)
                    {
                        string[] sArray = lines[i - 1].Split(',');  //按","将每一行分割成四个字符串
                        pt[i].Number = i;
                        pt[i].Name = sArray[0];
                        pt[i].x = Convert.ToDouble(sArray[1]);
                        pt[i].y = Convert.ToDouble(sArray[2]);
                        pt[i].h = Convert.ToDouble(sArray[3]);
                    }
                }
            }
    

    3、确定所有点的范围

    //确定所有点的范围
            private void Area()
            {
                xmax = xmin = pt[1].x;
                ymax = ymin = pt[1].y;
                for (int i = 2; i <= Lines; i++)
                {
                    if (xmax < pt[i].x) xmax = pt[i].x;
                    if (xmin > pt[i].x) xmin = pt[i].x;
                    if (ymax < pt[i].y) ymax = pt[i].y;
                    if (ymin > pt[i].y) ymin = pt[i].y;
                }
            }
    

    4、计算坐标转换比例因子

     //计算坐标转换比例因子
            public double CalcScale()
            {
                Area();
                Rectangle m_rect = pictureBox1.ClientRectangle;
                double ds = 1.0;
                double dsx, dsy;
                if ((xmax - xmin != 0) && (ymax - ymin != 0))
                {
                    dsx = Math.Abs((xmax - xmin) / m_rect.Height);
                    dsy = Math.Abs((ymax - ymin) / m_rect.Width);
                    ds = Math.Max(dsx, dsy);
                }
                else
                {
                    if (xmax - xmin != 0)
                    {
                        ds = Math.Abs((xmax - xmin) / m_rect.Height);
                    }
                    else
                    {
                        if (ymax - ymin != 0)
                        {
                            ds = Math.Abs((ymax - ymin) / m_rect.Width);
                        }
                        else { ds = 1; }
                    }
                }
                return ds;
            }
    

    5、找到最近的两个高程点

     //找到两个最近的高程点
            public void MinDistance(Point[] pt, out int pt1, out int pt2)
            {
                int i, j;
                double[,] Distance = new double[Lines, Lines];
                //将任意两点间的距离存储到矩阵Distance中
                for (i = 1; i <= Lines; i++)
                    for (j = i + 1; j < Lines; j++)
                        if (i != j)
                            Distance[i, j] = Math.Sqrt(Math.Pow(pt[i].x - pt[j].x, 2) + Math.Pow(pt[i].y - pt[j].y, 2));
                double[] Mindistance = { 10000, 0, 0 };
                //找到矩阵Distance中的最小值,并记录行列号
                for (i = 1; i <= Lines; i++)
                    for (j = i + 1; j < Lines; j++)
                        if (Mindistance[0] > Distance[i, j])
                        {
                            Mindistance[0] = Distance[i, j];
                            Mindistance[1] = i;
                            Mindistance[2] = j;
                        }
                pt1 = (int)Mindistance[1];
                pt2 = (int)Mindistance[2];
            }
    

    6、找到离中点最近的点

    //找到离中点最近的点
            public void Find(int pt1, int pt2, out int pt3)
            {
                int i;
                double meanx = (pt[pt1].x + pt[pt2].x) / 2;
                double meany = (pt[pt1].y + pt[pt2].y) / 2;
                double Min = 10000000000;
                pt3 = 0;
                for (i = 1; i <= Lines; i++)
                {
                    if (i != pt1 && i != pt2)
                    {
                        double temp = Math.Sqrt(Math.Pow(pt[i].x - meanx, 2) + Math.Pow(pt[i].y - meany, 2));
                        if (Min > temp)
                        {
                            Min = temp;
                            pt3 = i;
                        }
                    }
                }
            }
    

    7、判断三角形扩展是否在同一侧

    //判断三角形扩展点是否在同一侧
            public bool Direction(int point1, int point2, int point3, int point4)
            {
                //计算直线方程的系数a,b
                double a = (pt[point2].y - pt[point1].y) / (pt[point2].x - pt[point1].x);
                double b = (pt[point1].x * pt[point2].y - pt[point2].x * pt[point1].y) / (pt[point2].x - pt[point1].x);
                double fxy1 = pt[point3].y - (a * pt[point3].x - b);
                double fxy2 = pt[point4].y - (a * pt[point4].x - b);
                //当位于非同一侧时
                if (fxy1 < 0 && fxy2 > 0 || fxy1 > 0 && fxy2 < 0)
                    return true;
                //当位于同一侧时
                else return false;
            }
    

    8、计算扩展边的角度余弦值

    //计算扩展边的角度余弦值
            public double Angle(int pt1, int pt2, int pt3)
            {
                double angle;
                double L1 = Math.Sqrt((pt[pt2].x - pt[pt3].x) * (pt[pt2].x - pt[pt3].x) + (pt[pt2].y - pt[pt3].y) * (pt[pt2].y - pt[pt3].y));
                double L2 = Math.Sqrt((pt[pt1].x - pt[pt3].x) * (pt[pt1].x - pt[pt3].x) + (pt[pt1].y - pt[pt3].y) * (pt[pt1].y - pt[pt3].y));
                double L3 = Math.Sqrt((pt[pt2].x - pt[pt1].x) * (pt[pt2].x - pt[pt1].x) + (pt[pt2].y - pt[pt1].y) * (pt[pt2].y - pt[pt1].y));
                angle = (L1 * L1 + L2 * L2 - L3 * L3) / (2 * L1 * L2);
                return angle;
            }
    

    9、找到扩展边形成张角最大的点

    //找到扩展边形成张角最大的点
            private int MaxAngle(int[] x, int A, int B, int n)
            {
                double C = 0, temp, s = 0;
                int max = 0;
                for (int i = 1; i <= n; i++)
                {
                    if (x[i] != A && x[i] != B)
                    {
                        s = Angle(A, B, x[i]);
                        if (s < 1)
                            C = Math.Acos(s);
                        else C = 0;
                        max = x[i];
                        break;
                    }
                }
                for (int i = 1; i <= n; i++)
                {
                    if (i != A && i != B)
                    {
                        s = Angle(A, B, x[i]);
                        if (s < 1)
                            temp = Math.Acos(s);
                        else temp = 0;
                        if (temp > C)
                        {
                            C = temp;
                            max = x[i];
                        }
                    }
                }
                return max;
            }
    

    10、判断三角形的一条边是否已经出现过两次

     //判断三角形的一条边是否已经出现过两次
            public bool Repeat(int point1, int point2, int L)
            {
                int sum = 0;
                for (int i = 1; i <= L; i++)
                {
                    if (point1 == t1[i] && point2 == t2[i] || point1 == t2[i] && point2 == t1[i] ||
                        point1 == t2[i] && point2 == t3[i] || point1 == t3[i] && point2 == t2[i] ||
                        point1 == t3[i] && point2 == t1[i] || point1 == t1[i] && point2 == t3[i])
                    {
                        sum++;
                        if (sum == 2)
                            return false;
                    }
                }
                return true;
            }
    

    12、构建并绘制TIN

    private void 构建TINCToolStripMenuItem_Click(object sender, EventArgs e)
            {
    
                //找到所有点中距离最小的两个点,作为第一个三角形的第一个点和第二个点
                MinDistance(pt, out int point1, out int point2);
                t1[1] = point1;
                t2[1] = point2;
    
                //寻找第一个三角形的第三个点:离第一条边距离最短的点
                Find(point1, point2, out int point3);
                t3[1] = point3;
    
                //设置计数变量K记录扩展的三角形数
                K = 0;
                //设置计数变量L记录已经形成的三角形数
                int L = 1;
                //设置数组存储可能的扩展点
                int[] x = new int[Lines];
    
                //扩展三角形
                while (K != L)
                {
                    K++;
                    point1 = t1[K];
                    point2 = t2[K];
                    point3 = t3[K];
    
                    //第一条扩展边不重复,没有被两个三角形共用
                    if (Repeat(point1, point2, L))
                    {
                        //判断新扩展的边
                        int t = 0;
                        x[t++] = 0;
                        //寻找可能的扩展点
                        for (int i = 1; i <= Lines; i++)
                            if (i != point1 && i != point2 && i != point3 && Direction(point1, point2,point3, i))
                            {
                                x[t++] = i;
                            }
                        //存在扩展点
                        if (t > 1)
                        {
                            int max = MaxAngle(x, point1, point2, t - 1);
                            L = L + 1;
                            t1[L] = point1;
                            t2[L] = point2;
                            t3[L] = max;
                        }
                    }
    
                    //第二条扩展边不重复,没有被两个三角形共用
                    if (Repeat(point1, point3, L))
                    {
                        int t = 0;
                        x[t++] = 0;
                        for (int i = 1; i <= Lines; i++)
                            if (i != point1 && i != point3 && i != point2 && Direction(point1, point3, point2, i))
                            {
                                x[t++] = i;
                            }
                        if (t > 1)
                        {
                            int max = MaxAngle(x, point1, point3, t - 1);
                            L = L + 1;
                            t1[L] = point1;
                            t2[L] = point3;
                            t3[L] = max;
                        }
                    }
    
                    //第三条扩展边不重复,没有被两个三角形共用
                    if (Repeat(point2, point3, L))
                    {
                        int t = 0;
                        x[t++] = 0;
                        for (int i = 1; i <= Lines; i++)
                            if (i != point2 && i != point3 && i != point1 && Direction(point2, point3, point1, i))
                            {
                                x[t++] = i;
                            }
                        if (t > 1)
                        {
                            int max = MaxAngle(x, point2, point3, t - 1);
                            L = L + 1;
                            t1[L] = point2;
                            t2[L] = point3;
                            t3[L] = max;
                        }
                    }
                }
    
                //绘制TIN
                Graphics g = pictureBox1.CreateGraphics();
                double m_scale = CalcScale();
                Pen mypen = new Pen(Color.Red, 1);                   //创建画笔
                Rectangle m_rect = pictureBox1.ClientRectangle;      //获得画布大小
                g.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.HighQuality; //消除锯齿
                for (int i = 1; i <= L; i++)
                {
                    //由测量坐标计算屏幕坐标
                    double ix1 = (pt[t1[i]].y - ymin) / m_scale;
                    double iy1 = m_rect.Height - (pt[t1[i]].x - xmin) / m_scale - 20;
    
                    double ix2 = (pt[t2[i]].y - ymin ) / m_scale;
                    double iy2 = m_rect.Height - (pt[t2[i]].x - xmin) / m_scale - 20;
    
                    double ix3 = (pt[t3[i]].y - ymin) / m_scale;
                    double iy3 = m_rect.Height - (pt[t3[i]].x - xmin) / m_scale - 20;
    
    
                    g.DrawLine(mypen, (float)ix1, (float)iy1, (float)ix2, (float)iy2);
                    g.DrawLine(mypen, (float)ix1, (float)iy1, (float)ix3, (float)iy3);
                    g.DrawLine(mypen, (float)ix3, (float)iy3, (float)ix2, (float)iy2);
                }
                //g.Dispose();
            }
    

    展点结果

    在这里插入图片描述

    设计界面

    功能菜单设置-1
    在这里插入图片描述
    在这里插入图片描述

    绘制TIN结果

    在这里插入图片描述

    高程点文件内容:()

    1,512851.699,1121834.867,210.310
    2,512850.236,1121835.836,210.430
    3,512848.802,1121836.824,210.310
    4,512847.151,1121814.595,210.290
    5,512849.057,1121831.194,210.440
    6,512846.319,1121834.680,210.360
    7,512847.872,1121828.652,210.430
    8,512844.406,1121835.692,210.410
    9,512849.974,1121822.530,210.350
    10,512847.420,1121826.715,210.330
    11,512841.893,1121816.777,210.380
    12,512842.204,1121833.716,210.390
    13,512845.495,1121825.847,210.410
    14,512847.488,1121821.435,210.470
    15,512839.877,1121837.289,210.520
    16,512842.601,1121829.914,210.470
    17,512847.693,1121830.249,210.360
    18,512843.665,1121825.828,210.440
    19,512841.285,1121830.542,210.350
    20,512850.042,1121810.872,210.320
    21,512850.820,1121807.228,210.350
    22,512839.262,1121831.614,210.430
    23,512840.900,1121826.505,210.360
    24,512847.948,1121806.836,210.330
    25,512839.078,1121822.817,210.360
    26,512851.561,1121787.907,210.460
    27,512836.039,1121822.946,210.330
    28,512843.538,1121805.103,210.410
    29,512845.537,1121792.055,211.540
    30,512848.374,1121791.586,211.930
    31,512849.211,1121789.581,211.860
    32,512831.485,1121831.862,210.350
    33,512841.485,1121810.862,210.350
    34,512835.537,1121810.055,211.540
    35,512838.540,1121805.496,210.528
    36,512830.158,1121800.693,211.359
    37,512840.088,1121790.363,210.358
    

    —————————————————————————————

    完整代码

    using System;
    using System.Collections.Generic;
    using System.ComponentModel;
    using System.Data;
    using System.Drawing;
    using System.Linq;
    using System.Text;
    using System.IO;
    using System.Threading.Tasks;
    using System.Windows.Forms;
    
    namespace TIN
    {
        public partial class Form1 : Form
        {
            public string Filename;
            public System.Drawing.Bitmap curBitmap;
            public Form1()
            {
                InitializeComponent();
            }
            int[] t1 = new int[1000];
            int[] t2 = new int[1000];
            int[] t3 = new int[1000];
            //创建高程点的结构,存储高程点的名称,X、Y坐标,高程H值
            public struct Point
            {
                public int Number;
                public string Name;      //存储点的名称
                public double x;         //存储点的X坐标
                public double y;         //存储点的Y坐标
                public double h;         //存储点的高程值H
            }
            Point[] pt = new Point[1000];   //定义初始的点数组大小为1000
            int Lines;                      //记录文件的行数,即点的个数
            double xmax, xmin, ymax, ymin;  //记录所有点中的x,y坐标最大最小值
            int K;
    
            //打开高程点数据文件
            private void 打开OToolStripMenuItem_Click(object sender, EventArgs e)
            {
    
                OpenFileDialog filename = new OpenFileDialog();
                filename.Filter = "All files(*.*)|*.*|txt files(*.txt)|*.txt|dat files(*.dat)|*.dat";
                filename.FilterIndex = 2;
                //filename.RestoreDirectory = true;                          
                if (filename.ShowDialog() == DialogResult.OK)
                {
                    Filename = filename.FileName.ToString();
                    string[] lines = File.ReadAllLines(Filename);
                    Lines = lines.Length;
                    for (int i = 1; i <= Lines; i++)
                    {
                        string[] sArray = lines[i - 1].Split(',');  //按","将每一行分割成四个字符串
                        pt[i].Number = i;
                        pt[i].Name = sArray[0];
                        pt[i].x = Convert.ToDouble(sArray[1]);
                        pt[i].y = Convert.ToDouble(sArray[2]);
                        pt[i].h = Convert.ToDouble(sArray[3]);
                    }
                }
            }
    
            //确定所有点的范围
            private void Area()
            {
                xmax = xmin = pt[1].x;
                ymax = ymin = pt[1].y;
                for (int i = 2; i <= Lines; i++)
                {
                    if (xmax < pt[i].x) xmax = pt[i].x;
                    if (xmin > pt[i].x) xmin = pt[i].x;
                    if (ymax < pt[i].y) ymax = pt[i].y;
                    if (ymin > pt[i].y) ymin = pt[i].y;
                }
            }
    
            //计算坐标转换比例因子
            public double CalcScale()
            {
                Area();
                Rectangle m_rect = pictureBox1.ClientRectangle;
                double ds = 1.0;
                double dsx, dsy;
                if ((xmax - xmin != 0) && (ymax - ymin != 0))
                {
                    dsx = Math.Abs((xmax - xmin) / m_rect.Height);
                    dsy = Math.Abs((ymax - ymin) / m_rect.Width);
                    ds = Math.Max(dsx, dsy);
                }
                else
                {
                    if (xmax - xmin != 0)
                    {
                        ds = Math.Abs((xmax - xmin) / m_rect.Height);
                    }
                    else
                    {
                        if (ymax - ymin != 0)
                        {
                            ds = Math.Abs((ymax - ymin) / m_rect.Width);
                        }
                        else { ds = 1; }
                    }
                }
                return ds;
            }
    
            //找到两个最近的高程点
            public void MinDistance(Point[] pt, out int pt1, out int pt2)
            {
                int i, j;
                double[,] Distance = new double[Lines, Lines];
                //将任意两点间的距离存储到矩阵Distance中
                for (i = 1; i <= Lines; i++)
                    for (j = i + 1; j < Lines; j++)
                        if (i != j)
                            Distance[i, j] = Math.Sqrt(Math.Pow(pt[i].x - pt[j].x, 2) + Math.Pow(pt[i].y - pt[j].y, 2));
                double[] Mindistance = { 10000, 0, 0 };
                //找到矩阵Distance中的最小值,并记录行列号
                for (i = 1; i <= Lines; i++)
                    for (j = i + 1; j < Lines; j++)
                        if (Mindistance[0] > Distance[i, j])
                        {
                            Mindistance[0] = Distance[i, j];
                            Mindistance[1] = i;
                            Mindistance[2] = j;
                        }
                pt1 = (int)Mindistance[1];
                pt2 = (int)Mindistance[2];
            }
    
            //找到离中点最近的点
            public void Find(int pt1, int pt2, out int pt3)
            {
                int i;
                double meanx = (pt[pt1].x + pt[pt2].x) / 2;
                double meany = (pt[pt1].y + pt[pt2].y) / 2;
                double Min = 10000000000;
                pt3 = 0;
                for (i = 1; i <= Lines; i++)
                {
                    if (i != pt1 && i != pt2)
                    {
                        double temp = Math.Sqrt(Math.Pow(pt[i].x - meanx, 2) + Math.Pow(pt[i].y - meany, 2));
                        if (Min > temp)
                        {
                            Min = temp;
                            pt3 = i;
                        }
                    }
                }
            }
    
            //判断三角形扩展点是否在同一侧
            public bool Direction(int point1, int point2, int point3, int point4)
            {
                //计算直线方程的系数a,b
                double a = (pt[point2].y - pt[point1].y) / (pt[point2].x - pt[point1].x);
                double b = (pt[point1].x * pt[point2].y - pt[point2].x * pt[point1].y) / (pt[point2].x - pt[point1].x);
                double fxy1 = pt[point3].y - (a * pt[point3].x - b);
                double fxy2 = pt[point4].y - (a * pt[point4].x - b);
                //当位于非同一侧时
                if (fxy1 < 0 && fxy2 > 0 || fxy1 > 0 && fxy2 < 0)
                    return true;
                //当位于同一侧时
                else return false;
            }
    
            //计算扩展边的角度余弦值
            public double Angle(int pt1, int pt2, int pt3)
            {
                double angle;
                double L1 = Math.Sqrt((pt[pt2].x - pt[pt3].x) * (pt[pt2].x - pt[pt3].x) + (pt[pt2].y - pt[pt3].y) * (pt[pt2].y - pt[pt3].y));
                double L2 = Math.Sqrt((pt[pt1].x - pt[pt3].x) * (pt[pt1].x - pt[pt3].x) + (pt[pt1].y - pt[pt3].y) * (pt[pt1].y - pt[pt3].y));
                double L3 = Math.Sqrt((pt[pt2].x - pt[pt1].x) * (pt[pt2].x - pt[pt1].x) + (pt[pt2].y - pt[pt1].y) * (pt[pt2].y - pt[pt1].y));
                angle = (L1 * L1 + L2 * L2 - L3 * L3) / (2 * L1 * L2);
                return angle;
            }
    
            //找到扩展边形成张角最大的点
            private int MaxAngle(int[] x, int A, int B, int n)
            {
                double C = 0, temp, s = 0;
                int max = 0;
                for (int i = 1; i <= n; i++)
                {
                    if (x[i] != A && x[i] != B)
                    {
                        s = Angle(A, B, x[i]);
                        if (s < 1)
                            C = Math.Acos(s);
                        else C = 0;
                        max = x[i];
                        break;
                    }
                }
                for (int i = 1; i <= n; i++)
                {
                    if (i != A && i != B)
                    {
                        s = Angle(A, B, x[i]);
                        if (s < 1)
                            temp = Math.Acos(s);
                        else temp = 0;
                        if (temp > C)
                        {
                            C = temp;
                            max = x[i];
                        }
                    }
                }
                return max;
            }
    
            //判断三角形的一条边是否已经出现过两次
            public bool Repeat(int point1, int point2, int L)
            {
                int sum = 0;
                for (int i = 1; i <= L; i++)
                {
                    if (point1 == t1[i] && point2 == t2[i] || point1 == t2[i] && point2 == t1[i] ||
                        point1 == t2[i] && point2 == t3[i] || point1 == t3[i] && point2 == t2[i] ||
                        point1 == t3[i] && point2 == t1[i] || point1 == t1[i] && point2 == t3[i])
                    {
                        sum++;
                        if (sum == 2)
                            return false;
                    }
                }
                return true;
            }
    
            private void 构建TINCToolStripMenuItem_Click(object sender, EventArgs e)
            {
    
                //找到所有点中距离最小的两个点,作为第一个三角形的第一个点和第二个点
                MinDistance(pt, out int point1, out int point2);
                t1[1] = point1;
                t2[1] = point2;
    
                //寻找第一个三角形的第三个点:离第一条边距离最短的点
                Find(point1, point2, out int point3);
                t3[1] = point3;
    
                //设置计数变量K记录扩展的三角形数
                K = 0;
                //设置计数变量L记录已经形成的三角形数
                int L = 1;
                //设置数组存储可能的扩展点
                int[] x = new int[Lines];
    
                //扩展三角形
                while (K != L)
                {
                    K++;
                    point1 = t1[K];
                    point2 = t2[K];
                    point3 = t3[K];
    
                    //第一条扩展边不重复,没有被两个三角形共用
                    if (Repeat(point1, point2, L))
                    {
                        //判断新扩展的边
                        int t = 0;
                        x[t++] = 0;
                        //寻找可能的扩展点
                        for (int i = 1; i <= Lines; i++)
                            if (i != point1 && i != point2 && i != point3 && Direction(point1, point2,point3, i))
                            {
                                x[t++] = i;
                            }
                        //存在扩展点
                        if (t > 1)
                        {
                            int max = MaxAngle(x, point1, point2, t - 1);
                            L = L + 1;
                            t1[L] = point1;
                            t2[L] = point2;
                            t3[L] = max;
                        }
                    }
    
                    //第二条扩展边不重复,没有被两个三角形共用
                    if (Repeat(point1, point3, L))
                    {
                        int t = 0;
                        x[t++] = 0;
                        for (int i = 1; i <= Lines; i++)
                            if (i != point1 && i != point3 && i != point2 && Direction(point1, point3, point2, i))
                            {
                                x[t++] = i;
                            }
                        if (t > 1)
                        {
                            int max = MaxAngle(x, point1, point3, t - 1);
                            L = L + 1;
                            t1[L] = point1;
                            t2[L] = point3;
                            t3[L] = max;
                        }
                    }
    
                    //第三条扩展边不重复,没有被两个三角形共用
                    if (Repeat(point2, point3, L))
                    {
                        int t = 0;
                        x[t++] = 0;
                        for (int i = 1; i <= Lines; i++)
                            if (i != point2 && i != point3 && i != point1 && Direction(point2, point3, point1, i))
                            {
                                x[t++] = i;
                            }
                        if (t > 1)
                        {
                            int max = MaxAngle(x, point2, point3, t - 1);
                            L = L + 1;
                            t1[L] = point2;
                            t2[L] = point3;
                            t3[L] = max;
                        }
                    }
                }
    
                //绘制TIN
                Graphics g = pictureBox1.CreateGraphics();
                double m_scale = CalcScale();
                Pen mypen = new Pen(Color.Red, 1);                   //创建画笔
                Rectangle m_rect = pictureBox1.ClientRectangle;      //获得画布大小
                g.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.HighQuality; //消除锯齿
                for (int i = 1; i <= L; i++)
                {
                    //由测量坐标计算屏幕坐标
                    double ix1 = (pt[t1[i]].y - ymin) / m_scale;
                    double iy1 = m_rect.Height - (pt[t1[i]].x - xmin) / m_scale - 20;
    
                    double ix2 = (pt[t2[i]].y - ymin ) / m_scale;
                    double iy2 = m_rect.Height - (pt[t2[i]].x - xmin) / m_scale - 20;
    
                    double ix3 = (pt[t3[i]].y - ymin) / m_scale;
                    double iy3 = m_rect.Height - (pt[t3[i]].x - xmin) / m_scale - 20;
    
    
                    g.DrawLine(mypen, (float)ix1, (float)iy1, (float)ix2, (float)iy2);
                    g.DrawLine(mypen, (float)ix1, (float)iy1, (float)ix3, (float)iy3);
                    g.DrawLine(mypen, (float)ix3, (float)iy3, (float)ix2, (float)iy2);
                }
                //g.Dispose();
            }
    
            //展高程点
            private void 选项OToolStripMenuItem_Click(object sender, EventArgs e)
            {
                Area();
                Graphics g = pictureBox1.CreateGraphics();
                Rectangle m_rect = pictureBox1.ClientRectangle;//获得画布大小
                Font myFont = new Font("宋体", 8, FontStyle.Bold);//创建字体
                Brush bush = new SolidBrush(Color.Black);//创建单色画刷
                double m_scale = CalcScale();
                for (int i = 1; i <= Lines; i++)
                {
                    //由测量坐标计算屏幕坐标
                    double ix = (pt[i].y - ymin ) / (m_scale);
                    double iy = m_rect.Height - (pt[i].x - xmin) / (m_scale) -20;
    
                    g.DrawEllipse(new Pen(Color.Black), (float)ix, (float)iy, 3, 3);
                    g.FillEllipse(new SolidBrush(Color.Black), (float)ix, (float)iy, 3, 3);
                    g.DrawString(pt[i].Name, myFont, bush, (float)ix - 3, (float)iy + 5);
                }
            }
    
            //导出三角形
            private void toolStripMenuItem1_Click(object sender, EventArgs e)
            {
                SaveFileDialog filename1 = new SaveFileDialog();
                string newTxtPath = Application.StartupPath + "/Result-All-Tri.txt";
                StreamWriter sw = new StreamWriter(newTxtPath, false, Encoding.Default);
                sw.WriteLine("=========================三角形组成========================");
                sw.WriteLine("三角形序号      第一点序号      第二点序号       第三点序号");
                for (int i = 1; i <= K; i++)
                {
                    sw.WriteLine("{0,5}{1,17}{2,17}{3,17}", i.ToString(), t1[i].ToString(), t2[i].ToString(), t3[i].ToString());
                }
                sw.Flush();
                System.Diagnostics.Process.Start(newTxtPath);
            }
    
            //退出窗口
            private void 退出XToolStripMenuItem_Click(object sender, EventArgs e)
            {
                Close();
            }
        }
    }
    
    
    展开全文
  • 三角剖分—三角网生长算法。Delaunay三角网有一个特性,每个三角网形成的外接圆都不包含其他参考点。利用这一个性质,我们可以直接构成Delaunay三角网。
  • 用C++写的一个简单的三角网生长算法,MFC界面
  • 针对传统三角网生长算法需要花费大量时间检索第三点的问题,对三角网生长算法进行改进,即对离散点集所在的区域由外到内进行矩形环式的分区,而后从内环到外环逐渐生成Delaunay三角形。每次查询第三点时,在当前环和其...
  • 三角网生长法具有独特的优势,但将其扩展到三维的研究远远少于逐点插入法、分治法以及二者的合成算法,研究扩展三角网生长法实现三维DT剖分的算法。引入k近邻思想优化了原始算法,时间复杂度可达O(NlogN),且改进...
  • Delaunay三角剖分—三角网生长算法

    千次阅读 2017-03-08 20:35:53
    Delaunay三角网是俄国数学家B.Delaunay于1934年发现的。关于Delaunay三角网构建的研究有许多,但由于本课题具有数据量大的特征,不宜直接沿用已有构建方法,笔者针对本课题数据特征,研究获得了适应本课题,速度较快...

    Delaunay三角网是俄国数学家B.Delaunay于1934年发现的。关于Delaunay三角网构建的研究有许多,但由于本课题具有数据量大的特征,不宜直接沿用已有构建方法,笔者针对本课题数据特征,研究获得了适应本课题,速度较快的构建方法。Delaunay三角网有一个特性,每个三角网形成的外接圆都不包含其他参考点。利用这一个性质,我们可以直接构成Delaunay三角网:
    一、建立第一个三角形
    1、判断用来建立TIN的总脚点数,小于3则报错退出。
    2、第一点的选择:
    链表的第一节点,命名为Pt1;
    3、第二点的选择:
    A.非Pt1点; B.距Pt1最近
    命名为Pt2
    4、第三点的选择
    A.非Pt1,Pt2点;
    B.与Pt1,Pt2点组成的三角形的外接圆内无其他节点;
    C.与Pt1,Pt2组成的三角形中的角Pt1Pt3Pt2最大。
    命名为Pt3
    5、生成三边,加入边表
    6、生成第一个三角形,组建三角形表
    二、扩展TIN
    1、从边表头取一边,要求:该边flag标志为假(只在一个三角形中)
    2、从点链表中搜索一点,要求:
    A、与边中的Pixel3在边的异侧;
    B、该点与边组成的三角形的外接圆内无其他点
    C、满足上面两条件的点中角Pt1Pt3Pt2最大的点为Pt3。
    3、判断新生成的边,如果边表中没有,则加入边表尾,设定标志flag为假,如果有,则设定该边flag为真。
    4、将生成的三角形假如三角形表
    5、设定选中的边的标志flag为真
    6、转至1,直至边表边的标志flag全部为真。

    注:如果需要进行限制三角剖分,则可利用重心法取出不要的三角形,必要时,可对边界进行限制,不让生成的边与边界相交

    数据结构:

    struct Pixel    //脚点数据
    {
    double x,y,z,g;
    bool flag;
    };
    struct List //数据链表
    {
    Pixel *pixel;
    List *next;
    };
    struct Line //三角形边
    {
    Pixel *pixel1;  //三角形边一端点
    Pixel *pixel2;  //三角形边另一端点
    Pixel *pixel3;  //三角形边所对顶点
    bool flag;
    };
    struct Linelist //三角形边表
    {
    Line *line;
    Linelist *next;
    };
    struct Triangle //三角形表
    {
    Line *line1;
    Line *line2;
    Line *line3;
    Triangle *next;
    };
    
    
    
    以下是程序中关于建网的部分:
    // DelaunayTIN.cpp: implementation of the CDelaunayTIN class.
    //
    //
    //功能:   用给定的数据链表数据,组建Delaunay不规则三角网
    //输入参数:数据链表list;区域范围(XMin,YMin),(XMax,YMax)
    //输出参数:不规则三角网首三角形地址
    
     Triangle * CSimRegular::CreateDelaunayTIN(List *list)
    {
        //组建第一个三角形
         List *node;
         Pixel *pt1,*pt2,*pt3;
        bool flag;
        Triangle *TIN;
        pt1=list->pixel;
        pt2=list->next->pixel;
        node=list->next->next;
        while(node!=NULL)
        {
            if(
             (pt1->x-node->pixel->x)*(pt1->x-node->pixel->x)+(pt1->y-node->pixel->y)*(pt1->y-node->pixel->y)
           <(pt1->x-pt2->x)*(pt1->x-pt2->x)+(pt1->y-pt2->y)*(pt1->y-pt2->y)         
                )
            {
                pt2=node->pixel;
            }
            node=node->next;
        }
        node=list->next;
        pt3=NULL;
        while(node!=NULL)
        {
            if(node->pixel==pt1 || node->pixel==pt2)
            {
                node=node->next;
                continue;
            }
    
            if(pt3==NULL)
            {
                pt3=node->pixel;
            }
            else
            {
                float dist11=sqrt((pt1->x-node->pixel->x)*(pt1->x-node->pixel->x)+(pt1->y-node->pixel->y)*(pt1->y-node->pixel->y));
                float dist12=sqrt((pt2->x-node->pixel->x)*(pt2->x-node->pixel->x)+(pt2->y-node->pixel->y)*(pt2->y-node->pixel->y));
                float dist12_3=sqrt((pt1->x-pt2->x)*(pt1->x-pt2->x)+(pt1->y-pt2->y)*(pt1->y-pt2->y));
                float dist21=sqrt((pt1->x-pt3->x)*(pt1->x-pt3->x)+(pt1->y-pt3->y)*(pt1->y-pt3->y));
                float dist22=sqrt((pt3->x-pt2->x)*(pt3->x-pt2->x)+(pt3->y-pt2->y)*(pt3->y-pt2->y));
                if((pow(dist11,2)+pow(dist12,2)-pow(dist12_3,2))/(2*dist11*dist12)
                    <(pow(dist21,2)+pow(dist22,2)-pow(dist12_3,2))/(2*dist21*dist22)) //余弦判断角度
    
                {
                    pt3=node->pixel;
                }
            }
            node=node->next;
        }
        //LineList
        Linelist *linehead,*linenode,*linelast;
        Line *ln1,*ln2,*ln3;
        linenode=new Linelist;
        linenode->line=new Line;
        linenode->line->pixel1=pt1;
        linenode->line->pixel2=pt2;
        linenode->line->pixel3=pt3;
        linenode->line->flag=false;
        linenode->next=NULL;
        linehead=linelast=linenode;
        ln1=linenode->line;
        linenode=new Linelist;
        linenode->line=new Line;
        linenode->line->pixel1=pt2;
        linenode->line->pixel2=pt3;
        linenode->line->pixel3=pt1;
        linenode->line->flag=false;
        linenode->next=NULL;
        linelast->next=linenode;
        linelast=linenode;
        ln2=linenode->line;
        linenode=new Linelist;
        linenode->line=new Line;
        linenode->line->pixel1=pt3;
        linenode->line->pixel2=pt1;
        linenode->line->pixel3=pt2;
        linenode->line->flag=false;
        linenode->next=NULL;
        linelast->next=linenode;
        linelast=linenode;
        ln3=linenode->line;
        //first Triangle
        Triangle *tglhead,*tglnode,*tgllast;
        tglnode=new Triangle;
        tglnode->line1=ln1;
        tglnode->line2=ln2;
        tglnode->line3=ln3;
        tglnode->next=NULL;
        tglhead=tgllast=tglnode;
    
    
        //expend tin;
        Linelist *linetmp,*linetemp;
        List *pixeltmp;
        float x1,y1,x2,y2,x3,y3;
        linetmp=linehead;
        while(linetmp!=NULL)
        {
            if(linetmp->line->flag==true)
            {
                linetmp=linetmp->next;
                continue;
            }
            ln1=linetmp->line;
            pt1=linetmp->line->pixel1;
            pt2=linetmp->line->pixel2;
            x1=linetmp->line->pixel1->x;
            y1=linetmp->line->pixel1->y;
            x2=linetmp->line->pixel2->x;
            y2=linetmp->line->pixel2->y;
            x3=linetmp->line->pixel3->x;
            y3=linetmp->line->pixel3->y;
    
    
            pixeltmp=list;
            pt3=NULL;
            while(pixeltmp!=NULL)
            {
                if(pixeltmp->pixel==pt1 || pixeltmp->pixel==pt2)
                {
                    pixeltmp=pixeltmp->next;
                    continue;
                }
                if(((y2-y1)*pixeltmp->pixel->x+(x1-x2)*pixeltmp->pixel->y+(x2*y1-x1*y2))
                *((y2-y1)*x3+(x1-x2)*y3+(x2*y1-x1*y2))>=0)
                {
                    pixeltmp=pixeltmp->next;
                    continue;
                }
    
    
                if(pt3==NULL)pt3=pixeltmp->pixel;
                else
                {
                    float dist11=sqrt((pt1->x-pixeltmp->pixel->x)*(pt1->x-pixeltmp->pixel->x)+(pt1->y-pixeltmp->pixel->y)*(pt1->y-pixeltmp->pixel->y));
                    float dist12=sqrt((pt2->x-pixeltmp->pixel->x)*(pt2->x-pixeltmp->pixel->x)+(pt2->y-pixeltmp->pixel->y)*(pt2->y-pixeltmp->pixel->y));
                    float dist12_3=sqrt((pt1->x-pt2->x)*(pt1->x-pt2->x)+(pt1->y-pt2->y)*(pt1->y-pt2->y));
                    float dist21=sqrt((pt1->x-pt3->x)*(pt1->x-pt3->x)+(pt1->y-pt3->y)*(pt1->y-pt3->y));
                    float dist22=sqrt((pt3->x-pt2->x)*(pt3->x-pt2->x)+(pt3->y-pt2->y)*(pt3->y-pt2->y));
                    if((pow(dist11,2)+pow(dist12,2)-pow(dist12_3,2))/(2*dist11*dist12)
                        <(pow(dist21,2)+pow(dist22,2)-pow(dist12_3,2))/(2*dist21*dist22)) //余弦判断角度
                    {
                        pt3=pixeltmp->pixel;
                    }
                }
                pixeltmp=pixeltmp->next;
            }
            if(pt3!=NULL)
            {
                linetemp=linehead;
                flag=false;
                while(linetemp!=NULL)
                {
                    if((pt1==linetemp->line->pixel1 && pt3==linetemp->line->pixel2)
                        || (pt3==linetemp->line->pixel1 && pt1==linetemp->line->pixel2))
                    {
                        linetemp->line->flag=true;
                        flag=true;
                        ln2=linetemp->line;
                        break;
                    }
                    linetemp=linetemp->next;
                }
                if(!flag)
                {
                    linenode=new Linelist;
                    linenode->line=new Line;
                    linenode->line->pixel1=pt3;
                    linenode->line->pixel2=pt1;
                    linenode->line->pixel3=pt2;
                    linenode->line->flag=false;
                    linenode->next=NULL;
                    linelast->next=linenode;
                    linelast=linenode;
                    ln2=linenode->line;
                }
                linetemp=linehead;
                flag=false;
                while(linetemp!=NULL)
                {
                    if((pt2==linetemp->line->pixel1 && pt3==linetemp->line->pixel2)
                        || (pt3==linetemp->line->pixel1 && pt2==linetemp->line->pixel2))
                    {
                        linetemp->line->flag=true;
                        flag=true;
                        ln3=linetemp->line;
                        break;
                    }
                    linetemp=linetemp->next;
                }
                if(!flag)
                {
                    linenode=new Linelist;
                    linenode->line=new Line;
                    linenode->line->pixel1=pt2;
                    linenode->line->pixel2=pt3;
                    linenode->line->pixel3=pt1;
                    linenode->line->flag=false;
                    linenode->next=NULL;
                    linelast->next=linenode;
                    linelast=linenode;
                    ln3=linenode->line;
                }
                tglnode=new Triangle;
                tglnode->line1=ln1;
                tglnode->line2=ln2;
                tglnode->line3=ln3;
                tglnode->next=NULL;
                tgllast->next=tglnode;
                tgllast=tglnode;
            }
    
    
            linetmp->line->flag=true;
            linetmp=linetmp->next;
        }
        TIN=tglhead;
           return TIN;
    展开全文
  • 三角网TIN——扩张生长算法

    千次阅读 2019-09-12 16:02:19
    扩张生长算法

    构建三角网

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    注意事项

    1.三角形每条边的拓展方向为该边的右邻三角形(跟逆时针存储顶点和三角形边有关)

    2.如何判断第三点在三角边的左侧还是右侧

    C语言编程实现——类设计

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    参考资料

    1. https://wenku.baidu.com/view/6cbe5acf29ea81c758f5f61fb7360b4c2e3f2a04.html?rec_flag=default&sxts=1568191831740
    2. https://wenku.baidu.com/view/be2ec90ef78a6529647d53de.html
    展开全文
  • 基于生长算法构建Delaunary三角网,此法是根据生长法构建的Delaunary三角网
  • DELAUNAY三角网算法是什么东西呢。。。大概就是对于许多密集的点,,,可以形成一个三角网。。然后最近的三个点搞成一个三角形。任何一个三角形的外接圆都不包含其他的点。并且没有相交边,并且所有三角面的合集就是...

     DELAUNAY三角网算法是什么东西呢。。。大概就是对于许多密集的点,,,可以形成一个三角网。。然后最近的三个点搞成一个三角形。任何一个三角形的外接圆都不包含其他的点。并且没有相交边,并且所有三角面的合集就是一个凸包。,Delaunay三角剖分所形成的三角形的最小角最大。

    1.最接近:以最近的三点形成三角形,且各线段(三角形的边)皆不相交。
    2.唯一性:不论从区域何处开始构建,最终都将得到一致的结果。
    3.最优性:任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话,那么两个三角形六个内角中最小的角度不会变大。
    4.最规则:如果将三角网中的每个三角形的最小角进行升序排列,则Delaunay三角网的排列得到的数值最大。
    5.区域性:新增、删除、移动某一个顶点时只会影响临近的三角形。
    6.具有凸多边形的外壳:三角网最外层的边界形成一个凸多边形的外壳。
    算法不久之后实现 = =

    #include<bits/stdc++.h>
    using namespace std;
    #define PI 3.1415926
    struct triangleNode
    {
        double coordinateX[3],coordinateY[3];   //坐标
        double triangleLength;            //周长
        double triangleArea;              //面积
        double triangSideleLength[3];        //边长
    };
    struct pointNode
    {
        double x,y;
    
    };
    double dist(double xx,double yy,double xxx,double yyy)
    {
        return sqrt((xx-xxx)*(xx-xxx)+(yy-yyy)*(yy-yyy));
    }
    double getTriangleCircumcircleRadius(triangleNode a)  //外接圆半径
    {
        a.triangSideleLength[0]=dist(a.coordinateX[0],a.coordinateY[0],a.coordinateX[1],a.coordinateY[1]);
        a.triangSideleLength[1]=dist(a.coordinateX[0],a.coordinateY[0],a.coordinateX[2],a.coordinateY[2]);
        a.triangSideleLength[2]=dist(a.coordinateX[2],a.coordinateY[2],a.coordinateX[1],a.coordinateY[1]);
        double triangleCircumcircleRadius=0.5*(sqrt((a.triangSideleLength[0]+a.triangSideleLength[1]-a.triangSideleLength[2])
                                               *(a.triangSideleLength[0]-a.triangSideleLength[1]+a.triangSideleLength[2])
                                               *(a.triangSideleLength[1]+a.triangSideleLength[2]-a.triangSideleLength[0]))
                                               /(a.triangSideleLength[0]+a.triangSideleLength[1]+a.triangSideleLength[2]));
        return triangleCircumcircleRadius;
    }
    double getTriangleCircumcircleLength(triangleNode a)  //外接圆周长
    {
        return 2*PI*getTriangleCircumcircleRadius(a);
    }
    double getTriangleCircumcircleArea(triangleNode a)  //外接圆面积
    {
        return PI*getTriangleCircumcircleRadius(a)*getTriangleCircumcircleRadius(a);
    }
    double getTriangleLength(triangleNode a)            //三角形周长
    {
        a.triangSideleLength[0]=dist(a.coordinateX[0],a.coordinateY[0],a.coordinateX[1],a.coordinateY[1]);
        a.triangSideleLength[1]=dist(a.coordinateX[0],a.coordinateY[0],a.coordinateX[2],a.coordinateY[2]);
        a.triangSideleLength[2]=dist(a.coordinateX[2],a.coordinateY[2],a.coordinateX[1],a.coordinateY[1]);
        return a.triangSideleLength[0]+a.triangSideleLength[1]+a.triangSideleLength[2];
    }
    double getTriangleArea(triangleNode a)            //三角形面积
    {
        a.triangSideleLength[0]=dist(a.coordinateX[0],a.coordinateY[0],a.coordinateX[1],a.coordinateY[1]);
        a.triangSideleLength[1]=dist(a.coordinateX[0],a.coordinateY[0],a.coordinateX[2],a.coordinateY[2]);
        a.triangSideleLength[2]=dist(a.coordinateX[2],a.coordinateY[2],a.coordinateX[1],a.coordinateY[1]);
        double halfPerimeter=getTriangleArea(a)*0.5;  //半周长
        return sqrt(halfPerimeter*(halfPerimeter-a.triangSideleLength[0])*(halfPerimeter-a.triangSideleLength[1])*(halfPerimeter-a.triangSideleLength[2])); //海伦公式
    }
    int main()
    {
    
    }
    

    展开全文
  • 提出一种基于离散点Delaunay 三角网快速构建的网格生长算法,采用分治算法将离散点表达为唯一网格,利用稀疏矩阵完成网格数据的压缩存储,通过标识码实现有值单元格与离散点之间的高效检索,从而提高网格构建的效率...
  • TIN三角形生长算法的C程序实例

    热门讨论 2009-11-27 15:36:20
    这是本人自己用C语言编写的一个由离散数据点生成TIN(不规则三角网)的DOS程序实例,有EXE可执行文件并附带源代码和详细的注释以及供测试用的数据,源代码可在Turbo C环境下编译。三角形生长算法是GIS初学者比较容易...
  • 不规则三角网算法设计与实…

    千次阅读 2016-01-25 15:28:29
    原文地址:不规则三角网的算法设计与实现作者:笨笨...摘要:本文对不规则三角网生长算法实现的研究,利用了VB强大的可视化用户界面及其编程语言的灵活性及简单易懂特点,基于各行业对于DEM的需要,从而开发出一种利用V
  • Delaunay三角网生成算法

    万次阅读 2017-12-11 15:52:26
    Delaunay三角网的两个重要性质 空外接圆性质:在由点集S构成的Delaunay三角网中,每个三角形的外接圆均不包含点集S中的其他任意点,即任何一个Delaunay三角形的外接圆不包含其他任何点。 最大的最小角性质:在由点集...
  • 网构建研究中的3类方法逐点插入法、三角网生长法和分治法, 以及在各自原理框架下的不同实现算法; 比较 分析了3种不同方法的优缺点和各自代表性算法的时间复杂度, 并详细讨论了Delaunay三角网构建方法在大规模 场景...
  • 运用生长法实现DTIN的生成,先生成随机点,然后采用三角形生长算法形成三角形。采用动态数组,所以在三角网产生之后也能将后来产生的点加入到新的三角网之中。
  • 【实例简介】运用生长法实现DTIN的生成,先生成随机点,然后采用三角形生长算法形成三角形。采用动态数组,所以在三角网产生之后也能将后来产生的点加入到新的三角网之中。【实例截图】【核心代码】DTIN└── DTIN...
  • 基于三角网生长算法和分治算法的思想 ,提出并实现了一个平面域散乱点的三角网格重构算法 。 算法首先利用分治算 法的思想将散乱点集进行分割,然后在四个极值点确定初始三角形的基础上,基于边的扩展原则构造新的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 713
精华内容 285
关键字:

三角网生长算法