Find C++の点集合を囲む楕円の最小部分

Question

私は2D点の集合を持っています。私は、すべての点を囲む最小面積の楕円を見つける必要があります。誰かがどのように問題に取り組まなければならないかという考えを伝えることができますか？サークルのためには簡単でした。中心とポイントの間の最大距離。しかし、楕円については、それは私が知らない非常に複雑です。私はこれをC++で実装する必要があります。

Answer 1

私がそれを証明できるかどうかはわかりませんが、最適解は（少なくとも）3点の接線で表され、他のすべての点は楕円の中にあります！）。だから何もしなければ、〜n^3点の3つの点をすべてチェックし、それらが解を定義しているかどうかを調べることで、それを強制することができます。周囲の楕円の中に厳密に含まれていなければならないすべての点を削除することでそれを改善することが可能であるべきですが、どうすればそれができるかわかりません。たぶんxとyの座標でポイントを並べ替えると、何か派手なやり方で。

完全な解決策ではありませんが、それはスタートです。

EDIT： 残念ながら、3点では楕円を定義するには不十分です。しかし、おそらくあなたが3点を接する最小面積の楕円に制限したら？

Answer 2

Rory Daultonは、解の制約を明確に指定する必要があると示唆しています。手始めに、今はこれを前提としています

• それは2D問題
• 楕円を軸
• センターは、私はこのような標準のgenereを攻撃する代わりに(0,0)

の任意で整列されているとテストapproximation search（バイナリ検索とリニア検索のハイブリッド）の問題でスピードアップできます（ただし、最初からブルートフォースを試すこともできますそれが動作する場合）。ソリューション

の

1. 計算制約を使用すると、楕円のおおよその配置位置とサイズを見つける必要があり、検索を制限します。そのためにはあなたのポイントにアウトスクライブサークルを使用することができます。楕円領域は円以下であり、配置は近くになることは明らかです。

   1. 円がそのバウンディングボックスにセンタリングさせて、半径が最大なるポイント
   2. のバウンディングボックスを見つける：円は私たちは、これは例えば使用することができ、必ずしも可能な最小1である必要はありません。その中心から任意の点までの距離。

   これはO(n)の複雑さです（nはあなたのポイントの番号です）。

