曲線拐點快速尋找算法+C代碼

定理 ：

 記關于平面上兩點 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的外點。

對于不在同一直線上的三點可以确定此段曲線的凹凸性，而要獲得曲線拐點資訊至少需要四個點。

假設 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 (x3, y3), 可以确定點 P3(x3 ,y3) 位于得到正向直線方程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) 不是拐點。

重複上述計算步驟，即可判斷 P3, P4, P5, ......, Pn-1 是否為拐點。

c語言代碼如下：

#include "stdio.h"

#include "stdlib.h"

#include "math.h"

struct point

{

double x;

double y;

};

point p[200];

double fun(point p1, point p2, point p3);  //正向直線方程

void getPoint();   //擷取測試點

void main()

{

int i, j;

getPoint();

double s1, s2;

for(i=3; i<199; i++)

{

s1 = fun(p[i-2], p[i-1], p[i]);

s2 = fun(p[i-1], p[i], p[i+1]);

if(s1*s2<0)

printf(" %lf  %lf\n", p[i].x, p[i].y);

}

}

 //正向直線方程

double fun(point p1, point p2, point p3)

{

double s;

s= (p2.x-p1.x)*(p3.y-p1.y)+(p1.y-p2.y)*(p3.x-p1.x);

return s;

}

//擷取測試點

void getPoint()

{

double i; 

int j=0;

for(i=0; i<7; i+=0.035)

{

p[j].x = i;

p[j].y = sin(i);

j++;

}

}

運作結果：

從結果中我們可以看出，函數 f=sinx，x=[0, 7]；在PI 和 2*PI 處存在拐點。