如何比較兩條曲線（點陣）

我有問題找到方法來比較兩條軌跡（曲線）。第一個原稿包含點（x，y）。第二個可以偏移，更小或更大的比例，並與旋轉 - 也與點（x，y）排列如何比較兩條曲線（點陣）

我的第一個方法是找到兩點之間的最小距離，並重復此過程迭代，它的總和除以點數 - 那麼我的結果告訴我珍惜每點的平均誤差： http://www.mathopenref.com/coorddist.html

，也是我覺得這個方法： https://help.scilab.org/docs/6.0.0/en_US/fminsearch.html

，但我不能想出如何用它。我想比較兩個軌跡，但我的結果必須包括旋轉，或至少偏移開始。

我當前結果是每點計算誤差（距離）

獲得座標（x，y）的第二軌跡。
在循環中，我嘗試從1中找到（x，y）之間的min_distance並指向原始軌跡。
添加smallest_distance我發現在2步驟。
從第二個軌跡除以點數的最小距離的總和。

我的結果描述了每個點的平均誤差（距離），如果我們比較原始軌跡。

但我不知道如何處理如果軌跡旋轉，縮放或移位。

請大家看我的例子軌跡：

來源

2017-09-18 anna95

你應該用'[算法]'如果你想要的東西通用的，或者你應該指定編程語言，你想將其標記爲實現這一點，並提供您當前的結果。 –

謝謝你的建議。我正在寫自由軟件，如scilab或八度。 – anna95

所以你需要比較2條曲線上旋轉，平移和尺度不變的形狀。

解決方案

讓我們假設2個sinwaves進行測試。旋轉和縮放都具有相同的寬高比和一個增加的噪音。我生成它們在C++這樣的：

struct _pnt2D 
    { 
    double x,y; 
    // inline 
    _pnt2D() {} 
    _pnt2D(_pnt2D& a) { *this=a; } 
    ~_pnt2D() {} 
    _pnt2D* operator = (const _pnt2D *a) { *this=*a; return this; } 
    //_pnt2D* operator = (const _pnt2D &a) { ...copy... return this; } 
    }; 
List<_pnt2D> curve0,curve1;   // curves points 
_pnt2D p0,u0,v0,p1,u1,v1;   // curves OBBs 

const double deg=M_PI/180.0; 
const double rad=180.0/M_PI; 
void rotate2D(double alfa,double x0,double y0,double &x,double &y) 
    { 
    double a=x-x0,b=y-y0,c,s; 
    c=cos(alfa); 
    s=sin(alfa); 
    x=x0+a*c-b*s; 
    y=y0+a*s+b*c; 
    } 

// this code is the init stuff: 
int i; 
double x,y,a; 
_pnt2D p,*pp; 
Randomize(); 
for (x=0;x<2.0*M_PI;x+=0.01) 
    { 
    y=sin(x); 

    p.x= 50.0+(100.0*x); 
    p.y=180.0-(50.0*y); 
    rotate2D(+15.0*deg,200,180,p.x,p.y); 
    curve0.add(p); 

    p.x=150.0+(50.0*x); 
    p.y=200.0-(25.0*y)+5.0*Random(); 
    rotate2D(-25.0*deg,250,100,p.x,p.y); 
    curve1.add(p); 
    }

OBB方向包圍盒

計算OBB其中將找到曲線的旋轉角度和位置，從而使它們旋轉的一個，這樣便開始在相同的位置並具有相同的方向。

如果OBB尺寸太差，那麼曲線就不同了。

對於上面的例子中它yealds這個結果：

每個OBB由開始點和P基本向量U,V定義，其中的U x V爲正|U|>=|V|和z座標。這將確保所有OBB的繞組相同。它可以在OBBox_compute加入這年底完成：

// |U|>=|V| 
if ((u.x*u.x)+(u.y*u.y)<(v.x*v.x)+(v.y*v.y)) { _pnt2D p; p=u; u=v; v=p; } 
// (U x V).z > 0 
if ((u.x*v.y)-(u.y*v.x)<0.0) 
    { 
    p0.x+=v.x; 
    p0.y+=v.y; 
    v.x=-v.x; 
    v.y=-v.y; 
    }