2. 検索「すべて」の可能な楕円と最善の解決策

   を覚えているので、我々はarea = M_PI*rx*ryが最小であるrx,ryながら、楕円の中心(x0,y0)と半車軸を見つける必要があります。近似探索では、各変数はO(log(m))の係数を持ち、各反復はO(n)という妥当性をテストする必要があるため、最終的な複雑度はO(n.log^4(m))となります。ここで、mは各検索パラメータの可能なバリエーションの平均数です（精度と検索の制約に依存します）。単純なブルート検索ではO(n.m^4)となります。特に浮動小数点の場合は、実際には恐ろしいです。mが本当に大きくなる可能性があります。

   これをスピードアップするために、楕円の面積は見つかった円の面積以下であるため、すべてのより大きい楕円を無視することができます。 rx,ryの制約は、境界ボックス+/-一部の予備の縦横比から導き出すことができます。

   //--------------------------------------------------------------------------- 
   // input points 
   const int n=15; // number of random points to test 
   float pnt[n][2]; 
   // debug bounding box 
   float box_x0,box_y0,box_x1,box_y1; 
   // debug outscribed circle 
   float circle_x,circle_y,circle_r; 
   // solution ellipse 
   float ellipse_x,ellipse_y,ellipse_rx,ellipse_ry; 
   //--------------------------------------------------------------------------- 
   void compute(float x0,float y0,float x1,float y1) // cal with bounding box where you want your points will be generated 
       { 
       int i; 
       float x,y; 
       // generate n random 2D points inside defined area 
       Randomize(); 
       for (i=0;i<n;i++) 
        { 
        pnt[i][0]=x0+(x1-x0)*Random(); 
        pnt[i][1]=y0+(y1-y0)*Random(); 
        } 
       // compute bounding box 
       x0=pnt[0][0]; x1=x0; 
       y0=pnt[0][1]; y1=y0; 
       for (i=0;i<n;i++) 
        { 
        x=pnt[i][0]; if (x0>x) x0=x; if (x1<x) x1=x; 
        y=pnt[i][1]; if (y0>y) y0=y; if (y1<y) y1=y; 
        } 
       box_x0=x0; box_x1=x1; 
       box_y0=y0; box_y1=y1; 
       // "outscribed" circle 
       circle_x=0.5*(x0+x1); 
       circle_y=0.5*(y0+y1); 
       circle_r=0.0; 
       for (i=0;i<n;i++) 
        { 
        x=pnt[i][0]-circle_x; x*=x; 
        y=pnt[i][1]-circle_y; y*=y; x+=y; 
        if (circle_r<x) circle_r=x; 
        } 
       circle_r=sqrt(circle_r); 
       // smallest area ellipse 
   
       int N; 
       double m,e,step,area; 
       approx ax,ay,aa,ab; 
       N=3; // number of recursions each one improves accuracy with factor 10 
       area=circle_r*circle_r; // solution will not be bigger that this 
       step=((x1-x0)+(y1-y0))*0.05; // initial position/size step for the search as 1/10 of avg bounding box size 
       for (ax.init(  x0,   x1,step,N,&e);!ax.done;ax.step()) // search x0 
       for (ay.init(  y0,   y1,step,N,&e);!ay.done;ay.step()) // search y0 
       for (aa.init(0.5*(x1-x0),2.0*circle_r,step,N,&e);!aa.done;aa.step()) // search rx 
       for (ab.init(0.5*(y1-y0),2.0*circle_r,step,N,&e);!ab.done;ab.step()) // search ry 
        { 
        e=aa.a*ab.a; 
        // is ellipse outscribed? 
        if (aa.a>=ab.a) 
         { 
         m=aa.a/ab.a; // convert to circle of radius rx 
         for (i=0;i<n;i++) 
          { 
          x=(pnt[i][0]-ax.a); x*=x; 
          y=(pnt[i][1]-ay.a)*m; y*=y; 
          // throw away this ellipse if not 
          if (x+y>aa.a*aa.a) { e=2.0*area; break; } 
          } 
         } 
        else{ 
         m=ab.a/aa.a; // convert to circle of radius ry 
         for (i=0;i<n;i++) 
          { 
          x=(pnt[i][0]-ax.a)*m; x*=x; 
          y=(pnt[i][1]-ay.a); y*=y; 
          // throw away this ellipse if not 
          if (x+y>ab.a*ab.a) { e=2.0*area; break; } 
          } 
         } 
        } 
   
       ellipse_x =ax.aa; 
       ellipse_y =ay.aa; 
       ellipse_rx=aa.aa; 
       ellipse_ry=ab.aa; 
       } 
   //--------------------------------------------------------------------------- 
   

   のみ15ポイントでさえ、この単純な例で計算するのに約2秒を要した：上記のリンクからapproxクラスがいることを利用し

ここでは、単純な小さなC++例。 circle_r^2などのテスト専用領域のようなヒューリスティックを追加するか、数学のルールでソリューション領域を選択することで、パフォーマンスを向上させることができます。近似探索の代わりにブルートフォースを使用すると、計算時間がほんの数分になることが予想されるので、O(scary) ...

この例は、ポイントのアスペクト比については、 rx,ry〜2.0*circle_rこれでは不十分かもしれません。代わりに、rx*ry<=circle_r^2 ...

がCCD（環状下降座標）の一例のバリエーションのための他の（「高速」）方法を使用することができるにも存在することアスペクト点の比およびまたは状態から上限を計算することができます。 。しかし、このような方法は、通常、最適な解決策がまったく見つからないか、または任意のされることを保証することはできません...出力例のここ

は概要：

ドットは、pnt[n]から灰色の個々の点です破線のものはバウンディングボックスであり、アウトスクライブサークルを使用しています。緑色の楕円が解です。