同じピクセルグループ内の他のピクセルから最も離れたピクセルを見つける方法

Question

"グループ"とは、すべてのピクセルが少なくとも同じセット内の1つの隣接ピクセルを持つようなピクセルのセットを意味します。グループ。

Iは、（例えば、緑色ピクセル）指定された画素からの最大直線距離を有する画素を見つけることを望みます。また、2つのピクセルを結んでいる直線（赤い線）は、グループを離れてはいけません。

私の解決策は、度合いをループして、度合いのある緑色ピクセルから始まる線の進行をシミュレートし、どの線が最も遠くに移動したかを見ています。

longestDist = 0 
bestDegree = -1 
farthestX = -1 
farthestY = -1 
FOR EACH degree from 0 to 360 
    dx=longestDist * cos(degree); 
    dy=longestDist * sin(degree); 
    IF Point(x+dx , y+dy) does not belong to the group 
     Continue with next degree 
     //Because it must not be the longest line, so skip it 
    END IF 
    (farthestX , farthestY) = simulate(x,y,degree) 
    d = findDistance(x , y , farthestX , farthestY) 
    IF d > longestDist 
     longestDist = d 
     bestDegree = degree 
    END IF 
END FOR 

明らかに最適なアルゴリズムではありません。私はここで助けを求めています。

ありがとう、貧しい私の英語のために申し訳ありません。

Answer 1

最初に、アルゴリズムの角度離散化はグリッドのサイズによって異なる場合があることに注意してください。ステップが大きすぎると、特定のセルが見つからないことがあります。小さすぎると、同じセルを何度も何度も訪れることになります。

リージョンのセルを列挙し、それぞれのセルの条件を個別にテストすることをお勧めします。列挙は、幅優先や深さ優先の検索を使用して行うことができます（後者が望ましいでしょう。なぜなら、下限を素早く確立し、いくつかのプルーニングを行うことができるからです）。

これまでに発見された最も遠い点Xを維持することができ、領域内の新しい点ごとに、（a）これまでに発見された点よりも離れており、（b）その領域の細胞のみを通過する直線である。両方の条件が満たされている場合は、Xを更新し、それ以外の場合は検索を続けます。条件（a）が満たされない場合、条件（b）を確認する必要はない。

この溶液の複雑さはN領域内のセルの数であり、M領域（max(width,height)）の大きな寸法であるO(N*M)であろう。パフォーマンスが本質的であれば、より洗練された経験則を適用することができますが、合理的なサイズのグリッドではうまくいくはずです。

Answer 2

斜面用ではなく、ピクセルを検索します。擬似コード。

bestLength = 0 
for each pixel in pixels 
    currentLength = findDistance(x, y, pixel.x, pixel.y) 
    if currentLength > bestLength 
    if goodLine(x, y, pixel.x, pixel.y) 
     bestLength = currentLength 
     bestX = pixel.x 
     bestY = pixel.y 
    end 
    end 
end 

ピクセルを降順でソートするとよいでしょう。 + | dy |それ以前は。

Answer 3

私はアングルでは動作しません。しかし、私はかなり大きな距離が常にセットの端にある2つのピクセルの間にあることを確信しているので、私はアウトラインを辿るでしょう：セットのどのピクセルからも、あなたがセットの端に達するまで、次に、エッジに沿って時計回りに移動（couter）します。どのピクセルでもこれを開始点として実行すれば、最大の距離を見つけることができます。それはまだかなり貪欲ですが、私はあなたに改善のための代替出発点を与えるかもしれないと思った。

編集：ちょうど私の心に来たもの：開始ピクセルsと終了ピクセルeがあるとき。 sを使用する最初の反復では、対応するが隣接します（時計回りの方向に沿って次のもの）。辺に沿って反復するとき、ケースには、sとeの間の直線を通らないケースが発生する可能性があります。その場合、ラインはセットエッジ（ピクセルp）の別の部分に当たってしまいます。あなたは、そのピクセル（e = p）

EDIT2でエッジの繰り返しを継続することができます。そして、あなたはpをヒットした場合、あなたはそうあなたがスキップできsの次の反復でsとeの間には距離が長いがないことを知っていますよその部分全体（sとpの間）で始まり、再びpで始まります。

Edit3：上記の方法を使用して、最初のpを探します。 pを次のようにsとしてください。もう一度最初にpに到達するまで繰り返します。最大距離は、pの2つの間になります。ただし、セットのエッジが凸でない場合は、pが見つかりません。

免責事項：これはテストされていないで、私の頭の上から単なるアイデアです、（あなたがそれを実装する前に、つまり、自分自身のためにそれについて考える; D）は何の図面は、私の主張を立証するために行われていない、すべてが間違っている可能性があります

Answer 4

ダブルデータ構造を使用してください。

• アングルでソートされたピクセルを含むもの。
• 距離でソートされた2番目のもの（高速アクセスの場合は、最初のデータ構造の "ポインタ"も含まれている必要があります）。

アングルソートされた角度を歩き、各ピクセルがその領域内にあることを確認します。いくつかのピクセルは同じ角度を持つので、線に沿って原点から歩き、あなたがその地域から外に出るまで行くことができます。その点を超えるピクセルをすべて削除することができます。また、最大距離が増加した場合は、距離の短いすべてのピクセルを削除します。

Answer 5

領域をピクセルのコレクションではなくポリゴンとして扱います。これにより、線分（ポリゴンの端）のリストを取得できます。

開始ピクセルから確認する各ピクセルに線を描画します。ポリゴンの線分と交差しない最長の線は、ピクセルから直線で到達できる最も遠いピクセルを示します。

これをチェックしていくつかのエッジのケースに行うことができるさまざまな最適化がありますが、それらを投稿する前にアイデアを理解すれば教えてください...特に、ポリゴンの代わりにピクセルのコレクション？

追加するには、このアプローチは、最小のピクセル集合を除いて「ウォーキング」を必要とするあらゆる角度ベースの手法やアプローチよりも大幅に高速になります。問題は、始点からの交差していない直線を経由して到達できる多角形エッジの最も遠い端点を見つけることと同じであるため、さらに最適化することができます。これはO（N^2）で行うことができます。ここで、Nはエッジの数です。 Nはピクセル数よりもはるかに小さいであろうことに注意してください。アルゴリズムの多くは、使用角度やピクセル繰り返しが代わりにピクセル数に依存することを提案しています。