解释用例

不规则三角网（TIN）是一系列互不交叉、互不重叠的连接在一起的三角形来表示物体/地形表面，能够很好的描述和维护空间关系，在地理信息系统里有广泛应用。

给定一系列点，利用这些点作为不规则三角网中三角形的节点，来构建TIN。TIN对三角形的几何形状有三个基本要求：
1、三角形的格网唯一；
2、每一个三角形都尽可能接近正三角形；
3、三角形边长之和最小，保证最近的点形成三角形。

算法实现

1. 查找最近的两个点（findCloestPoint）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
Point* findCloestPoint(QVector<Point>& initialPoints)
{// 查找距离最近的两个点并返回
// 初始点集合 initialPoints。返回最近的两个点。   
    static Point cloestPoints[2]; // 存放距离最近的两个点

    // 初始化两个点为列表中的前两个点
    Point p1 = initialPoints[0];
    Point p2 = initialPoints[1];
    int index1 = 0;
    int index2 = 1;
    double mindis = p1.cal_distence(p2); // 计算初始两点的距离

    // 遍历所有的点，找到距离最近的两个点
    for (int i = 1; i < initialPoints.size() - 1; i++) {
        for (int j = i + 1; j < initialPoints.size(); j++) {
            double tempdis = initialPoints[i].cal_distence(initialPoints[j]);
            if (mindis > tempdis) {
                p1 = initialPoints[i];
                p2 = initialPoints[j];
                index1 = i;
                index2 = j;
                mindis = tempdis; // 更新最小距离
            }
        }
    }

    // 存储找到的两个最近点
    cloestPoints[0] = p1;
    cloestPoints[1] = p2;

    // 删除已经使用的两个点
    initialPoints.erase(initialPoints.begin() + index1);
    initialPoints.erase(initialPoints.begin() + index2 - 1); // 由于已经删除了index1，index2需要调整

    return cloestPoints;
}

解析：

  • 初始化 cloestPoints 数组用于存储最近的两个点。
  • 选择初始的两个点 p1 和 p2，并计算它们的距离，设定为当前最小距离。
  • 使用两层嵌套循环来遍历 initialPoints 中的点，计算每两点之间的距离。
  • 如果发现新计算的距离比当前的最小距离更小，则更新最近的两个点和它们的索引，并更新最小距离。
  • 找到最近点后，将其从初始点集合中删除（注意索引调整）。

2. 查找第一个三角形（findFirstTIN）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void findFirstTIN(Point& p1, Point& p2, QVector<Point>& v)
{
    // 生成第一个三角形并返回 p1 和 p2 为已知的两个点，v 为所有点集合。将生成的三角形边存入 allline 和 baseline。
    MyVector mv1, mv2;
    int index = 0;
    mv1 = MyVector(p1, v[0]);  // 计算p1与第一个点的向量
    mv2 = MyVector(p2, v[0]);  // 计算p2与第一个点的向量
    double cos00 = mv1.cal_number(mv2) / (mv1.length * mv2.length);  // 计算余弦值

    // 循环找出最小的余弦值
    for (int i = 1; i < v.size(); i++) {
        mv1 = MyVector(p1, v[i]);
        mv2 = MyVector(p2, v[i]);
        double cos0 = mv1.cal_number(mv2) / (mv1.length * mv2.length);
        if (cos0 < cos00) {
            cos00 = cos0;
            index = i; // 找到最小余弦值对应的点
        }
    }

    // 形成三条边，构成第一个三角形，并存入allline和baseline
    Line line1 = Line(p1, p2, v[index], 1);
    Line line2 = Line(p1, v[index], p2, 1);
    Line line3 = Line(p2, v[index], p1, 1);
    m_allline = { line1, line2, line3 };
    m_baseline = { line1, line2, line3 };
    qDebug() << "三角形总边数为：" << m_allline.size();
}

解析：

  • 采用 p1 和 p2 作为已知的两个点，并逐一计算与其他点的向量。
  • 通过计算这些向量的余弦值来确定与这两个点的角度，越小表示角度越接近，形状越“尖”。
  • 循环找到余弦值最小的点，作为三角形的第三个点。
  • 根据这三个点生成三条边并存入 m_allline 和 m_baseline。这个操作构成了第一个三角形，并为后续三角网的构建提供基础。

