取现拐点的自动确立.doc

曲线拐点的自动确定
摘要：对于由离散点表示的数字地图与图形数据，本文首先利用两相邻矢量叉积乘积的原理来判定拐点所在的折线边；然后利用曲线光滑原理，在已确定的折线边的两个端点之间，建立一条光滑加密了的S形曲线，把后者看作是原始折线的精确曲线，对它进行曲线段凹向改变点（拐点）的定位计算。对于离散数据，多次应用矢量叉积乘积的原理，求出最或然拐点，并看作是理论拐点。为了简化计算量，探讨了如何避免为求拐点而进行光滑加密的辅助计算过程。对此，研究分析了拐点在折线边上的移动规律与其前后的曲线转角之间的相关关系，借此可直接根据原始离散数据作简单计算，在足够精确的程度上得出拐点的位置。

关键词：拐点；弯曲；曲折系数；矢量叉积

曲线的弯曲可看作是线状物体的子物体。在常规作业中，地图工作者识别各个弯曲不存在任何问题。而在计算机环境下，为了能使计算机自动识别曲线的各个弯曲，需要对弯曲作出数学形式化定义。
一、 拐点的定义
曲率最小点（零曲率点）即拐点，它是曲线凹向的变化（凸凹交替）点，是图形数学弯曲的分界点。拐点的连线就构成弯曲的底线，不同层次的拐点连线反映着线状物体不同级别的趋势走向。然而，拐点信息在数据获取中难以精确定位，通常也不像对待其他特征点那样给以特别的考虑，且在数据库管理中也未予以显式标示，即在原始数据中往往没有明确包含曲线的拐点信息。因此，在必要的情况下，只能通过计算来确定。
拐点又叫做扭转点，即在其前后存在的一个邻域内，使得其前后曲线段的凸凹特性相反。或者说，过拐点的切线把邻域内的曲线分成两部分，后者位于此切线的异侧。
在数字环境下，曲线不是由显式数学函数来表示，而是由离散坐标点来表示。此时，拐点的确定可分为两个子过程来进行：在原始数据的哪两点之间或曲线图形的哪一条边的区间存在拐点；拐点在该区间的何处。
二、 拐点存在区间的判别
由于两个不共线矢量的叉积可决定所成转角的凸凹特征，故对于拐点存在区间的判别，可通过对每相邻4 点（A，B，C，D）（其中每相邻三点不共线）进行测试来实现。在下图中A、D点是否位于B、C点连线的异侧。由这4个有序点可形成3个有序矢量（AB，BC，CD），这3个有序矢量可形成两个有序的矢量叉积。拐点存在的充要条件就是曲线凹向改变，即
（ＡＢ×ＢＣ）×（ＢＣ×ＣＤ）＜０ （1）
（图 拐点存在的折线段BC的判别）

