フットプリント検索アルゴリズム

Question

私は、その形状に含まれる値を最大にするためにポリゴン（または複数のポリゴン）の形状を最適化するアルゴリズムを考え出しています。

• X：X軸上の位置
• Y：Y軸上の位置
• 値：正有することができ、ブロックの値と

  私は3列のデータを持っています負の値。

このデータは規則的なグリッドからのものなので、x値とy値の間隔は一定です。

追加された条件で含まれる値を最大にする境界ポリゴンを作成したいと思います。

• ポリゴンのすべてのポイントで最小半径を維持する必要があります。これは、正の価値ブロックを失うか、負の価値ブロックを得ることを意味します。この場合

私が使用している現在のアルゴリズムは以下

1. が出発点（またはユーザ定義）として最大ブロック値を求めない
2. は最小半径内のすべてのブロックを検索し、決定します
3. 最小探索半径内のすべてのブロックをさらなる値計算から除外し、最終形状の一部としてフラグを付けます。
4. 次のポインタに移動します原点を中心としたスパイラルによって決定される。 （中心は常にデルタXまたはデルタYで移動する格子点です）

これは不要なセルをいくつか取り込んでいるようです。そこに形のアルゴリズムがあると確信していますが、私は助けを見つけるために何を見上げるか分からない。

以下は、質問の概要を示すのに役立つ画像です。陽性細胞は赤色で示されている（陰性細胞は示されていない）。黒いアウトラインは、私の現在のルーチンが返す形を示しています。私は、左サイドがもっと持ち込まれるべきだと思う。最小半径は100mです。左下の黒丸はおよそこれです。

今のコードでは、Rで実行されているが、私は、アルゴリズムが正しい得ることができる場合、私はおそらく何か他に移動します。

不明の投票に応えて、私は背景や未遂解決せずに解決しようとしています問題は次のとおりです。

「に含まを最大化するために一連の点の周りに境界ポリゴン（またはポリゴン）を作成します。値は、「多角形に沿って曲率の最小半径を維持しながら

編集：

データ

いくつかのデータが含まれているはずです。hereです。

ファイルはcsvです。 4列（X、Y、Z [未使用]、値）、長さは〜25kサイズは800kbです。

Answer 1

場合、私は貪欲アプローチをしようとするだろう。

すべてのピクセル（あなたの「ブロック」）については、その周りのディスクの値の合計を計算し、その値を取ることができます。この問題は難しいかもしれません。最高の合計で。マークされたピクセルが「消費」されているため、このピクセルをマークし、ディスク内のすべてのピクセルの合計を調整します。次に、エッジまたはコーナーで接触しているすべてのピクセルをスキャンし、最大の合計でピクセルをマークします。

すべての合計が負になるまで、このプロセスを続行します。その後、合計はもう増えません。

効率的な実装のためには、境界ピクセル、すなわちマークされたピクセルの近傍であるマークのないピクセルのリストを保持する必要があります。ボーダーピクセルを最大の合計で選択してマークした後、そのピクセルをリストから削除し、ディスク内のマークされていないピクセルの合計を再計算します。それに触れるマークのないピクセルも追加します。

画像では、ピクセルは青色で、境界ピクセルは緑色でマークされています。ハイライトされた画素は

• マークされます1、
• 合計は再計算する必要のあるものです。

計算時間が画像時間（合計の初期の計算のため）ディスクの領域の面積、プラス形状倍の面積に比例する面積ディスク（合計の更新用）に、シェイプの連続した周囲の長さの合計（最大の合計を見つけるために）を計算します。 [後者の用語は、形状の領域の積の長さによる順序のコストがかかるため、ヒープデータ構造を使用することをお勧めします。これにより、長さの合計が合計に減少しますそれらの対数の]]

Answer 2

グラフィカルなアプローチ

私がグラフィカルにこの近づくだろう。私の直感は、内側の点が、近くにあるすべてのフットプリントポイントからの最小半径rのキャストされた円の中に完全に入っていることを教えてくれます。つまり、半径rの各フットプリントポイントから円をキャストすると、隣接するすべての円の少なくとも半分の内側にあるすべてのポイントがポリゴンの内側にあります。ポリゴンの内部に深くいる場合、あまりあいまいでないようにするには、どんなピクセルでもこの​​ような重なり合う円がPi*r^2になります。あなたは彼らの半分を持っているエッジにいる場合。これは簡単に計算可能です。