3. 判断边的使用次数（lineUsedCount）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
LineInfo lineUsedCount(Line& line, QVector<Line>& v)
{
    // 判断一条边在 allline 中的使用次数，line 为待检查的边，v 为 allline 中的边集合。返回LineInfo 结构体，包含该边的使用次数和索引。
    LineInfo lineinfo; // 存储边的使用信息

    // 遍历allline，检查边是否已存在
    for (int i = 0; i < v.size(); i++) {
        if (line == v[i]) { // 如果该边已经存在
            if (v[i].flag == 2) {
                lineinfo.count = 2; // 如果已经使用了两次
                lineinfo.index = i;
                return lineinfo;
            }
            else {
                lineinfo.count = 1; // 如果只使用了一次
                lineinfo.index = i;
                return lineinfo;
            }
        }
    }

    // 如果该边是新边，未出现在allline中
    lineinfo.count = 0;
    lineinfo.index = -1;
    return lineinfo;
}

解析：

  • lineUsedCount 函数用来检查一条边在已有边集合中的状态。
  • 遍历所有边，判断传入的 line 是否与已有边相等。
  • 如果相等，根据 flag 值判断是否已使用过两次并更新计数和索引。
  • 返回一个结构体 LineInfo，它包含了该边的使用情况。

4. 生成完整的三角网（createTIN）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
void creatTIN(QVector<Line>& va, QVector<Line>& vb, QVector<Point>& vp)
{
    // 创建三角网，进行边的扩展：va 为存储所有边的集合，vb 为存储基线边的集合，vp 为所有点的集合。最终生成的边存储在 va 和 vb 中。建网结束的标志是基线表中没有基线
    while (vb.size()) {
        Line baseline = vb[0]; // 取出基线

        // 如果基线已经被使用两次，则跳过
        if (lineUsedCount(baseline, va).count == 2) {
            vb.erase(vb.begin());
            continue;
        }

        // 寻找第三个点来扩展基线
        while (true) {
            std::vector<Point> potentialpt; // 存储可能的扩展点

            // 计算基线与其他点的相对位置
            double re1 = MyVector(baseline.startpt, baseline.endpt).cal_vector(MyVector(baseline.startpt, baseline.sametinpt));

            for (int i = 0; i < vp.size(); i++) {
                double re2 = MyVector(baseline.startpt, baseline.endpt).cal_vector(MyVector(baseline.startpt, vp[i]));
                // 如果re1与re2异号，表示可能的扩展点
                if (re1 * re2 < 0) {
                    potentialpt.push_back(vp[i]);
                }
            }

            // 如果没有找到扩展点，说明基线是最外层的边
            if (potentialpt.size() == 0) {
                vb.erase(vb.begin());
                break;
            }

            // 找出余弦值最小的点
            MyVector mv1, mv2;
            int index = 0;
            mv1 = MyVector(baseline.startpt, potentialpt[0]);
            mv2 = MyVector(baseline.endpt, potentialpt[0]);
            double cos00 = mv1.cal_number(mv2) / (mv1.length * mv2.length);

            for (int i = 1; i < potentialpt.size(); i++) {
                mv1 = MyVector(baseline.startpt, potentialpt[i]);
                mv2 = MyVector(baseline.endpt, potentialpt[i]);
                double cos0 = mv1.cal_number(mv2) / (mv1.length * mv2.length);
                if (cos0 < cos00) {
                    cos00 = cos0;
                    index = i;
                }
            }

            // 扩展新的边
            Line newl1 = Line(baseline.startpt, potentialpt[index], baseline.endpt, 1);
            Line newl2 = Line(baseline.endpt, potentialpt[index], baseline.startpt, 1);

            // 判断并加入新的边
            LineInfo info1 = lineUsedCount(newl1, va);
            if (info1.count == 0) {
                va.push_back(newl1);
                vb.push_back(newl1);
            }
            else {
                vb.push_back(newl1);
                va[info1.index].flag = 2; // 标记边为已使用
            }

            LineInfo info2 = lineUsedCount(newl2, va);
            if (info2.count == 0) {
                va.push_back(newl2);
                vb.push_back(newl2);
            }
            else {
                vb.push_back(newl2);
                va[info2.index].flag = 2;
            }

            // 将基线的flag标记为2，表示它已经扩展过
            va[lineUsedCount(baseline, va).index].flag = 2;
            vb.erase(vb.begin());
            break;
        }
    }

    qDebug() << "建网结束！";
}