作连续两个相邻矢量叉积（曲率或凹向的标志数）a×b和b×c 乘积，当（ＡＢ×ＢＣ）×（ＢＣ×ＣＤ）＜０，则存在拐点，，这个拐点就在两个矢量叉积的中间共享边BC 区间某处。如果拐点所在边的长度很短，则可取其中点为所需拐点，这时可直接进入下一个拐点
的确定。否则，需要进行离散点曲线拐点位置的确定。
三 、离散点曲线拐点位置的确定
此处研究的是拐点在其存在边BC区间的定位。在进行拐点在其存在边BC区间的定位之前，先得做一些准备工作——高精度S形光滑曲线的生成。
① 高精度S形光滑曲线的生成
为了使所求的拐点位置尽可能精确，需要有十分精确的曲线数据。数字化时是在精度范围内“以直代曲”，此处借助曲线光滑来实施“将直复曲”，以获取所需的更为精确的数据。用“斜轴抛物线光滑插值”【1】来表述拐点位置，进而确定拐点的位置与其前后相关数据点之间的关系，以便利用此关系绕过光滑插值直接按原始数据解算拐点。
斜轴抛物线光滑插值生成高精度S形光滑曲线的基本原理可通过与正轴抛物线光滑插值作比较来说明(图2)。对于 x值单调的非共线3个原始数据(节)点A、B、C。用拉格朗日差值多项式建立的正轴抛物线图形为曲线段 ABDC。此时的最大曲率点位于D点，而D 点并不是给定的已知的原始数据点。若借助坐标平移使抛物线的顶点位于中间点B。并通过坐标系旋转使抛物线同时通过A、C。这样的抛物线是一个局部坐标系中的斜轴抛物线，只是其坐标轴转角是个待定值．它可通过已知3点来解出[1] 。过已知三点A、B、C的斜轴抛物线图形(路径)为曲线段ABC。这两种抛物线之间的差异是显然的。如果骑自行车通过给定的A、B、C三点，其路径显然是近似于曲线ABC而不是ABDC。由此可见，路径问题是一个与坐标系无关的问题，斜轴抛物线是一条与坐标系无关的路径曲线。
（图 过A，B，C三点的斜轴抛物线ABC与正轴抛物线ABDC的区别）
当 x值不满足单调条件时，对于正轴抛物线来说，在出现多值函数的情况下．不能用正轴抛物线进行插值。而在斜轴条件下，无任何限制。
②拐点在其存在边BC区间的定位
如前所述，拐点的位置是在前后两个相邻的凹向相反的地方。拐点的位置由曲线光滑方法所限定，而光滑方法却有多种。因此，借助不同的光滑方法会得出不同的拐点。可以这样说．对于离散数据点曲线没有惟一的精确拐点存在．从而可用尽可能简单的方法来得到科学合理的拐点。为此，先通过图3所示的特殊对称情况(αB=αC)来说明拐点的计算问题。笔者在此仍采用计算表达
凸凹特性的矢量叉积乘积法来定位拐点。
首先观察图3所示的过4个已知点A、B、C、D 的折线连接和存在拐点边的BC区间的S形光滑曲线连接。此处的S形光滑曲线是用“斜轴抛物线光滑插值”【1】 所算出的。
问题是在S形光滑曲线的密集点列上计算所存在的拐点，并把这样所得的拐点称为理论拐点。此处，对S形曲线BFC的密集点列求其必然存在的拐点，仍采用前述两个相邻矢量叉积乘积的方法，如同在确定拐点存在边的
算法一样。其差别在于，前面处理的对象是比较稀疏的原始数据点，而此处处理的对象是光滑加密数据点，后者之间的边长足够短。因此，在确定
了拐点所在的短小边之后，就可认为拐点位于该边的中点处(图3)。在图3中。F为理论拐点(通过光滑插值计算而得)，d为拐点F在相关BC边的垂足。

第二个问题是拐点F是否落在BC边上。对此可作一些初步的机理分析：当拐点所在边的两端顶点处的转角αB和αC 相等时(图3中αB=αC=135。)，其比例关系R=αB /αC =1 即BC边两端弯曲程度对称时，则拐点F 位于BC边上，即它到BC边上的垂距为Fd=0，并且拐点位于BC边的中点处，亦即Bd=dC．这时的定比分割比
λ＝ Bd/dC=1。这种情况也可用Hermite带导数插值原理来说明。
由前人的总结知，拐点近似地位于相关边BC上。进而可以认为，可用拐点F在BC 边上的投影d 来代替F(图4）。

第三个问题是在不对称的一般情况下，拐点在BC 边上的定位（移动）规律R=αB /αC有无内在联系。若存在某种明显联系，则可根据所探明的联系直接由原始数据计算具有足够精确度的拐点，而无需借助曲线光滑手段。
四、简述拐点信息的主要应用
1>、形成曲线的总体趋势线
2>、用于曲线特征的自动分段
3>、线状目标曲折程度的测度
4> 、相对曲折的确定
5>、用于曲线信息量的评估
五、总结
地图上的曲线都有其明确的要素类型定义，特别是自然要素曲线有着更明确的地理含义，如河弯、海弯、谷地与山脊等【5】。它们是线状目标的子目标【4】，拐点和与之相关曲线上的弯曲对于面向图形子目标（弯曲段）的图形信息处理无疑是极为重要的，但在地图曲线综合中的具体操作却有差异。以地貌形态为例，表示谷地与其两侧相邻的山体，在综合处理中不是以拐点来分界，而是以弯曲的顶点来分界。因此，在图形综合中，需要根据拐点分割出曲线的弯曲段，进而求出各个弯曲的顶点，借此为综合功能程序提供处理对象。
参 考 文 献
1 毋河海.斜轴抛物线光滑插值.见：第三届全国地图学术会议论文选集（上集）. 北京：测绘出版社，1980
2 龚剑文.地图量算. 北京：测绘出版社，1989
3 祝国瑞，张根寿.地图分析. 北京：测绘出版社，1994
4 Buttenfield B P.Treatment of The Cartographic Line .Cartographica,1985,22(2):1~6
5 保查罗夫MK，尼古拉耶夫CA.制图作业数理统计法.北京：测绘出版社，1960