等值线算法.doc

等值线算法：
1. 根据给定点生成三角形网格（具体见三角形网格生成算法），假设标量场在三角形的内部及边上满足线性分布关系。
2. 根据标量场的最大值和最小值以及等值线的条数（可以设置一个缺省值比如30， 用户可以改变该值）， 均匀划分出一系列的等值线的给定值。
3. 对每一个给定值， 对所有三角形单元搜索一遍。 如果这个给定值位于某三角形单元的三个顶点处的标量值的最大值和最小值之间， 则必定在三角形的边上存在着两个点， 这两个点的标量值等于给定值。 把这两个点连接起来就得到等值线的一部分（参见图1）。 将所有三角形单元按上述方法搜索一遍， 就画出了等值线。
4. 上述算法画出的等值线不够光滑， 采用适当的光滑算法比如样条插值就得到光滑的等值线。

流线图算法：
1. 根据给定点生成三角形网格，假设矢量场在三角形的内部及边上满足线性分布关系。
2. 用户可选择流线的起始点（seed）。 可以逐点选择， 也可以选择一条线段，再对线段等分得到起始点。
3. 起始点可能不在给定点中，这时要搜索起始点位于哪个单元（具体见搜索算法）。 通过插值可得到起始点处的矢量。 选择合适的时间步长，具体数值可以使得在该时间步长内沿矢量场方向走过的距离约等于当地网格的尺寸。 运动到下一位置后， 再搜索该点位于哪个单元，插值可得到该点处的矢量， 如此循环， 直到点运动到边界以外或达到最大的步数（可以设成一个较大的数值如1000）。

三角形网格生成算法（Delaunay方法）：参见所附论文。

搜索算法: 搜索某个点位于哪个单元
将区域分为若干子矩形区域（比如50×50），先扫描所有单元，将单元按区域归类。 对于给定点， 先根据区域的坐标范围判断该点位于哪个区域。 然后扫描该区域所有单元， 判断该点位于哪个单元。 判断一个点是否在一个三角形内部的方法（参见图2）： 将该点与三角形的每条边分别相连，得到三个三角形， 计算这三个三角形的面积， 如果面积之和等于原三角形的面积， 则该点在三角形内。 这三个三角形的面积和原三角形之比，就是该点的插值函数。

图1 等值线算法示意图

图2 判断点是否在三角形内部的算法示意图