解析：

  • 外层循环保持执行，直至 vb 中没有基线。
  • 取出当前基线 baseline 并检查它是否已使用两次，若是则跳过。
  • 在内层循环中，计算当前基线的两侧可能的扩展点。
  • 通过计算相对基线与扩展点的向量，再判断是否可以作为扩展点（即异号）。
  • 如果不存在可扩展点，说明此基线是外层边，删除该基线，跳出内循环。
  • 找到余弦值最小的点并生成两个新边 newl1 和 newl2。
  • 利用 lineUsedCount 检查这些新边是否已存在，并根据情况将新边加入到 va 和 vb 中或标记为已使用。
  • 最后，将基线标记为已使用，继续处理下一根基线。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
//遍历所有点，找到距离最近的两个点并返回它们的坐标。
Point* findCloestPoint(QVector<Point>& initialPoints)
{// 查找距离最近的两个点并返回
// 初始点集合 initialPoints。返回最近的两个点。   
    static Point cloestPoints[2]; // 存放距离最近的两个点
    
    // 初始化两个点为列表中的前两个点
    Point p1 = initialPoints[0];
    Point p2 = initialPoints[1];
    int index1 = 0;
    int index2 = 1;
    double mindis = p1.cal_distence(p2); // 计算初始两点的距离
    
    // 遍历所有的点，找到距离最近的两个点
    for (int i = 1; i < initialPoints.size() - 1; i++) {
        for (int j = i + 1; j < initialPoints.size(); j++) {
            double tempdis = initialPoints[i].cal_distence(initialPoints[j]);
            if (mindis > tempdis) {
                p1 = initialPoints[i];
                p2 = initialPoints[j];
                index1 = i;
                index2 = j;
                mindis = tempdis; // 更新最小距离
            }
        }
    }
    
    // 存储找到的两个最近点
    cloestPoints[0] = p1;
    cloestPoints[1] = p2;
    
    // 删除已经使用的两个点
    initialPoints.erase(initialPoints.begin() + index1);
    initialPoints.erase(initialPoints.begin() + index2 - 1); // 由于已经删除了index1，index2需要调整
    
    return cloestPoints;
}

// 基于两个点，寻找第三个点来形成第一个三角形，并存储该三角形的边信息。。
void MainInterface::findFirstTIN(Point& p1, Point& p2, QVector<Point>& v)
{
    // 生成第一个三角形并返回 p1 和 p2 为已知的两个点，v 为所有点集合。将生成的三角形边存入 allline 和 baseline。
    MyVector mv1, mv2;
    int index = 0;
    mv1 = MyVector(p1, v[0]);  // 计算p1与第一个点的向量
    mv2 = MyVector(p2, v[0]);  // 计算p2与第一个点的向量
    double cos00 = mv1.cal_number(mv2) / (mv1.length * mv2.length);  // 计算余弦值
    
    // 循环找出最小的余弦值
    for (int i = 1; i < v.size(); i++) {
        mv1 = MyVector(p1, v[i]);
        mv2 = MyVector(p2, v[i]);
        double cos0 = mv1.cal_number(mv2) / (mv1.length * mv2.length);
        if (cos0 < cos00) {
            cos00 = cos0;
            index = i; // 找到最小余弦值对应的点
        }
    }
    
    // 形成三条边，构成第一个三角形，并存入allline和baseline
    Line line1 = Line(p1, p2, v[index], 1);
    Line line2 = Line(p1, v[index], p2, 1);
    Line line3 = Line(p2, v[index], p1, 1);
    m_allline = { line1, line2, line3 };
    m_baseline = { line1, line2, line3 };
    qDebug() << "三角形总边数为：" << m_allline.size();
}