所以curve0有p0,u0,v0和curve1有p1,u1,v1。

現在我們要重新調整，平移和旋轉curve1匹配curve0它可以這樣做：

// compute OBB 
OBBox_compute(p0,u0,v0,curve0.dat,curve0.num); 
OBBox_compute(p1,u1,v1,curve1.dat,curve1.num); 
// difference angle = - acos((U0.U1)/(|U0|.|U1|)) 
a=-acos(((u0.x*u1.x)+(u0.y*u1.y))/(sqrt((u0.x*u0.x)+(u0.y*u0.y))*sqrt((u1.x*u1.x)+(u1.y*u1.y)))); 
// rotate curve1 
for (pp=curve1.dat,i=0;i<curve1.num;i++,pp++) 
rotate2D(a,p1.x,p1.y,pp->x,pp->y); 
// rotate OBB1 
rotate2D(a,0.0,0.0,u1.x,u1.y); 
rotate2D(a,0.0,0.0,v1.x,v1.y); 
// translation difference = P0-P1 
x=p0.x-p1.x; 
y=p0.y-p1.y; 
// translate curve1 
for (pp=curve1.dat,i=0;i<curve1.num;i++,pp++) 
    { 
    pp->x+=x; 
    pp->y+=y; 
    } 
// translate OBB1 
p1.x+=x; 
p1.y+=y; 
// scale difference = |P0|/|P1| 
x=sqrt((u0.x*u0.x)+(u0.y*u0.y))/sqrt((u1.x*u1.x)+(u1.y*u1.y)); 
// scale curve1 
for (pp=curve1.dat,i=0;i<curve1.num;i++,pp++) 
    { 
    pp->x=((pp->x-p0.x)*x)+p0.x; 
    pp->y=((pp->y-p0.y)*x)+p0.y; 
    } 
// scale OBB1 
u1.x*=x; 
u1.y*=x; 
v1.x*=x; 
v1.y*=x;

您可以使用Understanding 4x4 homogenous transform matrices做到這一切在一個步驟。這裏的結果：

取樣不均勻或曲線之間或其任何部分之間非常不同的點密度的情況下

你應該重新品嚐你的曲線有共同點密度。您可以對此使用線性或多項式插值。您也不需要將新採樣存儲在內存中，而是可以構建函數，該函數返回從起點開始按照弧長參數化的每條曲線的點。
```
point curve0(double distance); 
point curve1(double distance); 
```

比較

現在你可以在。減去2條曲線和總結的差異腹肌。然後將其除以曲線長度並將結果閾值。

for (double sum=0.0,l=0.0;d<=bigger_curve_length;l+=step) 
sum+=fabs(curve0(l)-curve1(l)); 
sum/=bigger_curve_length; 
if (sum>threshold) curves are different 
else curves match

你應該試試這個，即使+ 180deg旋轉的方位差從OBB只有真正的範圍的一半。

以下幾個相關的問題答案：

來源

2017-09-19 07:46:17 Spektre

好的，但我需要什麼，如果我想比較兩條軌跡，但第二條是在兩個較小的比較。我想考慮一下這個例子，例如，原始模式是矩形，什麼是繪製，但規模較小。所以我的計算假設軌跡是不同的，但我想他們認爲是相等的 – anna95

@ anna95，所以即使比例不變......只需重新調整其中一條曲線，以便OBB大小匹配。或者將攤位重新調整到常見的長邊尺寸...... – Spektre

所以也許我應該做從0-1頻譜值（x，y）的軌跡歸一化和規模第二個之前我試圖compate他們？抽樣是什麼意思？我應該用x，y的相同密度重現軌跡？例如兩個軌跡的另一個座標應該每2個像素出現一次？ – anna95

如何比較兩條曲線（點陣）

回答

相關問題