实验 7 曲线波形图拐点的快速查找问题 7.1 实验问题 平面波形曲线一般是由一系列较短时间间隔采集数据点获得的平面离散点集，再经过分段线性插值的 方法画出的。波形特征（如波形曲线的极值点和拐点）的计算机自动识别在各种探伤和检测的计算机信息 处理中占有重要的地位。如何快速确定构成波形的这些离散点集中的拐点在平面曲线波形的计算机自动识 别中是经常要考虑的问题之一。试尝试给出一种确定平面波形曲线拐点的快速算法。 7.2 问题分析 因为平面波形曲线没有具体的函数表达式，因此不能象高等数学中介绍的通过对函数求导数的方法来 求拐点。如果采用借助数值微分的多点数值微分公式或外推算法来求平面波形曲线，会出现有计算量大和 误差大的缺点。由于，本题中所要做的是在平面离散点集中找出拐点，不是一般的求拐点问题，因此，可 以从平面离散点集本身的特点着手，来找出专门用于确定平面离散点集中的拐点的算法。由 于没有现成的 概念和结果可以利用，这里采用定义和论证的方法从基础做起。 为研究平面离散点集的特点，引入如下定义 定义 1. 设平面上两点的坐标分别为 P1(x1 ,y1) 和 P2(x2 ,y2), P1„ P2，称具有方向 P1P2 且过此两点的有向 直线为正向直线，而称对应的直线方程 L: (x 2-x1)(y-y1) + (y1-y2)(x-x1) = 0 为关于点 P1 ，P2 的正向直线方程。 定义 2. 给定平面上一条正向直线 L 后，平面上不在 L 上的点分为两类，处于直线 L 顺时针一侧的点称为 关于正向直线 L 的内点, 而处于直线 L 逆时针一侧的点称为关于正向直线 L 的外点。 利用如上定义，我们有 定理 1. 记关于平面上两点 P1(x1 ,y1) 和 P2(x2 ,y2)的正向直线方程 L 的左端表达式为函数 S12 (x , y)= (x2-x1)(y-y1) + (y1-y2)(x-x1) 对于不在直线 L 上的任何一点 P0 (x0,y0 ) ，有 (1) 如果 S12 (x0,y0) <0 , 则 P0 (x0,y0 ) 是正向直线 L 的内点. (2) 如果 S12 (x0,y0) >0 , 则 P0 (x0,y0 ) 是正向直线 L 的外点 证明 取与点 P0 (x0,y0 )有同一横坐标且在 L 上的参考点 Q(x0,y*)，则有 S12 (x0 , y*)= (x2-x1)(y*-y1) + (y1-y2)(x0-x1) =0 将 P0 (x0,y0 ) 代入函数 S12 (x ,y),有 S12 (x0 , y0)= (x2-x1)(y0-y1) + (y1-y2)(x0-x1) =( x2-x1) (y0-y*+y*-y1)+ (y1-y2)(x0-x1) =( x2-x1) (y0-y*)+( x2-x1) (y*-y1)+ (y1-y2)(x0-x1) =( x2-x1) (y0-y*) 关于 P1 和 P2 的正向直线 L 有四种情况（见图 1）。 (a) x1x2, y1x2, y1‡ y2 图 1 关于 P1 和 P2 构成的正向直线及对应的内点 

如果 S12 (x0 ,y0)<0 ,由式 (1), 对于图 1 中的 (a) 和 (b)，由于 x2-x1>0, 得 y0-y*<0, 即 y0 < y*,说明 在情况(a) 和 (b)下，点 P0 (x0 ,y0)位于直线 L 下方；而对于图 1 中的 (c) 和 (d)，由于 x2-x1<0, 得 y0-y*>0, 即 y0 > y*,说明在情况(c) 和 (d)下，点 P0 (x0 ,y0)位于直线 L 上方。因此，不论是哪种情况，当 S12 (x0 ,y0) <0 , 点 P0 (x0 ,y0) 都位于正向直线 L 的顺时针一侧，由定义 2，可以知道 P0 (x0 ,y0)是关于正向直线 L 的内点。于是得出如果 S12 (x0 ,y0) <0 ,则点 P0 (x0 ,y0) 是关于正向直线 L 的内点。 同理，可以证明如果 S12 (x0 ,y0) >0 ,则点 P0 (x0 ,y0) 是关于正向直线 L 的外点。 7.3 拐点的确定及算法 拐点是曲线凹凸交界点，注意到不在同一直线上的三点可以确定此段曲线的凹凸性。因此，要获得曲 线拐点信息至少需要四个点。本文采用前面正向直线和内外点知识，可以对连续 4 个点中的第 3 个点进行 是否为拐点的判断。由于凸（或凹）曲线是其所有切线的包络线，因此，在较小的范围内，凸（或凹）曲 线上的点都处于其上切线族的同侧。假设给定的点集来自彼此很接近的曲线点集，则曲线的切线可以由相 继两点的正向直线代替，这样就可以用关于正向曲线的点集分类来确定拐点。 设 P1(x1 ,y1), P2(x2 ,y2), P3(x3 ,y3) 和 P4(x4 ,y4)是曲线上相继的彼此很接近的 4 个点，且点 P3(x3 ,y3) 可能是拐点。取 P1(x1 ,y1) 和 P2(x2 ,y2), 得到正向直线方程 L1 : S12(x, y) =0 计算函数值 S12 (x 3, y3), 可以确定点 P3(x3 ,y 3) 位于得到正向直线方程 L1 的哪一侧，然后再取点 P2(x2 ,y2), P3(x3 ,y3) 得到另一正向直线方程 L2 : S23 (x, y) =0 计算函数值 S23 (x4, y4), 可以确定点 P4(x4 ,y4) 位于得到正向直线方程 L2 的哪一侧。 如果 S12 (x3, y3) S23 (x4, y4) <0,可以得出点 P3(x3 ,y3) 是一个拐点，否则 P3(x3 ,y3) 不是拐点（见图 2）。 (a)P3 不是拐点 （b）P3 是拐点 (c)P3 不是拐点 （d）P3 是拐点 图 2 P3 是否为拐点的几种情况 对来自某一曲线上相继的彼此很接近的一组离散点集 Pi (xi, yi), i=1,2，……，n，假设曲线上的拐 点都在其中。可以先由开始的 4 个点 P1(x1 ,y1), P2(x2 ,y2), P3(x3 ,y3) 和 P4(x4 ,y4) 来判别 P3 是否为拐 点，然后加入下一个点 P5(x5 ,y5) 并用 P2(x2 ,y2), P3(x3 ,y3) , P4(x4 ,y4)和 P5(x5 ,y5) 来判别 P4 是否为 拐点，这样继续下去就可以知道 P5, P6,…,Pn-1 是否为拐点。由于处于曲线开始和结尾的拐点一般不做考虑， 因此，可以得到如下确定平面曲线离散点集中拐点的快速算法 ： (1) 计算 S12 (x3, y3)并将其存储在变量 S1 中，即 S12 (x3, y3) =>S1. (2) 对 i = 3,4,5，………，n-1 ‹ Si-1 i (xi+1, yi+1)=>S2 › 如果 S1*S2<0 ，则 Pi (xi, yi) 是拐点，保存或打印此点 Pi (xi, yi) fi 替换 S1 的值，进行下一个点的判别：S2 => S1 （3）停止 

