2

特定の状況に対する解決策が必要です。基本的に線分で機能するアルゴリズムがあります。線分の終点と始点しか知りません。(ポイントには 2 つの座標 x、y があります。これらは画像上のピクセル ポイントです。また、画像のサイズも知っています。) これらの線分を調べて、それらに対して何かを実行したいと考えています。ただし、同じ線分を再度調べないように、調べた線分を追跡する必要もあります。C++を使っているのでstl set containerを使いたいです。

私の質問は、これらの線分を終点と始点に従ってどのように保存できますか? 終点と始点の一意の番号を生成する必要があります。（また、 stl set を使用する以外のアドバイスも受け付けています:)）

考えられる解決策の 1 つは、(y*image->Witdh) + x によって、これら 2 つのピクセルのインデックス番号を作成したことです。次に、2 つのインデックス番号を取得します (ちなみに、これらは整数です)。次に、これらの番号を次のように連結します: (indexStart << 32) + indexEnd.(double を取得します)。これで固有の番号があり、セットに簡単に保管できます。しかし、問題は私の検索中に、線分の始点が同じ線分の終点になる可能性があることです。エンドポイントから同じ線分に出くわした場合、連結された線分の一意の番号は (indexEnd << 32) + indexStart になります。次に、回避する必要がある同じ線分をセット コンテナーに追加します。

アドバイスをありがとう。

4

4 に答える 4

1

線分に適切な順序関係演算子を指定するだけです。つまり、セグメントが次のようになっている場合：

struct LineSegment {
  int start;
  int end;
};

operator<のインスタンス化が存在するように、その構造体を定義するだけです（これが重要である理由については、setstd::less<LineSegment>の定義を参照してください）。

bool operator<(LineSegment const& lhs, LineSegment const& rhs) {
  if (lhs.start == rhs.start)
    return lhs.end < rhs.end;
  return lhs.start < rhs.start;
}

std::set<LineSegment>これにより、適切な順序を尊重するセットを使用できます。LineSegmentsは、実際に異なる場合にのみ、区別できることが保証されます（質問を正しく理解していれば、これはまさにあなたが望むものです。そうでない場合は、operator<実装を簡単に適応させることができます）。

同様に、セットにポインターを格納する場合は、2番目のテンプレートパラメーター（置換std::less<LineSegment*>）でセットの比較演算子をオーバーライドできます。LineSegment*

于 2012-05-07T12:58:55.860 に答える
1

ソリューションを保持するか、を使用できますoperator<。いくつかのハッシュセット実装への切り替えは簡単であり、もう1つは全体的に優れた実践であるという利点があります（理解しやすく、おそらく高速で、64ビット座標で使用できます）。

startとを区別せendずlowerに調整することで、説明する問題を解決するだけです（両方のアプローチでこれを行う必要があります）upper。常に同じ場所で小さい座標を使用すると、逆に発見したときに誤検知の異なるセグメントを取得するための簡単な修正です。

于 2012-05-07T13:10:23.397 に答える
1

1つの解決策は次のとおりです。

    (indexLeft << 32) + indexRight

ただし、毎回 Left と Right を割り当てる必要があります。たとえば、左は X 値が最小のものです。

于 2012-05-07T13:07:52.430 に答える
0

すぐに頭に浮かぶ 1 つの構造は、setspairのpairs のints です。

std::set<std::pair<std::pair<int, int>, std::pair<int, int> > >

このようにして、各キーは明確に一意の値を持ち、完全な線分を記述します。

于 2012-05-07T13:01:00.943 に答える