2つの可能なインデックスを持つセット内の要素を格納する

Question

特定の状況の解決策が必要です。私は基本的に線分上で動作するアルゴリズムを持っています。私は線分の終点と始点を知っているだけです。 （ポイントには2つの座標x、yがあります。これらは画像上のピクセルポイントです。画像のサイズもわかります）これらの線分を調べて、何かしたいと思います。しかし、私はまた、検査された線分を追跡して、同じ線分をもう一度調べる必要がないようにする必要があります。私はC++を使用していますので、stl set containerを使用したいと思います。

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

私はこれらの2つのピクセルのインデックス番号を生成したということが考えられます：（y * image-> Witdh）+ x。次に、2つのインデックス番号を（整数であるのと同じ方法で）取得します。次に、これらの数値を連結します：（indexStart < < 32）+ indexEnd（2倍になります）。今私はユニークな番号を持っていて、簡単にセットで保管することができます。しかし、私の検索では、線分の始点が同じ線分の終点になることが問題になります。もし私が終点から同じ線分に遭遇した場合、連結された線分の一意の数は（indexEnd < < 32）+ indexStartになります。それから私は避ける必要がある私のセットしたコンテナに同じ線分を追加します。

ありがとうございました。

Answer 1

あなたの解決策はそのままにしておくか、operator<を使用してください。あなたは、ハッシュセット実装への切り替えが簡単であるという利点があります。もう1つは、全体的にわかりやすい（はるかに理解しやすく、おそらく高速ですが、64ビット座標などで使用できます）。

ちょうどあなたが記述問題を解決startとendが、lowerとupper座標を区別しないことにより、（あなたは、両方のapporachesのためにこれを行う必要があるでしょう）。常に小さいが同じ場所に座標使用すると、あなたは彼らにあなたがyour'reは、セグメントと先となるつもりは何を教えてくれませんでした

Answer 2

線分に適切な順序関係演算子を指定するだけです。私。あなたのセグメントは次のようになり場合：

struct LineSegment { 
    int start; 
    int end; 
}; 

単にstd::less<LineSegment>のインスタンス化が存在するように、その構造体、（これは重要である理由のためにdefinition of setを参照）にoperator<を定義します。

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<の実装に適応できます）。

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

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

各キーが決定的に一意の値を持っており、完全な線分を説明し、この方法：すぐに頭に浮かぶ

Answer 3

一方の構築物は、int秒のpair秒のsetpairのSです。

(indexLeft << 32) + indexRight 

しかし、あなたは、左右それぞれの時間を割り当てる必要があります。

Answer 4

一つの解決策はあります。たとえば、Leftは最小X値を持つものです。