6

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

グループの例

指定したピクセル (たとえば、緑色のピクセル) からの直線距離が最大のピクセルを見つけたいと考えています。また、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

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

ありがとう、そして私の下手な英語でごめんなさい。

4

5 に答える 5

1

私は角度を使って仕事をしません。しかし、最大距離は常にセットの端にある2つのピクセルの間にあると確信しているので、アウトラインをトレースします。セット内の任意のピクセルから、セットの端に到達するまで任意の方向に移動します。次に、端に沿って（クーター）時計回りに移動します。任意のピクセルを開始点としてこれを行うと、最大距離を見つけることができます。それはまだかなり貪欲ですが、私はそれがあなたに改善するための代替の出発点を与えるかもしれないと思いました。

編集：ちょうど私の頭に浮かんだこと：あなたが開始ピクセルsと終了ピクセルを持っているときe。最初の反復sでは、対応eするものを使用して隣接します（時計回りの方向のエッジに沿った次の反復）。エッジに沿って反復すると、との間のセットを通る直線がない場合が発生する可能性がありsますe。その場合、線はセットエッジの別の部分（ピクセルp）にヒットします。そのピクセルでエッジの反復を続行できます（e = p）

Edit2：そして、aを押すと、間にp距離がなくなることがわかります。そのため、次の反復では、エッジのその部分全体（との間）をスキップして、最初からやり直すことができます。sesspp

Edit3：上記の方法を使用して最初のを見つけますp。それpを次のように受け止めsて続行します。もう一度最初に到達するまで繰り返しますp。pセットのエッジが凸である場合を除いて、最大距離はそれらの2つの間になります。凸である場合は。は見つかりませんp。

免責事項：これはテストされておらず、私の頭の上のアイデアにすぎません。私の主張を実証するための図面は作成されておらず、すべてが間違っている可能性があります（つまり、実装する前に自分で考えてください; D）

于 2012-09-20T10:13:24.070 に答える
0

まず、アルゴリズムの角度の離散化はグリッドのサイズに依存する可能性があることに注意してください。ステップが大きすぎると、特定のセルを見逃す可能性があります。小さすぎると、同じセルに何度もアクセスすることになります。

代わりに、領域内のセルを列挙し、各セルの状態を個別にテストすることをお勧めします。列挙は、幅優先探索または深さ優先探索を使用して実行できます（下限をすばやく確立し、剪定を行うことができるため、後者の方が望ましいと思います）。

これまでに見つかった最も遠い点Xを維持でき、領域内の新しい点ごとに、（a）点がこれまでに見つかった点よりも離れているかどうか、および（b）通過する直線によって原点に接続されているかどうかを確認します。領域のセルのみ。両方の条件が満たされている場合はXを更新し、そうでない場合は検索を続行します。条件（a）が満たされない場合、条件（b）をチェックする必要はありません。

このソリューションの複雑さは次のようになりますO(N*M)。ここNで、は領域内のセルの数であり、は領域Mのより大きな次元です（max(width,height)）。パフォーマンスが重要な場合は、より高度なヒューリスティックを適用できますが、適度なサイズのグリッドの場合、これは問題なく機能するはずです。

于 2012-09-20T10:05:24.573 に答える
0

double データ構造を使用します。

  • 角度別に並べ替えられたピクセルを含むもの。
  • 距離でソートされた 2 番目のもの (高速アクセスのために、これには最初のデータ構造の「ポインター」も含まれている必要があります)。

並べ替えられた角度を調べて、ラインが領域内にあることをピクセルごとに確認します。一部のピクセルは同じ角度になるため、原点から線に沿って歩き、領域から出るまで進むことができます。そのポイントを超えるすべてのピクセルを削除できます。また、最大距離が増加した場合は、距離が短いすべてのピクセルを削除します。

于 2012-09-20T10:49:12.307 に答える
0

領域をピクセルのコレクションではなく多角形として扱います。これから、線分 (ポリゴンのエッジ) のリストを取得できます。

開始ピクセルからチェックしている各ピクセルまで線を引きます。ポリゴンのどの線分とも交差しない最長の線は、ピクセルから直線で到達できる最も遠いピクセルを示します。

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

さらに、このアプローチは、角度ベースのアプローチや、ピクセルの最小コレクションを除くすべての「ウォーキング」を必要とするアプローチよりも大幅に高速になります。問題は、始点から交差しない直線を介して到達できるポリゴン エッジの最も遠い端点を見つけることと同じであるため、さらに最適化できます。これは、O(N^2) で実行できます。ここで、N はエッジの数です。N はピクセル数よりもはるかに小さいことに注意してください。また、角度やピクセル反復を使用する提案されたアルゴリズムの多くは、代わりにピクセル数に依存することに注意してください。

于 2012-11-07T18:32:18.747 に答える
0

勾配ではなく、ピクセルを検索します。疑似コード。

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

ピクセルを |dx| で降順に並べ替えることができます。+ |ディ| それ以前は。

于 2012-09-20T10:11:52.510 に答える