まずはデータセットが必要です。あなたはちょうどjpgファイルを提供したので、私はvalesプロットを持っていません。だから私はこの問題をバイナリイメージのように扱います。最初に、画像を取り除くために、jpgの色の歪みを取り除く必要がありました。

私が容易画像に添加数学を適用する黒の背景を選択しても、私は白、よりそれを好むとフットプリント赤（最大飽和）を残す。その後、これは私の入力です。今アルゴリズム：

1. はそれは同じ大きさと黒(color=0)にクリアしなければなりません

   一時イメージを作成します。オーバーラップする円の整数カウンターのようなピクセルを処理します。

2. キャスト円source image各赤色画素と同じ画素の周囲の最小限の半径rでなくtemp imageの円内の各画素に+1を追加するための

   。結果は次のようである（青私pixelformatの下位ビットである）：rとして

   

   それはあなたの例+/-画素における左下円半径であるように、私はr=24を用います。

3. のみ

   そう一時画像色を変更内部のピクセルを選択します。 color < 0.5*pi*r^2のピクセルはすべて、の黒色のに、残りはの赤色のに再描画されます。 を選択したポリゴンの周囲ポイントのみ

   ただ、いくつかのニュートラルカラー青と黒に残りの部分に黒画素の全てのホテル赤ピクセルの色を変更

   

4. ：結果は、このようなものです。結果：

   

   今だけの結果をpolygonize。あなたがそれらの両方を（私はそれらを一緒にOR）組み合わせることができ、入力画像と比較するために：あなたは分半径やエリアtresholdで遊ぶことができます

   

[注]

異なる動作を実現するプロパティ。しかし、私はこれがあなたの問題にかなり近いと思う。

ここでは、このためのいくつかのC++ソースコード：一部のメンバーがいるので、私はイメージのため、私自身pictureクラスを使用

//picture pic0,pic1; 
    // pic0 - source 
    // pic1 - output/temp 
int x,y,xx,yy; 
const int r=24;     // min radius 
const int s=float(1.570796*float(r*r));  // half of min radius area 
const DWORD c_foot=0x00FF0000; // red 
const DWORD c_poly=0x000000FF; // blue 
// resize and clear temp image 
pic1=pic0; 
pic1.clear(0); 
// add min radius circle to temp around any footprint pixel found in input image 
for (y=r;y<pic1.ys-r;y++) 
for (x=r;x<pic1.xs-r;x++) 
    if (pic0.p[y][x].dd==c_foot) 
    for (yy=-r;yy<=r;yy++) 
    for (xx=-r;xx<=r;xx++) 
    if ((xx*xx)+(yy*yy)<=r*r) 
     pic1.p[y+yy][x+xx].dd++; 
pic1.save("out0.png"); 
// select only pixels which are inside footprint with min radius (half of area circles are around) 
for (y=0;y<pic1.ys;y++) 
for (x=0;x<pic1.xs;x++) 
    if (pic1.p[y][x].dd>=s) pic1.p[y][x].dd=c_foot; 
    else     pic1.p[y][x].dd=0; 
pic1.save("out1.png"); 
// slect only outside pixels 
pic1.growfill(c_foot,0,c_poly); 
for (y=0;y<pic1.ys;y++) 
for (x=0;x<pic1.xs;x++) 
    if (pic1.p[y][x].dd==c_foot) pic1.p[y][x].dd=0; 
pic1.save("out2.png"); 
pic1|=pic0; // combine in and out images to compare 
pic1.save("out3.png"); 

：ピクセル

p[y][x].ddにおける画像の

• xs,ysサイズピクセルは(x,y)の位置にあります。32ビット整数型
• clear(color)は - 画像全体
• resize(xs,ys)をクリア - 新しい解像度に画像をリサイズし

私は、いくつかのエッジが鋭すぎるので、私はチェックして気づい

ソースコード内の小さなバグを得た[EDIT1]コードと私は円の条件を追加するのを忘れていましたので、代わりに四角で塗りつぶしました。私は上記のソースコードを修復しました。私は実際にはif ((xx*xx)+(yy*yy)<=r*r)という行を追加しました。結果は少しので、私はまた、新しい結果

で画像を更新変更された私は、内側の領域係数比と、この1でプレイ：

const int s=float(0.75*1.570796*float(r*r)); 

はあなたのためのより良い試合につながります。ポリゴンが小さくなるほど、ポリゴンは外側のフットプリントと重なることがあります。結果：ソリューション・セットが指定された半径のディスクの労働組合でなければなりません