一、程序概述

源程序：hxghuiwn/tin-contour-generation: Automatic contour line generation based on Triangulated Irregular Network (TIN).

本程序基于 PyQt5 构建 GUI 应用，实现了从离散高程点数据到等高线自动绘制的完整流程。核心算法包括：凸包构建、Delaunay 三角剖分、等高线追踪与拼接。

1、算法总流程

散点数据 → 凸包构建(Graham Scan) → Delaunay三角网(逐点插入法) → 等高线追踪 → 输出结果

2、数据格式

输入为文本文件，每行格式：点号, x, y, 高程

1, 100.5, 200.3, 15.2
2, 150.0, 180.7, 18.6

二、核心数据结构

1、Point 类 — 点数据存储

class Point:
    def __init__(self, n=None, x=None, y=None, h=None):
        self.n = n          # 点号
        self.x = float(x)   # x坐标
        self.y = float(y)   # y坐标
        self.h = float(h)   # 高程

无论是原始数据点还是计算出的交点，统一使用 Point 类存储。

所有参数均有默认值的好处是：在构造点对象时，某些参数可以不传，灵活性更高。

2、Triangle 类 — 三角形存储

class Triangle:
    def __init__(self, a, b, c):
        self.a = a    # 顶点A（Point对象）
        self.b = b    # 顶点B（Point对象）
        self.c = c    # 顶点C（Point对象）

三、凸包构建

1、Graham Scan算法

（1）叉积函数

def cross(a, b, c):
    # 计算ab和ac的叉积，＞0，表示左拐，即ac在ab的左边
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)

（2）辅助函数

函数	作用
distance2(p1, p2)	计算两点距离的平方（避免开方）
angle(p0, p)	计算 p0 到 p 的方向角（极角）
find_stone(points)	找 y 最小的基点

（3）Graham Scan 五步流程

1. 找基点：y 最小的点作为起始
2. 去掉基点：将基点从点集中移除
3. 排序：按极角排序，极角相同则按距离排序
4. 构建：用栈维护凸包，新点加入时检查是否满足左转
5. 完成：栈中剩余的点即为凸包顶点

2、增量迭代法

（1）核心思想：从凸包的初始四边形出发，逐条边检查外部是否有更远的点，有则插入。

（2）流程

1. 查找四个极值顶点（最左、最上、最右、最下），构成初始凸包 CH
2. 删除这四个顶点，剩余点作为候选点集
3. 主循环（迭代思想）：
   a. 枚举 CH 的每一条边
   b. 找到在边左侧（凸包外侧）的所有点 LP
   c. 如果 LP 为空，继续下一条边
   d. 在 LP 中找最远点 F（面积最大）
   e. 将 F 插入到当前边之后的位置
   f. 凸包结构已变化，i 重置为 0，重新遍历所有边

（3）代码实现

# 1、查找四个顶点
p1 = min(points, key=lambda p: p.x)   # 最左
p2 = max(points, key=lambda p: p.y)   # 最上
p3 = max(points, key=lambda p: p.x)   # 最右
p4 = min(points, key=lambda p: p.y)   # 最下
CH = [p1, p2, p3, p4]                 # 顺时针

# 2、删除四个顶点
points = [p for p in points if p not in CH]

# 3、主循环
i = 0
while i < len(CH):
    edge_start = CH[i]
    edge_end = CH[(i + 1) % len(CH)]
    # 找边外侧的点
    LP = [p for p in points if cross(edge_start, edge_end, p) > 0]
    if not LP:
        i += 1
        continue
    # 找最远点（面积最大）
    F = max(LP, key=lambda p: area(p))
    CH.insert(i + 1, F)
    i = 0  # 重新遍历

四、Delaunay 三角剖分 — 逐点插入法

1、辅助函数

（1）点是否在外接圆内 — is_in 函数

（2）公共边查找 — find_shared_lines 函数

2、三角网构建流程

1. 删除凸包点，保留内部离散点
2. 初始化：取第一个内部点，与凸包的每条边相连，构成初始三角网 T1
3. 遍历剩余内部点，逐个插入：
   a. 找到包含待插点的所有三角形，移入 t2
   b. 从 T1 中移除 t2
   c. 找 t2 的非公共边
   d. 将非公共边的两端点与待插点连接，生成新三角形，加入 T1

3、三种初始化方法对比

方法	描述
超级三角形法	构造一个包含所有点的超级三角形，最后删除与超级三角形顶点相关的三角形
凸包边法（本程序使用）	取一个内部点与所有凸包边相连，更直观
初始矩形	构造一个包含所有点的最小外包矩形（或初始包围矩形），作为初始区域，再在其基础上逐步细分生成三角网

四、等高线构建

先确定等高线的高程范围，然后遍历每个高度 h 的等高线。对于高度为 h 的等高线：

1. 通过 triangle_contour_segments 函数，找到其与所有 Delaunay 三角网的交点线段
2. 通过 build_contours_from_segments 进行拼接为一条完整的等高线

build_contours_from_segments 函数的流程：

• 线段去重：相邻三角形共享边会产生重复线段，通过 point_key 转元组进行去重
• 建立邻接图：将去重后的线段转为点的邻接关系（同一个邻接图的点，高度相同）
• 两轮等高线追踪：
  • 第一轮：从度数=1 的端点出发，追踪开放等高线
  • 第二轮：从剩余未走边出发，追踪闭合等高线
• 最终把结果整合到一起

邻接关系和 sorted 排序的重要性： 各三角形独立计算出的交点线段是零散的，线段之间没有直接的连接关系。邻接图的作用是将这些零散线段的节点对应上——通过 point_key 四舍五入后转为元组，再用 sorted 排序保证方向无关（A→B 和 B→A 得到相同的 key），从而正确识别哪些点共享同一条边。只有节点能够对应上，才能从零散线段中”走”出一条完整的等高线。