//判断某条边在 allline 中出现的次数，用于处理边是否已在两个三角形中被使用。
LineInfo lineUsedCount(Line& line, QVector<Line>& v)
{
    // 判断一条边在 allline 中的使用次数，line 为待检查的边，v 为 allline 中的边集合。返回LineInfo 结构体，包含该边的使用次数和索引。
    LineInfo lineinfo; // 存储边的使用信息
    
    // 遍历allline，检查边是否已存在
    for (int i = 0; i < v.size(); i++) {
        if (line == v[i]) { // 如果该边已经存在
            if (v[i].flag == 2) {
                lineinfo.count = 2; // 如果已经使用了两次
                lineinfo.index = i;
                return lineinfo;
            }
            else {
                lineinfo.count = 1; // 如果只使用了一次
                lineinfo.index = i;
                return lineinfo;
            }
        }
    }
    
    // 如果该边是新边，未出现在allline中
    lineinfo.count = 0;
    lineinfo.index = -1;
    return lineinfo;
}

// 通过循环扩展基线，生成完整的三角网。
void creatTIN(QVector<Line>& va, QVector<Line>& vb, QVector<Point>& vp)
{
    // 创建三角网，进行边的扩展：va 为存储所有边的集合，vb 为存储基线边的集合，vp 为所有点的集合。最终生成的边存储在 va 和 vb 中。建网结束的标志是基线表中没有基线
    while (vb.size()) {
        Line baseline = vb[0]; // 取出基线
        
        // 如果基线已经被使用两次，则跳过
        if (lineUsedCount(baseline, va).count == 2) {
            vb.erase(vb.begin());
            continue;
        }
        
        // 寻找第三个点来扩展基线
        while (true) {
            std::vector<Point> potentialpt; // 存储可能的扩展点
            
            // 计算基线与其他点的相对位置
            double re1 = MyVector(baseline.startpt, baseline.endpt).cal_vector(MyVector(baseline.startpt, baseline.sametinpt));
            
            for (int i = 0; i < vp.size(); i++) {
                double re2 = MyVector(baseline.startpt, baseline.endpt).cal_vector(MyVector(baseline.startpt, vp[i]));
                // 如果re1与re2异号，表示可能的扩展点
                if (re1 * re2 < 0) {
                    potentialpt.push_back(vp[i]);
                }
            }
            
            // 如果没有找到扩展点，说明基线是最外层的边
            if (potentialpt.size() == 0) {
                vb.erase(vb.begin());
                break;
            }
            
            // 找出余弦值最小的点
            MyVector mv1, mv2;
            int index = 0;
            mv1 = MyVector(baseline.startpt, potentialpt[0]);
            mv2 = MyVector(baseline.endpt, potentialpt[0]);
            double cos00 = mv1.cal_number(mv2) / (mv1.length * mv2.length);
            
            for (int i = 1; i < potentialpt.size(); i++) {
                mv1 = MyVector(baseline.startpt, potentialpt[i]);
                mv2 = MyVector(baseline.endpt, potentialpt[i]);
                double cos0 = mv1.cal_number(mv2) / (mv1.length * mv2.length);
                if (cos0 < cos00) {
                    cos00 = cos0;
                    index = i;
                }
            }
            
            // 扩展新的边
            Line newl1 = Line(baseline.startpt, potentialpt[index], baseline.endpt, 1);
            Line newl2 = Line(baseline.endpt, potentialpt[index], baseline.startpt, 1);
            
            // 判断并加入新的边
            LineInfo info1 = lineUsedCount(newl1, va);
            if (info1.count == 0) {
                va.push_back(newl1);
                vb.push_back(newl1);
            }
            else {
                vb.push_back(newl1);
                va[info1.index].flag = 2; // 标记边为已使用
            }
            
            LineInfo info2 = lineUsedCount(newl2, va);
            if (info2.count == 0) {
                va.push_back(newl2);
                vb.push_back(newl2);
            }
            else {
                vb.push_back(newl2);
                va[info2.index].flag = 2;
            }
            
            // 将基线的flag标记为2，表示它已经扩展过
            va[lineUsedCount(baseline, va).index].flag = 2;
            vb.erase(vb.begin());
            break;
        }
    }
    
    qDebug() << "建网结束！";
}