如上算法可以可以非常快速准确的找到给定平面曲线离散点集中的拐点，且计算误差小，效率高。不 但可以快速确定通常探伤和检测波形图中的拐点，而且可以快速确定平面参数曲线离散点集中的拐点。特 别，当给定的离散点集来自于点集横坐标为等距递增情况时，即 xi=x1+ih, i=2,3,….,n,步长 h >0，此时 选取任意相邻三个点 Pi-1(xi-1, yi-1), Pi(xi, yi), Pi+1(xi+1-, yi-1) 由坐标的等距性，有 Si-1 i (xi+1,yi+1)= (xi-xi-1)(yi+1-yi-1)+(yi-1 –yi)(xi+1 –xi-1) =h (yi+1–2yi +yi-1) =h[(yi+1 –yi) – (yi-yi-1)] 为减少计算量，引入变元 zi =yi-yi-1, 于是有 Si-1 i (xi+1,yi+1) =h (zi+1 –zi). 注意到 h >0,于是 zi+1 –z i 的符号可以决定 Si-1 i (xi+1,yi+1) 的符号，这样可以得到如下关于点集横坐标为 等距递增的平面曲线离散点集拐点的更加快速简洁的查找算法： (1) 对 i=2,3,4….,n ,计算 zi =yi-yi-1, (2) 做 z1-z2=>S1 (3) 对 i =2,3,4,…..,n , ‹ 做 zi -zi-1 =>S2. › 如果 S1*S2<0 ，则 Pi (xi, yi) 是拐点，保存或打印此点 Pi (xi, yi) fi 替换 S1 的值，进行下一个点的判别：S2 => S1 (4) 停止 7.4 算例 为说明如上给出查找平面曲线离散点集的拐点算法的效率，下面分别给出一般曲线波形和参数曲线离 散点集来进行求拐点的计算例题。 例1． 考虑在[-3，3]上的函数 y=x*sin x2，它在[-3，3]上的有 7 个拐点，分别为： x1= -2.5514, x2=-1.88206,x3= -0.994103, x4=0. , x5=0.994103, x6=1.88206, x7=2.5514. 现在从该曲线上取 400 个等距点获得该曲线图形的离散点集。利用本算法快速准确的求出了该离散点集的 拐点，分别为： 第 31 点 {-2.55, -0.55478}；第 76 个点 {-1.875, 0.685072}；第 135 个点 {-0.99, -0.822248} 第 201 个点 {2.42861 10-15 , 1.43243 10- 44 }；第 268 个点 {1.005, 0.851079} 第 327 个点 {1.89, -0.788757}； 第 372 个点 {2.565, 0.748299}。 计算结果是非常令人满意的。它的散点图与求出的拐点在同一坐标系中的图形见图 3。 图 3 函数 y=x*sin x2 的散点图与求出的拐点图 例 2．考虑参数方程 x=sin[t]*cos[t], y=sin[t]*sin[t2]; t˛ [0,p ], 现在从该参数曲线上取 1000 个等 距点获得该参数曲线图形的离散点集。利用本算法快速准确的求出了该离散点集的拐点为： 第 590 个点 {-0.265256, -0.267822}；第 923 个点 {-0.235352, 0.208575} 处理参数曲线点集的计算结果也是非常令人满意的。它的散点图与求出的拐点在同一坐标系中的图形见图 4。 

图 4 参数曲线 x=sin[t]*cos[t], y=sin[t]*sin[t 2]的散点图与求出的拐点图 7.5 思考与提高 1． 怎样用数学软件画出例 1 和例 2 中的图形？ 2． 你从本题的处理问题方法中能得到什么启发？