Delaunay 的 TIN - 三角不规则网络

• 下载源码 - 49 Kb
• 下载演示项目 (需要 GDI+ 和 MFC71.dll) - 1123 Kb

引言

这个程序基于 Delaunay 三角剖分，从二维平面上的散点生成不规则三角网 (TIN)。这种数据结构可以将数据展示为三维表面，或者用于地形分析，包括绘制等高线和可视性mapping。

使用代码

如果成功编译源代码，将生成一个简单的控制台程序，只需要两个参数。第一个参数应该是点文件的名称。 点是从一个简单的文本文件中读取的，该文件包含以逗号分隔的 X-Y 或 X-Y-Z 坐标列表。 虽然 z 坐标在计算中没有使用，但是包含高度信息的数据可以用于演示程序 TriNET 中的透视观察。 下面是图中所示数据的输入文件示例

200,790
370,760
60,670
360,890
280,620
30,880
230,960

或，

200,790,100
370,760,110
60,670,115
360,890,92
280,620,125
30,880,95
230,960,110

三角形列表保存到三角形文件中。 三角形文件生成在与输入文件相同的目录中，扩展名为 "tri"。 输出文件将如下所示。 在此示例中，生成了六个三角形，在生成的 "tri" 文件中，生成的三角形顶点的序列号列出如下

1,6,7
1,3,6
2,7,4
1,2,5
1,7,2
1,5,3

例如，第一个三角形 (A) 由输入文件中的第一个、第六个和第七个顶点组成。

此分发文件中包含两个点文件，Davis.nod 和 test32.nod 作为示例。

关于算法的说明

此程序的第二个参数决定是否使用凸包。 如果将其设置为 N，或者没有给出第二个参数，为了在区域边界之外生成三角形，将在点的范围周围生成一组伪点。
相反，如果将 'Y' 赋给此参数，则会生成凸包并将其用作输入区域的边界。 凸包（在 2D 中）是包含所有输入点的最小凸多边形。 如下面的示例所示，与左侧的网络相比，凸包中的所有部分都在右图中进行了三角剖分，但它倾向于创建不规则形状的三角形（右图中的蓝色三角形），这不满足所有生成的三角形的最大内角必须最小化的条件。

演示程序

我添加了 Windows 程序 TriNET，以交互方式运行和显示三角剖分的结果。 要从一组散点构建 TIN，请从菜单中选择 "Terrain" -> "Construct TIN" 或 "Construct TIN - Convex Hull"，然后从对话框中选择点文件。 检查菜单项 "Terrain" -> "Display Monitor" 以实时观察三角剖分的过程。 这对计算结果没有影响，除了它会使其明显变慢。 只是为了好玩！ 输入点和生成的三角形可以在 TriNET 中显示。 如果点具有 z 坐标，则生成的 TIN 可以用于透视观察。 从 "Draw" 菜单中选择每个功能。


在三维显示中，使用左右箭头水平旋转，使用向上和向下键改变俯仰角。 F1 和 F2 键可以扩大和缩小视野。

TriNET 需要 GDI+ 库。 运行时模块可以在 Microsoft 网站上获得。 将 gdiplus.dll 复制到 Windows 系统目录。 TriNET 还需要 MFC71.dll 和 msvcr71.dll。

参考文献

这个程序使用 Delaunay 三角剖分方法。 有许多关于此算法的文档已发表或可在网上获得。 我使用 John C. Davis 编写的 "Statistics and Data Analysis in Geology, Third Edition", John Wiley and Sons(2002) 一书，其中包含对此算法非常简单但透彻的描述。

历史

• 首次上传，14/4/2004 - 只希望人们在阅读我的英语后不必呕吐。