一次元領域の重なり検出のアルゴリズムについての質問です。


たとえば
 領域A(1以上-7以下;以下同様),
 領域B(2-5),
 領域C(3-9)
から
 重なり領域イ(2-3)AとB
 重なり領域ロ(3-5)AとBとC
 重なり領域ハ(5-7)AとC
というような解をもとめるアルゴリズムで知られたものがあるでしょうか?
Webページないし,書籍での資料を教えていただければ幸いです。
CやRubyなどでのサンプルがあるとなおありがたいです。

回答の条件
  • 1人2回まで
  • 登録:2008/03/25 11:45:19
  • 終了:2008/03/27 08:53:20

ベストアンサー

id:ita No.2

ita回答回数204ベストアンサー獲得回数482008/03/25 22:24:28

ポイント70pt

アルゴリズムとしては特別なものはいらないと思います。

全ての領域の両端の値と、それが左か右かの情報と組にします

struct Bndry

{

double pos; //位置

char LR; //右か左か

int idx; //何番目の領域か

}

これを全部用意してからposの値でソートします。

並び替えた小さい方から順に見て行って、初期値0の変数を、LRを見て

左端なら+1、右端なら-1していきます。

これが2以上となる部分が重なってる部分です。

元のデータ

pos,LR,idx

1,L,0

7,R,0

2,L,1

5,R,1

3,L,2

9,R,2

ソート

ーーーー

  カウンタ

    0

1L  1

2L  2

   二重

3L  3

   三重

5R  2

   二重

7R  1

9R  0

id:snpia

ご回答ありがとうございました。この方法で実装することが出来ました。

実際には構造体に「領域(区間)名」を入れることで,どの区間が,重なっているかも

出力することにしました。

とてもエレガントな解だと思います。

2008/03/27 08:43:54

その他の回答(1件)

id:haruo-31 No.1

haruo-31回答回数80ベストアンサー獲得回数102008/03/25 16:48:34

ポイント35pt

行列演算アルゴリズムと呼ばれる分野ですよね。

とりあえず詳しくないながらURLを張っておきます。

http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/geo.html

1次元であってもY軸を0にしたりして、無理やり2次元にして計算してしまえば良いと思いますよ。

id:snpia

ご回答ありがとうございます。

「面と面の重なり検出」「面と点の重なり検出」というのは一つの分野のようですね

他に自分で

http://mgccl.com/2007/07/04/1d-segment-intersection-detection-pa...

http://en.wikipedia.org/wiki/Segment_tree

http://en.wikipedia.org/wiki/Interval_tree

なども見つけてみました。

ただ,私の今回の目的には,ちょっとやりすぎのようでしたので,結局,次の回答者様の

アルゴリズムを採用しました。ともあれ,とてもいい勉強になりました。

2008/03/27 08:49:22
id:ita No.2

ita回答回数204ベストアンサー獲得回数482008/03/25 22:24:28ここでベストアンサー

ポイント70pt

アルゴリズムとしては特別なものはいらないと思います。

全ての領域の両端の値と、それが左か右かの情報と組にします

struct Bndry

{

double pos; //位置

char LR; //右か左か

int idx; //何番目の領域か

}

これを全部用意してからposの値でソートします。

並び替えた小さい方から順に見て行って、初期値0の変数を、LRを見て

左端なら+1、右端なら-1していきます。

これが2以上となる部分が重なってる部分です。

元のデータ

pos,LR,idx

1,L,0

7,R,0

2,L,1

5,R,1

3,L,2

9,R,2

ソート

ーーーー

  カウンタ

    0

1L  1

2L  2

   二重

3L  3

   三重

5R  2

   二重

7R  1

9R  0

id:snpia

ご回答ありがとうございました。この方法で実装することが出来ました。

実際には構造体に「領域(区間)名」を入れることで,どの区間が,重なっているかも

出力することにしました。

とてもエレガントな解だと思います。

2008/03/27 08:43:54

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません