オーバーラップフォームのグループ間の合計領域

Question

与えられたゾーンでPythonでプロットされたカーブのグループ間の残りの領域を計算する上で問題があります。ここ

を例示する画像である。

各フォームはパラメトリック方程式と高 に対して異なるパラメータを有する2半の楕円で形成されている：

X  =Xc+A *cos(Theta) 
Y_down=Yc+B1*sin(Theta) 
Y_up =Yc+B2*sin(Theta) 

1つのラインに沿って（ X方向）では、パラメトリック方程式はXcを除いて同じです。 Y軸（垂直方向）に沿って、AはXcとYcと共に変化します。

すべてのフォームは、X軸の反復とY軸の反復によって作成されます。私はプロットの中でZorderを使って、彼らが創造の順番で重なり合うようにしました。

問題は、すべてのフォームの面積を計算することができますが、これらのフォームが可能な限りあらゆる方法で重複しているため、どのように赤色の領域が見つかるかわかりません。 現時点では、すべての曲線をプロットし、出力されたFigureを2進化して合計することで、赤い領域にアクセスできます。しかし、私は出力図のDPIに依存しないより分析的で洗練されたソリューションを探したいと思っています。それとも私は何かできることがありますか？

ありがとうございました！私は明らかに希望します。

Answer 1

これはジオメトリの問題です。合計面積合計から重複面積を削除する必要があります。それは簡単な仕事ではありません。あなたは、楕円弧曲線間の統合によってそれを解決しようとすることができます。 2つの省略記号は簡単ですが、最初に使用する円弧と内側か外側かを判断する必要があります。それは退屈なコードになる可能性があります。

代わりに、十分な幅（積分の精度）で垂直スライスにシーンを分割し、ヒットテストを使用して、塗りつぶされていないすべての領域を決定/合計することができます。レイキャスティング

1. プロセスシーン一部dxステップ

   によってdxステップは、結果の精度を決定します。各xため

2. このNが楕円の数で単純O(N)検索すべての交点

   を集めます。現在のxごとに2つのyの各楕円の座標を計算し、それをリストに追加します（有効な場合）。

3. これはnは交差点の数であるO(n^2)

   別の楕円の内側にあるすべての交点を除去します。いずれかの交差点が任意の楕円交点内にあるかどうかを簡単にテストします。はいの場合は削除のためにフラグを立ててください。結果を無効にするので、検索中にそれらを削除しないでください。この方法では、リストには外側の交点のみが含まれます。重複があるかもしれないことに注意してください!!!

4. ソート交差点y

   によってこれは、次のプロセスを簡素化/高速化されます。 y=y_start

5. から

6. キャストレイ、それは単にリストの最初の交点であるパス

   で最初の交差点を見つけます。統合範囲内にあるかどうかをチェックし、そうでない場合はスキップ/停止します。有効な場合は、最後の点までの距離を追加します（最後の反復からのy_startまたはy）。 yの値をy_endに固定することを忘れないでください。そうしないと、画面に表示されない領域を領域に追加することができます...

7. yは（重複した値を処理するために）ジャンプ座標まで単に交差点リストを指し示すインデックスをインクリメントこの楕円

   の終わりを見つけます。リストの最後にy_endをyの値として使用すると...領域に追加して停止します。

8. ループ＃6 y_endまではヒットするか

ここでは、このために私C++/VCL実装を交差させている座標：ここ

//--------------------------------------------------------------------------- 
struct _ellipse 
    { 
    double x,y,rx,ry0,ry1; 
    _ellipse() {} 
    _ellipse(_ellipse& a) { *this=a; } 
    ~_ellipse() {} 
    _ellipse* operator = (const _ellipse *a) { *this=*a; return this; } 
    //_ellipse* operator = (const _ellipse &a) { ...copy... return this; } 
    }; 
struct _hit 
    { 
    double y; // hit y coordinate 
    int ix;  // ellipse index 
    int f;  // 0 means ry0, 1 means ry1 edge, >=2 means deleted 
    _hit() {} 
    _hit(_hit& a) { *this=a; } 
    ~_hit() {} 
    _hit* operator = (const _hit *a) { *this=*a; return this; } 
    //_hit* operator = (const _hit &a) { ...copy... return this; } 
    }; 
const int N=50; 
_ellipse ell[N]; 
//--------------------------------------------------------------------------- 
void sort_asc_bubble(_hit *a,int n) 
    { 
    int i,e; _hit q; 
    for (e=1;e;n--) 
    for (e=0,i=1;i<n;i++) 
     if (a[i-1].y>a[i].y) 
     { q=a[i-1]; a[i-1]=a[i]; a[i]=q; e=1; } 
    } 
//--------------------------------------------------------------------------- 
void init() 
    { 
    int i; double xs=512,ys=512; 
    _ellipse a; 
    RandSeed=587654321; 
    for (i=0;i<N;i++) 
     { 
     a.x=xs*Random(); 
     a.y=ys*Random(); 
     a.rx =xs*(0.02+(0.25*Random())); 
     a.ry0=ys*(0.02+(0.09*Random())); 
     a.ry1=ys*(0.02+(0.09*Random())); 
     ell[i]=a; 
     } 
    } 
//--------------------------------------------------------------------------- 
double area() 
    { 
    double area,dx=1.0; 
    double x,y,xx,y0,y1,rxx,ryy0,ryy1; 
    _ellipse *p; 
    _hit hit[N+N];  // intersection points 
    int i,j,n;   // n = number of intersections 
    int _in; 
    for (area=0.0,x=0.0;x<scr.xs;x+=dx)  // all vertical slices 
     { 
     // [prepare data] 
     // O(N) precompute intersection points for ray/ellipses 
     for (n=0,p=ell,i=0;i<N;i++,p++) 
     if ((x>=p->x-p->rx)&&(x<=p->x+p->rx)) 
      { 
      xx=x-p->x; xx*=xx; 
      rxx =p->rx *p->rx ; 
      ryy0=p->ry0*p->ry0; 
      ryy1=p->ry1*p->ry1; 
      hit[n].ix=i; hit[n].f=0; hit[n].y=p->y-sqrt(ryy0*(1.0-(xx/rxx))); n++; 
      hit[n].ix=i; hit[n].f=1; hit[n].y=p->y+sqrt(ryy1*(1.0-(xx/rxx))); n++; 
      } 
     // O(n^2) flag inside edges 
     for (i=0;i+1<n;i+=2) 
      { 
      y0=hit[i+0].y; 
      y1=hit[i+1].y; 
      for (j=0;j<n;j++) 
      if ((i!=j)&&(i+1!=j)) 
       if ((hit[j].y>y0)&&(hit[j].y<y1)) 
       hit[j].f|=2; 
      } 
     // O(n) delete flagged edges 
     for (i=0,j=0;i<n;i++) 
     if (hit[i].f<2) 
      { hit[j]=hit[i]; j++; } n=j; 
     // O(n^2) sort y asc and original indexes are in i0,i1 
     sort_asc_bubble(hit,n); 

     // [integrate area] 
     for (i=-1,y0=0.0,y1=0.0;;) 
      { 
      i++; if (i<n) y=hit[i].y; else y=scr.ys; 
      if (y>scr.ys) y=y>scr.ys; 
      if (y>y1) 
       { 
       y0=y1; y1=y; 
       area+=y1-y0; 
       // debug draw for visual check (render red pixel at x,y0 ... x,y1) 
       //for (y=y0;y<=y1;y++) scr.pyx[int(y)][int(x)]=0x00FF0000; 
       } 
      if (i>=n) break; 
      y=hit[i].y; 
      for (;i<n;i++) if (hit[i].y>y) { y1=hit[i].y; break; } 
      } 
     } area*=dx; // rectangular rule 
    return area; 
    } 
//--------------------------------------------------------------------------- 

はdx=1.0と解像度512x512のためになります：

ウィンドウCaption内の数字は、窓面の[pixels^2]略31%における計算領域です。任意の統合ルールまたはdxのステップを使用できます。また、あなたは何かのためにバブルの並べ替えを変更することができますが、しばしばそのような小さなバブルは、他のものを打ち負かす...とコード化するのは簡単です。

コード自体はまだ最適化されていません...

Answer 2

これはラインスキャンの問題のようです。

上から下に、左から右に、どの方向にも簡単に処理できる行を想像してください。それを上から下に移動させてみましょう。

あらゆる点で、線と重なる図形は間隔を生成します（線が図形に遭遇するところで開き、線が図形を出るところで閉じます）。間隔が与えられていると、

これで、上から下に移動して領域を合計する必要がありますが、ピクセル単位で移動する必要はありませんDPIに依存しますので、線が動くにつれて間隔が少し動いていますが、図形がその点で交差しない限り、線が遭遇する新しい図形があります。すべての図形に対してmin & max yを取って並べ替えます。また、重なり合った図形の各ペアの間に交点が必要です。しかし、それらを計算する代わりに、スキャンライン上でお互いに近いものだけを計算することができます（各ステップで次のものを見つける必要があるため、ヒープに保管してください）。

これを行う1つの方法は、ラインを少し（次のポイントに）移動し、ラインで掃引したエリアを計算して合計に加算することです。これは、行移動ごとにO（N^3）、O（N）になり、O（N^2）行移動することがあります（すべての図形が他のすべての図形と重なっていると仮定します）。

エリア計算を高速化すると、少し速くO（N^2 log N）することができます。あなたが計算する必要があるのは、スワップする間隔の周りだけです。これは、フリー・インターバルごとに、あなたが最後に更新されたことを覚えておく必要があることを意味します。

私はあなたに数学を残しますが、それは簡単です。間隔を考えると、基本的に2つの省略記号で埋められた長方形です。矩形の面積はシンプルで、楕円形のスライスの外側にある必要があります。