三角测量与三角剖分是 几何学中两个密切相关的概念,英文均称为 triangulation。在测量中,三角测量是指根据在已知位置观测到的方向,结合一段已知距离或其他能够确定尺度的信息,求出未知位置。在数学中,三角剖分是指将一个区域或空间分解为三角形或其高维推广形式,并使这些单元在相交处彼此吻合。这两种含义都利用了这样一个事实:复杂的几何关系可以通过简单而具有刚性的基本单元来组织。
在电子测距和卫星定位普及之前,测角三角测量是国家测绘工作的基础。其原理至今仍是立体视觉、摄影测量、光学计量以及某些无线电测向方法的核心。与此同时,几何三角剖分也是计算几何、计算机图形学、数值模拟和拓扑学的基础。这些应用有着共同的几何思想,但直接目标有所不同:测量是根据观测结果重建位置,而数学中的三角剖分则是为一个已经给定的区域或空间构造一种表示。
位置测定的几何原理
最基本的测量问题涉及两个已知测站 和 ,以及从这两个测站都能观测到的未知点 。线段 称为基线。基线的长度确定了整个几何构形的尺度,而观测到的方向 和 则确定了三角形 的形状。如果没有已知基线或等效的尺度信息,仅凭角度观测只能确定一组相似三角形,而无法确定绝对距离。
设 、,并假定 位于基线上方。若 点和 点处的内角分别为 和 ,则 点处的内角为
根据三角学中的基本定理——正弦定理,可得
在相应的笛卡尔坐标系中,未知点的坐标为
这些表达式也揭示了几何退化的情形:当两条视线近乎平行或近乎共线时,微小的角度误差就可能造成很大的位置误差。
例如,当基线长为 米、两个底角均为 时,该点沿基线方向距起点 米,垂直于基线方向的距离也为 米。两个测站都没有直接测量到该点的距离。这正是三角测量在测定难以到达的目标时的核心优势,例如山顶、河对岸的某一点,或相机观测到的远处地物。
相关术语在一定程度上取决于所观测的量。前方交会通常指从已知观测站测定未知目标的位置。后方交会则通过观测指向已知控制点的方向,确定观测站自身的位置。**三边测量**使用的则是距离:在平面内,三次配置适当的距离观测通常可以确定一个点的位置,但还须考虑观测值是否相容,以及是否存在多解。角度与距离相结合的方法通常称为边角测量。
三维三角测量使用空间中的视线射线,而不是局限于同一平面内的直线。例如,经过标定的相机所获取的一次观测,可以确定一条从相机中心穿过像点的射线。理想情况下,来自不同相机中心的两条射线相交于物点。实际中,它们通常不会精确相交,因此重建时需要采用某种估计准则。除非已知观测中心之间的距离或其他某个实际长度,否则仅凭角度仍无法确定绝对尺度。
测量控制网与地球形状
大型测量工作很少只涉及一个三角形,而是利用由观测方向连接起来的测站网络,并通过测定选定的距离来确定和检核尺度。解算出一个三角形后,其计算所得的一条边便可作为相邻三角形的基线。重复这一过程,就能将位置控制扩展到难以直接测量所有长距离的区域。闭合图形、重叠观测和增设的基线,可对累积误差提供独立检核。
传统测量控制网通常分为一等、二等及更低等级的控制网。一等控制点间距较大,采用当时所能达到的最高精度进行测量;随后布设的较密控制网则为局部测图和工程建设提供支持。测站设在山丘、塔楼或其他高处,以确保彼此通视。**经纬仪**是一种测量水平角和竖直角的仪器,逐渐成为这项工作的核心工具。以仪器的不同盘位反复观测,有助于减小度盘分划和对准不完善所引起的误差。
测量时,必须区分实际观测与计算坐标所依据的数学曲面。距离较短时,采用平面近似可能就已足够;距离较长时,则必须考虑地球的曲率。大地测量通常用参考椭球表示地球,并将观测方向和距离归算到这一曲面上。仪器高度、地形高程,以及重力方向与椭球法线方向之间的差异,都会影响所需的归算。
对于由大圆弧围成的球面三角形,其内角和大于 。在半径为 的球面上,以弧度计量的球面超额 与其面积 的关系为
因此,实测大型三角形的内角和不等于 ,并不一定意味着存在观测误差。椭球面上的测量需要进行更精细的计算,其中涉及测地线,即参考曲面上局部最短的路径。地图投影又带来了另一层区别:平面地图上的角度或距离,不一定等于椭球面上对应的角度或距离。
控制网的坐标还需要一个参考框架,即**大地基准**。一个仅由角度观测构成、未加约束的自由网,其平移、定向和尺度均未确定。施加适当的约束可以消除这些自由度,并将控制网与选定的坐标系联系起来。历史上,可以通过一个原点、一个起始方位角和一条实测基线来建立大地基准;现代地球参考框架则通过多个测站的协同观测来实现。
电子测距和卫星技术改变的是各类观测所占的比重,而非取代控制网的几何结构。现代控制网可以综合利用角度、距离、高差以及卫星测定的坐标。传统三角测量对于解读历史地图、转换旧有坐标系,以及理解误差和参考基准的选择如何影响整个国家测量控制网,仍然十分重要。
误差传播与测量网平差
通过三角测量得到的坐标,是根据存在误差的观测值推算出的估计值。角度读数误差、测站位置的不确定性、基线误差、大气影响以及仪器失准,都会造成测量不确定度。这些因素的影响在很大程度上取决于几何构型。微小的角度误差在垂直于某条视线的方向上可能只引起很小的位移,却在沿该视线的方向上引起显著位移,因此形成的往往是狭长的不确定区域,而非各方向不确定度均匀的区域。
一个简单的深度模型可以说明基线长度的重要性。对于位于短基线中垂线附近的远处目标,交会角 近似满足 ,其中 为目标距离。由一阶误差传播可得
当基线长为 米、目标距离约为 千米、交会角不确定度为一角秒时,根据这一近似公式得到的深度不确定度约为 厘米。在角度精度相同的情况下,距离增至十倍,深度不确定度便增至约一百倍。此例未计入基线不确定度、大气影响及其他系统性因素的贡献。
测量网在设计时,通常会使观测量的数量多于确定坐标所必需的最少数量。这种冗余既有助于发现彼此不相容的观测值,也能支持联合平差。采用最小二乘法时,选择使下式最小的坐标 :
其中, 由观测量与预测量之间的差值组成, 为权矩阵。处理角度观测值时需要格外注意,因为方向具有周期性:在 分界附近,残差应表示较小的角度差,而不是接近一整周的角度。
线性化时使用观测模型的雅可比矩阵 。若观测误差的协方差 已知,且基准自由度已受到适当约束,则局部坐标协方差近似为
所得的协方差矩阵既描述各个坐标的不确定度,也描述坐标之间的相关性。其解释仅在局部有效,并依赖于所采用的模型;误差较大或构型具有强非线性时,一阶近似可能失效。
仅靠冗余观测并不能消除系统误差。大气折射可能使视线路径弯曲,温度可能影响基线测量设备,而对中不准确则可能使实际观测点发生偏移。在几乎相同的条件下重复测量,可能会重复产生相同的偏差。因此,采用独立基线、在不同时间观测、进行仪器换向观测以及开展校准,都有不同于简单重复测量的作用。
从数学上看,这不仅涉及观测精度,也涉及以条件数衡量的数值条件。即使仪器精度很高,也无法弥补视线近乎平行所带来的问题。因此,测量网设计需要兼顾测站的可达性、通视条件、成本、交会角和冗余度,而不能只追求角度精度。
三角测量的历史发展
在有组织的三角测量网出现之前许多世纪,人们就已利用几何方法测定无法直接量取的距离。古希腊的数学天文学和测量传统运用了三角形、角度测量和比例推理。埃拉托色尼在古代估算地球周长时,也结合了角度与距离信息,但按后来的大地测量学含义来看,这并不属于三角测量网。这一方法独特的发展在于:通过相互连接的三角形,在广阔地域内系统地传递尺度。
1533年,赫马·弗里修斯对这一方法作出了颇具影响力的论述,说明如何利用从选定测站测得的方向进行地图测绘。随后,威勒布罗德·斯涅利乌斯将三角测量应用于荷兰的子午线测量。他于1617年出版的《巴达维亚的埃拉托色尼》记述了连接阿尔克马尔与贝亨奥普佐姆的测量工作。这项工程有助于确立一种实用模式:以一条精密测定的基线为基础,建立远比基线更长的三角锁。
17至18世纪,法国的测量工作将三角测量与地球形状研究联系起来。让·皮卡尔于1669至1670年开展的子午线测量采用了改进的角度观测和基线测量方法。后来,前往拉普兰和今厄瓜多尔一带的考察队研究了子午线弧长随纬度的变化。这些测量有助于确认地球两极扁平的形状,并解决了对早期测量结果的不同解释之间的争议。
卡西尼家族在18世纪开展的法国地图测绘,展现了统一的三角测量框架在行政管理和地图制作方面的价值。另一项重要应用是让-巴蒂斯特-约瑟夫·德朗布尔与皮埃尔·梅尚自1792年起开展的敦刻尔克至巴塞罗那子午线弧测量。他们的工作为最初以地球子午线长度的一定分数来定义米提供了依据。这些观测将抽象的长度单位与大尺度的大地测量联系起来,不过后来米的定义已不再依赖地球的尺寸。
英国的全国主三角测量始于威廉·罗伊在18世纪80年代主持开展的工作,并延续至19世纪。印度大三角测量于1802年在威廉·兰姆顿主持下启动,后来由乔治·埃弗里斯特领导。此类工程不仅需要测角仪器,还需要精密基线测量设备、永久性测量标志、测量塔、运输条件以及大量计算工作。它们为地图测绘提供了支撑,同时也反映了组织这些工程的机构所处的行政与政治背景。
三角测量还推动了用于综合观测数据的统计方法的发展。卡尔·弗里德里希·高斯自1821年起参与汉诺威的三角测量,而大地测量平差则是最小二乘法发展和应用的重要领域。20世纪,电子测距、航空摄影测量和卫星大地测量逐步取代了纯粹依靠测角建立的国家测量网。不过,历史上的三角测量仍留存于测量标石、地图、坐标档案以及现代平差的数学基础之中。
摄影测量、立体视觉与三维重建
在摄影测量和计算机视觉中,三角测量根据空间点在两幅或多幅图像中的投影重建该点。基本成像模型是针孔相机:物点、相机中心及其像点位于同一直线上。相机标定通过考虑焦距、主点和镜头畸变等参数,建立图像坐标与空间射线之间的关系。随后,利用已知的相机位置和姿态,将这些射线置于同一坐标系中。
采用齐次坐标时,理想相机可表示为
其中, 是一个 相机矩阵, 表示空间点, 表示其像点。消去未知尺度因子 ,便可得到关于 的线性约束。将多个视图的约束叠加,可得到一个齐次方程组,并用奇异值分解求得近似解。这是一种实用的初始化方法,但最小化代数残差通常并不等同于最小化图像测量误差。
对于光轴平行且经过校正的双目相机,深度关系具有特别简单的形式:
其中, 为以像素为单位的焦距, 为两台相机之间的距离, 为图像中的水平视差。若 像素、 米、 像素,则重建深度为 米。根据一阶误差传播,在这一距离处, 像素的视差不确定度对应约 米的深度不确定度。
在不同图像中找到同一个物理特征,往往比求所得射线的交点更困难。重复纹理可能导致错误匹配;平滑表面可能缺乏可辨识的特征;遮挡则可能使一个点仅在一幅图像中可见。通过射影几何描述的图像对几何关系,可将潜在匹配点限制在一条极线上,却无法唯一确定匹配点。反光物体和透明物体还可能违背“图像特征对应于稳定表面点”这一假设。
由于含噪声的射线通常无法精确相交,重建时往往采用最小化重投影误差的方法,即最小化观测像点与估计空间点的投影之间的差异。对相机参数和大量物点进行联合优化,称为**光束法平差**。其权重设置应反映图像测量的不确定度,而要稳健地处理错误对应关系,还需要额外的统计方法或算法措施。
仅凭图像也无法消除参考系的自由度。对于已标定的相机,若没有外部尺度信息,重建结果通常只能确定到相差一个相似变换的程度,其中包括任意的尺度因子。已知距离、经测量确定的控制点,或独立测得的相机运动,都可用于确定实际的物理尺度。相机纯旋转不提供基线,因此无法通过常规三角测量确定有限距离处空间点的深度。
光学计量、测向与天文视差
三角测量仪器不一定要使用两台被动式相机。一种常见的光学配置是从已知位置投射激光光斑或光条,再用一台与投射器相隔一定距离的相机进行观测。投射器确定一条已知射线或一个光平面,相机则提供另一项几何约束,两者相交即可确定受照表面的位置。一条投射光条可以生成完整的截面轮廓,多次获取的轮廓又可拼接成三维表面。
**结构光扫描**利用的就是这一原理:投射图案使对应关系的建立比在无纹理物体上更容易。经过编码的条纹或图案序列可用于识别每个相机像素所对应的投射器射线。这种方法依赖于投射器与相机之间几何关系的稳定标定。阴影、遮挡、表面反射特性的变化,以及图案序列投射期间的运动,都可能造成测量缺失或错误。增大基线可以提高深度灵敏度,但也可能加剧投射器与相机所能覆盖的可见区域之间的差异。
光学三角测量与飞行时间测距的物理原理不同。三角测量传感器根据角位移推算距离,而飞行时间设备则根据信号传播时间或相关的相位测量结果推算距离。两者都可能使用激光并生成点云,但其误差模型和工作条件限制各不相同。同样,日常语言中也常将卫星导航称为三角测量,但其主要几何观测量是距离或伪距,而非实测的视线夹角。
无线电测向通过方向交会来确定发射源的位置。两个或更多接收机估计信号的到达方向,再由这些方位线的交点确定发射源的位置。方向估计可以通过定向天线或天线阵列获得。建筑物和地形造成的反射,可能使估计出的方位指向间接传播路径,而非通往信号源的直线路径。到达时间差定位则是另一种方法:测得的传播时间差在平面上确定一条双曲线,在空间中确定一个双曲面,而不是一条方位线。
天文**视差**在截然不同的尺度上运用了相同的基线原理。恒星周年视差测量的是与地球在轨道上位置变化相对应的视角位移。按照惯例,视差角 对应的基线长度为一个天文单位。以秒差距为单位的距离为
最早成功测得并发表的恒星视差结果可追溯至19世纪30年代末,其中包括弗里德里希·贝塞尔于1838年对天鹅座61的测量。
现代天体测量学通过长期观测,将视差与自行及其他效应区分开来。对于含噪声的测量值,直接取实测视差的倒数,未必能得到统计性质良好的距离估计;当不确定性相对于视差较大时,尤其如此。其几何原理虽然简单,但要作出可靠推断,仍取决于观测模型及其不确定性。
多边形与平面区域的三角剖分
在计算几何中,简单多边形的三角剖分是将其内部划分为若干三角形,这些三角形的顶点均为多边形的顶点,且内部互不重叠。三角形在多边形内部的边,都是位于多边形内部的对角线。这种构造并不是根据测得的角度推算未知坐标,而是将已知区域重新划分为便于处理的部分。它可用于面积计算、渲染、几何查询,以及后续的数值计算网格构建。
每个具有 个顶点的简单多边形都可以进行三角剖分。在非退化情形下,每一种这样的剖分都恰好包含 个三角形和 条内部对角线。这些数量关系可以通过基本的平面计数方法或欧拉示性数推导出来,与多边形是否为凸多边形无关。凸性会影响哪些对角线可以使用,但一旦形成有效的三角剖分,所需三角形的数量就不受凸性影响。
两耳定理是一项实用的构造性结论。耳由多边形的三个连续顶点构成,这三个顶点形成的三角形位于多边形内部,且其内部不包含多边形的其他顶点。移除一个耳,就能将问题化为对一个更小多边形的处理。直接的耳切法通常具有关于顶点数的二次时间复杂度,不过更精巧的方法可以达到更优的复杂度界。贝尔纳·沙泽勒提出了一种用于简单多边形三角剖分的线性时间算法,并于1991年发表;这种理论上的高效率伴随着相当高的实现复杂度。
一个凸 边形通常有许多种不同的三角剖分方式,其数量为卡特兰数
因此,凸四边形有两种三角剖分,凸五边形有五种,凸六边形有十四种。局部的边翻转操作,是将两个相邻三角形组成的凸四边形中的一条对角线替换为另一条对角线。这类操作将几何三角剖分与组合数学联系起来,也提供了一种改进三角剖分或在不同剖分之间转换的机制。
带孔区域需要额外记录一些信息。如果一个连通平面区域具有 个边界顶点、 个孔,且没有添加内部顶点,那么其三角剖分包含
个三角形。在通常的相容性假设下,插入 个内部顶点后,三角形数量变为 。对于自相交的多边形曲线,必须先明确约定平面上的哪些部分属于所指的内部区域,三角剖分才有明确定义。
实际算法必须区分有效的几何构形与近乎退化的输入。重复顶点、极短的边、共线顶点,以及几乎相交的线段,都可能使判断变得复杂。因此,稳健的方向判定和相交检测与整体的分解方法同样重要。
德劳内三角剖分与沃罗诺伊对偶性
对于平面上的有限点集,问题不仅是将给定多边形细分,还要将这些点连接成有用的三角形网络。**德劳内三角剖分**的特征是满足空外接圆条件:每个三角形的外接圆内部都不包含其他输入点。它以鲍里斯·德劳内命名,德劳内于1934年发表了关于这一构造的奠基性研究。对于不全共线且任意四点不共圆的平面点集,德劳内三角剖分是唯一的。
它最核心的几何联系是与**沃罗诺伊图**之间的关系。每个沃罗诺伊单元包含这样的位置:这些位置到该单元对应输入点的距离,不大于到任何其他输入点的距离。在非退化的平面情形下,两个点对应的沃罗诺伊单元共边,当且仅当这两个点之间存在一条德劳内边;而沃罗诺伊顶点则对应于一个德劳内三角形的外心。这种对偶性将三角网格与最近邻几何联系起来。
德劳内三角剖分倾向于产生形状较好的三角形,但这一性质有明确且有限的含义:在同一平面点集的所有三角剖分中,它使最小角达到最大。这有助于避免某些不必要的狭长三角形,但对于任意分布的输入点,并不能保证得到良好的角度。点间距过小或近乎共线,都可能迫使剖分中出现质量较差的单元。如果四个或更多点位于同一个空圆上,相应的德劳内细分可能包含多边形面,此时需要选择对角线才能得到三角剖分。
提升构造提供了更深层的解释。将每个平面点 映射到三维空间中抛物面上的点
。将提升后各点的凸包的下侧面投影回平面,就得到德劳内细分。这将空圆判定问题转化为凸包问题,而且可以自然地推广到更高维。加权变体通过调整提升高度,得到正则三角剖分。
使用标准算法,可以在 时间内构造平面德劳内三角剖分。随机增量法逐点插入,并通过局部修改恢复空圆性质。分治法则先构造较小的三角剖分,再将其合并。可靠的实现需要稳健的方向判定和圆内判定,因为浮点运算造成的符号错误可能破坏网格的组合结构。
边界要求引出了约束德劳内三角剖分:它在保留指定线段的同时,对通常的德劳内条件作出调整。在三维空间中,对应的单元是外接球内部不含其他输入点的四面体。平面情形下良好的角度性质并不能直接推广到三维:三维德劳内网格可能包含薄片状四面体,即各边长度相近、体积却极小的四面体。
单纯复形与拓扑三角剖分
在拓扑学中,三角剖分用简单的构件及其粘合方式来表示空间。一个 维**单纯形**是 个仿射无关点的凸包。点是 维单纯形,线段是 维单纯形,三角形是 维单纯形,四面体是 维单纯形。更高维的单纯形沿用同一定义,只是超出了直接可视化的范围。
**单纯复形**是由单纯形组成的集合,其中包含每个单纯形的所有面,且任意两个单纯形要么交于一个公共面,要么互不相交。这些相容性条件使三角剖分区别于任意一组相互重叠的三角形。特别地,在满足这些条件的单纯复形中,一个三角形的顶点不能严格位于另一个三角形某条未经细分的边的内部;这条边必须相应地细分。
拓扑空间 的一个三角剖分由单纯复形 以及从其几何实现 到 的一个同胚组成。这比要求每个构件都平直地嵌在原空间中更为灵活。曲面可以与一个分片平坦的复形同胚,尽管二者的内蕴长度、角度和曲率并不相同。这种拓扑对应保持连续性和连通性,但不一定保持度量几何性质。
三角剖分使我们能够通过有限的组合数据研究整体不变量。对于一个具有有限三角剖分的曲面,
其中,、 和 分别表示顶点数、边数和三角形面数。对于亏格为 的连通、闭、可定向曲面,
球面的欧拉示性数为 ,而环面的欧拉示性数为 。三角剖分还提供了用于计算同调的链复形,通过对定向单纯形进行代数运算来刻画闭链、边界和孔洞。
细分会改变三角形,却不改变其底层拓扑空间。例如,重心细分引入与各个面相对应的顶点,并根据面之间的嵌套序列构造更小的单纯形。这类操作使我们能够比较不同的剖分,并用组合映射逼近连续映射。它们也揭示了两个问题之间的区别:一个空间是否可三角剖分,以及两个三角剖分是否在适当的分片线性意义下等价。
并非每个维数中的空间都必然可三角剖分。光滑流形具有相容的三角剖分,维数不超过三的拓扑流形也都可三角剖分。埃德温·莫伊兹于20世纪50年代初确立了三维流形的三角剖分及其唯一性的基本结果。相比之下,在四维以及每个不低于五维的维数中,都存在不可三角剖分的拓扑流形。因此,三角剖分体现了连续结构与组合结构之间的实质性联系,而不仅仅是一种方便的绘图技巧。
数值网格、插值与计算限制
三角剖分为函数逼近和物理方程求解提供计算域。在有限元法中,区域被划分为若干单元,二维中通常使用三角形,三维中则通常使用四面体。这样,复杂的全局问题便可通过局部函数及相邻单元之间的相互作用来表示。其应用包括结构变形、热流、电磁场和流体运动,不过,某种单元类型是否适用,取决于所求解的方程和采用的离散化方式。
在顶点为 的三角形内,每一点都有满足下式的重心坐标:
在三角形内部,三个坐标均非负。给定顶点值 ,分片线性插值的形式为
在相容网格上,相邻单元若使用相同的顶点值,其插值结果在公共边上便保持一致。插值函数是连续的,但其梯度通常会在单元边界处发生跳变。
精度并非仅由单元尺寸决定。过小的角或接近退化的单元会放大坐标误差,并降低导数近似的精度。标准的插值误差估计通常针对形状正则的网格族给出,即单元在缩小的过程中不会变得任意狭长。在适当假设下,对于足够正则的函数,线性有限元通常可在能量范数下达到 的误差,在 范数下达到 的误差。这些收敛阶取决于解的正则性、计算域的几何形状以及所求解的方程。
自适应加密会在当前离散化不足的区域集中布置单元,例如在凹角附近或场量急剧变化的区域。后验误差指标用于指导局部加密,而相容性要求可能使相邻三角形也必须进一步细分。当解沿某一方向变化迅速、沿另一方向变化缓慢时,各向异性方法会有意采用狭长单元。这类单元并非天然低劣:必须结合具体的逼近任务和相关方向上的尺度来评判其质量。
对曲边区域进行网格划分还会引入几何近似误差。以直边三角形网格逼近圆形边界,无法精确再现圆形。加密可以减小这种偏差,而曲边单元或高阶单元则能更准确地表示边界。因此,能够刻画连通关系的拓扑三角剖分,并不一定就是合适的数值网格。
最后,维度越高,三角剖分的计算开销就越大。平面德洛内三角剖分的输出规模为线性,而三维德洛内剖分中的四面体数量可能达到二次量级,更高维构造的规模增长还可能更快。内存需求、几何判定、边界相容性和单元质量都会成为重要的制约因素。计算中的核心权衡不仅在于单纯形的数量,还在于其排列方式能否有效表示几何形状和待逼近的量。