等距线的画法
本文作者 徐庆荣（武汉大学）
等距线画法可分为栅格（光栅）方式和矢量方式二种。栅格方式一般采用“距离变换”等算子实现，算法简练，但在不同方向上的等距线可能不严格等距。矢量方式是按几何关系通过坐标计算获得等距线位置，算法复杂，但精度高。本文介绍的是矢量方式的等距线画法。
1. 概述
简言之，等距线是指与已知线条（折线或曲线）等距的线条。等距线的应用甚广，例如：在地图上用于表示由平行线组成的各种线状符号（如道路，管线等）；在多边形内可由一系列闭合的等距线（称等距圈或同心线，例如在CorelDraw中执行Effects->Contour选项所产生的图形）来表示某种区域特征；在GIS“缓冲带”分析时，“缓冲带”的轮廓就是以某一线状要素为中轴在其两侧构造等距线，并使两端闭合的图形。又如，沿海国家可按等距线方法计算确定专属经济区海域的界线。此外，等距线还用于数控机床刀路计算和机器人行走路径规划等。
设等距线偏离（法线方向）已知线条的距离用d 表示。若有已知曲线C，在C 上的每点沿法线方向（同侧）与该点相距d 处定一新点，则这些点的轨迹C0 称为曲线C 的等距线。
这里，我们称构造等距线所依据的已知线条（折线或曲线）为原始线。当原始线是折线时，等距线可用“推平行线”法产生。若原始线是任一参数曲线C（t），则理论上其等距线的数学表达式为
C0(t) = C(t) ±（d·N(t)）
式中t 为曲线参数，N（t）为曲线在t 处的单位主法矢量，其方向指向曲线凹的一侧。式中的正号或负号取决于等距线的偏离方向。当等距线偏离方向与主法矢量同向时取正号，反之取负号。在曲线拐点处，法矢量为不确定，须作特殊处理。若C（t）＝{ x（t），y（t）}，即C（t）为平面参数曲线，则
N(t)={-y’(t)／sqrt((x’(t))2+(y’(t)) 2) ，x’(t)／sqrt((x’(t)) 2+(y’(t)) 2)}
2. 折线的等距线
原始线为折线的等距线，其计算和绘制过程（“推平行线”）如下。
（1）计算折线节点（各直线段的转折点）处的角平分线方向B
折线是由各直线段组成的，与各直线段等距的同侧平行线邻接于折线节点处的角平分线上。这里约定：角平分线方向指向折线走向的左侧（面向线段前进方向看的情况），并是从ｘ轴正向起算按反时针方向计的角度。角平分线方向B 可由与之相邻的两直线段的方向来计算确定。
（2）计算等距线的节点坐标
这里，等距线节点是指等距线上相邻直线段的交接点，它位于角平分线上，与原始线节点（x，y）对应的等距线节点的坐标（x0，y0）为：
x0=x±d'×cosB
y0=y±d'×sinB
式中d’代表等距线在角平分线上的截距，可由d和相邻的两直线段方向算得，一般情况下d’> d。如果在折线左侧作等距线，式中d’前的符号应取正号，反之取负号。
对于不闭合的折线，在首、末点处，以垂直于该处直线段的方向作为角平分线方向。等距线在首、末点处的端点坐标亦按上式计算。
（3）从等距线始点起顺序连接等距线各节点直至终点（也可一边计算一边连接）
3. 参数曲线的等距线
在计算参数曲线的等距线过程中，须用折线逼近原始曲线C（t）和等距线C0（t），即根据逼近的精度要求，以合适的步距（Δt）将曲线C（t）离散化，在离散点上计算等距线点，最后，以顺序连接各等距线点形成的折线近似作为等距线C0（t）。具体过程如下。
（1）令曲线参数t＝t0（t0是曲线起点处的参数），计算曲线起点处的N（t）和等距线点；
（2）根据逼近C（t）和C0（t）的精度要求确定Δt，在下一离散点（t＝t+Δt）处，计算原始曲线的N（t）和等距线点；
（3）反复（2）的过程，直至终点；
（4）顺序连接各等距线点（也可一边计算一边连接）。
Δt 的值也可以根据曲线情况分段确定，在变化不大的同一段曲线上采用相同的Δt。
参数曲线常用于拟合各种不规则曲线，这种拟合本身已具有一定误差。因此，在实际计算此种曲线的等距线时，可将曲线离散化后近似按折线处理。
4. 异常处理
当等距线与原始线（折线或曲线）的间距d 较大时（d 大于该处原始曲线的曲率半径），或者原始线迂回形成的自身间隔小于d 的两倍时，计算得到的等距线可能产生自交（形成“自交圈”）、不协调弯曲等异常现象。在计算过程中可按如下步骤判别和消除异常（以折线的等距线为例）。
（1）消除“反向自交圈”
我们称下列之一为反向自交圈（不包括首、末端闭合形成的等距线圈）：
a. 当等距线在原始线的左侧时，顺时针走向的等距线自交圈。
b. 当等距线在原始线的右侧时，逆时针走向的等距线自交圈。
（2）若等距线自交圈含有“逆向线段”，则该自交圈应被消除
如果等距线上的某直线段与对应的原始线上的直线段方向相反，则称等距线上的该直线段为逆向线段。含有逆向线段的自交圈，不管圈的走向，都应将其删除。
（3）消除含有“逆向线段”的不协调弯曲
尽管不在自交圈上，但若等距线局部线段为逆向线段，则在该处会形成与原始线不协调的弯曲。这时应作调整或删除，使等距线中不含逆向线段，从而消除不协调弯曲。
（4）消除与邻近原始线相距小于d 的自交圈或线段
若等距线某线段与邻近原始线的距离小于d（计算等距线时采用的应偏离原始线的距离），则应删去该线段。若此种线段位于自交圈，则应删去整个自交圈。
对于曲线的等距线，若在处理过程中它是被离散化的，则上述原则亦能适用。
对等距线可能出现的各种异常，尚难完全预料；由于机器精度所限的计算误差亦可能导致判别失误。上述消除异常的措施只是初步的，尚需有进一步的解决办法。
5. 应用
上述等距线生成和异常处理的算法，已用于图形软件开发工具UGS（通用绘图软件），UGS采用此法在区域内生成的等距圈纹理，效果如下图。UGS发布于CSDN（图形处理类），下载处：http://www.csdn.net/cnshare/shtm/18.shtm
作者发表于CSDN的相关文章:
"与图形结构无关"的矢量绘图算法
为图形软件的开发添一新工具
联系：可在CSDN论坛向xqr发短信息。
